Как сделать игру в крестики-нолики непобедимой с помощью минимаксного алгоритма

Ахмад Абдолсахеб

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

Подобно профессиональному шахматисту, этот алгоритм видит на несколько шагов вперед и ставит себя на место противника. Он продолжает играть вперед, пока не достигнет конечного положения доски (конечное состояние), что приводит к ничьей, победе или поражению. Оказавшись в терминальном состоянии, ИИ присвоит произвольную положительную оценку (+10) за победу, отрицательную оценку (-10) за поражение или нейтральную оценку (0) за ничью.

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

Попробуйте сами в следующей игре, желательно в браузере Chrome.

См. среду Pen minimax 4 от Ахмада Абдолсахеба (@abdolsa) на CodePen.

Алгоритм минимакса лучше всего определить как рекурсивную функцию, которая выполняет следующие действия:

1. вернуть значение, если найдено конечное состояние (+10, 0, -10)
2. пройти через доступные места на доске
3. вызвать минимаксную функцию на каждом доступном месте (рекурсия)
4. оценивать возвращаемые значения из вызовов функций
5. и вернуть лучшее значение

Если вы новичок в концепции рекурсии, я рекомендую посмотреть это видео из Гарвардского университета CS50.

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

Минимакс в коде

В этом уроке вы будете работать с почти конечным состоянием игры, которое показано на рисунке 2 ниже. Поскольку минимакс оценивает каждое состояние игры (сотни тысяч), близкое конечное состояние позволяет вам легче отслеживать рекурсивные вызовы минимакса (9).

Для следующего рисунка предположим, что ИИ — это X, а игрок-человек — это O.

Чтобы упростить работу с доской Ti Tac Toe, вы должны определить ее как массив из 9 элементов. Каждый элемент будет иметь свой индекс в качестве значения. Это пригодится позже. Поскольку приведенная выше доска уже заполнена некоторыми ходами X и Y, давайте определим доску с уже сделанными ходами X и Y (origДоска).

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

Затем объявить айплеер а также huPlayer переменные и установите для них значения «X» и «O» соответственно..

Кроме того, вам нужна функция, которая ищет выигрышные комбинации и возвращает true, если она их находит, и функция, которая перечисляет индексы доступных мест на доске.

/* исходная плата O | | Х --------- Х | | Х --------- | О | O */ var origBoard = ["O", 1 "X", "X", 4 "X", 6 "O", "O"]; // человек var huPlayer = «O»; // ai var aiPlayer = «X»; // возвращает список индексов пустых мест на доске function emptyIndexies(board) < return board.filter(s =>s != "O" && s != "X"); > // выигрышные комбинации с использованием указателей доски function Wining(board, player) < if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3 ] == игрок && доска[4] == игрок && доска[5] == игрок) || (доска[6] == игрок && доска[7] == игрок && доска[8] == игрок) || (доска[0] == игрок && доска[3] == игрок && доска[6] == игрок) || (доска[1] == игрок && доска[4] == игрок && доска[7] == игрок) || (доска[2] == игрок && доска[5] == игрок && доска[8] == игрок) || (доска[0] == игрок && доска[4] == игрок && доска[ 8] == player) || (board[2] == player && board[4] == player && board[6] == player)) < return true; >else < вернуть ложь; >>

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

// основная минимаксная функция function minimax(newBoard, player)< //доступные места var availSpots = emptyIndexies(newBoard);

Кроме того, вам необходимо проверить терминальные состояния и вернуть значение соответственно. Если выиграет O, вы должны вернуть -10, если выиграет X, вы должны вернуть +10. Кроме того, если длина Доступные места array равен нулю, это означает, что места для игры больше нет, игра закончилась ничьей, и вы должны вернуть ноль.

 // проверяет терминальные состояния, такие как выигрыш, проигрыш и ничья // и возвращает соответствующее значение if (winning(newBoard, huPlayer))< return ; > иначе если (победа (newBoard, aiPlayer))< return ; > else if (availSpots.length === 0)< return ; >

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

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

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

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

// массив для сбора всех объектов var moves = []; // прокручиваем доступные точки for (var i = 0; i < availSpots.length; i++)< // создаем объект для каждой и сохраняем индекс этой точки var move = <>; move.index = newBoard[availSpots[i]]; // устанавливаем пустое место для текущего игрока newBoard[availSpots[i]] = player; /*собираем очки, полученные в результате вызова минимакса у оппонента текущего игрока*/ if (player == aiPlayer) < var result = minimax(newBoard, huPlayer); ход.счет = результат.счет; >else < var result = minimax(newBoard, aiPlayer); ход.счет = результат.счет; >// сбросить место на пустое newBoard[availSpots[i]] = move.index; // помещаем объект в массив move.push(move); >

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

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

В конце Minimax возвращает объект, хранящийся в лучшийMove.

// если компьютер перебирает ходы и выбирает ход с наибольшим количеством очков var bestMove; if(player === aiPlayer) < var bestScore = -10000; for(var i = 0; i < moves.length; i++)< if(moves[i].score >bestScore) < bestScore = move[i].score; лучший ход = я; >> >else < // else перебираем ходы и выбираем ход с наименьшим счетом var bestScore = 10000; for(var i = 0; i < moves.length; i++)< if(moves[i].score < bestScore)< bestScore = move[i].score; лучший ход = я; >>> // вернуть выбранный ход (объект) из массива ходов return move[bestMove]; >

Вот и все для минимаксной функции. 🙂 вы можете найти приведенный выше алгоритм на github и codepen. Поиграйте с разными досками и проверьте результаты в консоли.

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

Минимакс в действии

Используя следующий рисунок, давайте проследим вызовы функций алгоритма (ФК) по одному.

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

1.origДоска а также айплеер поступает в алгоритм. Алгоритм составляет список из трех найденных пустых мест, проверяет терминальные состояния и перебирает каждое пустое место, начиная с первого. Затем он изменяет новыйДоска путем размещения айплеер на первом пустом месте. После этого он вызывает себя с помощью новыйДоска и huPlayer и ждет, пока FC вернет значение.

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

3. Наконец, алгоритм составляет список пустых мест и находит выигрыш для игрока-человека после проверки конечных состояний. Поэтому он возвращает объект со свойством score и значением -10.

Поскольку во втором ФК было два пустых места, Минимакс меняет новыйДоска поместив huPlayer на втором пустом месте. Затем он вызывает себя с новой доской и айплеер.

4. Алгоритм составляет список пустых мест и находит выигрыш для игрока-человека после проверки конечных состояний. Поэтому он возвращает объект со свойством score и значением -10.

На втором ФК алгоритм собирает значения, поступающие с нижних уровней (3-й и 4-й ФК). С huPlayerочередь привела к двум значениям, алгоритм выбирает наименьшее из двух значений. Поскольку оба значения похожи, он выбирает первое и возвращает его первому FC.

В этот момент первый FC оценил счет перемещения айплеер на первом пустом месте. Далее он изменяет новыйДоска поместив айплеер на втором пустом месте. Затем он вызывает себя с новыйДоска и huPlayer.

5. На пятом FC алгоритм составляет список пустых мест и находит выигрыш для игрока-человека после проверки конечных состояний. Поэтому он возвращает объект со свойством score и значением +10.

После этого первый ФК движется дальше, меняя новыйДоска и размещение айплеер на третьем пустом месте. Затем он вызывает себя с новой доской и huPlayer.

6. 6-й FC начинает с составления списка из двух найденных пустых мест, проверяет терминальные состояния и перебирает два пустых места, начиная с первого. Затем он изменяет новыйДоска путем размещения huPlayer на первом пустом месте. После этого он вызывает себя с помощью новыйДоска и айплеер и ждет, пока FC вернет счет.

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

8. На 8-м ФК алгоритм составляет пустой список пустых мест и находит выигрыш для айплеер после проверки терминальных состояний. Следовательно, он возвращает объект со свойством score и значением +10 на один уровень выше (7-й FC).

7-й ФК получил только одно положительное значение от нижних уровней (8-й ФК). Потому что ход aiPlayer получено это значение, алгоритм должен вернуть наибольшее значение, полученное от более низких уровней. Поэтому он возвращает свое единственное положительное значение (+10) на один уровень выше (6-й FC).

Поскольку 6-й ФК указал два пустых места, Минимакс меняется новыйДоска поместив huPlayer на втором пустом месте. Затем вызывает себя с новой доской и айплеер.

9. Далее алгоритм составляет список пустых мест и находит выигрыш для айплеер после проверки терминальных состояний. Таким образом, он возвращает объект со свойствами оценки и значением +10.

В этот момент 6-й ФК должен выбрать между результатом (+10), полученным от 7-го ФК (первоначально возвращенным из 8-го ФК), и результатом (-10), возвращенным 9-м ФК. С huPlayerочередь привела к этим двум возвращаемым значениям, алгоритм находит минимальный балл (-10) и возвращает его вверх как объект, содержащий свойства score и index.

Наконец, все три ветви первого FC были оценены (-10, +10, -10). Но поскольку ход aiPlayer привел к этим значениям, алгоритм возвращает объект, содержащий наибольшее количество очков (+10) и его индекс (4).

В приведенном выше сценарии Минимакс заключает, что перемещение X в середину доски приводит к лучшему результату. 🙂

Конец!

К настоящему времени вы должны быть в состоянии понять логику алгоритма Minimax. Используя эту логику, попробуйте реализовать алгоритм Minimax самостоятельно или найдите приведенный выше пример на github или codepen и оптимизируйте его.

Спасибо за чтение! Если вам понравилась эта история, не забудьте поделиться ею в социальных сетях.

Особая благодарность Тубе Йилмаз, Рику МакГэвину и Джавиду Аскерову. за просмотр этой статьи.