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

Всем, кто сейчас смотрит нашумевший сериал «Ход королевы» (The Queen's Gambit), посвящается. Еще больше шахматных терминов в нашем новом переводе.

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

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

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

Фрагменты кода в этом посте упрощены и содержат только самые важные части. Вы можете найти полный код движка по ссылке github.com/zserge/carnatus (carnatus — латинское название морского окуня, вид Sebastes carnatus).

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

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

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

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

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

××××××××××
××××××××××
×........×
×........×
×........×
×........×
×........×
×........×
×........×
×........×
××××××××××
××××××××××

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

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

          |
          |
 RNBQKBNR |
 PPPPPPPP |
 ........ |
 ........ |
 ........ | <- выглядит как настоящая шахматная доска
 ........ |
 ........ |
 ........ |
 pppppppp |
 rnbkqbnr |
          |
          |

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

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 { ... }

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

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

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

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

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

const N, E, S, W = -10, 1, 10, -1

var directions = map[Piece][]Square{
  'P': {N, N + N, N + W, N + E},
  'N': {N + N + E, E + N + E, E + S + E, S + S + E, S + S + W, W + S + W, W + N + W, N + N + W},
  'B': {N + E, S + E, S + W, N + W},
  'R': {N, E, S, W},
  'Q': {N, E, S, W, N + E, S + E, S + W, N + W},
  'K': {N, E, S, W, N + E, S + E, S + W, N + W},
}

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{from: i, to: j})
        if p == 'P' || p == 'N' || p == 'K' || (q != ' ' && q != '.' && !q.ours()) {
          break
        }
      }
    }
  }
  return moves
}

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

func (pos Position) Move(m Move) (np Position) {
  np = pos
  np.board[m.to] = pos.board[m.from]
  np.board[m.from] = '.'
  return np.Flip()
}

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

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

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

Оценка доски

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

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

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

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

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

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

Дополнительно нам нужно отрегулировать в PST-таблице ценность ладьи во время рокировки и ценность пешки во время превращения или взятия на проходе. Но в здесь мы не будем это рассматривать:

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.