Всем привет!

Сравнительно недавно я нашел сайт drawbackchess.com, где к правилам обычных шахмат добавляются различные усложнения, как, например, “нельзя ходить королем”, или “нужно иметь четырех коней, чтобы поставить мат”. Я немного поиграл и подумал, что было бы прикольно написать свою версию, но с различными усилениями. Это была изначальная задумка, однако по ходу разработки фокус сместился на разработку как можно более сильного бота с учетом “адекватного” времени на ход, и без использования сторонних ресурсов или API - чистые алгоритмы и вычисления)

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

1. Я лучше всего знаком с ним, и писать на нем для меня проще, чем на других языках.

2. Мне хотелось, чтобы у программы был веб интерфейс, а создавать и поднимать апишку отдельно для этого показалось лишним.

Конечно, это замедлило вычисления, по сравнению с тем же c++, но это было не так важно.

Первый этап. Разработка базовых шахмат, в которые можно играть

Все, что происходит в игре отрисовывается на canvas, клики по клеткам рассчитываются через остаток от деления.

const col = Math.floor(event.offsetX / TILE_SIZE);

const row = Math.floor(event.offsetY / TILE_SIZE);

Изначальный вид доски такой:

const initialBoardUnflipped = [
    ['♜', '♞', '♝', '♛', '♚', '♝', '♞', '♜'],
    ['♟', '♟', '♟', '♟', '♟', '♟', '♟', '♟'],
    [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
    ['♙', '♙', '♙', '♙', '♙', '♙', '♙', '♙'],
    ['♖', '♘', '♗', '♕', '♔', '♗', '♘', '♖'],
];

Ходы фигурами делаются следующим образом:

• Игрок нажимает на фигуру;

• Подсвечиваются возможные ходы;

• Игрок выбирает, куда хочет сходить;

• Изменяется переменная состояния доски, и отрисовываются изменения в позиции.

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

Таким образом, определив фигуру и получив массив доступных ей клеток, мы можем его отобразить и с одной стороны подстветить игроку его возможности, а с другой у нас уже есть массив для проверки корректности его нажатия.

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

Второй этап. Жадный алгоритм

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

Весь вопрос в том, что означает “лучшая позиция”. Для первой итерации, я принял максимальной простую концепцию, что чем больше материала - тем позиция лучше. При этом, по классике, ценности фигур такие:
const pieceValues = {
    '♖': 5, '♘': 3, '♗': 3, '♕': 9, '♙': 1, '♔': 0,
    '♜': 5, '♞': 3, '♝': 3, '♛': 9, '♟': 1, '♚': 0,
}

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

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

Третий этап. Более умный анализ позиции

Очевидно, что просто посчитать фигуры не самый точный показатель того, кто выигрывает, ведь даже с пятью ферзями, тебе могут поставить мат следующим ходом. А значит анализатор надо улучшать.

Интересным и в то же время логичным открытием для меня стали таблицы активности фигур, которые позволяли заставить программу развить фигуры ближе к центру доски, что даст им больше полезных возможностей.

Пример такой таблицы для коня:

'♘': [
    [-0.05, -0.04, -0.03, -0.03, -0.03, -0.03, -0.04, -0.05],
    [-0.04, -0.02, 0, 0, 0, 0, -0.02, -0.04],
    [-0.03, 0, 0.01, 0.015, 0.015, 0.01, 0, -0.03],
    [-0.03, 0.005, 0.015, 0.02, 0.02, 0.015, 0.005, -0.03],
    [-0.03, 0, 0.015, 0.02, 0.02, 0.015, 0, -0.03],
    [-0.03, 0.005, 0.01, 0.015, 0.015, 0.01, 0.005, -0.03],
    [-0.04, -0.02, 0, 0.005, 0.005, 0, -0.02, -0.04],
    [-0.05, -0.04, -0.03, -0.03, -0.03, -0.03, -0.04, -0.05]
],

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

Еще одна полезная деталь, которую некоторые люди могут назвать читерством - дебютная книга. Однако она встроена почти в каждого бота, и пока она создана исключительно вручную, жульничеством это я называть не хочу.

Чертвертый этап. Ускорение анализа

На данном этапе процесс работает, однако слишком медленно, и даже простые размены иногда приводят к плачевным последствиям. Глубину анализа надо увеличивать.

Один из способов это сделать - альфа-бета отсечение (оптимизация алгоритма минимакс):

1. Алгоритм минимакс рекурсивно перебирает все возможные ходы до заданной глубины.

2. На каждом уровне игрок (максимизатор или минимизатор) выбирает лучший для себя результат.

3. В итоге в корне мы получаем оптимальный ход, если считать, что соперник тоже играет идеально.

Проблема при этом заключается в том, что количество возможных позиций растёт экспоненциально (ветвление × глубина). Даже на глубине 5 - 6 это уже тысячи узлов.

Что добавляет альфа-бета:

• α (альфа) - лучшая (максимальная) оценка, которую текущий максимизатор уже может гарантировать себе.

• β (бета) - лучшая (минимальная) оценка, которую текущий минимизатор может навязать сопернику.

Когда при просмотре ветки становится ясно, что:

• максимизатор уже нашёл вариант лучше, чем всё, что минимизатор допустит (α ≥ β),

• или минимизатор уже нашёл худший исход, чем всё, что максимизатор допустит (β ≤ α),

дальнейший перебор не имеет смысла, а значит можно просто отсечь эту ветку и пойти дальше.

Таким образом получилось добиться ускорения до глубины 6 в миттельшпиле, где все еще много фигур и возможных ходов, и до 8 в эндшпиле, где возможности сторон более ограничены.

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

Пятый этап. Похвастаюсь партией бота

Тесты сначала проходили в партиях со мной и моими друзьями/родными, однако достаточно быстро стало интересно, насколько бот может соперничать с ничего не подозревающим противником на lichess.org. Боту был создан отдельный аккаунт (я даже надеялся, что он настолько хорош, чтобы аккаунт забанили, но пока нет).

И вот одна из партий, которая была сыграна против живого человека (с рейтингом 2062!):

https://lichess.org/XFBoKDd2/white - ссылка на партию. Я же расскажу ключевые моменты и свои эмоции.

Началось все с того, что бот, как любой нормальный шахматист (шутка) решил поставить противнику детский мат, от которого противник успешно защитился.

И в целом было видно, что противник играет сильнее и в позиции бота все больше проблем.

Так, например, бот решил, что ладье лучшее место на второй горизонтали, пешки уже были сдвоены, а развития не хватало. 

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

В этот момент я практически потерял надежду, и машинально делал ходы, которые мне говорил бот…

За несколько ходов позиция окончательно испортилась, а пешки почти кончились. И в этот момент бот решает, что он готов атаковать черного короля (основная идея в том, что Rh8 - мат, если как-то убрать оттуда пешки, что бот и делает ходом h5).

Противник же ошибается и тоже жадничает, что позволяет съесть пешку, забирать обратно которую никак нельзя, да и остановить ее от прохода в ферзи тоже будет сложно. Позиция снова равная, а я трясусь от волнения за исход партии!

После нескольких разменов, противник остается с лишним конем и двумя пешками, однако остановить нашу проходную можно лишь отдав ладью, что и происходит в дальнейшем. И тут начинается второй волнительный момент:

Бот снова ошибается и всячески откзывается останавливать пешку черных от прохождения в ферзи.

Казалось бы, партия вновь проиграна, но нет - противник слишком торопится и появляется спасение, которое даже я не увидел во время партии. Зато увидел бот!

Мы отдаем пешку, чтобы ладья успела съесть пешку противника. Еще несколько ходов спустя противник допускает финальную ошибку:

Пытаясь уйти от связки, он выбирает не то поле, и, после хода королем белых, у коня остается два варианта - сбежать и отдать обе оставшиеся пешки, или уйти на а3 и полностью оставить попытки остановить проходную белых.

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

Поиграть с ботом можно по ссылке