[Разработка игр, Kotlin, Научно-популярное, Логические игры] Создаем свой шахматный движок: алгоритм игры компьютера
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Продолжаю рассказывать, как докручиваю свой шахматный движок, и это вторая часть статьи. Она небольшая, здесь я подсвечу настройку ИИ в игре. Сыграем с соперником в лице собственного компьютера.
В первой статье я начал с истории и поделился реализацией ходов. Было много по делу в комментариях, поэтому в планах движок продолжать улучшать. Не претендую на звание гроссмейстера, just for fun. Но, как и для любого программиста, нет предела совершенству :)
Итак, перейдем к реализации алгоритма игры в шахматы для компьютерного соперника. На вход этот алгоритм получает всё множество ходов, которое допускается правилами игры, исходя из текущей ситуации на доске. Компьютеру остается только выбрать самый оптимальный ход.
Безусловно, алгоритм игры можно сделать сколько угодно сложным, а также просчитывать миллионы комбинаций на десятки шагов вперед, однако, я хочу предложить довольно простой алгоритм, который играет на уровне новичка и при этом не совершает откровенно глупых ходов.
Задаем алгоритм игры компьютера
Создадим класс с очень амбициозным именем 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
}
В этом алгоритме ключевое влияние на профит оказывает возможность уничтожения вражеской фигуры и изменение «статуса атакованности» для той фигуры, которая выполняет ход. Стоимость фигуры зависит от типа и также влияет на итоговый профит.
Поскольку король имеет наибольшую стоимость, то появление фигуры вражеского короля в качестве атакуемой практически наверняка делает этот ход заслуживающим внимания для алгоритма.
Все исходники проекта выложил на Github.
Вместо заключения
Можно не один месяц совершенствовать алгоритм игры. Можно строить дерево принятия решений с большим уровнем вложенности. Можно значительно уменьшить расход памяти, используя битовые поля для хранения состояния доски. Однако такой цели передо мной не стояло.
Я находился под впечатлением от сериала «Ход королевы», который мотивировал меня чуть глубже разобраться в шахматных правилах и написать более-менее читаемый код. Поэтому я просто взял и сделал такую реализацию шахматного движка, которая понятна мне и, надеюсь, большинству из вас.
Буду рад любой обратной связи и продолжать улучшать алгоритм, поэтому пишите свои вопросы и идеи в комментариях!
===========
Источник:
habr.com
===========
Похожие новости:
- [Обработка изображений, Научно-популярное, Космонавтика, Мультикоптеры] НАСА показало потоки марсианской пыли во время полета вертолета «Индженьюити»
- [Научно-популярное] По подсчётам палеонтологов на Земле жило больше 2,5 млрд тираннозавров
- [Научно-популярное, Экология] Из-за изменений климата уменьшается доступность качественного кофе
- [Научно-популярное, Старое железо, Космонавтика] РФ начала строительство первого модуля новой орбитальной станции
- [Научно-популярное] Сиджизмондо Малатеста. Психопат который смог
- [Программирование, Проектирование и рефакторинг, Разработка под Android, Kotlin] Пишем под android с Elmslie
- [Научно-популярное] Чума в станице Ветлянской
- [Научно-популярное, Энергия и элементы питания, Физика, Экология] Насколько экологична атомная энергетика? На самом деле так же, как солнечная и ветровая
- [Научно-популярное, Краудсорсинг, Астрономия] Непрофессиональные астрономы открыли новую особенность процесса формирования звёзд
- [Научно-популярное, Космонавтика, Мультикоптеры, Будущее здесь] НАСА опубликовало видео первого полета марсианского вертолета «Индженьюити», сделанное марсоходом
Теги для поиска: #_razrabotka_igr (Разработка игр), #_kotlin, #_nauchnopopuljarnoe (Научно-популярное), #_logicheskie_igry (Логические игры), #_shahmaty (шахматы), #_kotlin, #_shahmatnyj_dvizhok (шахматный движок), #_logicheskie_igry (логические игры), #_blog_kompanii_rajffajzenbank (
Блог компании Райффайзенбанк
), #_razrabotka_igr (
Разработка игр
), #_kotlin, #_nauchnopopuljarnoe (
Научно-популярное
), #_logicheskie_igry (
Логические игры
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 01:56
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Продолжаю рассказывать, как докручиваю свой шахматный движок, и это вторая часть статьи. Она небольшая, здесь я подсвечу настройку ИИ в игре. Сыграем с соперником в лице собственного компьютера.  В первой статье я начал с истории и поделился реализацией ходов. Было много по делу в комментариях, поэтому в планах движок продолжать улучшать. Не претендую на звание гроссмейстера, just for fun. Но, как и для любого программиста, нет предела совершенству :) Итак, перейдем к реализации алгоритма игры в шахматы для компьютерного соперника. На вход этот алгоритм получает всё множество ходов, которое допускается правилами игры, исходя из текущей ситуации на доске. Компьютеру остается только выбрать самый оптимальный ход. Безусловно, алгоритм игры можно сделать сколько угодно сложным, а также просчитывать миллионы комбинаций на десятки шагов вперед, однако, я хочу предложить довольно простой алгоритм, который играет на уровне новичка и при этом не совершает откровенно глупых ходов. Задаем алгоритм игры компьютера Создадим класс с очень амбициозным именем 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 } В этом алгоритме ключевое влияние на профит оказывает возможность уничтожения вражеской фигуры и изменение «статуса атакованности» для той фигуры, которая выполняет ход. Стоимость фигуры зависит от типа и также влияет на итоговый профит.  Поскольку король имеет наибольшую стоимость, то появление фигуры вражеского короля в качестве атакуемой практически наверняка делает этот ход заслуживающим внимания для алгоритма. Все исходники проекта выложил на Github. Вместо заключения Можно не один месяц совершенствовать алгоритм игры. Можно строить дерево принятия решений с большим уровнем вложенности. Можно значительно уменьшить расход памяти, используя битовые поля для хранения состояния доски. Однако такой цели передо мной не стояло. Я находился под впечатлением от сериала «Ход королевы», который мотивировал меня чуть глубже разобраться в шахматных правилах и написать более-менее читаемый код. Поэтому я просто взял и сделал такую реализацию шахматного движка, которая понятна мне и, надеюсь, большинству из вас. Буду рад любой обратной связи и продолжать улучшать алгоритм, поэтому пишите свои вопросы и идеи в комментариях! =========== Источник: habr.com =========== Похожие новости:
Блог компании Райффайзенбанк ), #_razrabotka_igr ( Разработка игр ), #_kotlin, #_nauchnopopuljarnoe ( Научно-популярное ), #_logicheskie_igry ( Логические игры ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 01:56
Часовой пояс: UTC + 5