Создаем свой шахматный движок: алгоритм игры компьютера

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



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

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

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

Все исходники проекта выложил на Github.

Задаем алгоритм игры компьютера

Создадим класс с очень амбициозным именем Ai и свойством color, который будет содержать цвет игрока-компьютера (чёрный или белый). Класс содержит единственный публичный метод nextTurn(). Этот метод принимает текущее состояние доски в виде фигур и возвращает объект Turn, который он считает наиболее оптимальным.

class Ai(private val color: PieceColor) {
    fun nextTurn(board: Board): Turn { ... }

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

val pieces = HashMap(board.getPieces())
val currentSpacesUnderEnemyAttack = utils.getSpacesUnderAttack(pieces)
    .getValue(color.other())

Теперь запросим у движка все доступные ходы для каждой фигуры текущего игрока-компьютера и для каждого из них вычислим «профит» — числовую оценку успешности хода. Всю необходимую информацию сохраняем во вспомогательный data-класс TurnProfitInfo.

val profits = board.getTurnsForColor(color)
    	.entries.map { (from, turns) ->
        	turns.map { turn ->
            	    TurnProfitInfo(
                        from = from,
                        turn = turn,
                	profit = turn.getProfit(pieces, currentSpacesUnderEnemyAttack)
            	    )
        	}
    	}
    	.flatten()

Сама логика вычисления профита содержится в методе расширения Turn.getProfit(). После вычисления всех профитов найдем максимальный.

val maxOwnProfit = profits.maxOf { it.profit }

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

val turnPriceInfo = profits.filter { it.profit == maxOwnProfit }
    	.shuffled()
    	.first()

	return turnPriceInfo.turn
}

Оценка хода, или какая фигура будет уничтожена

Теперь вернемся к методу getProfit(), который выполнен как расширение класса Turn. На вход он принимает текущее состояние доски и клетки, которые могут быть атакованы противником на следующем ходу.

private fun Turn.getProfit(
	pieces: HashMap<Point, Piece>,
	currentSpacesUnderEnemyAttack: Set<Point>
): Int {
	var profit = 0

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

this.enemyPiece?.let { profit += it.getPrice() }
this.execute(pieces)

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

val newSpacesUnderEnemyAttack = utils.getSpacesUnderAttack(pieces)
    	.getValue(color.other())

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

if (this.from in currentSpacesUnderEnemyAttack && this.to !in newSpacesUnderEnemyAttack) {
    	profit += this.sourcePiece.getPrice()
} else if (this.from !in currentSpacesUnderEnemyAttack && this.to in newSpacesUnderEnemyAttack) {
    	profit -= this.sourcePiece.getPrice()
}

В конце отменяем пробный ход.

	this.revert(pieces)
	return profit
}

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

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

Вместо заключения

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

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

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