ICFPC 2017: Ticket to Ride на Rust (вторая часть)
Продолжение. Первая часть здесь.
День второй.
Я возвращаюсь в чат в полдень, к этому времени там уже произошло:
В 13:44 я обнаруживаю в списках игроков на серверах вот такое имя: "A Storm of Minds: Mine Connect Claimer" -- понимаю, что я на верном пути =) Дальше мы пытаемся придумать какую-нибудь простую, но более эффективную стратегию, а параллельно я усиленно программирую link_mines.
В 14:17 организаторы объявляют продление лайтнинга на час (в качестве компенсации за то, что начало конкурса задержалось из-за обвала сайта с заданием). Это круто, потому что я как раз начал усиленно переживать, что не успеваю к трём. В солвере я, помимо соединения шахт, планирую один из этих маршрутов объявлять фьючерсом. Но вот засада -- не могу найти карту с фьючерсами, прошу команду помочь.
В 14:33 солвер у меня научился соединять шахты дейкстрой, осталось срочно придумать, что делать, когда все шахты на карте соединены. Решаю пока просто захватывать оставшиеся реки в случайном порядке.
В 15:01 у меня всё готово, прошу в чате всех помочь с тестированием.
RUST_LOG=lambda_punter=debug,lambda_punter_online=debug cargo run --release -- --server-port 9024 link_mines В процессе оказывается, что играет оно плохо: пока я тяну дорогу, враги быстро перекрывают подступы к шахтам. В срочном порядке бранчуюсь и начинаю кодить вариант, который строит маршрут не от одной точки другой, а от обеих сразу к центру маршрута.
В 15:10 готово, все продолжаем тестировать. Через 10 минут Sectoid находит баг в декодере пакетов: оказывается, что количество очков может быть отрицательным (например, за проваленный фьючерс). На серверах тем временем играют боты каких-то товарищей под таким именем: "WISE_PIDOR_SOLUTION" :) В целом, всё остальное вроде ок, и в 15:33 Sectoid пошёл собирать сабмишн.
В 15:39 обнаруживаю карту "Oxford sparse" на которой только одна шахта: на ней солвер link_mines отказывается работать :) Срочно бросаюсь делать фикс. В 15:42 фикс готов, идёт вывариваться новый сабмишн. В 15:45 решаю срочно улучшить поведение, когда все основные цели солвер выполнил. В 15:53 у меня готов очередной фикс. Но там баг! К 15:56 готов багфикс. Пока решали, сабмитить или нет, к 15:59 я обнаружил ещё один баг! Короче пофиг, решаем больше не дёргаться.
16:00: lightning division типа закончен. Но что-то везде тишина.
Тем временем, в 16:19 я делаю окончательный багфикс солвера. Результаты с eager punter-ами улучшились в два с половиной раза :) Решаем на авось засабмитить, вдруг это решение каким-то чудом на лайтнинг пройдёт. Ну а если нет, то и не надо. К 16:30 сабмишн уезжает, я отправляюсь обедать, а ребята там ещё в остаются в чате придумывать разнообразные стратегии победы на будущее. Sectoid решает сделать автоматическую тестировалку наших ботов об сервера организаторов.
Дальше часок мы там просто абстрактно размышляли на разные темы, а дальше на меня (как на жирафа) начала накатывать череда озарений:
В 19:50 организаторы фиксят свой lamduct (по многочисленным жалобам), сделав там блокирующий режим в пайпе -- это ведь как раз то, с чем я сражался половину предыдущей ночи. Мне всегда в такие моменты немного обидно: ты типа мучался, тратил время, и потом с таким трудом одолел проблему -- а кто-то вместо этого немного поныл в чатик организаторам, и ему всё принесли готовое. Лучше б я поспал вчера :)
В 20:15 я решаю как-нибудь несложно доработать утилиту lambda_punter_online, чтобы она умела одновременно проводить сразу несколько игр на разных рандомных серверах. Эта работа немного пересекается с автоматической обстреливалкой, которую делает Sectoid, но мне вот прямо щас уже нужны какие-то массовые результаты, чтобы было представление о качестве солвера. Turtle к этому времени начинает писать кастомный сервер, но вскоре ему приходится уехать. Jtootf с Sectoid в это время садятся брейнштормить алгоритмы. Я им для затравки подробно описал как сейчас работает мой текущий солвер.
Далее мы примерно этим расслабленно занимаемся вплоть до 22:00. Из любопытных идей было порождено следующее:
Тем не менее, периодически попадаются товарищи, которые меня наказывают. Например, на random-* картах солверу достаточно быстро обрубают пути, которыми он пытается соединять рудники, и он начинает метаться по карте вместо полезной деятельности.
Постепенно lambda_punter_online отыгрывает 256 игр на разных случайных картах: получаю винрейт 82%. Через пять минут соображаю, что сервера слишком рандомно выбираются, и из-за их ограниченного количества и долгого времени ожидания на некоторых картах, возникает ситуация, когда у меня бот играет сам с собой. Иногда бывает даже до 12 моих ботов на одной карте :) Сажусь переделывать, чтобы сервера предлагались гарантированно разные.
22:46 -- анализирую очередной луз, и возникает идея сохранять чат протокола, чтобы потом сделать реплеи. Все остальные активно поддерживают. Дальше рассуждаем про идею не брать фьючерсы вообще на картах, где много мостов, ну или брать только короткие.
К 23:05 замечаю, что сломалась игра через lambda_punter_offline -- какая-то проблема с сериализацией стейта. Оказалось, что serde_json не хочет сериализовать через #[derive(Serialize)] хэш-таблицу, где ключами являются не строки. Сажусь ремонтировать :(
К 23:51 доигрались 256 игр с условием, чтобы мои боты сами с собой не играли: винрейт почти 90%!
К полуночи ремонтирую сериализацию стейта (пришлось делать отдельный враппер для хеш-таблицы), lambda_punter_offline заработал. Ориентировочно собираюсь идти спать (хехе). Turtle всё ещё делает игровой сервер, а Sectoid бенчмарк.
Чуть подумав, вместо того, чтобы пойти спать, я в книжке Mining Of Massive Data Sets откапываю алгоритм, который давно хотел сюда как-то применить: Girvan-Newman, про кластеризацию графа. Сама по себе кластеризация мне тут вроде ни к чему, но меня больше интересуют коэффициенты рёбер, которые показывают, сколько идёт кратчайших путей из любого узла графа в любой другой.
Чтобы проиллюстрировать, какие конкретно результаты я хотел получить с помощью этого алгоритма, я уже сильно после конкурса спрограммировал специальный визуализатор. Его можно взять из репозитория команды, он там называется map_vis. Выглядит он примерно вот так:
А вот так, например, отрисовывается эта же карта randomMedium.jspn с реками, интенсивность подсветки которых зависит от коэффициента betweenness.
Очевидно, что на этой карте имеет смысл как можно быстрее забирать центральную реку, которая отмечена жирным жёлтым. Через этот мост проходит большинство кратчайших путей, если их строить из каждого узла графа в каждый другой.
В половину второго внезапно прибегает Sectoid с вопросом, можно ли разложить граф на плоскости, и если можно, то как это использовать :)
Ближе к четырём ночи я коммичу реализацию Girvan-Newman в репо вместе с тестами, и отваливаюсь спать.
День третий.
Сажусь за комп ближе к часу дня, и обнаруживаю новый апдейт задания: бахвальство (Splurges). Смысл его в том, что теперь не обязательно строить маршрут по одному сегменту за ход, а вместо этого можно соответствующее количество раз спасовать, и потом за один ход построить весь маршрут махом.
Надо сказать, что я так до конца конкурса и не понял, честно говоря, как можно выгодно применять бахвальство. Единственная осмысленная мысль была про то, что можно использовать splurge, когда хочется других игроков ввести в заблуждение относительно своих намерений.
Вплоть до двух часов ничего не происхоит, я только объясняю товарищам, зачем я сделал Girvan-Newman, и как я собираюсь им пользоваться. Пока, на самом деле, особых идей нет, кроме как при стройке маршрута сначала стараться захватывать не просто какую-то реку, а ту, которая имеет наибольший коэффициент betweenness -- теоретически, так можно первей всех забрать мосты, испортить маршруты врагам, и воспрепятствовать тому, чтобы враги тебе самому обломали планы.
Два часа дня. Тыкаюсь какое-то время в игровые сервера: сильные игроки всё ещё не играют, винрейт стабильно за 90%. Делаю поддержку бахвальства в протоколе. Сажусь писать поддержку Girvan-Newman в солвере, чтобы он захватывал сначала важные реки: заодно, решаю переименовать солвер в solvers::gn (от Girvan-Newman), чтобы можно было всегда откатиться к solvers::link_mines, если что.
Народу приходит интересная идея, как в теории можно применить бахвальство: если нам не хватает времени досчитать ход, мы пасуем и сохраняем в стейт недосчитаное решение. Затем на следующем ходу досчитываем и делаем сразу ход из двух сегментов. Идея любопытная, на самом деле, но пока у нас проблема с таймаутами не стоит, ну и вообще это сложно как-то реализовывать.
16:00: Turtle бросает сервер и садится делать реплеи.
Я пока всячески апгрейжу по-мелочи solvers::gn -- по сравнению с link_mines он теперь:
К пяти вечера я ещё разок пробую уговорить Turtle попрограммировать на расте, конкретно портировать визуализатор из сокобана. Но он боится, не хочет :)
Ещё через полчаса раздумий, куда бы правильней применить результаты Girvan-Newman, я решаю реализовать пока свою первоначальную идею: когда приходит ход, захватывать ту речку из маршрута, которая имеет самый высокий коэффициент betweenness. По-идее, должно полегчать на картах с явно выраженными мостами: они должны теперь у меня захватываться в первую очередь.
Через некоторое время обнаруживаю, что в наборе предлагаются карты, имеющие ровно одну шахту, и к которой ведут всего три или четыре реки. Игроков на карте при этом 16 :) Очевидно, что если при этом стартовать не в числе первых, то очков получаем стабильно нуль, и с этим, похоже, ничего не сделать.
К шести вечера выясняется, что на треугольнике и некоторых рандомах солвер стабильно проигрывает боту от kontur.ru. Ну вот, а ведь так хорошо всё начиналось =) Думаю, как можно улучшить наши результаты на этих картах. Есть подозрение, что у нас что-то неправильное происходит с фьючерсами.
Sectoid предлагает продумать идею, чтобы не брать слишком нахальные фьючерсы. Например, можно принудительно ограничивать их длину, в зависимости от размеров карты. В свою очередь, я начинаю размышлять на предмет того, чтобы как-то попробовать использовать расчитанные betweenness коэффициенты, чтобы найти такие точки:
Обнаруживаю, что lambda_punter_online при массовой игре засчитывает ничью как поражение. Исправляю. Обстрел показывает, что старый солвер link_mines показывает (вроде бы) более лучшие результаты, чем новый gn.
Turtle тем временем нарисовал на бумажке картинок и рассказывает нам своё видение стратегии победы. К сожалению, в итоге в его алгоритме что-то не срастается. В конце концов сходимся на том, что я выдаю ребятам рассчитанные betweenness коэффициенты для карты randomMedium, а сам удаляюсь по делам на пару часов. По возвращении я строго наказываю придумать мне ясный и эффективный алгоритм для объявления фьючерсов.
Возвращаюсь в половину десятого, алгоритм не придуман :) Sectoid пытается разобраться с тем, как именно работает Girvan-Newman. К половине одинадцатого предлагаю забить на придумывание алгоритма, и закончить насущные дела по реплеям, серверу и бенчмаркам.
Параллельно я начинаю прорабатывать идею, которая меня навязчиво мучила всё время, пока я отсутствовал. Общий смысл программы примерно такой:
Но, как известно, на словах-то я Лев Толстой, а на деле это самое. Немного посидев с формулами минут десять, усиленно делая умный вид, я осознаю, что время уже позднее, башка не варит, да и тервер-то я знаю так себе (что уж там греха таить). По этому поводу расталкиваю в параллельном чате Игоря, который только что вернулся убитый с дачи. В конкурсе он участвовать дальше отказывается, но, тем не менее, мне удаётся уговорить его помочь мне с математикой. Выдаю ему упрощённый примере, где противники делают ходы полностью случайно, с одинаковой вероятностью захватывая одну из оставшихся рек. В идеале хочу формулу, куда можно было бы засунуть маршрут, количество и очерёдность игроков, а оттуда бы приехала вероятность построения этого маршрута.
Следует отметить, что такую формулу Игорь мне всё-таки умудряется подогнать, правда, только для двух игроков. При попытке придумать что-то для большего количества у него вскипает мозг, и он тоже сдаётся.
Ну что ж, раз в математику мы не можем, решаю идти путём слабаков: будем брутфорсить вероятности через монте-карло. Теория такая, что раз у нас на этот раз быстрый Rust, должна быть возможность запустить достаточное количество симуляций игр, чтобы получились нужные числа. Короче, сажусь постепенно что-то делать.
К полуночи приезжает последнее обновление к заданию: опционы. Смысл аналогичен вокзалам в паровозах: во время игры можно N раз воспользоваться чужой рекой для построения своего маршрута, где N равно количеству рудников на карте. В принципе, крутое дополнение: в отличие от бахвальства, тут хотя бы понятно как этим воспользоваться и как запрограммировать :) Собственно, потихоньку начинаю писать код, покуда в фоне идёт обсуждение системы реплеев имени Turtle.
В половину первого ночи ворвался Sectoid с сообщением, что у него заработал бенчмарк, и мы теперь можем типа объективно оценивать солвер. Запускаем играть gn. Пример выхлопа выглядит примерно так:
^CGot INTERRUPT. Finalizing... +---------------------+-------+--------+-----------------+-----------+----------------+---------+ | MAP | GAMES | ERRORS | SCORE | METASCORE | TOTALMETASCORE | WINRATE | +---------------------+-------+--------+-----------------+-----------+----------------+---------+ | sample | 10 | 0 | 25.8 | 2 | 20 | 1 | | lambda | 10 | 0 | 678 | 3.9 | 39 | 0.9 | | Sierpinski-triangle | 10 | 0 | 1078 | 3 | 30 | 1 | | circle | 15 | 5 | 276.5 | 4 | 40 | 1 | | randomMedium | 10 | 0 | 5107.2 | 3.9 | 39 | 0.9 | | randomSparse | 11 | 1 | 5490.5 | 3.9 | 39 | 0.9 | | boston-sparse | 6 | 0 | 108926.66666667 | 8 | 48 | 1 | | tube | 0 | 0 | 0 | 0 | 0 | 0 | | edinburgh-sparse | 0 | 0 | 0 | 0 | 0 | 0 | | nara-sparse | 0 | 0 | 0 | 0 | 0 | 0 | | oxford | 0 | 0 | 0 | 0 | 0 | 0 | | gothenburg-sparse | 0 | 0 | 0 | 0 | 0 | 0 | +---------------------+-------+--------+-----------------+-----------+----------------+---------+ В процессе разглядывания результатов рождаются сопутствующие идеи:
Тем временем уже почти два ночи. У turtle уже появляются реплеи с отрисовкой в gnuplot. Выглядит это как серия изображений вот такого типа:
Три ночи. Sectoid развёл какую-то невероятную активность в бенчмарке, коммиты прилетают один за другим. Turtle куда-то пропал, а я всё ещё изо всех сил программирую фьючерсы через монте-карло.
Четыре ночи. Предлагаю в чат подумать над тем, какой алгоритм можно быстро запрограммировать для бахвальства и опционов -- что-нибудь совсем простое, но, чтобы с этим было явно лучше, чем если бы этого не было вообще.
Почти пять ночи. Turtle обнаруживает самый эпичный фейл за весь конкурс: фьючерсы запрограммированы, они расчитываются при инициализации, летают в стейте в lambda_punter_offline, но они не объявляются! Тупо заявки на них не передаются на сервер. Это провал, и я отправляюсь это поведение ремонтировать. Получается, солвер там на игровых серверах и без всяких футур умудрялся кого-то побеждать. Чудеса.
Тем временем, всё ещё пять ночи. Sectoid, судя по всему, погиб, а мы с turtle пока копошимся: я допинываю свой царский предсказатель фьючерсов, а он реплеи.
Почти шесть. Turtle тоже куда-то отошёл, а я коммичу уже практически готовый предсказатель фьючерсов.
Собственно, морда map_vis, которую я уже упоминал в контексте визуализации результатов Girvan-Newman, умеет отрисовывать и результаты предсказания фьючерсов тоже. Если интересно, можно понапередавать ей разных карт и разные значения для общего количества игроков и очередности их хода. Например, вот такие фьючерсы предлагаются на randomMedium.json при двух игроках, когда мы ходим первые:
cargo run --release -- -f ../maps/randomMedium.json -c 2 -i 0
А вот такая картина будет для четырёх игроков, когда наш ход последний:
cargo run --release -- -f ../maps/randomMedium.json -c 4 -i 3
Можно наблюдать, что во втором случае фьючерсы выбираются существенно менее наглые, так как при таком количестве игроков шансы обломать нам длинные маршруты очень высоки.
06:30 -- у меня поехали какие-то игры с новыми фьючерсами. Попутно ремонтирую всплывающие баги. Наконец-то идут победы на рандомных картах. Тем не менее, работягам из kontur.ru всё ещё стабильно сливаем, но уже хотя бы совсем немного, а не как раньше:
SUCCESS for game port 9327: Punter: 0, score: 19 Punter: 1, score: 35 Punter: 2, score: 8098 Punter: 3 (it's me), score: 7104
Почти семь утра -- уже собираюсь пойти вздремнуть, но обнаруживаю, что забыл доделать опционы :) Пришлось опять открывать емакс.
Восемь утра -- turtle уходит в магазин, я всё ещё мучаю опционы. К девяти заканчиваю. Стратегия предельно простая: если маршрут преградили враги, но в запасе есть опционы -- смело их тратим! Маршрут должен быть построен во что бы то ни стало. Это немедленно приносит результаты: на картах с поддержкой опционов резко легчает. Скорее всего, за счёт того, что возрастают шансы выполнить фьючерсы.
09:30 -- массовые результаты всё ещё неплохие, но контур нас стабильно наказывает на треугольниках и рандомах. Всплывает новая проблема: таймауты! На гигантских картах тормозят расчёты Girvan-Newman и, особенно, симуляции монте-карло. Выношу симуляции в отдельный тред, чтобы можно было отследить таймаут из основного. Вроде как результаты ещё улучшились: массовый прогон показывает winrate > 90%. Не знаю уж, сколько там попалось контуров, но, тем не менее.
Десять утра. Я решаю окончательно всё проверить, в том числе, что не развалился lambda_punter_offline. Для этого нужна помощь Turtle, и его виртуалка.
После проверки предполагается создать сабмишн, но этого никто делать не умеет, кроме Sectoid -- а он уснул. Тем не менее, только я про это подумал, Sectoid проснулся и вернулся в чат. Между прочим, это уже второй раз за конкурс так происходит -- походу я умею его будить силой мысли.
10:15 -- выясняется, что проклятые таймауты всё ещё не побеждены. Закапываюсь в ремонт. Тем временем, находится ещё баг в бенчмарке Sectoid-а.
11:20 -- я наделал разнообразных лимитов на количество симуляций и всего такого: вроде как, большую часть таймаутов победил. Но, как обнаруживается, не окончательно. Остальной расклад такой: на треугольнике без ничего мы стабильно чуть-чуть проигрываем, с фьючерсами и/или опционами выигрываем. Есть ещё какие-то проигрыши, но, в массе, результаты обнадёживающие: общий винрейт по результатам 128 игр 89%.
12:30 -- сабмит оргам ушёл, Sectoid уехал в офис, а Turtle отправился обедать. Сам я, по-моему, пошёл немного вздремнуть.
13:40 -- все вернулись, работаем дальше. Прошу найти мне какую-нибудь игру, где враги делают splurges, чтобы, хотя бы посмотреть как их надо готовить :) Сам отправляюсь по-мелочи улучшать солвер на граничных случаях.
14:00 -- бахвальства не нашли. То ли эту опцию реально никто не использует, то ли просто люди уже не играют на серверах.
14:30 -- по доброй традиции затеял серьёзное улучшение в солвере =) Разумеется, за 15 минут до окончания конкурса посыпались разнообразные баги, которые я в резком темпе пытался фиксить, короче, в итоге решили забить и оставить сабмит заведомо рабочей версии.
Есть наблюдение, что участники в своей массе тусуются на маленьких и небольших картах. На больших стабильно пусто -- а вот мы как раз на них вполне себе выступаем. Получается, что если всё удачно сложится, у нас есть неплохой шанс в третьем раунде общего зачёта (если мы туда вообще доберёмся, конечно :)). Вот так выглядит среднестатическая игра в толпе на большой карте:
SUCCESS for game port 9703: Punter: 0, score: 0 Punter: 1, score: 0 Punter: 2, score: 0 Punter: 3, score: 0 Punter: 4, score: 0 Punter: 5, score: 55 Punter: 6, score: 91 Punter: 7, score: 6699 Punter: 8 (it's me), score: 750349 Punter: 9, score: 0 Punter: 10, score: 0 Punter: 11, score: 0 Punter: 12, score: 281651 Punter: 13, score: 146012 Punter: 14, score: 299313 Punter: 15, score: 214630
15:30 -- конкурс закончен. Ну что ж, будем ждать результатов.
Постфактум.
В целом, мне задание в этом году очень понравилось. Конечно, неудачно вышло, что команда участвовала в неполном составе, с Rust-ом тоже получилось неаккуратно, а сам я вообще программировал со сломаной рукой, но, тем не менее. По-моему, мы сыграли неплохо, были реализованы интересные идеи, и, вообще, с драйвом и фаном было всё отлично. Собственно, для этого мы и участвуем в icfpc, так ведь? :)
Единственно, я пока никак не могу придумать стратегию, как же нам, в конце-концов, выиграть этот проклятый конкурс :) Как бы ты ни выкладывался в процессе, всё равно перед командами типа тех же kontur.ru или Unagi ощущаешь полное бессилие. У контуров, например, там шестнадцать башковитых человек в команде, они вместе сидят все выходные в офисе, у них разные алгоритмические и инфраструктурные группы, они проводят совещания в переговорках и успевают даже в процессе заниматься видео-блогом =) Японцы вообще параллельно делают по нескольку десятков солверов на разных языках от джавы до пхп, и потом комбинируют их в одного терминатора. Я не очень представляю себе, как их можно побеждать нашими ограниченными силами, мы просто физически не успеваем.
С другой стороны, был же ведь не так давно конкурс, где первое место взял на хаскеле соло чувак из Латвии. Получается, есть способ :)
Весь код у нас традиционно открыт в репе на битбакете, можно смотреть. Чем будем играть в следующем году пока непонятно. Возможно, это будет опять Rust, уж больно хорошо он зашёл.
Я возвращаюсь в чат в полдень, к этому времени там уже произошло:
- ничего.
В 13:44 я обнаруживаю в списках игроков на серверах вот такое имя: "A Storm of Minds: Mine Connect Claimer" -- понимаю, что я на верном пути =) Дальше мы пытаемся придумать какую-нибудь простую, но более эффективную стратегию, а параллельно я усиленно программирую link_mines.
В 14:17 организаторы объявляют продление лайтнинга на час (в качестве компенсации за то, что начало конкурса задержалось из-за обвала сайта с заданием). Это круто, потому что я как раз начал усиленно переживать, что не успеваю к трём. В солвере я, помимо соединения шахт, планирую один из этих маршрутов объявлять фьючерсом. Но вот засада -- не могу найти карту с фьючерсами, прошу команду помочь.
В 14:33 солвер у меня научился соединять шахты дейкстрой, осталось срочно придумать, что делать, когда все шахты на карте соединены. Решаю пока просто захватывать оставшиеся реки в случайном порядке.
В 15:01 у меня всё готово, прошу в чате всех помочь с тестированием.
RUST_LOG=lambda_punter=debug,lambda_punter_online=debug cargo run --release -- --server-port 9024 link_mines В процессе оказывается, что играет оно плохо: пока я тяну дорогу, враги быстро перекрывают подступы к шахтам. В срочном порядке бранчуюсь и начинаю кодить вариант, который строит маршрут не от одной точки другой, а от обеих сразу к центру маршрута.
В 15:10 готово, все продолжаем тестировать. Через 10 минут Sectoid находит баг в декодере пакетов: оказывается, что количество очков может быть отрицательным (например, за проваленный фьючерс). На серверах тем временем играют боты каких-то товарищей под таким именем: "WISE_PIDOR_SOLUTION" :) В целом, всё остальное вроде ок, и в 15:33 Sectoid пошёл собирать сабмишн.
В 15:39 обнаруживаю карту "Oxford sparse" на которой только одна шахта: на ней солвер link_mines отказывается работать :) Срочно бросаюсь делать фикс. В 15:42 фикс готов, идёт вывариваться новый сабмишн. В 15:45 решаю срочно улучшить поведение, когда все основные цели солвер выполнил. В 15:53 у меня готов очередной фикс. Но там баг! К 15:56 готов багфикс. Пока решали, сабмитить или нет, к 15:59 я обнаружил ещё один баг! Короче пофиг, решаем больше не дёргаться.
16:00: lightning division типа закончен. Но что-то везде тишина.
Тем временем, в 16:19 я делаю окончательный багфикс солвера. Результаты с eager punter-ами улучшились в два с половиной раза :) Решаем на авось засабмитить, вдруг это решение каким-то чудом на лайтнинг пройдёт. Ну а если нет, то и не надо. К 16:30 сабмишн уезжает, я отправляюсь обедать, а ребята там ещё в остаются в чате придумывать разнообразные стратегии победы на будущее. Sectoid решает сделать автоматическую тестировалку наших ботов об сервера организаторов.
Дальше часок мы там просто абстрактно размышляли на разные темы, а дальше на меня (как на жирафа) начала накатывать череда озарений:
- к 17:29 я внезапно соображаю, что при построении своих маршрутов я же ведь имею право пользоваться своими уже захваченными ранее реками! Казалось бы, очевидная вещь, но по какой-то причине она мне раньше не пришла в голову. Бегу программировать.
- к 18:46 я так же внезапно обнаруживаю, что фьючерсы (по заданию) должны начинаться в шахте, а заканчиваться не в шахте! Я же объявлял их от шахты до шахты. Бегу программировать.
- параллельно обнаруживаю ещё пару багов, один из которых про то, что реки (A, B) и (B, A) у меня кое-где считаются разными.
В 19:50 организаторы фиксят свой lamduct (по многочисленным жалобам), сделав там блокирующий режим в пайпе -- это ведь как раз то, с чем я сражался половину предыдущей ночи. Мне всегда в такие моменты немного обидно: ты типа мучался, тратил время, и потом с таким трудом одолел проблему -- а кто-то вместо этого немного поныл в чатик организаторам, и ему всё принесли готовое. Лучше б я поспал вчера :)
В 20:15 я решаю как-нибудь несложно доработать утилиту lambda_punter_online, чтобы она умела одновременно проводить сразу несколько игр на разных рандомных серверах. Эта работа немного пересекается с автоматической обстреливалкой, которую делает Sectoid, но мне вот прямо щас уже нужны какие-то массовые результаты, чтобы было представление о качестве солвера. Turtle к этому времени начинает писать кастомный сервер, но вскоре ему приходится уехать. Jtootf с Sectoid в это время садятся брейнштормить алгоритмы. Я им для затравки подробно описал как сейчас работает мой текущий солвер.
Далее мы примерно этим расслабленно занимаемся вплоть до 22:00. Из любопытных идей было порождено следующее:
- @jtootf: стараться отстраивать те куски маршрута, которые имеют больший коэффициент связности.
- @sectoid: выкрасть прямо из браузера graph-viewer и puntfx от организаторов (так как они грамнотно написаны и не обфусцированы), и собрать на их базе визуализатор.
Тем не менее, периодически попадаются товарищи, которые меня наказывают. Например, на random-* картах солверу достаточно быстро обрубают пути, которыми он пытается соединять рудники, и он начинает метаться по карте вместо полезной деятельности.
Постепенно lambda_punter_online отыгрывает 256 игр на разных случайных картах: получаю винрейт 82%. Через пять минут соображаю, что сервера слишком рандомно выбираются, и из-за их ограниченного количества и долгого времени ожидания на некоторых картах, возникает ситуация, когда у меня бот играет сам с собой. Иногда бывает даже до 12 моих ботов на одной карте :) Сажусь переделывать, чтобы сервера предлагались гарантированно разные.
22:46 -- анализирую очередной луз, и возникает идея сохранять чат протокола, чтобы потом сделать реплеи. Все остальные активно поддерживают. Дальше рассуждаем про идею не брать фьючерсы вообще на картах, где много мостов, ну или брать только короткие.
К 23:05 замечаю, что сломалась игра через lambda_punter_offline -- какая-то проблема с сериализацией стейта. Оказалось, что serde_json не хочет сериализовать через #[derive(Serialize)] хэш-таблицу, где ключами являются не строки. Сажусь ремонтировать :(
К 23:51 доигрались 256 игр с условием, чтобы мои боты сами с собой не играли: винрейт почти 90%!
К полуночи ремонтирую сериализацию стейта (пришлось делать отдельный враппер для хеш-таблицы), lambda_punter_offline заработал. Ориентировочно собираюсь идти спать (хехе). Turtle всё ещё делает игровой сервер, а Sectoid бенчмарк.
Чуть подумав, вместо того, чтобы пойти спать, я в книжке Mining Of Massive Data Sets откапываю алгоритм, который давно хотел сюда как-то применить: Girvan-Newman, про кластеризацию графа. Сама по себе кластеризация мне тут вроде ни к чему, но меня больше интересуют коэффициенты рёбер, которые показывают, сколько идёт кратчайших путей из любого узла графа в любой другой.
Чтобы проиллюстрировать, какие конкретно результаты я хотел получить с помощью этого алгоритма, я уже сильно после конкурса спрограммировал специальный визуализатор. Его можно взять из репозитория команды, он там называется map_vis. Выглядит он примерно вот так:
А вот так, например, отрисовывается эта же карта randomMedium.jspn с реками, интенсивность подсветки которых зависит от коэффициента betweenness.
Очевидно, что на этой карте имеет смысл как можно быстрее забирать центральную реку, которая отмечена жирным жёлтым. Через этот мост проходит большинство кратчайших путей, если их строить из каждого узла графа в каждый другой.
В половину второго внезапно прибегает Sectoid с вопросом, можно ли разложить граф на плоскости, и если можно, то как это использовать :)
Ближе к четырём ночи я коммичу реализацию Girvan-Newman в репо вместе с тестами, и отваливаюсь спать.
День третий.
Сажусь за комп ближе к часу дня, и обнаруживаю новый апдейт задания: бахвальство (Splurges). Смысл его в том, что теперь не обязательно строить маршрут по одному сегменту за ход, а вместо этого можно соответствующее количество раз спасовать, и потом за один ход построить весь маршрут махом.
Надо сказать, что я так до конца конкурса и не понял, честно говоря, как можно выгодно применять бахвальство. Единственная осмысленная мысль была про то, что можно использовать splurge, когда хочется других игроков ввести в заблуждение относительно своих намерений.
Вплоть до двух часов ничего не происхоит, я только объясняю товарищам, зачем я сделал Girvan-Newman, и как я собираюсь им пользоваться. Пока, на самом деле, особых идей нет, кроме как при стройке маршрута сначала стараться захватывать не просто какую-то реку, а ту, которая имеет наибольший коэффициент betweenness -- теоретически, так можно первей всех забрать мосты, испортить маршруты врагам, и воспрепятствовать тому, чтобы враги тебе самому обломали планы.
Два часа дня. Тыкаюсь какое-то время в игровые сервера: сильные игроки всё ещё не играют, винрейт стабильно за 90%. Делаю поддержку бахвальства в протоколе. Сажусь писать поддержку Girvan-Newman в солвере, чтобы он захватывал сначала важные реки: заодно, решаю переименовать солвер в solvers::gn (от Girvan-Newman), чтобы можно было всегда откатиться к solvers::link_mines, если что.
Народу приходит интересная идея, как в теории можно применить бахвальство: если нам не хватает времени досчитать ход, мы пасуем и сохраняем в стейт недосчитаное решение. Затем на следующем ходу досчитываем и делаем сразу ход из двух сегментов. Идея любопытная, на самом деле, но пока у нас проблема с таймаутами не стоит, ну и вообще это сложно как-то реализовывать.
16:00: Turtle бросает сервер и садится делать реплеи.
Я пока всячески апгрейжу по-мелочи solvers::gn -- по сравнению с link_mines он теперь:
- На картах с одной шахтой выбирает себе целью построить самый длинный возможный путь, а не случайный какой-нибудь.
- Для карты на этапе инициализации считаются betweenness-коэффициенты с помощью Girvan-Newman.
- В случае, когда все текущие цели выполнены, выбирается честно рандомная речка для захвата, а не первая свободная.
- В случае, когда ни один из ходов не принесёт дополнительных очков, всё равно захватывается какая-то случайная речка (до этого просто производился пас).
- + Делаю дампалку статусов выполнения фьючерсов после окончания игры
К пяти вечера я ещё разок пробую уговорить Turtle попрограммировать на расте, конкретно портировать визуализатор из сокобана. Но он боится, не хочет :)
Ещё через полчаса раздумий, куда бы правильней применить результаты Girvan-Newman, я решаю реализовать пока свою первоначальную идею: когда приходит ход, захватывать ту речку из маршрута, которая имеет самый высокий коэффициент betweenness. По-идее, должно полегчать на картах с явно выраженными мостами: они должны теперь у меня захватываться в первую очередь.
Через некоторое время обнаруживаю, что в наборе предлагаются карты, имеющие ровно одну шахту, и к которой ведут всего три или четыре реки. Игроков на карте при этом 16 :) Очевидно, что если при этом стартовать не в числе первых, то очков получаем стабильно нуль, и с этим, похоже, ничего не сделать.
К шести вечера выясняется, что на треугольнике и некоторых рандомах солвер стабильно проигрывает боту от kontur.ru. Ну вот, а ведь так хорошо всё начиналось =) Думаю, как можно улучшить наши результаты на этих картах. Есть подозрение, что у нас что-то неправильное происходит с фьючерсами.
Sectoid предлагает продумать идею, чтобы не брать слишком нахальные фьючерсы. Например, можно принудительно ограничивать их длину, в зависимости от размеров карты. В свою очередь, я начинаю размышлять на предмет того, чтобы как-то попробовать использовать расчитанные betweenness коэффициенты, чтобы найти такие точки:
- которые были бы максимально удалённые от исходной шахты
- до которых было бы проще всего добраться (минимальный шанс врагам обломать маршрут)
Обнаруживаю, что lambda_punter_online при массовой игре засчитывает ничью как поражение. Исправляю. Обстрел показывает, что старый солвер link_mines показывает (вроде бы) более лучшие результаты, чем новый gn.
Turtle тем временем нарисовал на бумажке картинок и рассказывает нам своё видение стратегии победы. К сожалению, в итоге в его алгоритме что-то не срастается. В конце концов сходимся на том, что я выдаю ребятам рассчитанные betweenness коэффициенты для карты randomMedium, а сам удаляюсь по делам на пару часов. По возвращении я строго наказываю придумать мне ясный и эффективный алгоритм для объявления фьючерсов.
Возвращаюсь в половину десятого, алгоритм не придуман :) Sectoid пытается разобраться с тем, как именно работает Girvan-Newman. К половине одинадцатого предлагаю забить на придумывание алгоритма, и закончить насущные дела по реплеям, серверу и бенчмаркам.
Параллельно я начинаю прорабатывать идею, которая меня навязчиво мучила всё время, пока я отсутствовал. Общий смысл программы примерно такой:
- На входе нам выдаётся карта, в которой известно количество рек, количество игроков и порядок их хода.
- Игроки типа совершают ходы в порядке своей очереди.
- В наш ход мы пытаемся забрать сегмент своего некоторого маршрута, который мы хотим объявить как фьючерс.
- Противник в свой ход может с какой-то вероятностью захватить одну из оставшихся рек. Допустим, эта вероятность будет прямо пропорциональна коэффициенту betweenness реки. Логика под этим такая, что более востребованные сегменты маршрутов (рёбра, через которые проходит большинство кратчайших путей) будут нужны большему количеству игроков, чтобы построить свой маршрут.
- Соответственно, в некоторый момент с какой-то вероятностью наш маршрут будет обломан. Очевидно, что чем дальше мы пытаемся строить этот маршрут, тем с большей вероятностью он будет обломан.
- Умея эту вероятность находить, в конце концов, нам надо пройти по всем узлам графа и для каждого из них получить оценку, насколько реально до сюда достроить фьючерс. И уже имея эту оценку, можно принимать решение, до куда конкретно нам его имеет смысл объявлять.
Но, как известно, на словах-то я Лев Толстой, а на деле это самое. Немного посидев с формулами минут десять, усиленно делая умный вид, я осознаю, что время уже позднее, башка не варит, да и тервер-то я знаю так себе (что уж там греха таить). По этому поводу расталкиваю в параллельном чате Игоря, который только что вернулся убитый с дачи. В конкурсе он участвовать дальше отказывается, но, тем не менее, мне удаётся уговорить его помочь мне с математикой. Выдаю ему упрощённый примере, где противники делают ходы полностью случайно, с одинаковой вероятностью захватывая одну из оставшихся рек. В идеале хочу формулу, куда можно было бы засунуть маршрут, количество и очерёдность игроков, а оттуда бы приехала вероятность построения этого маршрута.
Следует отметить, что такую формулу Игорь мне всё-таки умудряется подогнать, правда, только для двух игроков. При попытке придумать что-то для большего количества у него вскипает мозг, и он тоже сдаётся.
Ну что ж, раз в математику мы не можем, решаю идти путём слабаков: будем брутфорсить вероятности через монте-карло. Теория такая, что раз у нас на этот раз быстрый Rust, должна быть возможность запустить достаточное количество симуляций игр, чтобы получились нужные числа. Короче, сажусь постепенно что-то делать.
К полуночи приезжает последнее обновление к заданию: опционы. Смысл аналогичен вокзалам в паровозах: во время игры можно N раз воспользоваться чужой рекой для построения своего маршрута, где N равно количеству рудников на карте. В принципе, крутое дополнение: в отличие от бахвальства, тут хотя бы понятно как этим воспользоваться и как запрограммировать :) Собственно, потихоньку начинаю писать код, покуда в фоне идёт обсуждение системы реплеев имени Turtle.
В половину первого ночи ворвался Sectoid с сообщением, что у него заработал бенчмарк, и мы теперь можем типа объективно оценивать солвер. Запускаем играть gn. Пример выхлопа выглядит примерно так:
^CGot INTERRUPT. Finalizing... +---------------------+-------+--------+-----------------+-----------+----------------+---------+ | MAP | GAMES | ERRORS | SCORE | METASCORE | TOTALMETASCORE | WINRATE | +---------------------+-------+--------+-----------------+-----------+----------------+---------+ | sample | 10 | 0 | 25.8 | 2 | 20 | 1 | | lambda | 10 | 0 | 678 | 3.9 | 39 | 0.9 | | Sierpinski-triangle | 10 | 0 | 1078 | 3 | 30 | 1 | | circle | 15 | 5 | 276.5 | 4 | 40 | 1 | | randomMedium | 10 | 0 | 5107.2 | 3.9 | 39 | 0.9 | | randomSparse | 11 | 1 | 5490.5 | 3.9 | 39 | 0.9 | | boston-sparse | 6 | 0 | 108926.66666667 | 8 | 48 | 1 | | tube | 0 | 0 | 0 | 0 | 0 | 0 | | edinburgh-sparse | 0 | 0 | 0 | 0 | 0 | 0 | | nara-sparse | 0 | 0 | 0 | 0 | 0 | 0 | | oxford | 0 | 0 | 0 | 0 | 0 | 0 | | gothenburg-sparse | 0 | 0 | 0 | 0 | 0 | 0 | +---------------------+-------+--------+-----------------+-----------+----------------+---------+ В процессе разглядывания результатов рождаются сопутствующие идеи:
- Сохранять чат протокола тех игр, где мы проигрываем.
- Стараться выбирать игры, где играют не только одни eager punter'ы.
- Синхронизировать вывод формата с тем, что на входе ожидает Turtle, чтобы можно было сразу смотреть реплеи проигранных игр.
Тем временем уже почти два ночи. У turtle уже появляются реплеи с отрисовкой в gnuplot. Выглядит это как серия изображений вот такого типа:
Три ночи. Sectoid развёл какую-то невероятную активность в бенчмарке, коммиты прилетают один за другим. Turtle куда-то пропал, а я всё ещё изо всех сил программирую фьючерсы через монте-карло.
Четыре ночи. Предлагаю в чат подумать над тем, какой алгоритм можно быстро запрограммировать для бахвальства и опционов -- что-нибудь совсем простое, но, чтобы с этим было явно лучше, чем если бы этого не было вообще.
Почти пять ночи. Turtle обнаруживает самый эпичный фейл за весь конкурс: фьючерсы запрограммированы, они расчитываются при инициализации, летают в стейте в lambda_punter_offline, но они не объявляются! Тупо заявки на них не передаются на сервер. Это провал, и я отправляюсь это поведение ремонтировать. Получается, солвер там на игровых серверах и без всяких футур умудрялся кого-то побеждать. Чудеса.
Тем временем, всё ещё пять ночи. Sectoid, судя по всему, погиб, а мы с turtle пока копошимся: я допинываю свой царский предсказатель фьючерсов, а он реплеи.
Почти шесть. Turtle тоже куда-то отошёл, а я коммичу уже практически готовый предсказатель фьючерсов.
Собственно, морда map_vis, которую я уже упоминал в контексте визуализации результатов Girvan-Newman, умеет отрисовывать и результаты предсказания фьючерсов тоже. Если интересно, можно понапередавать ей разных карт и разные значения для общего количества игроков и очередности их хода. Например, вот такие фьючерсы предлагаются на randomMedium.json при двух игроках, когда мы ходим первые:
cargo run --release -- -f ../maps/randomMedium.json -c 2 -i 0
А вот такая картина будет для четырёх игроков, когда наш ход последний:
cargo run --release -- -f ../maps/randomMedium.json -c 4 -i 3
Можно наблюдать, что во втором случае фьючерсы выбираются существенно менее наглые, так как при таком количестве игроков шансы обломать нам длинные маршруты очень высоки.
06:30 -- у меня поехали какие-то игры с новыми фьючерсами. Попутно ремонтирую всплывающие баги. Наконец-то идут победы на рандомных картах. Тем не менее, работягам из kontur.ru всё ещё стабильно сливаем, но уже хотя бы совсем немного, а не как раньше:
SUCCESS for game port 9327: Punter: 0, score: 19 Punter: 1, score: 35 Punter: 2, score: 8098 Punter: 3 (it's me), score: 7104
Почти семь утра -- уже собираюсь пойти вздремнуть, но обнаруживаю, что забыл доделать опционы :) Пришлось опять открывать емакс.
Восемь утра -- turtle уходит в магазин, я всё ещё мучаю опционы. К девяти заканчиваю. Стратегия предельно простая: если маршрут преградили враги, но в запасе есть опционы -- смело их тратим! Маршрут должен быть построен во что бы то ни стало. Это немедленно приносит результаты: на картах с поддержкой опционов резко легчает. Скорее всего, за счёт того, что возрастают шансы выполнить фьючерсы.
09:30 -- массовые результаты всё ещё неплохие, но контур нас стабильно наказывает на треугольниках и рандомах. Всплывает новая проблема: таймауты! На гигантских картах тормозят расчёты Girvan-Newman и, особенно, симуляции монте-карло. Выношу симуляции в отдельный тред, чтобы можно было отследить таймаут из основного. Вроде как результаты ещё улучшились: массовый прогон показывает winrate > 90%. Не знаю уж, сколько там попалось контуров, но, тем не менее.
Десять утра. Я решаю окончательно всё проверить, в том числе, что не развалился lambda_punter_offline. Для этого нужна помощь Turtle, и его виртуалка.
После проверки предполагается создать сабмишн, но этого никто делать не умеет, кроме Sectoid -- а он уснул. Тем не менее, только я про это подумал, Sectoid проснулся и вернулся в чат. Между прочим, это уже второй раз за конкурс так происходит -- походу я умею его будить силой мысли.
10:15 -- выясняется, что проклятые таймауты всё ещё не побеждены. Закапываюсь в ремонт. Тем временем, находится ещё баг в бенчмарке Sectoid-а.
11:20 -- я наделал разнообразных лимитов на количество симуляций и всего такого: вроде как, большую часть таймаутов победил. Но, как обнаруживается, не окончательно. Остальной расклад такой: на треугольнике без ничего мы стабильно чуть-чуть проигрываем, с фьючерсами и/или опционами выигрываем. Есть ещё какие-то проигрыши, но, в массе, результаты обнадёживающие: общий винрейт по результатам 128 игр 89%.
12:30 -- сабмит оргам ушёл, Sectoid уехал в офис, а Turtle отправился обедать. Сам я, по-моему, пошёл немного вздремнуть.
13:40 -- все вернулись, работаем дальше. Прошу найти мне какую-нибудь игру, где враги делают splurges, чтобы, хотя бы посмотреть как их надо готовить :) Сам отправляюсь по-мелочи улучшать солвер на граничных случаях.
14:00 -- бахвальства не нашли. То ли эту опцию реально никто не использует, то ли просто люди уже не играют на серверах.
14:30 -- по доброй традиции затеял серьёзное улучшение в солвере =) Разумеется, за 15 минут до окончания конкурса посыпались разнообразные баги, которые я в резком темпе пытался фиксить, короче, в итоге решили забить и оставить сабмит заведомо рабочей версии.
Есть наблюдение, что участники в своей массе тусуются на маленьких и небольших картах. На больших стабильно пусто -- а вот мы как раз на них вполне себе выступаем. Получается, что если всё удачно сложится, у нас есть неплохой шанс в третьем раунде общего зачёта (если мы туда вообще доберёмся, конечно :)). Вот так выглядит среднестатическая игра в толпе на большой карте:
SUCCESS for game port 9703: Punter: 0, score: 0 Punter: 1, score: 0 Punter: 2, score: 0 Punter: 3, score: 0 Punter: 4, score: 0 Punter: 5, score: 55 Punter: 6, score: 91 Punter: 7, score: 6699 Punter: 8 (it's me), score: 750349 Punter: 9, score: 0 Punter: 10, score: 0 Punter: 11, score: 0 Punter: 12, score: 281651 Punter: 13, score: 146012 Punter: 14, score: 299313 Punter: 15, score: 214630
15:30 -- конкурс закончен. Ну что ж, будем ждать результатов.
Постфактум.
В целом, мне задание в этом году очень понравилось. Конечно, неудачно вышло, что команда участвовала в неполном составе, с Rust-ом тоже получилось неаккуратно, а сам я вообще программировал со сломаной рукой, но, тем не менее. По-моему, мы сыграли неплохо, были реализованы интересные идеи, и, вообще, с драйвом и фаном было всё отлично. Собственно, для этого мы и участвуем в icfpc, так ведь? :)
Единственно, я пока никак не могу придумать стратегию, как же нам, в конце-концов, выиграть этот проклятый конкурс :) Как бы ты ни выкладывался в процессе, всё равно перед командами типа тех же kontur.ru или Unagi ощущаешь полное бессилие. У контуров, например, там шестнадцать башковитых человек в команде, они вместе сидят все выходные в офисе, у них разные алгоритмические и инфраструктурные группы, они проводят совещания в переговорках и успевают даже в процессе заниматься видео-блогом =) Японцы вообще параллельно делают по нескольку десятков солверов на разных языках от джавы до пхп, и потом комбинируют их в одного терминатора. Я не очень представляю себе, как их можно побеждать нашими ограниченными силами, мы просто физически не успеваем.
С другой стороны, был же ведь не так давно конкурс, где первое место взял на хаскеле соло чувак из Латвии. Получается, есть способ :)
Весь код у нас традиционно открыт в репе на битбакете, можно смотреть. Чем будем играть в следующем году пока непонятно. Возможно, это будет опять Rust, уж больно хорошо он зашёл.