Хакатон 2020

Потому что совместный труд, для моей пользы — он объединяет.

Матроскин

Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою.

Козьма Прутков «Мысли и афоризмы».

Недавно, в прошлую пятницу, мы решили слегка разнообразить свои будни, проведя программистский турнир. Повестка определилась не сразу. Были мысли про аналитическую обработку данных, машинное обучение, но в конце концов, остановились на настольных играх. Нам хотелось ввести в мероприятие элемент соревнования, а что, как не игры, позволяет легко это сделать?

Итак, коллектив, желающий принять участие в соревновании, в наличии был, с призовым фондом тоже разобрались — осталось определиться с игрой. Я предложил «Атари Го» и на то у меня были самые веские основания.

Что вообще такое, это »Атари Го»?

• Го — хорошо изученная и очень популярная игра с интересной игровой механикой
• Разработка ботов для Го — сложное занятие, но «Атари Го» существенно проще
• Партии в «Атари Го» зрелищны и динамичны, а сама игра не подвержена «ничейной смерти«
• В разработке ботов, для этой игры, могут применяться как минимаксные алгоритмы, так и метод «Монте-Карло«
• По всей видимости, не существует общедоступных реализаций ботов для этой игры, которыми можно было бы воспользоваться в условиях острого дефицита времени

Относительно последнего пункта предвижу возражения. Да, действительно, ботов для Го пишется много и найти доступную реализацию совсем не проблема, но «Атари Го» — это другая игра. Потеря отдельных камней в Го не рассматривается как катастрофа — цели в игре совсем другие. В «Атари Го», потеря даже одного камня — это немедленное поражение.Поскольку мы не хотели связывать участников каким-то одним языком программирования, было решено разработать Web-сервис, предоставляющий REST API, для регистрации ходов участников турнира. Впоследствии, эта идея полностью себя оправдала. Помимо Java, в качестве языков разработки, участники соревнования использовали C++, Kotlin и даже Lua. Чтобы исключить возможное влияние различной производительности компьютеров, на которых планировался запуск ботов, были закуплены и первоначально протестированы два однотипных комплекта мини ПК, на которых была установлена ОС Ubuntu Linux 20-ой версии.

Сервис, фиксирующий ход партий, был разработан на Node.js с использованием фреймворка Nest, но это была только половина дела. Дело в том, что сервер задумывался как универсальное решение, не зависящее от конкретики каких либо из игр. Его задача — фиксация в БД ходов игроков и контроль времени, но он не проверяет на корректность сами ходы. Проверка корректности ходов, а также определение победителя — задача Арбитра, небольшого JavaScript-приложения, подключающегося к серверу с использованием библиотеки jQuery.

Больше технических деталей

Разработка ботов, даже для «Атари Го» — дело сложное. Трёх суток выделенных конкурсантам на подготовку, оказалось достаточно только для того, чтобы боты просто заработали. Кроме того, мини-ПК, на которых проводился конкурс, оказались существенно менее производительными, чем рабочие места, на которых выполнялась отладка. Всё это привело к тому, что боты, в ходе турнира, не блистали особым интеллектом, но забавные моменты всё же случались.

Это пример финальной позиции в одной из турнирных партий. Борьба ботов была интересная и ожесточённая. В конце-концов, белые попытались поймать противника в ситё, но не заметили, что следующим ходом чёрные поставили их в положение атари. Бот белых допустил ошибку, пытаясь продолжить «лестницу». Чёрные немедленно этим воспользовались — взяли камень и завершили игру.

Всё это хорошо иллюстрирует характер ошибок, допущенных участниками турнира

Одной из главных сложностей игры Го является то, что оценка материала в ней, практически, не имеет никакого смысла. Важно не то, сколько камней стоит на доске, а то, как они расположены. Существуют позиции требующие немедленной реакции игрока:

Это ситуация «атари» — угроза взятия камня. Если мы играем в «Атари Го», вне зависимости от очерёдности хода, игрок должен ответить в пункт «E6», над чёрным камнем. Белые, при этом, побеждают, а чёрные — защищаются от немедленного поражения, «удлиняя» камень, попавший в ловушку. При обнаружении на доске «атари», игрок должен отвечать немедленно, без каких либо предварительных расчётов. Существуют и более коварные позиции.

Здесь, слева направо, представлены: угроза двойного «атари«, угроза «гэта» и угроза «ситё«. Во всех трёх случаях, белые должны немедленно реагировать, вполне определённым образом, чтобы избежать поражения. Чёрные, в свою очередь, могут поймать белых в ловушку, на своём ходе. Сказанное не отменяет необходимости просмотра ходов в глубину, но ходы, связанные с обработкой этих ситуаций, должны рассматриваться в первую очередь.

Это больше похоже на распознавание образов, чем на задачу оптимизации

В силу нехватки времени, выделенного на разработку ботов, а также в связи со слабым знанием игры, ни один из участников не обрабатывал подобные ситуации специальным образом. Речь не идёт о сложных формах, боты не всегда корректно определяли даже ситуацию простого «атари».

Тем не менее, отборочный этап турнира, в рамках которого каждый из участников сыграл со всеми претендентами по две партии (белыми и чёрными), прошёл отлично и по количеству побед мы определили двух финалистов.

Далее, игры продолжались до трёх побед, с чередованием очерёдности первого хода. Победив с итоговым счётом 3:1, довольный (и три ночи не спавший) победитель забрал свой приз:

Поаплодируем ему!