company_banner

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

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

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



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

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

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


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


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

    Познакомимся c фигурами и запомним их вид в нашем движке.
    Иконка Фигура
    Пешка — pawn
    Конь — knight
    Слон — bishop
    Ладья — rook
    Ферзь — queen
    Король — king
    Обзор фигур, и как они ходят
    Здесь кратко напомню, как ходят фигуры.

    Пешка (англ. «pawn») — самая слабая фигура. Фактически, «пушечное мясо». Двигается только вперед. Атакует только по диагонали вперед на одну клетку.

    То есть в процессе атаки пешка переходит на соседний ряд. При этом прямо атаковать не может, поэтому, встретив у себя на пути любую другую фигуру, оказывается заблокированной. Слабость пешек компенсируется их количеством. Кроме того, это единственная фигура, которая превращается в любую другую (кроме короля), если достигнет противоположного края доски. Чаще всего пешку превращают (это действие promotion) в самую сильную фигуру — в ферзя. У каждого игрока по 8 пешек, они располагаются в ряд перед остальными фигурами.

    Ладья (устар. «тура», англ. «rook») — фигура основательная. Хотя бы своим видом, похожим на башню. Ходит по горизонтали и вертикали в любом направлении на любое количество клеток, пока не встретит на своем пути другую фигуру. У каждого игрока по две ладьи, которые ставятся по углам доски.

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

    Конь (англ. «knight») отличается как самым оригинальным внешним видом, так и самым причудливым ходом, который проще всего представлять буквой «Г». Две (или одна) клетка по горизонтали в любом направлении и одна (или две) клетки по вертикали. Причем неважно, есть на этих клетках другие фигуры или нет. То есть конь — единственная фигура, которая умеет «перепрыгивать» другие. У каждого игрока по два коня, которые ставятся между ладьей и слоном.

    Ферзь, он же королева (англ. «queen») ходит как хочет: и по горизонтали, и по вертикали, и по диагонали в любом направлении на любое количество клеток. По сути ход королевы является комбинацией ходов слона и ладьи. С точки зрения первоначальной расстановки на доске ферзь ставится рядом с королем и всегда на поле своего цвета.

    Король (англ. «king») ходит так же, как и королева, в любом направлении. Но монарху не к лицу суетиться, поэтому он ходит только на 1 клетку в каждую сторону. Также королю доступна рокировка (это действие castling) с ладьей, если между ними нет других фигур. Потеря короля означает проигрыш, поэтому ходы, в результате которых король окажется под ударом вражеской фигуры, запрещены.

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


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

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

    Сперва пишется первая буква, обозначающая фигуру (для пешек букву не используем). Затем поле, с которого фигура совершает ход. Координата по Х обозначается буквами от 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. Поскольку каждый объект неизменяемый и хранит всю необходимую информацию о ходе, мы легко можем сохранять всю историю, не создавая каких-то дополнительных сущностей.

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


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

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

    Похожие публикации

    Комментарии 19

      +7
      Мои выводы основаны на полезной обзорной статье, собственном опыте написания минимакса (не для шахмат) и скромном опыте игры:

      1. У вас не описана рокировка (потому что это движение одновременно короля и ладьи, из кода навскидку непонятно, как это должно работать)
      2. Не хватает «взятия на проходе» для пешки.
      3. Оценка веса позиции не учитывает мобильности фигур — с одной стороны, мало проку от зажатого со всех сторон ферзя (у которого большой вес), с другой стороны, проходная пешка может навести много суеты, когда протопает доску насквозь. Также неучет мобильности может, вероятно, привести к тому, что вашему движку можно будет поставить детский мат. Простейший способ учета мобильности — умножить вес фигуры на число возможных ходов.
      4. Использование в крайней степени неэкономичного способа хранения данных лишит вашу программу преимущества в виде возможности хранить (да и перебирать — перекидывание нескольких бит в регистрах CPU на порядки быстрее ковыряния в мапе) больше состояний в памяти. С другой стороны, это может мотивировать на поиск более оптимальных эвристик для отсечения и более точных оценок для позиций. Может показаться интересной задача сделать код и читаемым и оптимальным по ресурсам одновременно.
        0
        Все ваши замечания справедливы, однако я перед собой и не ставил цели сразу написать полноценный движок.
        1. Да, рокировка не описана, но можно сделать ещё одну реализацию интерфейса Turn, которая будет содержать всю необходимую информацию для рокировки (например, с какой ладьёй меняемся). В моём подходе все варианты рокировки должен возвращать движок, если рокировка возможна (король не двигался, ладья не двигалась, между ними нет других фигур и рокировка не поставит короля под мат).
        2. В силу специфичности данного хода я даже не пытался его реализовать в первой итерации. Довольно легко избежать взятия на проходе, если знаешь про это правило. Однако это будет ещё одна реализация Turn.
        3. Про мобильность интересное замечание. Приму к сведению.
        4. Вы абсолютно правы, но я на это пошёл сознательно. Хотя бы потому что в основном все пишут про битовые поля, а других вариантов особо не предлагают. Хотелось продемонстрировать такую структуру данных, которая была бы максимально простой для понимания.
          +5
          Есть прекрасный сайт www.chessprogramming.org — там очень много интересного на эту тему.
          «Довольно легко избежать взятия на проходе, если знаешь про это правило» — это правило было придумано примерно тогда, когда появилось правило хода пешкой на две клетки вперёд, чтобы нельзя было запирать позицию. Это такое особое правило, и как правило взятие на проходе «допускают» вполне осознанно, и не стараются его избегать.
          «король не двигался, ладья не двигалась, между ними нет других фигур и рокировка не поставит короля под мат»
          — между ними нет других фигур
          — поле, на котором стоит король, поле которое пересекает король и поле, на которое становится король — не атакуется вражескими фигурами.
            –1
            Спасибо за ссылку, почитаю! Что касается рокировки, то даже не все именитые шахматисты соблюдали эти правила. То есть имеется некоторая вариативность в правилах.
              +2
              Если мы говорим про классические шахматы, то вариативности никакой нет и не было. Если говорить о шахматах Фишера, где фигуры в начальной позиции случайным образом меняются местами, то там тоже всё хорошо. После рокировки король и ладья становятся на привычные в классических шахматах места.
              Была одна забавная шахматная задача в 1972 году, которая привела к уточнению формулировки правил рокировки в шахматах, но, разумеется, никто этой неоднозначностью не пользовался.
                0
                Хех, даже не знал про вертикальную рокировку))
                  +1
                  Была еще история о том, как шахматист на турнире сделал длинную рокировку при стоящем на своей исходной позиции ферзевом коне.
                  Когда ошеломленный соперник остановил часы и позвал судью, нарушитель предъявил тому последний «Шахматный кодекс», где черным по белому было написано «Ни одна фигура, кроме коня и ладьи при рокировке, не может перепрыгивать через другие фигуры.».
                  Судья, впрочем, принял решение быть верным духу, а не букве, и новатор был вынужден делать ход королем.
                  (Да, очевидно, в правилах рокировки не было указано требование отсутствия фигур между королем и ладьей.)
              +2
              Поглядите книжку Корнилов «Программирование шахмат и других логических задач». Правда, там не всё есть. Впрочем, кое-что, чего там нет, я в своей статье расписал.
                0
                А чего именно нет в этой книге, если в двух словах?
                  0
                  Например, Late Move Reduction.
              +1
              Для ладьи также будем генерить ходы в диапазоне 8 клеток, но с помощью метода generateDiagonalTurns()

              Для слона все же
                0
                спасибо за внимательность! исправили)
                0
                Вы бы прежде чем писать, все же ознакомились бы с теорией игры. Королева это вам не слон плюс ладья, а 9 пунктов. Король между прочим тоже не бесконечность, а 4 пункта (да да, в эндшпиле он очень даже фигура). Это материальная оценка. Плюс есть оценка позиции. Вам уже написали про мобильность. Если закрытая позиция конь больше слона, в открытой наоборот. И т.д. и т.п.
                Ах да, и еще «Прежде всего я установил несколько бесплатных и условно-бесплатных игр» — не занимайтесь ерундой, идите на chess.com. Там и уроки есть, и про фигуры объясняется ;)
                  0

                  1) chess.com bad, lichess good
                  2) материальная оценка не является объективной истинной. Stockfish использует PawnValueMg = 126, KnightValueMg = 781,
                  BishopValueMg = 825, RookValueMg = 1276,
                  QueenValueMg = 2538 (https://github.com/official-stockfish/Stockfish/blob/master/src/types.h#L182) как базу. И очень успешно использует, не знаю зачем автор условно бесплатные программы.

                    0
                    Возможно в статье это не совсем очевидно отражено, поэтому скажу ещё раз. Сначала мне просто захотелось поиграть в шахматы, а уже затем захотелось самому посмотреть, как можно реализовать простой движок. Если бы я изначально задавался целью написать полноценный движок, то да, я бы глубоко погружался в тему и начинал с изучения существующих аналогов.
                    +1
                    Хорошая статья, понятно что правила в шахматах не так просты, чтобы их с наскоку реализовать. Но её ценность не в полноте, а в том что это хороший старт, например для учебных целей.
                    Лично я её так воспринимаю, а не как исчерпывающий движок.
                      0
                      Да, вы очень точно отразили цель этой статьи. Спасибо!
                      +2
                      Про некоторые правила вы не обмолвились.
                      На счёт рокоровки и взятия на проходе уже писали.
                      Есть ещё про 3 повторяющиеся позиции (плюс там тоже есть свои хитрости с рокировкой) и про 50 ходов без взятия фигур, тогда можно объявить ничью.

                      И ещё:
                      Сперва пишется первая буква, обозначающая фигуру (для пешек букву не используем). Затем поле, с которого фигура совершает ход.

                      Поле НА которое фигура совершает ход, а поле с которого пишется иногда, если есть неопределённость (2 одинаковые фигуры могут сходить на одно поле).

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

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

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

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

                      Самое читаемое