Luché durante horas desplazándome a través de tutoriales, viendo videos y golpeándome la cabeza contra el escritorio tratando de construir un juego de Tic Tac Toe inmejorable con una Inteligencia Artificial confiable. Entonces, si está pasando por un viaje similar, me gustaría presentarle el algoritmo Minimax.
Como un jugador de ajedrez profesional, este algoritmo ve algunos pasos adelante y se pone en la piel de su oponente. Sigue avanzando hasta que alcanza una disposición terminal del tablero ( estado terminal ) que resulta en un empate, una victoria o una pérdida. Una vez en un estado terminal, la IA asignará una puntuación positiva arbitraria (+10) para una victoria, una puntuación negativa (-10) para una derrota o una puntuación neutral (0) para un empate.
Al mismo tiempo, el algoritmo evalúa los movimientos que conducen a un estado terminal en función del turno de los jugadores. Escogerá el movimiento con la puntuación máxima cuando sea el turno de la IA y elegirá el movimiento con la puntuación mínima cuando sea el turno del jugador humano. Usando esta estrategia, Minimax evita perder ante el jugador humano.
Pruébelo usted mismo en el siguiente juego, preferiblemente usando un navegador Chrom.
Un algoritmo Minimax se puede definir mejor como una función recursiva que hace lo siguiente:
- devolver un valor si se encuentra un estado terminal (+10, 0, -10)
- revisar los lugares disponibles en el tablero
- llamar a la función minimax en cada lugar disponible (recursividad)
- evaluar los valores de retorno de las llamadas a funciones
- y devuelve el mejor valor
Si es nuevo en el concepto de recursividad, le recomiendo que vea este video del CS50 de Harvard.
Para comprender completamente el proceso de pensamiento de Minimax, implementémoslo en código y veámoslo en acción en las siguientes dos secciones.
Minimax en código
Para este tutorial, trabajará en un estado cercano al final del juego que se muestra en la figura 2 a continuación. Dado que minimax evalúa cada estado del juego (cientos de miles), un estado cercano al final te permite realizar un seguimiento de las llamadas recursivas de minimax más fácilmente (9).
Para la siguiente figura, suponga que la IA es X y el jugador humano es O.
Para trabajar con la tabla Ti Tac Toe más fácilmente, debe definirla como una matriz con 9 elementos. Cada artículo tendrá su índice como valor. Esto te resultará útil más adelante. Debido a que el tablero anterior ya está poblado con algunos movimientos X e Y, definamos el tablero con los movimientos X e Y ya en él ( origBoard ).
var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];Luego declare las variables aiPlayer y huPlayer y configúrelas en "X" y "O" respectivamente .
Además, necesita una función que busque combinaciones ganadoras y devuelva verdadero si encuentra una, y una función que enumere los índices de lugares disponibles en el tablero.
/* the original board O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // human var huPlayer = “O”; // ai var aiPlayer = “X”; // returns list of the indexes of empty spots on the board function emptyIndexies(board){ return board.filter(s => s != "O" && s != "X"); } // winning combinations using the board indexies function winning(board, player){ if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3] == player && board[4] == player && board[5] == player) || (board[6] == player && board[7] == player && board[8] == player) || (board[0] == player && board[3] == player && board[6] == player) || (board[1] == player && board[4] == player && board[7] == player) || (board[2] == player && board[5] == player && board[8] == player) || (board[0] == player && board[4] == player && board[8] == player) || (board[2] == player && board[4] == player && board[6] == player) ) { return true; } else { return false; } }Ahora profundicemos en las partes buenas definiendo la función Minimax con dos argumentos newBoard y player . Luego, debe encontrar los índices de los lugares disponibles en el tablero y establecerlos en una variable llamada availSpots .
// the main minimax function function minimax(newBoard, player){ //available spots var availSpots = emptyIndexies(newBoard);Además, debe verificar los estados de los terminales y devolver un valor en consecuencia. Si O gana, debe devolver -10, si X gana, debe devolver +10. Además, si la longitud de la matriz availableSpots es cero, eso significa que no hay más espacio para jugar, el juego ha resultado en un empate y debes devolver cero.
// checks for the terminal states such as win, lose, and tie //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }A continuación, debe recopilar las puntuaciones de cada uno de los espacios vacíos para evaluarlas más tarde. Por lo tanto, haga una matriz llamada movimientos y recorra los espacios vacíos mientras recopila el índice y la puntuación de cada movimiento en un objeto llamado movimiento .
Luego, establezca el número de índice del lugar vacío que se almacenó como un número en origBoard en la propiedad de índice del objeto de movimiento . Más tarde, establezca el espacio vacío en el nuevo tablero para el jugador actual y llame a la función minimax con otro jugador y el nuevo tablero recién cambiado . A continuación, se debe almacenar el objeto como resultado de la Minimax llamada de función que incluye una puntuación de alojamiento a la puntuación de la propiedad del movimiento del objeto.
Si la función minimax no encuentra un estado terminal, sigue avanzando de forma recursiva nivel a nivel en el juego. Esta recursividad ocurre hasta que alcanza un estado terminal y devuelve una puntuación un nivel más arriba.Finalmente, Minimax restablece newBoard a lo que era antes y empuja el objeto de movimiento a la matriz de movimientos .
// an array to collect all the objects var moves = []; // loop through available spots for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard[availSpots[i]]; // set the empty spot to the current player newBoard[availSpots[i]] = player; /*collect the score resulted from calling minimax on the opponent of the current player*/ if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // reset the spot to empty newBoard[availSpots[i]] = move.index; // push the object to the array moves.push(move); }Luego, el algoritmo minimax necesita evaluar el mejor movimiento en la matriz de movimientos . Debe elegir el movimiento con la puntuación más alta cuando la IA está jugando y el movimiento con la puntuación más baja cuando está jugando el humano. Por lo tanto, si el jugador es aiPlayer , establece una variable llamada bestScore en un número muy bajo y recorre la matriz de movimientos , si un movimiento tiene una puntuación más alta que bestScore , el algoritmo almacena ese movimiento . En caso de que haya movimientos con puntuación similar, solo se almacenará el primero.
El mismo proceso de evaluación ocurre cuando el jugador es huPlayer , pero esta vez bestScore se establecería en un número alto y Minimax busca un movimiento con la puntuación más baja para almacenar.
Al final, Minimax devuelve el objeto almacenado en bestMove .
// if it is the computer's turn loop over the moves and choose the move with the highest score var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // else loop over the moves and choose the move with the lowest score var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // return the chosen move (object) from the moves array return moves[bestMove]; }En la siguiente sección, repasemos el código línea por línea para comprender mejor cómo se comporta la función minimax dada la placa que se muestra en la figura 2.
Minimax en acción
Usando la siguiente figura, sigamos las llamadas de función del algoritmo ( FC ) una por una.
Nota: En la figura 3, los números grandes representan cada llamada de función y los niveles se refieren a cuántos pasos por delante del juego está jugando el algoritmo.
1. OrigBoard y aiPlayer se alimentan al algoritmo. El algoritmo hace una lista de los tres espacios vacíos que encuentra, verifica los estados de los terminales y recorre cada espacio vacío comenzando por el primero. Luego, cambia el newBoard colocando el aiPlayer en el primer lugar vacío.Después de esto,se llama a sí mismo con newBoard y huPlayer y espera a que FC devuelva un valor.
2. While the first FC is still running, the second one starts by making a list of the two empty spots it finds, checks for terminal states, and loops through the empty spot starting from the first one. Then, it changes the newBoard by placing the huPlayer in the first empty spot.After thatit calls itself with newBoard and the aiPlayer and waits for the FC to return a value.
3. Finally the algorithm makes a list of the empty spots, and finds a win for the human player after checking for terminal states. Therefore, it returns an object with a score property and value of -10.
Dado que el segundo FC enumeró dos lugares vacíos, Minimax cambia el nuevo tablero colocando a huPlayer en el segundo lugar vacío. Luego, se llama a sí mismo con la nueva placa y el aiPlayer .4. El algoritmo hace una lista de los espacios vacíos y encuentra una ganancia para el jugador humano después de verificar los estados terminales. Por lo tanto, devuelve un objeto con una propiedad de puntuación y un valor de -10.
En el segundo FC, el algoritmo recoge los valores procedentes de niveles inferiores (3º y 4º FC). Dado que el turno de huPlayer resultó en los dos valores, el algoritmo elige el más bajo de los dos valores. Debido a que ambos valores son similares, elige el primero y lo devuelve al primer FC. En este punto, el primer FC ha evaluado la puntuación de mover aiPlayer en el primer lugar vacío. A continuación, cambia el newBoard colocando aiPlayer en el segundo lugar vacío. Luego, se llama a sí mismo con newBoard y huPlayer .5. En el quinto FC, el algoritmo hace una lista de los espacios vacíos y encuentra una victoria para el jugador humano después de verificar los estados terminales. Por lo tanto, devuelve un objeto con una propiedad de puntuación y un valor de +10.
Después de eso, el primer FC avanza cambiando el nuevo tablero y colocando aiPlayer en el tercer lugar vacío. Luego, se llama a sí mismo con la nueva placa y el huPlayer .6. El 6º FC comienza haciendo una lista de dos espacios vacíos que encuentra, verifica los estados de los terminales y recorre los dos espacios vacíos comenzando por el primero. Luego, cambia el newBoard colocando huPlayer en el primer lugar vacío.Después de esto,it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.
7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.
8. On the 8th FC,el algoritmo crea una lista vacía de espacios vacíos y encuentra una ganancia para aiPlayer después de verificar los estados terminales. Por lo tanto, devuelve un objeto con la propiedad de puntuación y un valor de +10 un nivel más arriba (7º FC).
El 7º FC solo recibió un valor positivo de los niveles inferiores (8º FC). Debido a que el turno de aiPlayer resultó en ese valor, el algoritmo debe devolver el valor más alto que ha recibido de los niveles más bajos. Por tanto, devuelve su único valor positivo (+10) un nivel más arriba (6º FC). Dado que el 6th FC enumeró dos lugares vacíos, Minimax cambia newBoard colocando a huPlayer en el segundo lugar vacío. Luego, se llama a sí mismo con la nueva placa y el aiPlayer .9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.
En este punto, el 6 FC tiene que elegir entre la puntuación (+10) que fue enviada desde el 7º FC (devuelta originalmente del 8 FC) y la puntuación (-10) devuelta por el 9º FC. Dado que el turno de huPlayer resultó en esos dos valores devueltos, el algoritmo encuentra la puntuación mínima (-10) y la devuelve hacia arriba como un objeto que contiene las propiedades de puntuación e índice. Finalmente, se han evaluado las tres ramas del primer CF (-10, +10, -10). Pero debido a que el turno de aiPlayer resultó en esos valores, el algoritmo devuelve un objeto que contiene la puntuación más alta (+10) y su índice (4).En el escenario anterior, Minimax concluye que mover la X al centro del tablero da como resultado el mejor resultado. :)
¡El fin!
By now you should be able to understand the logic behind the Minimax algorithm. Using this logic try to implement a Minimax algorithm yourself or find the above sample ongithub or codepen and optimize it.
Thanks for reading! If you liked this story, don't forget to share it on social media.
Special thanks to Tuba Yilmaz, Rick McGavin, and Javid Askerovfor reviewing this article.