gambit

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

Scala 3 дает здесь выразительный язык для моделирования доски, ходов и дерева вариантов. Но настоящий вызов не синтаксический, а алгоритмический: безошибочный генератор, честная оценка и поиск, который не считает бесконечно.

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

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

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

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

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

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