Потому что совместный труд, для моей пользы — он объединяет.
Матроскин
Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою.
Козьма Прутков «Мысли и афоризмы».
Недавно, в прошлую пятницу, мы решили слегка разнообразить свои будни, проведя программистский турнир. Повестка определилась не сразу. Были мысли про аналитическую обработку данных, машинное обучение, но в конце концов, остановились на настольных играх. Нам хотелось ввести в мероприятие элемент соревнования, а что, как не игры, позволяет легко это сделать?
Итак, коллектив, желающий принять участие в соревновании, в наличии был, с призовым фондом тоже разобрались — осталось определиться с игрой. Я предложил «Атари Го» и на то у меня были самые веские основания.
Что вообще такое, это ''Атари Го''?
Го — это абстрактная логическая игра, распространённая в Китае, Японии и Корее. Для игры используется прямоугольная доска, расчерченная вертикальными и горизонтальными линиями. Фигуры (камни), которыми играют противники, ставятся на пересечения линий (пункты). Стандартный размер доски — 19x19. В игре участвуют два игрока, один из которых получает чёрные камни, другой белые. Игрок с чёрными камнями начинает игру.
В начале игры доска пуста. Игроки, по очереди, ставят камни своего цвета на пустые пункты доски. Свободные пункты, граничащие с камнем по линиям, называются «дамэ». Поставленные на доску камни не перемещаются, но их можно убрать с доски, полностью окружив (лишив дамэ). Камни одного цвета, расположенные по соседству, составляют группу. Группа может быть снята с доски только целиком, после заполнения всех её дамэ:
В Го запрещены самоубийственные ходы. Нельзя ставить камень на доску, лишая свою группу последнего дамэ. Но это правило не касается того случая, когда своим ходом мы берём камни противника. Поскольку взятые камни соседствуют с камнем поставленным на доску, таким ходом мы не убиваем свою группу, а увеличиваем количество её дамэ:
Есть еще одно правило (Ко), запрещающее повторение на доске предыдущей позиции, но для нас оно не очень важно. Дело в том, что «Атари Го» продолжается лишь до первого взятия. Игрок, первым захвативший хотя бы один из камней противника, побеждает. Поскольку камни на доске не могут двигаться, очевидно, что повторение позиции может быть связано только с захватом камней. Таким образом, в «Атари Го», ситуация Ко возникнуть не может, поскольку после первого же взятия игра будет завершена.
«Атари Го» — игра детская, используемая для обучения учеников основам захвата камней в Го. Стандартный размер доски для неё — 9x9 линий. Для наших целей эта игра наиболее пригодна. Дело в том, что Го — очень сложная игра. В первую очередь, по той причине, что её цель — окружение наибольшей территории, связана с захватом камней лишь опосредованно. «Атари Го» более прямолинейна. Писать ботов для этой игры гораздо проще!
В начале игры доска пуста. Игроки, по очереди, ставят камни своего цвета на пустые пункты доски. Свободные пункты, граничащие с камнем по линиям, называются «дамэ». Поставленные на доску камни не перемещаются, но их можно убрать с доски, полностью окружив (лишив дамэ). Камни одного цвета, расположенные по соседству, составляют группу. Группа может быть снята с доски только целиком, после заполнения всех её дамэ:
В Го запрещены самоубийственные ходы. Нельзя ставить камень на доску, лишая свою группу последнего дамэ. Но это правило не касается того случая, когда своим ходом мы берём камни противника. Поскольку взятые камни соседствуют с камнем поставленным на доску, таким ходом мы не убиваем свою группу, а увеличиваем количество её дамэ:
Есть еще одно правило (Ко), запрещающее повторение на доске предыдущей позиции, но для нас оно не очень важно. Дело в том, что «Атари Го» продолжается лишь до первого взятия. Игрок, первым захвативший хотя бы один из камней противника, побеждает. Поскольку камни на доске не могут двигаться, очевидно, что повторение позиции может быть связано только с захватом камней. Таким образом, в «Атари Го», ситуация Ко возникнуть не может, поскольку после первого же взятия игра будет завершена.
«Атари Го» — игра детская, используемая для обучения учеников основам захвата камней в Го. Стандартный размер доски для неё — 9x9 линий. Для наших целей эта игра наиболее пригодна. Дело в том, что Го — очень сложная игра. В первую очередь, по той причине, что её цель — окружение наибольшей территории, связана с захватом камней лишь опосредованно. «Атари Го» более прямолинейна. Писать ботов для этой игры гораздо проще!
- Го — хорошо изученная и очень популярная игра с интересной игровой механикой
- Разработка ботов для Го — сложное занятие, но «Атари Го» существенно проще
- Партии в «Атари Го» зрелищны и динамичны, а сама игра не подвержена "ничейной смерти"
- В разработке ботов, для этой игры, могут применяться как минимаксные алгоритмы, так и метод "Монте-Карло"
- По всей видимости, не существует общедоступных реализаций ботов для этой игры, которыми можно было бы воспользоваться в условиях острого дефицита времени
Относительно последнего пункта предвижу возражения. Да, действительно, ботов для Го пишется много и найти доступную реализацию совсем не проблема, но «Атари Го» — это другая игра. Потеря отдельных камней в Го не рассматривается как катастрофа — цели в игре совсем другие. В «Атари Го», потеря даже одного камня — это немедленное поражение.
Поскольку мы не хотели связывать участников каким-то одним языком программирования, было решено разработать Web-сервис, предоставляющий REST API, для регистрации ходов участников турнира. Впоследствии, эта идея полностью себя оправдала. Помимо Java, в качестве языков разработки, участники соревнования использовали C++, Kotlin и даже Lua. Чтобы исключить возможное влияние различной производительности компьютеров, на которых планировался запуск ботов, были закуплены и первоначально протестированы два однотипных комплекта мини ПК, на которых была установлена ОС Ubuntu Linux 20-ой версии.
Сервис, фиксирующий ход партий, был разработан на Node.js с использованием фреймворка Nest, но это была только половина дела. Дело в том, что сервер задумывался как универсальное решение, не зависящее от конкретики каких либо из игр. Его задача — фиксация в БД ходов игроков и контроль времени, но он не проверяет на корректность сами ходы. Проверка корректности ходов, а также определение победителя — задача Арбитра, небольшого JavaScript-приложения, подключающегося к серверу с использованием библиотеки jQuery.
Больше технических деталей
Многопользовательский игровой сервер — это прежде всего, база данных. В качестве СУБД мы использовали PostgreSQL. Схема данных проектировалась «на вырост» и, на текущий момент, выглядит следующим образом:
Часть относящаяся к user-ам и token-ам, я думаю понятна (сервер использует JWT-авторизацию). Список поддерживаемых игр хранится в таблице games (только «Атари Го» на момент начала турнира). На каждую партию создаётся запись в game_sessions. Игроки, участвующие в партии (для некоторых игр их может быть больше двух) фиксируются в таблице user_games. Сами ходы сохраняются в game_moves.
Прежде всего, один из игроков создаёт игровую сессию (POST api/session), формирует вызов противнику (POST api/challenge) и выполняет первый ход (POST api/move). Второй игрок получает вызов (GET api/challenge) и присоединяется к сессии (POST api/join). Далее, каждый из игроков, в цикле, получает ход противника (GET api/move/confirmed/:id, здесь id — идентификатор сессии) и выполняет собственный ход (POST api/move).
Как я уже писал выше, сервер не проверяет корректность выполняемых ходов, но он учитывает время, затраченное на каждый ход. В соответствии с регламентом баёми, каждому из игроков выделяется основное время (games.main_time), по истечении которого даётся дополнительное время (games.additional_time), на выполнение каждого хода. Учитывается период времени от момента получения хода противника (или создания игровой сессии), до момента формирования собственного хода. Это довольно мягкая система контроля времени. Даже исчерпав основное время, игрок не проиграет, если укладывается в дополнительное время, при выполнении каждого хода.
Корректность ходов игроков (в соответствии с правилами игры), а также победителя определяет Арбитр — специальное приложение, подключающееся к серверу с правами администратора. Его задача — получение не подтверждённых ходов игроков, их проверка и формирование подтверждения (setup_str), позволяющего восстановить позицию, на момент завершения хода (это может понадобиться, например, при перезапуске Арбитра, без завершения партии). Также, Арбитр выполняет проверку исчерпания лимита времени и условия завершения игры (взятие хотя бы одного из камней). Дополнительно, эта программа осуществляет визуализацию хода игры (скриншоты в статье сделаны с её помощью).
Часть относящаяся к user-ам и token-ам, я думаю понятна (сервер использует JWT-авторизацию). Список поддерживаемых игр хранится в таблице games (только «Атари Го» на момент начала турнира). На каждую партию создаётся запись в game_sessions. Игроки, участвующие в партии (для некоторых игр их может быть больше двух) фиксируются в таблице user_games. Сами ходы сохраняются в game_moves.
Сервер предоставляет следующее API
{
"openapi":"3.0.0",
"info":{
"title":"Dagaz Server",
"description":"Dagaz Server API description",
"version":"0.0.1",
"contact":{
}
},
"tags":[
{
"name":"dagaz",
"description":""
}
],
"servers":[
],
"components":{
"schemas":{
"User":{
"type":"object",
"properties":{
"id":{
"type":"number"
},
"is_admin":{
"type":"number"
},
"name":{
"type":"string"
},
"username":{
"type":"string"
},
"password":{
"type":"string"
},
"email":{
"type":"string"
},
"created":{
"format":"date-time",
"type":"string"
},
"deleted":{
"format":"date-time",
"type":"string"
},
"last_actived":{
"format":"date-time",
"type":"string"
}
},
"required":[
"id",
"name",
"username",
"created",
"last_actived"
]
},
"Pref":{
"type":"object",
"properties":{
"id":{
"type":"number"
},
"user_id":{
"type":"number"
},
"game_id":{
"type":"number"
},
"created":{
"format":"date-time",
"type":"string"
}
},
"required":[
"game_id"
]
},
"Sess":{
"type":"object",
"properties":{
"id":{
"type":"number"
},
"status":{
"type":"number"
},
"game_id":{
"type":"number"
},
"game":{
"type":"string"
},
"filename":{
"type":"string"
},
"created":{
"format":"date-time",
"type":"string"
},
"creator":{
"type":"string"
},
"changed":{
"format":"date-time",
"type":"string"
},
"closed":{
"format":"date-time",
"type":"string"
},
"players_total":{
"type":"number"
},
"winner":{
"type":"number"
},
"loser":{
"type":"number"
},
"score":{
"type":"number"
},
"last_setup":{
"type":"string"
}
},
"required":[
"game_id"
]
},
"Challenge":{
"type":"object",
"properties":{
"id":{
"type":"number"
},
"session_id":{
"type":"number"
},
"user_id":{
"type":"number"
},
"user":{
"type":"string"
},
"player_num":{
"type":"number"
}
},
"required":[
"session_id"
]
},
"Join":{
"type":"object",
"properties":{
"id":{
"type":"number"
},
"user_id":{
"type":"number"
},
"user":{
"type":"string"
},
"session_id":{
"type":"number"
},
"player_num":{
"type":"number"
},
"is_ai":{
"type":"number"
}
},
"required":[
"session_id"
]
},
"Move":{
"type":"object",
"properties":{
"id":{
"type":"number"
},
"session_id":{
"type":"number"
},
"user_id":{
"type":"number"
},
"turn_num":{
"type":"number"
},
"move_str":{
"type":"string"
},
"setup_str":{
"type":"string"
},
"note":{
"type":"string"
},
"time_delta":{
"type":"number"
},
"time_limit":{
"type":"number"
},
"additional_time":{
"type":"number"
}
},
"required":[
"session_id",
"user_id",
"move_str"
]
},
"Result":{
"type":"object",
"properties":{
"id":{
"type":"number"
},
"session_id":{
"type":"number"
},
"user_id":{
"type":"number"
},
"result_id":{
"type":"number"
},
"score":{
"type":"number"
}
},
"required":[
"session_id",
"result_id"
]
}
}
},
"paths":{
"/api/auth/login":{
"post":{
"operationId":"AppController_login",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/User"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
}
},
"security":[
{
"basic":[
]
}
]
}
},
"/api/auth/refresh":{
"get":{
"operationId":"AppController_refresh",
"parameters":[
],
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
}
},
"security":[
{
"basic":[
]
}
]
}
},
"/api/users":{
"get":{
"operationId":"UsersController_findAll",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
},
"post":{
"operationId":"UsersController_update",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/User"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/users/{id}":{
"get":{
"operationId":"UsersController_findUsers",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
},
"delete":{
"operationId":"UsersController_delete",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"403":{
"description":"Forbidden."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/preferences":{
"get":{
"operationId":"PreferencesController_findAll",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
},
"post":{
"operationId":"PreferencesController_create",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Pref"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/preferences/{id}":{
"delete":{
"operationId":"PreferencesController_delete",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/session":{
"get":{
"operationId":"SessionController_findAll",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"403":{
"description":"Forbidden."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
},
"post":{
"operationId":"SessionController_create",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Sess"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/session/{id}":{
"get":{
"operationId":"SessionController_getSession",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/session/close":{
"post":{
"operationId":"SessionController_close",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Sess"
}
}
}
}
},
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"403":{
"description":"Forbidden."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/challenge":{
"get":{
"operationId":"ChallengeController_findAll",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
},
"post":{
"operationId":"ChallengeController_create",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Challenge"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/challenge/{id}":{
"delete":{
"operationId":"ChallengeController_delete",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/join/{id}":{
"get":{
"operationId":"JoinController_findJoined",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/join":{
"post":{
"operationId":"JoinController_join",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Join"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/move/all/{id}":{
"get":{
"operationId":"MoveController_getMoves",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"403":{
"description":"Forbidden."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/move/unconfirmed/{id}":{
"get":{
"operationId":"MoveController_getUnconfirmedMove",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"403":{
"description":"Forbidden."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/move/confirmed/{id}":{
"get":{
"operationId":"MoveController_getConfirmedMove",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/move":{
"post":{
"operationId":"MoveController_update",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Move"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/move/confirm":{
"post":{
"operationId":"MoveController_confirm",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Move"
}
}
}
}
},
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"403":{
"description":"Forbidden."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/result/{id}":{
"get":{
"operationId":"ResultController_getMoves",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/result":{
"post":{
"operationId":"ResultController_join",
"parameters":[
],
"requestBody":{
"required":true,
"content":{
"application/json":{
"schema":{
"type":"array",
"items":{
"$ref":"#/components/schemas/Result"
}
}
}
}
},
"responses":{
"201":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"404":{
"description":"Not Found."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
},
"/api/game":{
"get":{
"operationId":"GameController_allGames",
"parameters":[
],
"responses":{
"200":{
"description":"Successfully."
},
"401":{
"description":"Unauthorized."
},
"500":{
"description":"Internal Server error."
}
},
"security":[
{
"bearer":[
]
}
]
}
}
}
}Прежде всего, один из игроков создаёт игровую сессию (POST api/session), формирует вызов противнику (POST api/challenge) и выполняет первый ход (POST api/move). Второй игрок получает вызов (GET api/challenge) и присоединяется к сессии (POST api/join). Далее, каждый из игроков, в цикле, получает ход противника (GET api/move/confirmed/:id, здесь id — идентификатор сессии) и выполняет собственный ход (POST api/move).
Как я уже писал выше, сервер не проверяет корректность выполняемых ходов, но он учитывает время, затраченное на каждый ход. В соответствии с регламентом баёми, каждому из игроков выделяется основное время (games.main_time), по истечении которого даётся дополнительное время (games.additional_time), на выполнение каждого хода. Учитывается период времени от момента получения хода противника (или создания игровой сессии), до момента формирования собственного хода. Это довольно мягкая система контроля времени. Даже исчерпав основное время, игрок не проиграет, если укладывается в дополнительное время, при выполнении каждого хода.
Корректность ходов игроков (в соответствии с правилами игры), а также победителя определяет Арбитр — специальное приложение, подключающееся к серверу с правами администратора. Его задача — получение не подтверждённых ходов игроков, их проверка и формирование подтверждения (setup_str), позволяющего восстановить позицию, на момент завершения хода (это может понадобиться, например, при перезапуске Арбитра, без завершения партии). Также, Арбитр выполняет проверку исчерпания лимита времени и условия завершения игры (взятие хотя бы одного из камней). Дополнительно, эта программа осуществляет визуализацию хода игры (скриншоты в статье сделаны с её помощью).
Разработка ботов, даже для «Атари Го» — дело сложное. Трёх суток выделенных конкурсантам на подготовку, оказалось достаточно только для того, чтобы боты просто заработали. Кроме того, мини-ПК, на которых проводился конкурс, оказались существенно менее производительными, чем рабочие места, на которых выполнялась отладка. Всё это привело к тому, что боты, в ходе турнира, не блистали особым интеллектом, но забавные моменты всё же случались.
Это пример финальной позиции в одной из турнирных партий. Борьба ботов была интересная и ожесточённая. В конце-концов, белые попытались поймать противника в ситё, но не заметили, что следующим ходом чёрные поставили их в положение атари. Бот белых допустил ошибку, пытаясь продолжить «лестницу». Чёрные немедленно этим воспользовались — взяли камень и завершили игру.
Всё это хорошо иллюстрирует характер ошибок, допущенных участниками турнира
Одной из главных сложностей игры Го является то, что оценка материала в ней, практически, не имеет никакого смысла. Важно не то, сколько камней стоит на доске, а то, как они расположены. Существуют позиции требующие немедленной реакции игрока:
Это ситуация "атари" — угроза взятия камня. Если мы играем в «Атари Го», вне зависимости от очерёдности хода, игрок должен ответить в пункт «E6», над чёрным камнем. Белые, при этом, побеждают, а чёрные — защищаются от немедленного поражения, «удлиняя» камень, попавший в ловушку. При обнаружении на доске «атари», игрок должен отвечать немедленно, без каких либо предварительных расчётов. Существуют и более коварные позиции.
Здесь, слева направо, представлены: угроза двойного "атари", угроза "гэта" и угроза "ситё". Во всех трёх случаях, белые должны немедленно реагировать, вполне определённым образом, чтобы избежать поражения. Чёрные, в свою очередь, могут поймать белых в ловушку, на своём ходе. Сказанное не отменяет необходимости просмотра ходов в глубину, но ходы, связанные с обработкой этих ситуаций, должны рассматриваться в первую очередь.
В силу нехватки времени, выделенного на разработку ботов, а также в связи со слабым знанием игры, ни один из участников не обрабатывал подобные ситуации специальным образом. Речь не идёт о сложных формах, боты не всегда корректно определяли даже ситуацию простого «атари».
Это ситуация "атари" — угроза взятия камня. Если мы играем в «Атари Го», вне зависимости от очерёдности хода, игрок должен ответить в пункт «E6», над чёрным камнем. Белые, при этом, побеждают, а чёрные — защищаются от немедленного поражения, «удлиняя» камень, попавший в ловушку. При обнаружении на доске «атари», игрок должен отвечать немедленно, без каких либо предварительных расчётов. Существуют и более коварные позиции.
Здесь, слева направо, представлены: угроза двойного "атари", угроза "гэта" и угроза "ситё". Во всех трёх случаях, белые должны немедленно реагировать, вполне определённым образом, чтобы избежать поражения. Чёрные, в свою очередь, могут поймать белых в ловушку, на своём ходе. Сказанное не отменяет необходимости просмотра ходов в глубину, но ходы, связанные с обработкой этих ситуаций, должны рассматриваться в первую очередь.
Это больше похоже на распознавание образов, чем на задачу оптимизации
В своей реализации бота для «Атари Го», я постарался собрать наиболее важные паттерны, требующие специальной обработки. В человекочитаемом виде, это выглядит следующим образом:
Пункт, в который выполняется рассматриваемый ход, расположен в центре квадрата 5x5. Ходу присваивается некоторая стоимость, используемая для его оценки, а окружение описывается специальными символами (например, «В» означает камень противника с двумя дамэ). Разумеется, описание в такой нотации неудобно использовать в программе. Кроме того, было бы неплохо покрутить эту позицию на 90, 180 и 270 градусов, а если она не симметрична ещё и поотражать относительно осей. Набирать все такие позиции вручную неразумно. Лучше выполнить черновую работу скриптом.
На выходе получаем регулярные выражения, описывающие все интересующие нас позиции. Сама предварительная оценка хода выполняется здесь, в функции heuristic. Дополнительно, выполняется ещё несколько проверок. Например, в «Атари Го», ходы в отдалении от своих или чужих камней не имеют большого смысла, а ходы на первую и вторую линию, как правило, очень опасны.
1000 ; Двойное атари
-----
?????
??B??
?B.??
?????
?????
Пункт, в который выполняется рассматриваемый ход, расположен в центре квадрата 5x5. Ходу присваивается некоторая стоимость, используемая для его оценки, а окружение описывается специальными символами (например, «В» означает камень противника с двумя дамэ). Разумеется, описание в такой нотации неудобно использовать в программе. Кроме того, было бы неплохо покрутить эту позицию на 90, 180 и 270 градусов, а если она не симметрична ещё и поотражать относительно осей. Набирать все такие позиции вручную неразумно. Лучше выполнить черновую работу скриптом.
Dagaz.AI.Patterns.push({re: /.{7}B.{3}B0.{12}/, price: 1000});
Dagaz.AI.Patterns.push({re: /.{11}B0.{4}B.{7}/, price: 1000});
Dagaz.AI.Patterns.push({re: /.{12}0B.{3}B.{7}/, price: 1000});
Dagaz.AI.Patterns.push({re: /.{7}B.{4}0B.{11}/, price: 1000});
На выходе получаем регулярные выражения, описывающие все интересующие нас позиции. Сама предварительная оценка хода выполняется здесь, в функции heuristic. Дополнительно, выполняется ещё несколько проверок. Например, в «Атари Го», ходы в отдалении от своих или чужих камней не имеют большого смысла, а ходы на первую и вторую линию, как правило, очень опасны.
В силу нехватки времени, выделенного на разработку ботов, а также в связи со слабым знанием игры, ни один из участников не обрабатывал подобные ситуации специальным образом. Речь не идёт о сложных формах, боты не всегда корректно определяли даже ситуацию простого «атари».
Тем не менее, отборочный этап турнира, в рамках которого каждый из участников сыграл со всеми претендентами по две партии (белыми и чёрными), прошёл отлично и по количеству побед мы определили двух финалистов.
Далее, игры продолжались до трёх побед, с чередованием очерёдности первого хода. Победив с итоговым счётом 3:1, довольный (и три ночи не спавший) победитель забрал свой приз:
Поаплодируем ему!
vesper-bot
Там, где угроза гэта, ходить белым надо Е7?
Молодцы, вообще!
GlukKazan Автор
G6 — лучший ход противника — твой лучший ход! E7 — могут порезать наверное.
Спасибо.
GlukKazan Автор
По E7 белые выбегают, но теряют камень:
vesper-bot
Что для атари-го проигрыш. Значит, кю :) Спасибо.
GlukKazan Автор
Ну, для белого там возможны и другие ходы, тупо G5 например. Гэта — она больше для чёрных. Но G6, в данном случае, тоже нормальный ответ.