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

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


Программа для Windows.
Ходить можно как вводом хода в поле (E2-E4), так и мышкой — левая кнопка откуда, правая — куда.

Итак, начнём.
Для начала, стоит поискать специальную литературу о том, как же писать шахматные программы. Я из таковых использовал книжку Корнилова “Программирование шахмат и других логических задач” 2005 года. Одной этой книжки оказалось мало – автор не акцентировал внимание на кое-чём важном, а кое-что просто не рассказал. А это кое-что, между прочим, сильно сокращает дерево перебора. Сразу же предупреждаю, что в моём движке не используется генератор ходов на базе битовых массивов. Этот уровень мне пока недоступен. Впрочем, я особо и не пытался разобраться с ними, предпочитая написать как можно более прозрачный (для меня) механизм работы с ходами фигур, пусть даже в ущерб быстродействию (движок получился не очень быстрый, но вполне работоспособный).

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

#define CELL long 

А сама клетка у меня представлена битами как AHIIIIEWB0MFFF, где:

W-фигура белая
B-фигура чёрная
F-тип фигуры (0-фигуры нет)
M-ходила ли фигура
E-край доски
I-индекс фигуры в массиве для поиска фигур (0-15)
H-была короткая рокировка (флаг ставится только у короля и ладьи)
A-была длинная рокировка (флаг ставится только у короля и ладьи)

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

#define BYTE8(b7,b6,b5,b4,b3,b2,b1,b0) ((CELL)((b7<<7)|(b6<<6)|(b5<<5)|(b4<<4)|(b3<<3)|(b2<<2)|(b1<<1)|(b0<<0)))

//----------------------------------------------------------------------------------------------------
//Типы фигур
//----------------------------------------------------------------------------------------------------
//король
#define FIGURE_TYPE_KING   1
//ферзь
#define FIGURE_TYPE_QUEEN  2
//ладья
#define FIGURE_TYPE_ROOK   3
//слон
#define FIGURE_TYPE_BISHOP 4
//конь
#define FIGURE_TYPE_KNIGHT 5
//пешка
#define FIGURE_TYPE_PAWN   6

//цвета фигур
#define BLACK BYTE8(0,0,1,0,0,0,0,0)
#define WHITE BYTE8(0,1,0,0,0,0,0,0)
//флаг короткой рокировки
#define CASTLING_O_O (BYTE8(0,0,0,1,0,0,0,0)<<8)
//флаг длинной рокировки
#define CASTLING_O_O_O (BYTE8(0,1,0,0,0,0,0,0)<<8)
//сдвиг индекса
#define INDEX_SHIFT 8
//маска белых
#define MASK_WHITE      WHITE
//маска чёрных
#define MASK_BLACK      BLACK
//маска цвета
#define MASK_COLOR      (MASK_WHITE|MASK_BLACK)
//маска типа
#define MASK_TYPE       BYTE8(0,0,0,0,0,1,1,1)
//маска границы
#define MASK_BORDER     BYTE8(1,0,0,0,0,0,0,0)
//маска,ходила ли фигура
#define MASK_IS_MOVED   BYTE8(0,0,0,0,1,0,0,0)
//маска индекса фигуры в массиве
#define MASK_INDEX      ((BYTE8(0,0,0,0,1,1,1,1))<<INDEX_SHIFT)
//маска рокировки
#define MASK_CASTLING (BYTE8(0,0,1,1,0,0,0,0)<<8)
//пустая клетка
#define CELL_EMPTY 0

Дальше следует решить, какого размера будет доска. 8x8 неудобно для анализа выхода за пределы доски. Гораздо удобнее задать массив 16x16 с доской посередине, задав для всех тех клеток, которые не являются доской, флаг границы. В этом случае изменение координаты по X происходит изменением координаты X на нужный шаг, а по Y на шаг*16. Доска задаётся как

CELL Board[256];//шахматная доска с полем посередине (16x16).

Некоторые параметры в дальнейшем будет удобно задавать для поля 8x8, для этой цели стоит завести массив перекодировки координат из поля 16x16 в поле 8x8.

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

#define COORD long
COORD FigureWhiteCoord256[16];//позиции белых фигур на доске (для быстрого доступа к фигурам. 0- фигуры нет)
COORD FigureBlackCoord256[16];//позиции чёрных фигур на доске (для быстрого доступа к фигурам. 0- фигуры нет)
COORD *KingWhitePointer;//указатель на короля в массиве позиций белых
COORD *KingBlackPointer;//указатель на короля в массиве позиций чёрных

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

long KingMove[9]={16,-16,1,-1,17,-17,15,-15,0};//ходы короля
long QueenMove[9]={16,-16,1,-1,17,-17,15,-15,0};//ходы ферзя
long RookMove[5]={16,-16,1,-1,0};//ходы ладьи
long BishopMove[5]={17,-17,15,-15,0};//ходы слона
long KnightMove[9]={32+1,32-1,16+2,16-2,-(32+1),-(32-1),-(16+2),-(16-2),0};//ходы коня

Здесь в массивах заданы изменения координат в пространстве нашей доски 16x16 для одного шага фигуры. Ходы пешки удобно рассматривать отдельно, так как у неё ходы простые, но есть специфическое взятие на проходе.
Как таким массивом пользоваться? Ну вот, например, составление всех ходов ферзя:

 long n; 
 CELL cell=Board[coord256]; 
 FIGURE_COLOR color=cell&MASK_COLOR;
 FIGURE_COLOR opponent_color=color^(WHITE|BLACK);
 FIGURE_TYPE type=cell&MASK_TYPE;
//--------------------------------------------------
 //ферзь
 //--------------------------------------------------
 if (type==FIGURE_TYPE_QUEEN)
 {
  n=0;
  while(QueenMove[n]!=0)
  {
   COORD c256=coord256+QueenMove[n];    
   while(Board[c256]==CELL_EMPTY)//пока можно ходить
   {     
    Move_AddMove(coord256,c256,FIGURE_TYPE_QUEEN,MOVE_TYPE_SIMPLY,sMove_Ptr,move,sMove_FirstPtr,sMoveKitPtr);//клетка пустая, добавляем ход в список
    c256+=QueenMove[n];
   }
   cell=Board[c256];
   if ((cell&MASK_COLOR)==opponent_color)//фигура противника
   {
    Move_AddEatMove(coord256,c256,FIGURE_TYPE_QUEEN,MOVE_TYPE_SIMPLY,sMove_EatPtr,move_eat,sMove_FirstEatPtr,sMoveKitPtr);//добавляем ход взятия в список ходов взятия
   }
   n++;
  }
  return;
 }

Как видите, всё просто. Для хранения ходов я создал структуру

//Типы ходов
enum MOVE_TYPE
{
 MOVE_TYPE_EMPTY=-1,//хода нет
 MOVE_TYPE_SIMPLY=0,//простой ход
 MOVE_TYPE_CASTLING=1,//рокировка
 MOVE_TYPE_WHITE_PASSED_PAWN_EAT=2,//взятие проходной пешки
 MOVE_TYPE_BLACK_PASSED_PAWN_EAT=3,//взятие проходной пешки
 MOVE_TYPE_CONVERSION=4,//превращение пешки
};
 
//ход фигурой
struct SMove
{
 //начальная позиция
 COORD Coord256_1;
 //конечная позиция
 COORD Coord256_2;  
 MOVE_TYPE MoveType;//тип хода
 FIGURE_TYPE NewFigureType;//новый тип фигуры, если она получилась из пешки
 COORD Coord256_PassedPawn;//ход проходной пешкой (если он есть. 0- проходной пешки нет)
 ENGINE_BOOL IsEat;//ход-взятие
 //изменение веса хода (используем для сортировки ходов)
 long Score;
 //указатель на следующий элемент
 SMove *sMove_NextPtr;
};

Хоть массив ходов и задаётся как

SMove sMove_Level[MAX_PLY+5][200];//ходы фигурой
SMove sMove_EatLevel[MAX_PLY+5][200];//ходы фигурой со взятием

, где MAX_PLY – максимальная глубина анализа (а 200 – максимальное число ходов любой фигуры (с запасом)), но указатель на следующий элемент sMove_NextPtr позволяет удобно сортировать ходы (а сортировать их придётся). std::list (или ещё что из stl) я тут не стал использовать – у нас крайне критично быстродействие (да и я не скажу, что мастер в stl и современном Си++, скорее наоборот). Впрочем, вы можете сделать и с помощью stl и сравнить скорость работы программы – я же этого не проверял.

Ну, в целом, с ходами закончили, перейдём к алгоритмам.

Во-первых, нам нужна функция оценки позиции. Тут возможностей просто море. У меня в движке в engine_score.cpp вполне читаемо описано всё то, что я использую для оценки позиции. Там представлены массивы очков за нахождение фигуры в данной клетке поля (для поля 8x8 – так просто удобно задавать).

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

В-третьих, нам нужна хэш-таблица. Дело в том, что в шахматах позиция при переборе часто повторяется – зачем нам заново анализировать то, что уже мы смотрели? Выявить такую позицию и позволяет хэш-таблица. В ней хранятся “уникальные” значения, отличающие одну позицию от другой. Стоятся эти “уникальные” значения просто выполняя операцию xor для ключей элементов, описывающих позицию. Поэтому нам нужны будут массивы уникальных 64 битных чисел (вы можете и любую другую размерность взять, весь вопрос только в том, как часто будут одинаковым значениям позиции соответствовать разные позиции – ошибки хэша). У меня таблица описана так:

//----------------------------------------------------------------------------------------------------
//Зобрист-ключи
//----------------------------------------------------------------------------------------------------
//Хэш-ключи [тип фигуры][цвет фигуры][позиция фигуры на доске 16x16]
unsigned __int64 ZobristKey[FIGURE_TYPE_PAWN+1][2][256]=

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

unsigned __int64 ZobristKeyMove=0x54ca3eb5b5f3cb5b;//ключ смены хода
unsigned __int64 ZobristKeyNullMove=0x08d9bc25bebf91b1;//ключ нулевого хода

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

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

//----------------------------------------------------------------------------------------------------
//получить хэш-ключ позиции
//----------------------------------------------------------------------------------------------------
unsigned __int64 Hash_GetHKey(void)
{
 unsigned __int64 key=0;
 COORD coord256=4*16+4;
 for(long y=0;y<8;y++,coord256+=16)
 {
  COORD coord256_local=coord256;
  for(long x=0;x<8;x++,coord256_local++)
  {
   CELL cell=Board[coord256_local];
   FIGURE_COLOR color=cell&MASK_COLOR;
   FIGURE_TYPE type=cell&MASK_TYPE;
   if (type==0) continue;
   if (color==WHITE) key^=ZobristKey[type][ZOBRIST_WHITE][coord256_local];
   if (color==BLACK) key^=ZobristKey[type][ZOBRIST_BLACK][coord256_local];
  }
 }
 return(key);
}

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

В-четвертых, нам нужна такая штука, как статистика истории. Что это такое? Во время игры можно заметить, что какие-то ходы улучшают оценку позиции. Стоит этот факт отмечать, запоминать и в дальнейшем использовать при сортировке ходов. Как это сделать? Просто завести массив [64][64] ([начальная позиция фигуры на поле 8x8][конечная позиция фигуры на поле 8x8]), обнулить в начале оценки выбора лучшего хода и в дальнейшем просто увеличивать счётчик на 1 в случае хода, улучшающего для нас оценку позиции.

В-пятых, нам нужна сортировка ходов. Самыми первыми должны быть ходы с максимальной выгодой по оценке позиции. Понятно, что ходы взятия приоритетнее обычных “тихих” ходов. Ходы взятия сортируются по принципу MVV/LVA (наиболее ценная жертва – наименее ценный нападающий). При этом стоит продвигать все необычные ходы со взятием (любой ход, который не имеет тип MOVE_TYPE_SIMPLY). Так же вперёд стоит продвинуть и взятие последней ходившей фигуры противника (если взятие будет). Обычные ходы сортируются по возрастанию оценки позиции с учётом эвристики истории. Вся эта сортировка очень важна! Она и сама по себе позволяет сократить обход дерева игры, но более того, на нижних уровнях дерева можно в принципе выбрасывать почти все “тихие” ходы (и если король не под шахом) из рассмотрения без ущерба для качества игры программы! Я увидел такое в коде шахматной программы Ифрит (Ifrit) и, конечно же, применил. Это называется Late Move Reduction, насколько я понимаю.
Для этого используется следующий массив:

static const long FutilityMoveCount[9]={19,19,19,19,19,35,67,131,259};

Здесь числа означают то, сколько “тихих” ходов анализируется в зависимости от уровня дерева (массив задан в обратном порядке). То есть, на последних для анализа 9 уровнях дерева в рассмотрении будет сначала 259 ходов, потом 131, потом 67 и так далее до 19. Это сильно ускоряет работу программы (а также об этом Корнилов вроде как тоже не рассказал в своей книжке). Разумеется, без сортировки ходов такое отсечение не заработает.

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

В-седьмых, нам нужна будет эвристика убийцы. Заключается она в том, чтобы при анализе веток дерева пробовать первым ход, вызвавший отсечение на предыдущей ветке. Такой приём также позволяет сократить перебор. Следует помнить, что такой ход может быть только “тихий”: взятия и необычные ходы использовать для таких проверок нельзя.

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

В-девятых, есть ещё Futility Prunning. Что это такое? На последних двух полуходах дерева оценка позиции не точна и в ряде случаев (если мы не в нулевом ходе, если ход не является шахом, взятием и ход не продление анализа ветки), а также если разность оценки позиции была больше некоторой небольшой величины, то можно просто вернуть эту оценку и не анализировать глубже. Этот приём также ускоряет работу программы.

В-десятых, для сокращения вариантов придуман ещё и Razoring. Это почти то же самое, что и Futility Prunning, но относится к последним четырём полуходам и граница оценки задаётся в некоторую стоимость допустимых потерь фигур.

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

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

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

В архиве лежит сам движок (он поддерживает UCI, так что можете подключить его к Arena), программа под Windows для игры с ним (на скорую руку), шахматы для QNX 6.3. Уровень игры я точно оценить не могу (я не шахматист, как ни странно), но вроде как играет достаточно неплохо.