Как нарисовать шахматную доску golang
Перейти к содержимому

Как нарисовать шахматную доску golang

  • автор:

Алгоритм заполнения шахматной доски

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

Мы выведем в шахматном порядке восемь строк по восемь символов в каждой. Черный цвет у нас будет изображать символ «X», а белый – «O».

Самое первое, что приходит в голову:

  1. создать двумерный массив соответствующего размера;
  2. двойным циклом заполнить одним белым цветом все поля;
  3. затем можно запустить еще дополнительные циклы, которые будут обходить нужные клетки и назначать «черный» цвет.

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

var i, j : Integer; // переменные для циалов masChess : array[1..8, 1..8] of Char; // массив с полем begin // заполняем массив "белым" цветом for i := 1 to 8 do for j := 1 to 8 do masChess[i, j] := 'O'; // закрашиваем "черным" отдельные ячейки i := 1; while (i 

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

Если подойти к задаче более творчески, можно найти более интересное решение. Для этого достаточно заметить закономерности в расположении клеток. Все они идут через одну по вертикали и по горизонтали. То есть, одноцветные не могут быть рядом. Если присмотреться еще внимательнее, можно заметить еще одну очевидную вещь: номер каждой клетки как по вертикали, так и по горизонтали может быть как четным, так и нечетным. Но главное, что номер каждой «белой» клетки будет одновременно четным или нечетным по каждому направлению. «Черные» клетки при этом будут всегда со разными значениями – одно четное, другое нечетное.

неч чет неч Чет
неч 0 X 0 X
чет X 0 X 0
неч 0 X 0 X
чет X 0 X 0

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

var i, j : Integer; // переменные для циалов masChess : array[1..8, 1..8] of Char; // массив с полем begin // заполняем все ячейки for i := 1 to 8 do for j := 1 to 8 do if odd(i) = odd(j) then masChess[i, j] := 'O' else masChess[i, j] := 'X'; // вывод результата for i := 1 to 8 do begin for j := 1 to 8 do Write(masChess[i, j], ' '); Writeln; end; end.

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

Пишем простой шахматный движок на Go

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

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

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

Клетки и фигуры

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

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

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

Таким образом, нам необходим отступ по краям доски в две клетки. Мы могли бы создать доску 12x12, но так как мы представляем ее в виде линейного массива, нам нужна доска 12x10, потому что крайний правый квадрат отступа в предыдущей строке может использоваться в качестве крайнего левого квадрата отступа в следующей строке (× = отступ):

В нашем обозначении “a1” выглядела бы как 9×10+1=91, а “a8” — как “2×10+1"=21.

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

 | | RNBQKBNR | PPPPPPPP | . | . | . | 

Расшифровка сокращений
R — rook — ладья
N — knight — конь
B — bishop — слон
Q — queen — ферзь
K — king — король

Наконец мы можем начать писать код:

type Piece byte func (p Piece) Value() int < . >func (p Piece) Ours() bool < . >func (p Piece) Flip() Piece < . >type Board [120]piece func (b Board) Flip() Board < . >type Square int func (s Square) Flip() Square

Фигуры имеют определенную ценность. Эти значения нужны, чтобы оценивать позиции на доске и понимать, кто выигрывает. Обычно пешка = 100, конь = 280, слон = 320, ладья = 479, ферзь = 929, а король имеет настолько высокую ценность, что она превосходит 8 ферзей (пешки, превратившиеся в ферзей) в совокупности с парами коней, слонов и ладей. Если мы обладаем всем этим богатством, но теряем короля, подсчет все равно покажет, что мы проиграем.

Каждый тип имеет метод переворота (Flip() method), который возвращает то же самое значение после переворота доски перед ходом противника. У фигур он меняет регистр символа фигуры. У клеток он возвращает 119 клеток (считая с другого конца доски). Что касается доски, он копирует все фигуры с клеток в обратном порядке, меняя их регистр.

Генератор ходов

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

Что такое ход? Это комбинация двух клеток — клетка, на которой фигура находилась до совершения хода, и клетка, куда переместились фигура. Позиция — это шахматная доска со счетом, правилами рокировки для каждого игрока и квадратами прохода / блуждающими квадратами. Оба типа также имеют метод переворота (Flip() method) для ходов соперника.

type Move struct < from Square to Square >func (m Move) Flip() Move < . >type Position struct < board Board // текущая доска score int // очки по доске — чем их больше, тем лучше wc [2]bool // возможности рокировки для белых bc [2]bool // возможности рокировки для черных ep Square // битое поле, где пешка может быть взята на проходе kp Square // поле во время рокировки, где король может быть взят >func (p Position) Flip() Position

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

Чтобы сгенерировать все допустимые ходы, нам нужно:

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

Чтобы сделать арифметику направлений более читаемой, мы будем использовать константы направления N/E/S/W:

const N, E, S, W = -10, 1, 10, -1 var directions = map[Piece][]Square< 'P': , 'N': , 'B': , 'R': , 'Q': , 'K': , > func (pos Position) Moves() (moves []Move) < for index, p := range pos.board < if !p.ours() < continue >i := Square(index) for _, d := range directions[p] < for j := i + d; ; j = j + d < q := pos.board[j] if q == ' ' || (q != '.' && q.ours()) < break >if p == 'P' < if (d == N || d == N+N) && q != '.' < break >if d == N+N && (i < A1+N || pos.board[i+N] != '.') < break >> moves = append(moves, Move) if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) < break >> > > return moves >

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

func (pos Position) Move(m Move) (np Position)

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

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

Но как понять, что мы проигрываем?

Оценка доски

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

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

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

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

Чтобы оценить позицию после хода, нам нужно:

  • определить рейтинг текущей позиции,
  • вычесть ценность передвигаемой фигуры,
  • прибавить новую ценность фигуры в соответствии с таблицей PTS,
  • прибавить ценность захваченной фигуры, если такие имеются.
var pst = map[Piece][120]int< 'P': < . >, 'N': < . >, 'B': < . >, 'R': < . >, 'Q': < . >, 'K': < . >, > func (pos Position) value(m Move) int < i, j := m.from, m.to p, q := Piece(pos.board[i]), Piece(pos.board[j]) // Настроить значение передвигаемой фигуры в PST-таблице score := pst[p][j] - pst[p][i] if q != '.' && q != ' ' && !q.ours() < // Настроить значение захваченной фигуры в PST-таблице score += pst[q.Flip()][j.Flip()] >return score >

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

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

Алгоритм поиска

Наиболее распространенный алгоритм поиска в шахматных движках попроще — поиск в глубину, который начинается с корня и спускается до заданного предела глубины, повторяя все возможные ходы перед возвратом. Для каждого хода вычисляется ценность позиции с использованием алгоритма минимакс (minimax) c альфа-бета отсечением (alpha-beta pruning).

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

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

Альфа-бета отсечение (alpha-beta pruning) используется для ускорения алгоритма минимакс путем удаления узлов, которые не стоит рассматривать. В основе альфа-бета отсечения лежит следующая логика: представьте, что вы играете в шахматы и обнаруживаете очень хороший ход А. Вы продолжаете смотреть на доску и находите еще более удачный ход B. Но затем вы анализируете ситуацию глубже и понимаете, что в случае выбора хода B противник объявит вам шах и мат через несколько ходов. Теперь вы отбросите ход B и не будете тратить время на анализ других возможных комбинаций после хода B.

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

В нашем движке мы будем постепенно увеличивать глубину поиска и вызывать алгоритм MDF(f) для поиска нижних и верхних границ оптимального результата. Алгоритм MDF (f) будет использовать итерации альфа-бета отсечения с кэшем транспозиции.

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

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

Что дальше?

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

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

Да, он слабенький, но он играет настоящие шахматные партии!

Надеюсь, вам понравилась эта статья. Вы можете подписаться на меня в Github, Twitter или подписаться через rss.

Международная школа шахмат ChessToGo

Международная школа шахмат ChessToGo занимается профессиональным обучением шахмат детей и взрослых с 2011 года (до 2018 Educhess) .

Шахматы - это спортивная дисциплина, несмотря на то, что сила или рост не имеют значения!

Наша миссия: преподавать шахматы интересно и эффективно! Школа шахмат ChessToGo специализируется на преподавании шахмат детям и взрослым.

Школа шахмат ChessToGo есть в базе шахматных клубов и школ на сайте шахматной федерации Москвы.

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

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

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

Добро пожаловать на наш сайт! Здесь каждый сможет найти для себя или ребенка подходящий вариант, а команда школы шахмат ChessToGO поможет открыть для себя увлекательный мир шахмат!

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

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

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

Дальше следует решить, какого размера будет доска. 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]=;//ходы короля long QueenMove[9]=;//ходы ферзя long RookMove[5]=;//ходы ладьи long BishopMove[5]=;//ходы слона long KnightMove[9]=;//ходы коня 

Здесь в массивах заданы изменения координат в пространстве нашей доски 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]=; 

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

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

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

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

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

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

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

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

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

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *