В этом году контест по ряду причин был унылым, так что пост будет коротким и тоже унылым. Я и так целый месяц тянул с написанием отчёта, так что либо так, либо вообще никак.

Задание

Нам снова предложили игру на графе (зеркало). К примеру, вот на такой версии Оксфорда:

Здесь зелёные точки — это «города», некоторые из которых имеют «шахты» (красные кружки). «Города» соединены «реками» (серые линии). В шахтах добываются «лямбды» (отсылка к заданию 2012-го года), которые нужно доставлять в города. В чем более далёкий город удалось доставить лямбду, тем больше получается очков.

Команды пишут ботов, которые по очереди занимают реки. В конце игры для каждой пары шахта-город, соединённой реками бота, рассчитывается минимальный путь в графе (d), и бот получает d × d очков.

В течение контеста было выпущено три обновления задания, добавлявших:

• futures (зеркало) — бот в начале игры может сделать «ставку» на то, что ему удастся соединить некие шахту и город. Если ему действительно это удаётся, он получает d × d × d очков;
• splurges (зеркало) — бот может пропустить несколько ходов, после чего занять несколько рек сразу;
• options (зеркало) — бот может занять до n чужих рек, где n — количество шахт.

Для futures мы даже успели что-то реализовать, а остальные два дополнения проигнорировали.

Как мы играли

Вяло (относительно прошлых годов).

Codingteam в этом году представляли Akon32, ForNeVeR, grouzen, nightmare932, portnov и я. Akon32 выступал в ICFPC впервые.

Подробную хронику мне писать лень, поэтому просто перечислю те идеи, которые в итоге удалось реализовать. В порядке появления в репозитории:

• delegating strategy — мета-стратегия, выбирающая из «конкретных» стратегий ту, что лучше всего подходит для сложившейся ситуации. Предполагалось, что каждая из «конкретных» стратегий будет оценивать вероятность хорошего хода, и delegating strategy будет выбирать ту, у которой вероятность наивысшая. На практике вероятности брались чуть ли не с потолка, потому что нормальные алгоритмы оценки писать не проще, чем сами стратегии;

• random walker — стратегия, занимающая произвольную незанятую реку. Писалась, естественно, не пользы ради, а обучения для;

• random connector — почти как предыдущая, только выбирает не из всех рек, а только из тех, что соединены с городами, до которых уже добрался наш бот;

• жадная — занимает ту реку, что больше всего увеличит счёт;

• dumb obstructor — как random connector, только выбирает из рек, ближайших к какому-нибудь из противников;

• mixed — ещё одна мета-стратегия. Случайным образом выбирает из «конкретных» стратегий с учётом вероятностей хорошего хода и заданных нами весов стратегий. Хотелось сделать что-то типа смешанных стратегий из теории игр, но на практике всё упёрлось в подбор весов — мы так и не придумали, как разумней всего их распределить;

• component connector — пытается соединить два «кластера», образованных нашими реками;

• mine occupation — пытается занять как можно больше рек, соединённых с шахтами. Если не дать противнику доступа к шахте, он не сможет получить очков;

• antihero — выбирает случайного противника и использует жадную стратегию с его точки зрения, таким образом «отбирая» у него выгодный ход;

• future — пытается воплотить в жизнь futures, «придуманные» RandomFutureGenerator. Я в код вникнуть не успел, так что логику объяснять не могу.

Были мысли и о более крутых стратегиях, но т.к. имплементация шла медленно, до них мы так и не добрались.

Рефлексия

Уныло было по четырём причинам.

Во-первых, отсутствовал scoreboard. В прошлые годы именно scoreboard поддерживал дух соревнования, не давал расслабляться и при этом чётко сообщал, насколько хорошо справляется наше решение. В этом же году организаторы предоставили лишь игровые сервера, на которых были запущены примитивные боты. Если кому-то хотелось поиграть против настоящих противников, нужно было договариваться о матче через IRC или как-то ещё. Что-то тестировать в таких условиях было проблематично. Я под конец контеста для подбора весов в смешанных стратегиях просто написал свою реализацию сервера и сталкивал несколько инстансов нашего бота друг с другом.

Во-вторых, Scala. В отличие от 2015-го, я к Скале не готовился и потому кодинг шёл туго — приходилось подглядывать то синтаксис match, то названия методов у коллекций. По-хорошему, все эти штуки должны были бы быть у меня в кэше, чтобы я не отвлекался.

В-третьих, scala-graph. Осиливать такую библиотеку за считанные часы я никак не был готов. Малознакомый синтаксис Скалы плюс недостаток документации порой выводили из себя. Учитывая, что в итоге из библиотеки мы пользовались только маркировкой рёбер и поиском путей, я не уверен, что сто́ило вообще брать стороннюю библиотеку.

В-четвёртых, какое-то совершенно непритязательное задание. Не было какой-то изюминки, чего-то такого, за что это задание можно было бы вспоминать ещё лет десять.

Результат

Оценивание проводится в три этапа, на каждом из которых после ряда игр отсеивается половина участников. Мы вылетели на первом же (зеркало), заняв 102-е место из 120. В принципе, после такого выступления я ни на что особо и не рассчитывал; напротив, я несколько удивлён, что это не худший наш результат — в 2015-м мы старались гораздо больше и получили море фана, но лишь 151-е место из 194-х. Go figure.

Как всегда, весь наш код можно найти на GitHub.

Надеюсь, в следующем году будет повеселей.