Как реализовать ИИ для шашек / шашек?

Я видел эту игру в шашки и удивлялся, как реализован ИИ.

Как мне реализовать ИИ для шашек (шашки, дама, дама)? Есть ли известные алгоритмы?

Очень благодарен за все. Я очень удивляюсь, увидев это учебное сообщение в блоге Tic Tac Toe .

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

О, я люблю эти игры!

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

1. структура для работы с
2. правила игры
3. условие победы, чтобы работать к

Давайте займемся этим одним куском за раз.

Состав

Поскольку плата представляет собой сетку 8x8 (но может легко масштабироваться), и каждое пространство сетки может существовать только в одном из пяти состояний, давайте определим эти состояния:

[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]

Соответственно ENUM'd:

[0, 1, 2, 3, 4]

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

BOARD_ARRAY = array(8, 8)

Это даст нам массив 8 x 8, в котором мы можем хранить целые числа (наши перечисления из ранее):

(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)

Теперь вы уже можете видеть, как это начинает выглядеть как доска! Я никогда не играл вариант, упомянутый в видео на YouTube, но, похоже, он начинается с 2 рядов белых фигур в один ряд снизу, и 2 ряда черных фигур в один ряд сверху. Что означает, что когда мы запускаем игру, наш массив должен выглядеть так:

(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)

(Помните, что 2 представляет «BLACK_PIECE» и 1 представляет «WHITE_PIECE»)

Так что теперь у компьютера есть структура для работы. Шаг 1 завершен!

правила

Давайте представим, что перед вами установлена ​​настоящая доска, играющая против мастер-игрока. Если бы вы попытались сдвинуть одну из его фигур, вы бы ударили по руке. Если бы вы попытались переместить фигуру так, как не могли, вы бы ударили по руке. Если вы пытались обмануть хорошо ... вы поняли. Но проблема в том, что компьютеры этого не делают. Так что наша задача - обеспечить строгие правила игры внутри.

Нам нужно создать способ проверить, является ли любой данный шаг «законным». Это означает, что сначала нам нужен способ представить «движение». Одним из способов будет использование позиций массива; Например, чтобы переместить фигуру из [0, 0] в [0, 1], мы могли бы создать функцию, которая будет обновлять доску с учетом этого перемещения. Итак, вернемся к расслаблению:

MY_MOVE = array( [0, 0], [0, 1] )

Выше представлен один кусок, перемещающийся на один пробел вниз от верхнего угла доски (при условии, что 0, 0 - верхний левый угол). Вы также можете заметить, что я решил использовать многомерный массив для перемещения. Это потому, что фигуры теоретически могут перемещаться множество раз за один ход (для «прыжка» других фигур). Итак, давайте притворимся, что в 0, 1 была часть противника, что означает, что мы приземлимся в 0, 2

MY_MOVE = array( [0, 0], [0, 2] )

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

MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )

Это дает нам возможность описать любое движение на доске. Ура! Теперь, так как я не до конца понимаю правила конкретной игры (хотя в свое время я играл в канадские шашки), вам нужно будет определить законность хода. Хороший поток до этого момента будет выглядеть так:

FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn

Вышеприведенное предполагает, что вы можете циклически проходить через каждый фрагмент, чтобы найти все его законные ходы, а затем, учитывая совокупность всех законных ходов, каким-то образом выбрать лучший (стратегия здесь). Затем ход применяется к доске или выдает ошибку. Затем следующий игрок берет свой ход. Итак, у нас есть ИИ, который умеет играть! Радость! Двигаемся дальше.

выигрыш

Простые игры замечательны, потому что выигрыш определяется очень простым состоянием. Разве на доске нет белых фигур? Ну, я думаю, ты выиграл! Это реализуется на шаге 2, когда мы выбираем лучший ход, чтобы приблизить нас к условию победы.

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

Вы также можете создавать стратегии, такие как: если есть фигура, которую БУДЕТ перепрыгнуть, сохраните эту фигуру или если фигура может прыгнуть больше, чем одна другая фигура, которая делает этот прыжок.

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

Несколько слов о реализации

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

SQL - замечательный инструмент для хранения всех этих, казалось бы, бесконечных движений. Для тех, кто не имеет опыта работы с SQL, mySQL является бесплатным (довольно простым в использовании) и открытым SQL-сервером. SQL используется для управления базами данных, вроде электронной таблицы на стероидах. Он также способен хранить очень большие объемы данных и работать с ними очень быстро.

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

+Board State+          +All Possible Moves+               +Best Move+
([0,0,1,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([7,6],[7,7])
([0,0,2,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([5,5],[5,4])
([0,0,1,3,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([4,4],[4,3])
etc...

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

Отлично, теперь давайте создадим эту базу данных. Сначала нам нужно рассчитать каждое состояние доски. Что может быть сделано с большой неприятной петлей, если кто-то хочет потратить некоторое время и решить это, это было бы здорово. Посмотрите на массив как одно большое число, затем посчитайте вверх, за исключением базы 5 (0, 1, 2, 3, 4), и при условии, что у каждого игрока может быть только 16 фигур.

К этому моменту мы должны сохранить каждое состояние доски и можем рассчитать все возможные ходы.

После того, как все возможные ходы рассчитаны, наступает самое интересное в поиске пути - наилучшие возможные ходы. Это где мои знания начинают не хватать, и такие вещи, как Minimax или A * начинают вступать в игру. Извините, я не могу помочь вам больше: /

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

Этот подход называется минимаксом (википедия) .

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

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

*однако шашки - это игра с самым высоким коэффициентом ветвления, которая была полностью решена .

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