Минимаксный алгоритм в теории игр | Набор 3 (Крестики-нолики AI - Поиск оптимального хода)
Предпосылки: минимаксный алгоритм в теории игр, оценочная функция в теории игр.
Давайте объединять то , что мы узнали до сих пор о минимаксе и функции оценки , чтобы написать правильный Tic-Tac-Toe AI (A rtificial I ntelligence) , который играет идеальную игру. Этот ИИ рассмотрит все возможные сценарии и сделает наиболее оптимальный ход.
В поисках лучшего хода:
Мы представим новую функцию под названием findBestMove () . Эта функция оценивает все доступные ходы с помощью minimax (), а затем возвращает лучший ход, который может сделать максимайзер. Псевдокод выглядит следующим образом:
функция findBestMove (доска):
bestMove = NULL
за каждый ход на доске:
если текущий ход лучше, чем bestMove
bestMove = текущий ход
вернуть bestMoveМинимакс:
Чтобы проверить, лучше ли текущий ход лучшего, чем лучший, мы воспользуемся функцией minimax (), которая рассмотрит все возможные варианты развития игры и вернет лучшее значение для этого хода, предполагая, что противник также играет оптимально.
Код для максимизатора и минимизатора в функции minimax () аналогичен findBestMove () , с той лишь разницей, что вместо возврата хода он возвращает значение. Вот псевдокод:
функция minimax (доска, глубина, isMaximizingPlayer):
если текущее состояние платы является конечным:
возвращаемое значение платы
если isMaximizingPlayer:
bestVal = -INFINITY
за каждый ход на доске:
значение = минимакс (доска, глубина + 1, ложь)
bestVal = max (bestVal, значение)
вернуть bestVal
еще :
bestVal = + БЕСКОНЕЧНОСТЬ
за каждый ход на доске:
значение = минимакс (доска, глубина + 1, истина)
bestVal = min (bestVal, значение)
вернуть bestVal
Проверка состояния GameOver:
Чтобы проверить, окончена ли игра и не осталось ходов, мы используем функцию isMovesLeft () . Это простая прямолинейная функция, которая проверяет, доступен ли ход или нет, и возвращает истину или ложь соответственно. Псевдокод выглядит следующим образом:
функция isMovesLeft (доска):
для каждой ячейки на доске:
если текущая ячейка пуста:
вернуть истину
вернуть ложьДелаем наш ИИ умнее:
Последний шаг - сделать наш ИИ немного умнее. Несмотря на то, что следующий ИИ играет идеально, он может выбрать ход, который приведет к более медленной победе или более быстрому поражению. Давайте возьмем пример и объясним это.
Предположим, что есть два возможных способа для X выиграть игру из состояния отданной доски.
- Ход A : X может выиграть за 2 хода
- Ход B : X может выиграть за 4 хода
Наша оценочная функция вернет значение +10 для обоих ходов A и B. Несмотря на то, что ход A лучше, потому что он обеспечивает более быструю победу, наш ИИ может иногда выбирать B. Чтобы решить эту проблему, мы вычитаем значение глубины из оцененной оценки. Это означает, что в случае победы он выберет победу, которая требует наименьшего количества ходов, а в случае проигрыша будет пытаться продлить игру и сыграть как можно больше ходов. Таким образом, новое оцененное значение будет
- Движение A будет иметь значение +10-2 = 8.
- Движение B будет иметь значение +10-4 = 6.
Теперь, поскольку ход A имеет более высокий балл по сравнению с ходом B, наш ИИ выберет ход A, а не ход B. То же самое нужно применить и к минимайзеру. Вместо вычитания глубины мы добавляем значение глубины, которое минимизатор всегда пытается получить, как можно более отрицательное значение. Мы можем вычесть глубину либо внутри функции оценки, либо вне ее. Везде нормально. Я решил сделать это вне функции. Реализация псевдокода выглядит следующим образом.
если максимайзер выиграл:
return WIN_SCORE - глубина
иначе, если минимизатор выиграл:
вернуть LOOSE_SCORE + depthРекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.
Реализация :
Below is implementation of above idea.
C++
// C++ program to find the next optimal move for// a player#include<bits/stdc++.h>using namespace std;struct Move{ int row, col;};char player = "x", opponent = "o";// This function returns true if there are moves// remaining on the board. It returns false if// there are no moves left to play.bool isMovesLeft(char board[3][3]){ for (int i = 0; i<3; i++) for (int j = 0; j<3; j++) if (board[i][j]=="_") return true; return false;}// This is the evaluation function as discussed// in the previous article ( http://goo.gl/sJgv68 )int evaluate(char b[3][3]){ // Checking for Rows for X or O victory. for (int row = 0; row<3; row++) { if (b[row][0]==b[row][1] && b[row][1]==b[row][2]) { if (b[row][0]==player) return +10; else if (b[row][0]==opponent) return -10; } } // Checking for Columns for X or O victory. for (int col = 0; col<3; col++) { if (b[0][col]==b[1][col] && b[1][col]==b[2][col]) { if (b[0][col]==player) return +10; else if (b[0][col]==opponent) return -10; } } // Checking for Diagonals for X or O victory. if (b[0][0]==b[1][1] && b[1][1]==b[2][2]) { if (b[0][0]==player) return +10; else if (b[0][0]==opponent) return -10; } if (b[0][2]==b[1][1] && b[1][1]==b[2][0]) { if (b[0][2]==player) return +10; else if (b[0][2]==opponent) return -10; } // Else if none of them have won then return 0 return 0;}// This is the minimax function. It considers all// the possible ways the game can go and returns// the value of the boardint minimax(char board[3][3], int depth, bool isMax){ int score = evaluate(board); // If Maximizer has won the game return his/her // evaluated score if (score == 10) return score; // If Minimizer has won the game return his/her // evaluated score if (score == -10) return score; // If there are no more moves and no winner then // it is a tie if (isMovesLeft(board)==false) return 0; // If this maximizer"s move if (isMax) { int best = -1000; // Traverse all cells for (int i = 0; i<3; i++) { for (int j = 0; j<3; j++) { // Check if cell is empty if (board[i][j]=="_") { // Make the move board[i][j] = player; // Call minimax recursively and choose // the maximum value best = max( best, minimax(board, depth+1, !isMax) ); // Undo the move board[i][j] = "_"; } } } return best; } // If this minimizer"s move else { int best = 1000; // Traverse all cells for (int i = 0; i<3; i++) { for (int j = 0; j<3; j++) { // Check if cell is empty if (board[i][j]=="_") { // Make the move board[i][j] = opponent; // Call minimax recursively and choose // the minimum value best = min(best, minimax(board, depth+1, !isMax)); // Undo the move board[i][j] = "_"; } } } return best; }}// This will return the best possible move for the playerMove findBestMove(char board[3][3]){ int bestVal = -1000; Move bestMove; bestMove.row = -1; bestMove.col = -1; // Traverse all cells, evaluate minimax function for // all empty cells. And return the cell with optimal // value. for (int i = 0; i<3; i++) { for (int j = 0; j<3; j++) { // Check if cell is empty if (board[i][j]=="_") { // Make the move board[i][j] = player; // compute evaluation function for this // move. int moveVal = minimax(board, 0, false); // Undo the move board[i][j] = "_"; // If the value of the current move is // more than the best value, then update // best/ if (moveVal > bestVal) { bestMove.row = i; bestMove.col = j; bestVal = moveVal; } } } } printf("The value of the best Move is : %d
", bestVal); return bestMove;}// Driver codeint main(){ char board[3][3] = { { "x", "o", "x" }, { "o", "o", "x" }, { "_", "_", "_" } }; Move bestMove = findBestMove(board); printf("The Optimal Move is :
"); printf("ROW: %d COL: %d
", bestMove.row, bestMove.col ); return 0;} |
Java
// Java program to find the// next optimal move for a playerclass GFG{static class Move{ int row, col;};static char player = "x", opponent = "o";// This function returns true if there are moves// remaining on the board. It returns false if// there are no moves left to play.static Boolean isMovesLeft(char board[][]){ for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (board[i][j] == "_") return true; return false;}// This is the evaluation function as discussed// in the previous article ( http://goo.gl/sJgv68 )static int evaluate(char b[][]){ // Checking for Rows for X or O victory. for (int row = 0; row < 3; row++) { if (b[row][0] == b[row][1] && b[row][1] == b[row][2]) { if (b[row][0] == player) return +10; else if (b[row][0] == opponent) return -10; } } // Checking for Columns for X or O victory. for (int col = 0; col < 3; col++) { if (b[0][col] == b[1][col] && b[1][col] == b[2][col]) { if (b[0][col] == player) return +10; else if (b[0][col] == opponent) return -10; } } // Checking for Diagonals for X or O victory. if (b[0][0] == b[1][1] && b[1][1] == b[2][2]) { if (b[0][0] == player) return +10; else if (b[0][0] == opponent) return -10; } if (b[0][2] == b[1][1] && b[1][1] == b[2][0]) { if (b[0][2] == player) return +10; else if (b[0][2] == opponent) return -10; } // Else if none of them have won then return 0 return 0;}// This is the minimax function. It considers all// the possible ways the game can go and returns// the value of the boardstatic int minimax(char board[][], int depth, Boolean isMax){ int score = evaluate(board); // If Maximizer has won the game // return his/her evaluated score if (score == 10) return score; // If Minimizer has won the game // return his/her evaluated score if (score == -10) return score; // If there are no more moves and // no winner then it is a tie
РЕКОМЕНДУЕМЫЕ СТАТЬИ |