Как компьютер играет в шахматы? Программирование шахматной игры

В настоящее время можно найти немало коммерческих шахматных программ, играющих в силу международного мастера, среди которых особенно отличились Fritz, Junior, Shredder, объединенные эпитетом Deep. Они добились серьезных успехов в соревнованиях с гроссмейстерами. Постоянный интерес читателей нашего журнала к программированию древней игры заставил нас обратиться к Вадиму Чижову, одному из лауреатов конкурса Microsoft Office Extensions за второе полугодие 2002 г. (www.microsoft.ru/offext ), с просьбой рассказать о его разработке - «Шахматы 64» и о принципах, положенных в основу. (От редакции. )

В «Шахматах 64» использованы методы, типичные для большинства шахматных программ. Так, в основе ее алгоритма лежит минимаксный анализ, позволяющий выбирать ход, наилучший для данной позиции. Выполняется он с помощью поиска по дереву позиций. В его корне ищется лучшая последующая позиция за того игрока, которому предстоит сделать ход. На следующем уровне дерева позиций идет поиск лучшего хода за противника и т. д. При этом результаты поиска по дереву связываются с чередованием позиций, имеющих максимальные и минимальные оценки, поэтому такой метод нередко называют минимаксингом. В качестве оценочной используется функция, учитывающая условную «стоимость» шахматных фигур, защищенность королей, степень контроля за центром доски, подвижность фигур, наличие объектов для атаки, структуру пешечного построения и многое другое. Рассмотрим пример минимаксного анализа позиции, приведенный на рис. 1.

Пусть в позиции S ход принадлежит нам. При этом в нашем распоряжении есть несколько возможных ходов, два из которых показаны на рис. 1. В результате одного из ходов возникает позиция А , полностью проанализированная (ее количественная оценка - а ), а в результате другого - позиция Y с оценкой y . Пусть, далее, следующий ход из этой позиции приводит к новой позиции - Z , проанализированной с оценкой z . Покажем, что если z a, то результат позиций, следующих за Y , не изменит оценки S . Допустим, величины s и y - это значения оценок в узлах S и Y соответственно. Очевидно, что y z, так как в позиции Y ход остается за противником, который выберет ход, приводящий к позиции с наименьшей оценкой. Также можно убедиться, что s >a . Следовательно, получим, что y zas, и стало быть, неизвестное значение оценки y в позиции Y не изменит величину s . После анализа позиции Z остальные ветви дерева, выходящие из Y , могут быть отброшены. Обобщение данного случая лежит в основе алгоритма альфа-бета отсечения, более эффективного, чем обычный минимаксный алгоритм.

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

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

Алгоритм выбора хода в «Шахматах 64», или «движок» программы, реализован с помощью средств Visual Cи++ 6.0 в виде динамически подключаемой библиотеки (DLL), а интерфейс - в виде документа Microsoft Word.

На рис. 2 приведено отображение на экране позиции и заставки программы.

Вот пример игры программы «Шахматы 64» против Josh-Age 12 с рейтингом 2100 из Chessmaster 8000 (регламент - 3 мин на партию на ПК, оснащенном процессором Pentium III с тактовой частотой 366 МГц). Текст партии оформляется в английской нотации.

1.e4 e5 2. Bc4 Nc6 3. Nf3 Nf6 4. d3 d5 5. exd5 Nxd5 6. Bd2 f6 7. Bxd5 Qxd5 8. Nc3 Qd8 9. h3 Bf5 10. Nh4 Be6 11. f4 exf4 12. Nf3 Bd6 13. Nb5 O-O 14. Qe2 Re8 15. O-O-O Bxa2 16. Qf2 Be5 17. b3 Qd5 18. Nxe5 Nxe5 19. Nc3 Qxb3 20. Qc5 f3 21. gxf3 Qb6 22. Qxb6 axb6 23. Nb5 Re7 24. Rhe1 Be6 25. Bc3 c6 26. f4 Ng6 27. Rxe6 Rxe6 28. Nc7 Ree8 29. f5 Nf4 30. Nxa8 Ne2+ 31. Kd2 Nxc3 32. Kxc3 Rxa8 33. Kd2 b5 34. Ke3 Re6+ 35. Kf3 Re5 36. Kf4 Re2 37. Kf3 Rxc2 38. Ra1 Rh2 39. Ra8+ Kf7 40. Rb8 Rxh3+ 41. Ke4 Rh4+ 42. Ke3 g5 43. Rxb7+ Ke8 44. Rc7 Rf4 45. Rxc6 Rxf5 46. d4 h5 47. Ke4 Rf4+ 48. Ke3 Rf1 49. Ke2 Rf5 50. Re6+ Kf7 51. Rc6 h4 52. Rc7+ Kg6 53. Rc1 Rd5 54. Ke3 h3 55. Rc8 Kc5 56. Rc2 g4 57. Rh2 Ke6 58. Rh1 b4 59. Rh2 b3 60. Kd3 Rb5 61. Re2+ Kf7 62. Rb2 g3 63. Kc4 h2 64. Kxb5 h1=Q 65. Kb4 g2 66. Rxg2 Qxg2 67. Kxb3 Qd2 68. Kc4 Ke6 69. Kc5 f5 70. Kc4 f4 71. Kd5 f3 72. Kb6 f2 73. d5+ Qxd5 74. Kc7 f1=Q 75. Kb6 Qd6+ 76. Ka5 Qfa6# 0-1 (Белые проиграли.)

«Наиболее ценная жертва - наименее ценный нападающий».

Расшифровка аббревиатуры MVV/LVA

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

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

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

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

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

Для каждого из двух случаев, программируя «компьютерного» игрока, мы можем использовать концептуально различную алгоритмическую начинку, например, для детерминированных игр подходит булева логика, для недетерминированных - вероятностная. Хотя… вероятностная логика ближе к мышлению человека. То есть, взглянув на шахматную доску, опытный игрок способен не только выделить наиболее перспективные ветви развития, но и просчитать ситуацию на несколько ходов вперед. Машина сможет сделать такое же только благодаря переборному принципу поиска решений. Все это мы подробно рассмотрим, а для начала выведем два главных правила, от которых будем отталкиваться:

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

Говоря о вероятностной логике и схожих направлениях, можно отметить, что… да, некоторые из используемых в шахматной сфере приемов и технологических ноу-хау стоят близко к нечеткой логике (привязанной к нечеткой теории множеств), кою любят использовать в системах управления и в том же ИИ для компьютерных игр, но! Шахматные алгоритмы в большинстве случаев бронебойные! Они эмулируют только одну модель поведения - стремление к победе с минимальными потерями и быстрыми расчетами.

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

Общая информация

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

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

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

Полный перебор для современных компьютеров - вещь утопическая, потому как ветвление дерева поиска происходит экспоненциально. В среднем из каждой позиции имеется 40 вариантов перемещений для одного игрока. При глубине 4 получается 40х40х40х40, то есть, 2560000, а при глубине 5 - 40х40х40х40х40 вариантов, что равняется 102400000 (102 млн. 400 тыс.). А дальше рост вычислений продолжает увеличиваться в экспоненциальной прогрессии. Глубина 6 является предельной для реализации полного перебора в рамках современных вычислительных систем, а это подразумевает рассмотрение чуть больше, чем 24 млрд. позиций (чуть больше - это 96 млн). Именно поэтому нужно вводить особые условия и ограничения с выделением наиболее перспективных ветвей.

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

Есть и еще одна проблема - эффект горизонта. Например, вычисления на небольшую глубину (а 4, 5, 6 - это небольшая глубина) могут не показать эффективность длительного размена, не удобны при длительной дистанционной позиционной игре с минимальным количеством взятий и так далее. То есть, программа может вычислить наиболее выгодный ход с взятием, но при этом, к примеру, потеря пешки около короля при жертве более значимой фигуры со стороны соперника может изменить ситуацию в корне, а компьютер ее не увидит. Поэтому необходимо выявлять самые опасные ветви и рассчитывать их на максимально большую глубину.

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

GenerateAllMoves()

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

SortMoves()

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

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

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

MakeMove()

Непосредственно, сама реализация перемещения. Многие программисты смотрят на данный вопрос по-разному. Лично я использую MakeMove() для создания новой позиции на доске после указанного перемещения. То есть до этого у нас расположение фигур было одним, после MakeMove оно изменилось. Данная функция необходима для подготовки к расчетам оценок в рамках Evaluate Position().

UnMakeMove()

Эта функция возвращает исходную позицию, которая была до применения MakeMove().

EvaluatePosition()

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

Например, шкала оценок у нас такая:

Пешка - 100.
Конь - 300.
Слон - 300.
Ладья - 500.
Ферзь - 900.
Король - 10000 (можно и больше, иногда просто ставят бесконечность, иногда 1200, все зависит от дальнейшей настройки, король является самой ценной фигурой).

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

Учет только статической оценки выгоден, но далеко не всегда. Например, можно отметить, что максимальный прирост alpha дают взятия. Но если ориентироваться только на них можно проиграть позиционно. Это раз. Во-вторых, как быть, когда идет длительная дистанционная борьба с минимумом взятий? Материальная оценка тут нам мало, чем может помочь.

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

В качестве наглядного примера или просто ориентира (показать, как это может считаться) я приведу некоторые варианты из возможных, написанное или подобное ему вы можете встретить во многих листингах известных разработок. В данном случае заимствуем из GNU Chess (Free Software Foundation).

Итак, стратегическая оценка белой пешки (напомним, что ее «материальный» вес равен 100):

int WhitePawn {

0, 0, 0, 0, 0, 0, 0, 0,

12,16,24,32,32,24,16,12,

8,12,16,24,24,16,12, 8,

6, 8,12,16,16,12, 8, 6,

6, 8, 2,10,10, 2, 8, 6,

4, 4, 4, 0, 0, 4, 4, 4,

0, 0, 0, 0, 0, 0, 0, 0

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

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

Теперь рассмотрим самого короля, при этом раздельно должно оцениваться два случая - начало игры и конец. Для начала:

int KingStart {

0,0,-4,-10,-10,-4,0,0,

-4,-4,-8,-12,-12,-8,-4,-4,

-16,-20,-24,-24,-24,-24,-20,-12,

-12,-16,-20,-20,-20,-20,-16,-12,

-4,-4,-8,-12,-12,-8,-4,-4,

0,0,-4,-10,-10,-4,0,0,

Из данного массива оценок очевидно, что королю выгоднее всего сделать рокировку и/или оставаться на своей линии.

В конце игры приоритеты меняются, то есть королю выгоднее всего быть в центре.

int KingEnd {

0, 6,12,18,18,12, 6, 0,

6,12,18,24,24,18,12, 6,

12,18,24,30,30,24,18,12,

18,24,30,36,36,30,24,18,

12,18,24,30,30,24,18,12,

6,12,18,24,24,18,12, 6,

0, 6,12,18,18,12, 6, 0

Для ферзя обычно в качестве стратегической оценки считается близость к королю. Есть различные варианты вычисления этой близости, например, алгоритмы выделения «квадрата» короля и т.п. Лично я использую вариант А*-поиска, в котором стоимость достижения цели (а координаты ферзя - это узел, король - цель) считается как сумма столбцов и строк между узлом и целью. То есть никаких теорем Пифагора и выделения квадратов не нужно, к тому же это не занимает много кода. Чем меньше сумма, тем ближе ферзь к королю - начисляем премию.

Основным приоритетом для коня является занятие центра:

int Knight {

0, 4, 8,10,10, 8, 4, 0,

4, 8,16,20,20,16, 8, 4,

8,16,20,24,24,20,16, 8,

10,20,28,32,32,28,20,10,

8,16,20,24,24,20,16, 8,

4, 8,16,20,20,16, 8, 4,

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

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

Итак, приступим…

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

Способ хранения информации о текущей позиции

Во время игры человек видит, что происходит на доске. Аналогично и компьютер должен "видеть" как ему играть дальше.

Правила игры
То есть "объяснить" железному другу как в данной ситуации ходить можно, а как запрещено.

способ выбора хода
Цель - предоставить компьютеру средства для выбора из всевозможных доступных ходов одного.

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

пользовательский интерфейс
Я думаю здесь всё ясно

Ниже вкратце я расскажу вам о каждом из них. Более детально мы рассмотрим их позже.

Представление данных
Каждый из нас по-разному воспринимает входную информацию. На полотне Леонардо Да Винчи один человек может увидеть Джоконду, другой сто долларовую купюру, третий тещу (или зятя). J То же самое и в шахматах. Два соперника во время игры могут видеть совершенно "разные" позиции в один момент времени. Увы, один из них порой бывает неправ, тем более обидно, если им оказываешься ты.

Так чем же компьютер должен отличаться от человека, спросите вы? Ничем. Компьютерные программы, как и люди, не похожи друг на друга: "мыслят" и хранят информацию они по-разному. Но всё же одни из них играют лучше, другие хуже. В чём секрет? По поводу компьютерного "мышления" мы ещё поговорим ниже, а сейчас коснёмся темы хранения данных.

В программировании очень важно правильно выбрать представление данных.

Я думаю, что любой человек в состоянии придумать какой-нибудь способ отображения текущей информации на шахматной доске. Например, можно представить шахматную доску как таблицу (массив) размерами 8х8, где пустой клетке соответствует число - 0, белому королю - 1, и т.д. Увы, у этого способа наряду с преимуществами существует и куча недостатков (порассуждайте на досуге - что это за недостатки J). Но прогресс, как говорится, не стоит на месте, и был придуман (догадайтесь где) более совершенный способ отображения информации, получивший название "битовые поля" (Прим.авт. - cразу же прошу прощения за фривольность перевода; англ. - bitboards). Это 64-битное слово (то есть последовательность из 64 цифр, каждая из которых может иметь значение 0 либо 1), содержащее информацию об одном аспекте шахматной игры. Каждый бит - это одно поле шахматной доски. (Отсчет может вестись по-разному: поле а8 - это первый бит последовательности, h1 - последний, к примеру.)

Они могут содержать:

Поля, атакованные черной пешкой е6 (d5,f5)
00000000
00000000
00000000
00010100
00000000
00000000
00000000
00000000

Для наглядности число разбито по 8 бит, изображающих горизонтали доски.

Поля, занятые белыми пешками (фигурами)

Поля, куда может пойти белый конь и т.д.

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

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

Методы анализа
Итак, компьютер сможет "видеть" доску, делать всевозможные доступные ходы в данной позиции. Осталось дело за малым: научить его выбирать лучший ход и предоставить ему возможность оценивать позицию, пользуясь какими-то критериями, которые мы ему предоставим. Что касается первого, то пока ничего лучше не придумано (по крайней мере, я не слышал об этом, если кто-нибудь знает, то, пожалуйста, напишите), чем лобовое решение: чтобы выбрать лучший из двух ходов, анализируют последствия каждого из них до какого-то момента, скажем анализ на 5-6 ходов вперед, с последующей оценкой получившейся позиции. При этом делается предположение, что соперники стараются выбирать лучшие ответы на каждом ходе. Кстати, последнее предположение лежит в основе алгоритма MiniMax, являющегося ключевым для всех шахматных программ.
Всё бы было хорошо, но… не тут то было. Вам бы пришлось потратить пять, а может и больше, жизней, чтобы сыграть хотя бы одну партию, пусть даже с самым быстрым компьютером. Так что подумайте прежде чем садиться играть партию с компьютером J. Впоследствии я расскажу, что было придумано, чтобы заставить вашего железного друга соображать быстрее.

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

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

Это, несомненно, очень наивное мнение. Новую позицию в шахматах можно получить к десятому ходу. Хоть в шахматах и меньше позиций, чем в , тем не менее, уже после 3 ходов (ход - это один ход белых и чёрных, полуход - ход только одной стороны) дерево ходов состоит из почти 120 миллионов узлов. Более того, размер дерева после 14 полуходов из начальной позиции энтузиасты считают уже больше года, продвинувшись пока что примерно на треть.

Ещё я думал, что шахматные программы, несмотря на давнюю в матче над чемпионом мира, все еще находятся в пределах досягаемости лучших людей. Это тоже не верно.

Альфа-бета

Первая оптимизация - альфа-бета . Идея альфа-беты проста - если у меня уже есть хороший ход, то можно отсечь ходы, которые заведомо хуже. Рассмотрим пример на жуткой картинке слева. Допустим, у игрока А есть 2 возможных хода - a3 и b3. Проанализировав ход a3, программа получила оценку +1.75. Начав оценивать ход b3, программа увидела, что у игрока B есть два хода - a6 и a5. Оценка хода a6 +0.5. Так как игрок B выбирает ход с минимальной оценкой, то он никак не выберет ход с оценкой выше 0.5, а значит оценка хода b3 меньше 0.5, и рассматривать его смысла нет. Таким образом, все оставшееся поддерево хода b3 отсекается.

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

Узлы в альфа-бете делятся на 3 категории:

PV-Nodes - узлы, оценка которых попала в окно (между альфой и бетой). Корень и самый левый узел всегда являются узлами этого типа.
Cut-Nodes (или fail-high nodes ) - узлы в которых произошло отсечение по бете.
All-Nodes (или fail-low nodes ) - узлы, в которых ни один ход не превысил альфу по оценке.

Сортировка ходов

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

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

Для взятий может использоваться, например, простая эвристика MVV-LVA (Most Valuable Victim - Least Valuable Aggressor). Мы сортируем все взятия по убыванию ценности «жертвы», а внутри соритруем еще раз по возрастанию ценности «агрессора». Очевидно, что обычно забрать пешкой ферзя выгоднее, чем наоборот.

Для «тихих» ходов используется метод «убийственных» (killer) ходов - ходов которые вызвали отсечение по бете. Это ходы обычно проверяются сразу после ходов из хеша и взятий.

Хеш таблицы или таблицы перестановок

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

Итерационный поиск

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

Эти проблемы решает итерационный поиск. Для начала мы проводим анализ на глубину 1, потом на глубину 2 и т.д. Таким образом, каждый раз мы спускаемся чуть глубже, чем в прошлый раз, пока анализ не будет остановлен. Чтобы уменьшить размеры дерева поиска, результаты прошлой итерации обычно используются, чтобы отсекать заведомо плохие ходы на текущей. Этот метод называется «окно стремлений» (aspiration window) и используется повсеместно.

Поиск спокойствия(Quiescence Search)

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

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

Выборочный поиск

Идея выборочного поиска в том, чтобы дольше рассматривать «интересные» ходы и меньше - неинтересные. Для этого используются продления, которые увеличивают глубину поиска в определённых позициях, и сокращения, уменьшающие глубину поиска.

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

Отсечения и сокращения

С отсечениями и сокращениями всё гораздо интереснее. Именно они позволяют значительно сократить размер дерева.

Вкратце об отсечениях:

Дельта-отсечение - проверяем, может ли взятие улучшить текущую альфу. Для этого к оценке узла добавим ценность взятой фигуры и еще немного и посмотрим, больше ли получившееся значение, чем альфа. Например, если у белых не хватает ладьи, то взятие пешки вряд ли им поможет, с другой стороны, взятие слона может помочь.
Отсечение бесполезности - то же самое, только для не-взятий. Если текущая оценка настолько меньше альфы, что никакое позиционное преимущество не сможет это скомпенсировать, то такие узлы отсекаются. Обычно применяется на низкой глубине (1-2).
Историческое отсечение - для каждого хода мы храним, сколько раз данный ход спровоцировал отсечение, независимо от позиции. Ходы с высоким значением этой эвристики отсекаются. Обычно применяется начиная с определенной глубины и не применятся на PV узлы. Иногда объединяется с предыдущим методом.
Multi-Cut - если из первых M(например, 6) узлов хотя бы C(например, 3) являются Cut-node, то отсекаем все узлы.
Отсечение по null-ходу - если после null-хода (простая передача очереди хода сопернику) оценка все равно выше беты, то отсекаем узел. Проще говоря, если позиция настолько плоха, что даже сделав два хода подряд, игрок все равно не может ее улучшить, то нет смысла рассматривать эту позицию.

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

За счёт качественной сортировки ходов и отсечений, современные движки умудряются достигать коэффициента ветвления ниже 2 . За счёт этого, к сожалению, они иногда не замечают нестандартные жертвы и комбинации.

NegaScout и PVS

Две очень похожие техники, которые используют тот факт, что после того как мы нашли PV-node (приусловии что наши ходы достаточно хорошо отсортированы), она скорее всего не изменится, то есть все оставшиеся узлы вернут оценку ниже, чем альфа. Поэтому вместо поиска с окном от альфа до бета, мы ищем с окном от альфа до альфа+1, что позволяет ускорить поиск. Конечно, если в каком-то узле мы получаем отсечение по бете, то его надо ценить заново, уже нормальным поиском.

Разница между двумя методами лишь в формулировке - они были разработаны примерно в одно время, но независимо, и поэтому известны под разными названиями.

Параллельный поиск

Распараллеливание альфа-беты - отдельная большая тема. Я вкратце пройдусь по ней, а кому интересно - почитайте Parallel Alpha-Beta Search on Shared Memory Multiprocessors . Сложность в том, что при параллельном поиске многие Cut-nodes анализируются до того, как другой поток найдет опровержение (установит бету), в то время как в последовательном поиске, при хорошей сортировке многие из этих узлов отсеклись бы.

Lazy SMP

Очень простой алгоритм. Мы просто запускаем все потоки одновременно с одним и тем же поиском. Коммуникация потоков происходит за счёт хеш-таблицы. Lazy SMP оказался неожиданно эффективным, настолько, что топовый Stockfish перешел на него с YBW. Правда, некоторые считают , что улучшение произошло из-за плохой реализации YBWC и слишком агрессивных отсечений, а не из-за преимущества Lazy SMP.

Young Brothers Wait Concept (YBWC)

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

Dynamic Tree Splitting (DTS)

Быстрый и сложный алгоритм. Немного о скорости: скорость поиска измеряется через ttd (time to depth), то есть время, за которое поиск достигает определенной глубины. Этот показатель обычно можно использовать для сравнения работы разных версий движка или движка, запущенного на разном количестве ядер (хотя Komodo, например, увеличивает ширину дерева при большем количестве доступных ядер). Кроме того, во время работы движок отображает скорость поиска в nps (nodes per second). Это метрика гораздо более популярная, но она не позволяет сравнивать даже движок сам с собой. Lazy SMP, в котором нет никакой синхронизации, практически линейно увеличивает nps, но из-за большого объема лишней работы, его ttd не так впечатляющ. В то время как для DTS nps и ttd изменяются практически одинаково .

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

Оценка

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

Компьютер оценивает позицию в пешках: +1.0 означает, что у белых преимущество равноценное 1 пешке, -0.5 означает, что у черных преимущество в полпешки. Мат оценивается в 300 пешек, а позиция в которой известно количество ходов до мата x - в (300-0.01x) пешек. +299.85 значит, что белые ставят мат в 15 ходов. При этом сама программа обычно оперирует целыми оценками в сантипешках (1/100 пешки).

Какие параметры компьютер учитывает при оценке позиции?

Материал и мобильность

Самое простое. Ферзь 9-12 пешек, ладья 5-6, конь и слон 2.5-4 и пешка, соответственно, одна пешка. В общем, материал - это достойная эвристика оценки позиции и любое позиционное преимущество обычно трансформируется в конце концов в материальное.

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

Таблицы позиций фигур

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

Пешечная структура

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

Этапы игры

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

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

Прочее

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

Точная оценка или быстрый поиск?

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

Дебютные книги и эндшпильные таблицы

Дебютные книги

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

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

Эндшпильные таблицы

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

Генерация таблиц

Сгенерируем все возможные (с учетом симметрии) позиции с определенным набором фигур. Среди них найдем и обозначим все позиции, где стоит мат. Следующим проходом обозначим все позиции, в которых можно попасть в позиции с матом - в этих позициях ставится мат в 1 ход. Таким образом находим все позиции с матом 2,3,4, ходов. Во всех неотмеченных позициях - ничья.

Таблицы Налимова

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

Таблицы Ломоносова

В 2012 году на суперкомпьютере Ломоносов в МГУ были посчитаны все семифигурные окончания (кроме 6 против 1). Эти базы доступны только за деньги и это единственные существующие полные семифигурные эндшпильные таблицы.

Syzygy

Стандарт де-факто. Эти базы гораздо компактнее баз Налимова. Они состоят из двух частей - WDL (Win Draw Lose) и DTZ (Distance to zeroing). WDL базы предназначены для использования во время поиска. Как только узел дерева найден в таблице, у нас есть точный результат игры в этой позиции. DTZ предназначены для использования в корне - они хранят количество ходов до обнуляющего счётчик ходов хода (хода пешкой или взятия). таким образом для анализа достаточно WDL баз, а DTZ базы могут пригодиться при анализе эндшпилей. Размер Syzygy гораздо меньше - 68 гигабайт для шестифигурных WDL и 83 для DTZ. Семифигурных баз не существует, так как их генерация требует примерно терабайт оперативной памяти.

Использование

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

Жираф или нейронные сети играют в шахматы

Некоторые из вас возможно слышали о шахматном движке на нейронных сетях, достигшем уровня IM (что, как мы поняли во введении, не так уж и круто для движка). Его написал и выложил на Bitbucket Matthew Lai, который, к сожалению прекратил работу над ним из-за того, что начал работать в Google DeepMind .

Тюнинг параметров

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

Stockfish

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

Их решение типично для опенсорса - добровольцы предоставляют свои мощности чтобы прогнать на них сотни тысяч игр.

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

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

перемещение;
оценка шахматной доски;
минимакс;
альфа-бета-отсечение.

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

Готовый алгоритм можно найти на GitHub .

Шаг 1. Генерация ходов и визуализация шахматной доски

Мы будем использовать библиотеки chess.js для генерации ходов и chessboard.js для визуализации доски. Библиотека для генерации ходов реализует все правила шахмат. Исходя из этого, мы можем рассчитать все ходы для данного состояния доски.

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

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

Var calculateBestMove = function(game) { //Генерация всех ходов для данной позиции var newGameMoves = game.ugly_moves(); return newGameMoves; };

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

Черные играют случайными ходами

JSFiddle .

Шаг 2. Оценка доски

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

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

Var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null; //Используйте любое отрицательное число var bestValue = -9999; for (var i = 0; i < newGameMoves.length; i++) { var newGameMove = newGameMoves[i]; game.ugly_move(newGameMove); //Возьмите отрицательное число, поскольку ИИ играет черными var boardValue = -evaluateBoard(game.board()) game.undo(); if (boardValue > bestValue) { bestValue = boardValue; bestMove = newGameMove } } return bestMove; };

Единственным ощутимым улучшением является то, что теперь наш алгоритм съест фигуру, если это возможно:

Черные играют с помощью простой функции оценки

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle .

Шаг 3. Дерево поиска и минимакс

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

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

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

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

Визуализация минимакса в искусственном положении. Лучший ход для белых - b2-c3, так мы можем гарантировать, что доберемся до позиции, где оценка равна -50

Var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };

С минимаксом наш алгоритм начинает понимать основную тактику шахмат:

Минимакс с уровнем глубины 2

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle .

Эффективность минимакса в значительной степени зависит от достижимой глубины поиска. Именно это мы улучшим на следующем шаге.

Шаг 4. Альфа-бета-отсечение

Позиции, которые нам не нужны, если используется альфа-бета-отсечение. Дерево посещается в описанном порядке.

С альфа-бета-отсечением мы получаем значительное улучшение минимакса, как показано в следующем примере:

Количество позиций, которые нужно оценить в случае поиска с глубиной 4 и начальной позицией, изображённой на картинке.

Посмотреть, что получилось на данном этапе, вы можете на JSFiddle .

Шаг 5. Улучшенная функция оценки

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

Мы будем использовать слегка скорректированную версию квадратных таблиц, первоначально описанных в