Как желание поиграть в шахматы превратилось в написание своего движка. История и реализация

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

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



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

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

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

Обозначения для шахматных фигур

Для начала определимся с терминами и названиями. Не все, что стоит на доске, является фигурой (англ. «piece»). Пешку к фигурам не относят. Но это скорее профессиональный сленг. Мы для простоты все будем называть фигурами.

Познакомимся c фигурами и запомним их вид в нашем движке.

Обозначения ходов

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

Расскажу и покажу наглядно.

Сперва пишется первая буква, обозначающая фигуру (для пешек букву не используем). Затем поле, с которого фигура совершает ход. Координата по Х обозначается буквами от a до h, по Y — цифрами, начиная с 1. Очень похоже на морской бой.

Если в ходе была уничтожена вражеская фигура, то пишем «x», если никто не пострадал, то будет «–». Затем указываем поле, на которое перешла фигура. Ну, и в конце обозначаем особые случаи: для шаха — «+», для мата «++», для пата «=». Для превращения пешки указываем в конце тип новой фигуры.

Техническая реализация

На шахматной доске 8 на 8 клеток, всего 64. Поскольку на каждой клетке может находиться только одна фигура, то во всех современных движках шахматные фигуры хранятся в виде битовых полей в типе Long, который как раз имеет разрядность 64 бита. То есть каждая клетка получает порядковый номер от 0 до 63 и если на данной клетке есть фигура, то соответствующий бит равен 1. Но это делается для оптимизации расходов памяти и просчета большого количества комбинаций. Поскольку в моей реализации ничего такого нет, я сделал упор на читаемость кода и решил хранить фигуры в Map, где ключом является вот такой тип Point.

data class Point(
    val x: Int,
    val y: Int
)

Data class — это неизменяемый тип, автоматически определяющий такие методы, как equals и hashCode, а потому его можно использовать в качестве ключа мапы. Х — расположение фигуры по горизонтали, а Y — по вертикали.

Для самой фигуры определим два параметра: цвет и тип.

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

enum class PieceColor(val text: String) {
    WHITE("white"),
    BLACK("black");

    fun other(): PieceColor =
    when (this) {
        WHITE -> BLACK
        BLACK -> WHITE
    }
}

Тип фигуры также определим в виде enum class с параметрами: название, ценность и краткое обозначение.

enum class PieceType(
	val nameEn: String,
	val nameRu: String,
	val price: Int,
	val notation: String,
	val useForPromotion: Boolean
) {
	PAWN("pawn", "пешка", 100, "", false),
	KNIGHT("knight", "конь", 320, "N", true),
	BISHOP("bishop", "слон", 330, "B", true),
	ROOK("rook", "ладья", 500, "R", true),
	QUEEN("queen", "ферзь", 900, "Q", true),
	KING("king", "король", 20_000, "K", false)
}

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

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

Теперь мы подошли к такому вопросу, как ценность фигур.

Ценность фигур

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

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

Движок

К этому моменту мы можем полностью хранить текущее состояние игры в виде мапы. Для этого будем использовать поле pieces класса BoardImpl, который и будет по сути нашим движком. Затем, совершая каждый ход, мы будем менять нашу мапу pieces. Все совершаемые ходы будут добавляться в историю (поле history).

class BoardImpl : Board {
	private val pieces = mutableMapOf<Point, Piece>()
	private val history = mutableListOf<HistoryItem>()
// ...
}

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

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

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

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

Генерация доступных ходов

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

interface Turn {
	val sourcePiece: Piece
	val from: Point
	val to: Point
	val enemyPiece: Piece?

	fun execute(pieces: MutableMap<Point, Piece>)
	fun revert(pieces: MutableMap<Point, Piece>)
}

Каждый ход содержит информацию о фигуре sourcePiece, которая этот ход совершает, ее исходную позицию from, пункт назначения to и вражескую фигуру enemyPiece (опционально, если она находится в пункте назначения). Также имеется два метода, принимающие текущее состояние доски: execute() для выполнения хода и revert() для его отмены. По сути это паттерн «Команда».

Обычный ход

Этот интерфейс реализует класс NormalTurn. Его метод для выполнения хода execute() выглядит так:

override fun execute(pieces: MutableMap<Point, Piece>) {
    	pieces.remove(from)
    	pieces[to] = sourcePiece
}

Просто извлекаем текущую фигуру по ключу from и помещаем на новую клетку доски по ключу to. При этом, если там была вражеская фигура, она просто перезатрется, т.е. удалится с доски.

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

override fun revert(pieces: MutableMap<Point, Piece>) {
    	pieces.remove(to)
    	pieces[from] = sourcePiece
    	enemyPiece?.let { pieces[to] = it }
}

Ход с превращением

Также сделаем другую реализацию интерфейса Turn. Это будет специальный ход пешки, в результате которого она превращается в другую фигуру. Назовем его PromotionTurn и добавим в него одно дополнительное поле, а именно: в какую фигуру пешка должна превратиться. То есть перед этим ходом у нас имеется пешка, а после — уже другая фигура. Поэтому создаем копию исходной фигуры, поменяв ее тип с помощью метода copy().

override fun execute(pieces: MutableMap<Point, Piece>) {
    	pieces.remove(from)
    	pieces[to] = sourcePiece.copy(type = toType)
}

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

override fun revert(pieces: MutableMap<Point, Piece>) {
    	pieces.remove(to)
    	pieces[from] = sourcePiece
    	enemyPiece?.let { pieces[to] = it }
}

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

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

interface TurnGenerator {
    fun getTurns(
        position: Point, 
        pieces: Map<Point, Piece>
    ): Set<Turn>
}

Он состоит из одного метода getTurns(), который принимает текущее состояние доски и выбранную фигуру, для которой ищем доступные ходы (в виде ее координаты position). Метод возвращает множество доступных для данной фигуры ходов с учетом расположения других фигур на доске.

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

Метод addPointIfPossible() принимает текущую позицию, относительно которой ищем ходы, состояние доски, а также смещение deltaX и deltaY относительно текущей позиции. В методе мы проверяем, не выходит ли новая точка за пределы доски, а также смотрим, нет ли в полученной точке фигуры. Если фигуры нет — ход доступен. Если фигура вражеская — тоже ход доступен. Дополнительно сохраняем информацию о вражеской фигуре. Ну, и если в полученной точке есть другая наша фигура, то ход недоступен.

fun MutableSet<Turn>.addPointIfPossible(
	position: Point,
	pieces: Map<Point, Piece>,
	deltaX: Int,
	deltaY: Int
): Boolean {
	val current = pieces.getValue(position)
	val from = position
	val to = Point(from.x + deltaX, from.y + deltaY)
	val otherPiece = pieces[to]
	return to.takeIf { it.x in 0..7 && it.y in 0..7 }
    	?.let {
        	when {
            	    otherPiece == null -> { // нет фигуры
                	this += NormalTurn(sourcePiece = current, from = from, to = to)
                	true
            	    }
            	    otherPiece.color != current.color -> { // вражеская фигура
                	this += NormalTurn(sourcePiece = current, from = from, to = to, enemyPiece = otherPiece)
                	false
            	    }
            	    else -> { // своя фигура
                	false
            	    }
        	}
    	} ?: false
}

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

fun generateRectangularTurns(position: Point, pieces: Map<Point, Piece>, maxRange: Int): Set<Turn> {
	val spaces = mutableSetOf<Turn>()
	var left = true
	var right = true
	var top = true
	var bottom = true
	for (i in 1..maxRange) {
    	    if (left) {
        	left = spaces.addPointIfPossible(position, pieces, -i, 0)
    	    }
    	    if (right) {
        	right = spaces.addPointIfPossible(position, pieces, i, 0)
    	    }
    	    if (top) {
        	top = spaces.addPointIfPossible(position, pieces, 0, i)
    	    }
    	    if (bottom) {
        	bottom = spaces.addPointIfPossible(position, pieces, 0, -i)
    	    }
	}
	return spaces
}

Эта логика поиска доступных ходов характерна для ладьи.

Далее идет еще один подобный метод generateDiagonalTurns() для поиска ходов по диагоналям также в четырех направлениях с центром в указанной точке. И тут же ограничиваем поиск по maxRange.

fun generateDiagonalTurns(position: Point, pieces: Map<Point, Piece>, maxRange: Int): Set<Turn> {
	val spaces = mutableSetOf<Turn>()
	var leftTop = true
	var rightTop = true
	var leftBottom = true
	var rightBottom = true
	for (i in 1..maxRange) {
    	    if (leftTop) {
        	leftTop = spaces.addPointIfPossible(position, pieces, -i, i)
    	    }
    	    if (rightTop) {
        	rightTop = spaces.addPointIfPossible(position, pieces, i, i)
    	    }
    	    if (leftBottom) {
        	leftBottom = spaces.addPointIfPossible(position, pieces, -i, -i)
    	    }
    	    if (rightBottom) {
        	rightBottom = spaces.addPointIfPossible(position, pieces, i, -i)
    	    }
	}
	return spaces
}

Эта логика поиска подходит для слона.

Генераторы ходов для каждой фигуры

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

Для ладьи вызовем generateRectangularTurns() и укажем максимальный диапазон, в котором следует сгенерить ходы (8 клеток в каждом направлении):

class RookTurnGenerator : TurnGenerator {

	override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =
    	generateRectangularTurns(position, pieces, MAX_RANGE)

	private companion object {
    	    const val MAX_RANGE = 8
	}
}

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

class BishopTurnGenerator : TurnGenerator {

	override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =
    	generateDiagonalTurns(position, pieces, MAX_RANGE)

	private companion object {
    	    const val MAX_RANGE = 8
	}
}

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

class QueenTurnGenerator : TurnGenerator {

override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =
    listOf(
    	generateRectangularTurns(position, pieces, MAX_RANGE),
    	generateDiagonalTurns(position, pieces, MAX_RANGE)
    )
    .flatten()
    .toSet()

    private companion object {
         const val MAX_RANGE = 8
    }
}

Для короля будет все так же, за исключением того, что MAX_RANGE будет равен 1 клетке.

class KingTurnGenerator : TurnGenerator {

override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> =
     listOf(
    	generateRectangularTurns(position, pieces, MAX_RANGE),
    	generateDiagonalTurns(position, pieces, MAX_RANGE)
    )
    .flatten()
    .toSet()

    private companion object {
        const val MAX_RANGE = 1
    }
}

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

class KnightTurnGenerator : TurnGenerator {

    override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> {
    	val spaces = mutableSetOf<Turn>()
    	spaces.addPointsIfCan(position, pieces, 1, 2)
    	spaces.addPointsIfCan(position, pieces, 2, 1)
    	return spaces
    }

    private fun MutableSet<Turn>.addPointsIfCan(position: Point, pieces: Map<Point, Piece>, absX: Int, absY: Int) {
    	this.addPointIfPossible(position, pieces, absX, absY)
    	this.addPointIfPossible(position, pieces, absX, -absY)
    	this.addPointIfPossible(position, pieces, -absX, absY)
    	this.addPointIfPossible(position, pieces, -absX, -absY)
    }

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

Для краткости приведу только основной метод.

class PawnTurnGenerator : TurnGenerator {

    override fun getTurns(position: Point, pieces: Map<Point, Piece>): Set<Turn> {
    	val turns = mutableSetOf<Turn>()
    	val current = pieces.getValue(position)

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

val range = if (position.y == getStartY(current.color)) 2 else 1
val from = position

Метод getDirectionY() в зависимости от цвета определяет направление хода пешки (приращение по вертикали), так как она может двигаться только вперед.

val directionY = getDirectionY(current.color)
for (i in 1..range) {
    val to = Point(from.x, from.y + directionY * i)

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

if (to in pieces) {
    break
} else {
    turns.addTurnWithPromotionCheck(position, current, to, null)
}

Наконец, проверяем клетки атаки впереди слева и впереди справа от пешки.

   	addAttackPoint(position, current, 1, directionY, pieces, turns)
    	addAttackPoint(position, current, -1, directionY, pieces, turns)

    	return turns
        	.filter { it.to.x in 0..7 && it.to.y in 0..7 }
        	.toSet()
	}
// … другие вспомогательные методы
}

Объединяем все вместе

Теперь пришла пора объединить все эти классы внутри нашего движка.

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

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

fun getSpacesUnderAttack(pieces: Map<Point, Piece>): Map<PieceColor, Set<Point>> {
    	val spacesUnderAttack = mutableMapOf<PieceColor, MutableSet<Point>>()
    	pieces.entries.forEach { (position, piece) ->
        	spacesUnderAttack.putIfAbsent(piece.color, mutableSetOf())
        	spacesUnderAttack.getValue(piece.color).addAll(getTurnsForPiece(position, pieces).map { turn -> turn.to })
    	}
    	return spacesUnderAttack
} 

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

fun isKingUnderAttack(pieces: Map<Point, Piece>, kingColor: PieceColor): Boolean {
    	val spacesUnderAttack = getSpacesUnderAttack(pieces).getValue(kingColor.other())
    	val king = pieces.entries
        	.first { it.value.type == PieceType.KING && it.value.color == kingColor }
    	return king.key in spacesUnderAttack
}

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

override fun getTurnsForPiece(position: Point): Set<Turn> {
    	val turns = UTILS.getTurnsForPiece(position, pieces)
    	val result = mutableSetOf<Turn>()
    	val kingColor = pieces.getValue(position).color

    	// нужно исключить каждый ход фигуры, который ставит её короля под удар
    	turns.forEach { turn ->
            turn.execute(pieces)
            if (!UTILS.isKingUnderAttack(pieces, kingColor)) {
            	result += turn
            }
            turn.revert(pieces)
    	}
    	return result
}

Здесь мы получаем все множество допустимых ходов для данной фигуры. Выполняем каждый ход по очереди с помощью execute(), проверяем, не попадает ли король под мат в результате выполнения этого хода, и затем отменяем ход с помощью revert(). И так для каждого из возможных ходов, которые возвращает генератор.

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

Выполнение хода и проверка статуса игры

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

override fun executeTurn(turn: Turn): GameState {
    	val selectedPiece = pieces.getValue(turn.from)
    	turn.execute(pieces)

    	val state = getGameState(pieces, selectedPiece.color.other())

    	saveTurnHistory(selectedPiece, turn, state)

    	return state
}

Проверка состояния в методе getGameState() производится по следующей логике:

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

Дальше — дело за ИИ

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

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