21.01.2021 14:21
GlukKazan 5 1000 Источник
Кто мне сказал, — «не получится»?
Если мне хочется, сбудется!

Земфира

Плюнь тому в глаза, кто скажет,
что можно объять необъятное!

Козьма Прутков "Плоды раздумья"

Новогодние праздники вновь навалились внезапно. Такое обилие свободного времени было просто необходимо разбавить какой-то осмысленной деятельностью и я решил приделать к своему серверу бота для игры в Шахматы. Готовых шахматных движков существует множество. Я решил остановиться на Garbochess-JS — простой и понятной реализации, на языке JavaScript, названной в честь знаменитой актрисы Греты Гарбо (вы можете видеть её на фотографии).

Прежде всего, должен сказать пару слов о своём сайте. Поскольку вся идея состоит в том, чтобы люди играли с друг другом по сети, на сайте требуется регистрация. При регистрации не требуется указывать никакой конфиденциальной информации (EMail может быть сохранён в профиле пользователя, по желанию, позже). Ссылка, указанная мной выше и отображающая список всех имеющихся игр, работает без регистрации, но если вы решите пойти дальше, потребуется логин и пароль.


Игра, выбранная на карте, запоминается. Поэтому, после ввода логина и пароля, вы попадаете на вкладку запуска этой игры. Вы можете запустить игру (при помощи кнопки «Launch») или просмотреть сессии, ожидающие подключения второго игрока («Join») и ранее сыгранные игры («View»), при их наличии. Если вы запустите игру, создастся новая сессия, ожидающая подключения второго игрока. Вы попадёте в игру, сможете сделать ход (если выбрали игру первым игроком), но ожидание ответного хода может занять некоторое время (на самом деле, никто не гарантирует, что кто-нибудь вообще подключится к этой сессии). По этой причине, я рекомендую просматривать список сессий, ожидающих подключения, по интересующей вас игре, перед созданием новой сессии при помощи «Launch». Вы избавите себя от лишнего ожидания и, может быть, доставите удовольствие другому человеку.

Другая возможность реализована не для всех игр, но если на форме имеется чекбокс «Play against AI», вы можете ничего не ждать вовсе. Эта опция запускает режим игры с ботом, отвечающим на сделанные ходы практически немедленно. Как правило, речь идёт об очень простых ботах, без каких-то сложных вычислений (хотя победить некоторых из них, всё равно, может быть тяжело). Для Шахмат такое решение не подходит вовсе, но возможность поиграть с ботом всё-таки имеется.

Чего хотелось


Обычный встраиваемый в игру бот не является для Dagaz чем-то новым. Технически, такая игра представляет собой html-сборку, включающую в себя модуль выбора оптимального для этой игры хода, в зависимости от текущей позиции. К имени html-файла добавляется суффикс "-ai", позволяющий серверу загрузить правильную сборку, при выборе режима игры с ботом. Думаю понятно, что разработать бота, подходящего абсолютно для всех существующих на свете игр невозможно, но можно использовать одни и те же боты для различных, но сходных между собой игр.

Например, этот бот используется очень часто 
(function() {

function RandomAi(params) {
  this.params = params;
  if (_.isUndefined(this.params.rand)) {
      this.params.rand = _.random;
  }
}

var findBot = Dagaz.AI.findBot;

Dagaz.AI.findBot = function(type, params, parent) {
  if ((type == "random") || (type == "solver")) {
      return new RandomAi(params);
  } else {
      return findBot(type, params, parent);
  }
}

RandomAi.prototype.setContext = function(ctx, board) {
  ctx.board  = board;
}

RandomAi.prototype.getMove = function(ctx) {
  var moves = Dagaz.AI.generate(ctx, ctx.board);
  if (moves.length == 0) {      
      return { done: true, ai: "nothing" };
  }
  if (moves.length == 1) {
      return { done: true, move: moves[0], ai: "once" };
  }
  var ix = this.params.rand(0, moves.length - 1);
  return {
      done: true,
      move: moves[ix],
      ai:   "random"
  };
}

})();

Это не шутка. Дело в том, что в Dagaz боты выстроены в цепочку и бот рандомного выбора хода используется в тех случаях, когда боты, стоящие выше по иерархии, дать ответ отказались (такое возможно в тех случаях, когда любой ход ведёт к поражению). Разумеется, есть и более сложные боты, но, в целом, все они не очень сильные. Прежде всего, это связано с использованием универсальной (а значит медленной) модели, пригодной для абсолютно любых игр, реализуемых Dagaz.

Второе ограничение связано со временем расчёта хода. Для встроенного бота оно не может превышать 2-3 секунд, поскольку все вычисления производятся непосредственно в браузере пользователя и, в силу однопоточности JavaScript, все другие действия, на это время блокируются. Если задержаться слишком долго, браузер выбросит предупреждение о возможном зацикливании на странице или вообще молча остановит все выполняющиеся скрипты (такое случалось в Safari).

Как бороться с этими двумя бедами — понятно. Поскольку у нас есть сервер, надо разработать клиента, соединяющегося с ним по REST и отвечающего на ходы других пользователей. Иными словами, надо разработать внешнего бота. В качестве языка разработки можно использовать всё тот же JavaScript и запускать бота в Node.js, на одном хосте с сервером (или где-то ещё, это не принципиально).

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


После старта, бот выполняет инициализацию, авторизуясь на сервере, после чего переходит к циклу опроса: ищет на сервере сессии, в которых он должен выполнить очередной ход (TURN), загружает текущую позицию (RECO), передаёт её описание в Garbo Chess, а полученный ответный ход отправляет на сервер (MOVE). Если сессий ожидающих хода нет, бот переходит к проверке наличия ожидающих сессий, созданных ботом (CHCK), если таковых нет и общее количество сессий, в которых участвует бот, меньше заданного, создаёт новую (SESS).

При возникновении ошибок (например, в случае устаревания JWT-токена), бот возвращается к фазе инициализации (INIT) для выполнения повторной авторизации, а если ошибка возникла уже там (при недоступности сервера или чём-то подобном) переходит к фазе STOP и останавливается. Вот так всё это выглядит.

Бот может играть одновременно с несколькими игроками, но в каждый момент времени имеет дело не более чем с одной игрой. Таким образом, если игра ведётся с несколькими людьми, каждому придётся ждать чуть дольше. Кроме того, это не самый эффективный способ использования Garbo Chess. Движок поддерживает режим, при котором анализ игры ведётся непрерывно (запускается в отдельном потоке Web Worker-а), но в этом случае, играть можно только с одним противником.

SAN-ы, FEN-ы, PGN-ы


Прежде всего, с шахматным движком было необходимо договориться. В области компьютерных шахмат существует несколько общепринятых нотаций, но, по большому счёту, важно уметь описывать две вещи: текущую расстановку фигур (кто где стоит) и ход (кто куда ходит и как превращается). В первом случае, фактическим стандартом является FEN и именно в таком виде описание позиции необходимо передавать в Garbo Chess.

С этим была небольшая засада
Разумеется, в Dagaz я тоже описываю позиции. Это функциональность, обойтись без которой очень трудно. Представьте себе, что доиграв до середины партии мы вышли из игры, а потом зашли в неё заново (или просто перегрузили страницу). Было бы глупо прокручивать все ходы с самого начала. DagazServer использует описание позиции, чтобы загрузить правильную расстановку фигур сразу, без утомительной перемотки.

Вернее, он действует ещё хитрее: в случае если ожидается ход противника, загружается последняя расстановка фигур, как и было написано, но если ходить должен игрок, DagazServer загружает предыдущую позицию, возникшую в игре на момент начала последнего хода противника. Следующий ход игра получает обычным образом, уже после загрузки html. Благодаря этому, игрок, загружая игру, всегда видит анимацию последнего хода (или нескольких ходов) противника. А если он не успел рассмотреть этот ход во всех подробностях, всегда можно просто перезагрузить страницу.

Таким образом, модули описания позиции, вроде этого — важная часть проекта. У меня их несколько и я использую тот или иной, в зависимости от особенностей игры. Почему я не использовал FEN? Просто потому, что Dagaz — это не только Шахматы. Приведу простой пример: возможность рокировки, в FEN кодируется как «KQkq», но такое описание слишком завязано на правила традиционных шахмат! Даже в слегка изменённых шахматных вариантах нотацию приходится расширять. В любом случае, мне понадобился FEN и я его сделал.

В ответ на полученное описание, Garbo Chess, проработав некоторое время, возвращает лучший (по его мнению) ход (просто пара позиций вроде «e2e4» и тип фигуры, при наличии превращения). К сожалению, на момент разработки бота, на сервере было сыграно уже довольно много партий в Шахматы и я хранил описание хода немного в другом виде. Я не хотел, чтобы эти партии сломались и добавил дефис, разделяющий позиции (тот факт, что старые партии не использовали FEN-нотацию роли не играл, при проигрывании уже завершённых партий, описания позиций не используются).

С нотациями пришлось ещё повозиться
Одной из особенностей минимаксных алгоритмов является их детерминированность. При одинаковых условиях, будет формироваться один и тот же ход. Это может привести к однообразной игре бота, что не очень приятно. Я вижу два способа борьбы с этим:

  • Случайное ограничение времени на расчёт хода
  • Книга дебютов

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

В силу своей иерархической организации, дебютные таблицы предоставляют некоторую вариативность. При наличии для позиции нескольких «лучших» ходов, мы можем использовать случайный выбор. Я уже использовал дебютные таблицы в Dagaz, в формате SGF, но для сервера потребовалось реорганизовать их иначе. Вместо последовательностей ходов от начала партии, мне были нужны FEN-описания позиций со списками соответствующих им лучших ходов (это, кстати, позволяет описывать дебютные ловушки, путём сохранения лучших ходов только одной стороны). Здесь очень помогла утилита pgn2fen, обнаруженная в блоге Николая Кисленко, работающая как с SAN так и с Long algebraic notation.

Далее, я создал пользователя, для того чтобы бот мог заходить на сервер и прописал его id в качестве «дежурного бота» шахматным играм, для того чтобы frontend автоматически включал бота в созданную игру, при выборе опции «Play against AI». В целом, новая схема данных выглядела так:


Здесь есть ещё один момент, о котором стоит сказать. Я добавил табличку «ai_settings», для хранения настроек бота по отношению к игроку в конкретной игре. Это, своего рода, рейтинг. Если игрок выигрывает, дополнительное время, выделяемое боту на «раздумье», увеличивается. При поражениях оно уменьшается. Таким образом, бот может подстраиваться к силе игрока, с которым он играет.

Что получилось


Это одна из игр бота на сайте. И это не дебютная ловушка (можете проверить это самостоятельно)! При ограничении времени на расчёт хода в 1-2 секунды, бот вполне разумно играет против человека и умеет ставить красивые маты. Возможности бота не ограничиваются классическими шахматами. Подойдёт любая игра, в которой правила перемещения фигур не изменены, например "Шахматы Фишера" или "Шахматы Будённого".

Правда, здесь есть небольшая загвоздка
Шахматный движок должен знать, с какой позиции началась игра. Если первым ходит человек, никаких проблем нет — после выполнения хода, FEN-описание позиции передаётся на сервер, но если бот ходит первым, описать позицию некому, поскольку сервер ничего не знает о конкретике игры. Мне пришлось применить небольшой трюк — загружать FEN-описание начальной позиции даже в том случае, если игра после загрузки ожидает ход бота.

Может возникнуть, своего рода ситуация «гонок», когда бот получает описание сессии раньше, чем интерфейс игры успел загрузиться и сохранить FEN начальной позиции. Понятно, что ни к чему хорошему это привести не может, поэтому я добавил атрибут setup_required, требующий наличия FEN на момент загрузки сессии. Если FEN ещё не сформирован, сервер возвращает ошибку, получив которую, бот просто переходит к повторной авторизации, после чего продолжает выполнение обычным образом.

Также, без каких либо изменений, можно играть в "Шахматы втёмную". Если проявить немного фантазии, можно пойти ещё дальше. Помните, как построены миссии кампании в знаменитой "Battle vs Chess"?

Здесь, в качестве бота, используется обычный шахматный движок Fritz. Если подумать, это становится понятно. Подрыв на мине — просто потеря фигуры. Бот не будет ходить на мины в том случае если будет их учитывать — это просто невыгодно, а суть миссии как раз в том, чтобы заманивать в ловушку его фигуры. Решение простое — информация о минах просто не должна передаваться боту.


Вот что получается: я добавляю в FEN описание мин, но перед передачей в Garbo Chess, просто убираю мины из описания, а после получения ответа возвращаю в позицию те мины, которые не взорвались в результате хода бота. Теперь вы можете заманить бота в ловушку уже на DagazServer.

Что дальше


Есть много шахматных игр: Шатрандж, Макрук — бот может играть в них, надо только добавить в Garbo Chess новые фигуры. Есть игры на малых досках. Наконец, можно переосмыслить Garbo Chess, создав на его основе универсальный движок, подходящий для более широкого класса игр. Возможностей для развития много, было бы желание.