Как сделать шахматную программу

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

Игровая доска

Первое, что мы хотим сделать, это создать доску, на которой будет играться игра. В шахматы играют на доске 8×8, где ось X доски обозначена от AH, а ось Y от 1 до 8.

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

• Пешка = 1 (8 на игрока)
• Рыцарь = 2 (по 2 на игрока)
• Епископ = 3 (по 2 на игрока)
• Ладья = 4 (по 2 на игрока)
• Королева = 5 (по 1 на игрока)
• Король = 6 (по 1 на игрока)

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

• Черный = -1
• Белый = 1
• Пусто = 0

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

Создание web шахмат на HTML, JavaScript и PHP

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

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

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

Шт

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

• обозначение (используется в нашем игровом журнале)
• числовое значение

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

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

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

Слон ходит по диагонали столько клеток, сколько хочет, при условии, что на его пути ничего нет. Если на его пути есть противник, он может захватить этого противника. Когда противник взят, слон перестанет двигаться по этой клетке.

Шахматный движок С++ #0

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

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

Король ходит по прямой и диагональной линии, но может ходить только на одну клетку за раз. Если на его пути есть противник, он может захватить этого противника. Когда противник взят, король перестанет двигаться по этому полю.

Правила

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

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

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

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

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

Правило семидесяти пяти ходов возникает, когда ни один из игроков не взял ни одного игрока на семьдесят пятом ходу. Когда это правило выполняется, это автоматическая ничья. Чтобы построить это правило, мы собираемся проверить последние 150 ходов на «x». Если в журнале не найдено ни одного x, розыгрыш будет запущен автоматически.

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

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

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

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

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

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

Элементы управления

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

Из-за этого нам нужно преобразовать каждый ввод (обозначение на доске) в координату X, Y, чтобы программа могла найти нужные позиции на доске.

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

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

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

Спасибо

И вот, мы успешно создали шахматную игру с использованием Python 3. Используя созданные здесь фигуры, вы теперь можете создать игровую версию игры в шахматы для своей консоли. Надеюсь, вам понравилось читать первую часть этой серии, вы можете проверить полную версию кода на моем GitHub здесь.

использованная литература

• https://www.chessprogramming.org/Extended_Position_Description
• https://en.wikipedia.org/wiki/Алгебраическая_нотация_(шахматы)
• https://en.wikipedia.org/wiki/Пешка_(шахматы)
• https://ru.wikipedia.org/wiki/Knight_(шахматы)
• https://en.wikipedia.org/wiki/Слон_(шахматы)
• https://en.wikipedia.org/wiki/Ладья_(шахматы)
• https://en.wikipedia.org/wiki/Королева_(шахматы)
• https://en.wikipedia.org/wiki/Король_(шахматы)
• https://en.wikipedia.org/wiki/Promotion_(шахматы)
• https://en.wikipedia.org/wiki/Fifty-move_rule
• https://en.wikipedia.org/wiki/Threefold_repetition
• https://en.wikipedia.org/wiki/Draw_(chess)#:~:text=Impossibility%20of%20мат%20%E2%80%93%20if%20a,возможно%20in%20other%20positions%20too .
• https://en.wikipedia.org/wiki/Застой
• https://en.wikipedia.org/wiki/Шах и мат

Источник: design-hero.ru

Написание шахмат за 1 час с помощью СhatGPT

Цель этого эксперимента — проверить способности написания кода chatGPT.

Давайте посмотрим на диалог, который у меня был с chatGPT

Вопрос: Давай вместе напишем программу шахмат на Python

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

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

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

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

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

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

Вопрос: Начни с генерации кода шахматной доски

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

Источник: vc.ru

Разработка шахматной программы

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

Сначала я хотел дать полное описание своей реализации шахматного движка (я назвал его 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))<

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

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

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

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

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

Теперь определимся с тем, как мы будем задавать ходы. Очень удобно сделать так:
long KingMove[9]=;//ходы короля long QueenMove[9]=;//ходы ферзя long RookMove[5]=;//ходы ладьи long BishopMove[5]=;//ходы слона long KnightMove[9]=;//ходы коня

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

long n; CELL cell=Board[coord256]; FIGURE_COLOR color=cell FIGURE_COLOR opponent_color=color^(WHITE|BLACK); FIGURE_TYPE type=cell //————————————————— //ферзь //————————————————— 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 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 вполне читаемо описано всё то, что я использую для оценки позиции. Там представлены массивы очков за нахождение фигуры в данной клетке поля (для поля 8×8 – так просто удобно задавать).

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

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

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

//—————————————————————————————————- //Зобрист-ключи //—————————————————————————————————- //Хэш-ключи [тип фигуры][цвет фигуры][позиция фигуры на доске 16×16] 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 FIGURE_TYPE type=cell 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] ([начальная позиция фигуры на поле 8×8][конечная позиция фигуры на поле 8×8]), обнулить в начале оценки выбора лучшего хода и в дальнейшем просто увеличивать счётчик на 1 в случае хода, улучшающего для нас оценку позиции.

В-пятых, нам нужна сортировка ходов. Самыми первыми должны быть ходы с максимальной выгодой по оценке позиции. Понятно, что ходы взятия приоритетнее обычных “тихих” ходов. Ходы взятия сортируются по принципу MVV/LVA (наиболее ценная жертва – наименее ценный нападающий). При этом стоит продвигать все необычные ходы со взятием (любой ход, который не имеет тип MOVE_TYPE_SIMPLY).

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

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

static const long FutilityMoveCount[9]=;

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

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

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

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

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

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

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

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

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

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

Добавил ссылку на github:
Шахматы

• шахматы
• программирование игр

Источник: habr.com