Introducción al algoritmo Minimax con una implementación de Java

Programación

1. Información general

En este artículo, analizaremos el algoritmo Minimax y sus aplicaciones en IA. Como es un algoritmo de teoría de juegos, implementaremos un juego simple usándolo.

También discutiremos las ventajas de usar el algoritmo y veremos cómo se puede mejorar.

2. Introducción

Minimax es un algoritmo de toma de decisiones, generalmente utilizado en juegos de dos jugadores por turnos . El objetivo del algoritmo es encontrar el próximo movimiento óptimo.

En el algoritmo, un jugador se llama maximizador y el otro jugador es minimizador. Si asignamos una puntuación de evaluación al tablero de juego, un jugador intenta elegir un estado de juego con la puntuación máxima, mientras que el otro elige un estado con la puntuación mínima.

En otras palabras, el maximizador trabaja para obtener la puntuación más alta, mientras que el minimizador intenta obtener la puntuación más baja intentando contrarrestar los movimientos .

Se basa en el concepto de juego de suma cero. En un juego de suma cero, la puntuación total de la utilidad se divide entre los jugadores. Un aumento en la puntuación de un jugador da como resultado una disminución en la puntuación de otro jugador. Entonces, la puntuación total es siempre cero. Para que un jugador gane, el otro tiene que perder. Ejemplos de tales juegos son ajedrez, póquer, damas, tic-tac-toe.

Un hecho interesante: en 1997, la computadora de ajedrez de IBM Deep Blue (construida con Minimax) derrotó a Garry Kasparov (el campeón mundial de ajedrez).

3. Algoritmo Minimax

Nuestro objetivo es encontrar la mejor jugada para el jugador. Para hacerlo, simplemente podemos elegir el nodo con la mejor puntuación de evaluación. Para hacer el proceso más inteligente, también podemos mirar hacia adelante y evaluar los movimientos del oponente potencial.

Para cada movimiento, podemos mirar hacia adelante tantos movimientos como lo permita nuestra potencia informática. El algoritmo asume que el oponente está jugando de manera óptima.

Técnicamente, comenzamos con el nodo raíz y elegimos el mejor nodo posible. Evaluamos los nodos en función de sus puntuaciones de evaluación. En nuestro caso, la función de evaluación puede asignar puntuaciones solo a los nodos de resultados (hojas). Por lo tanto, llegamos de forma recursiva a las hojas con puntuaciones y las propagamos hacia atrás.

Considere el siguiente árbol de juegos:

Maximizer comienza con el nodo raíz y elige el movimiento con la puntuación máxima. Desafortunadamente, solo las hojas tienen puntuaciones de evaluación y, por lo tanto, el algoritmo tiene que alcanzar los nodos de las hojas de forma recursiva. En el árbol de juego dado, actualmente es el turno del minimizador para elegir un movimiento de los nodos hoja , por lo que los nodos con puntajes mínimos (aquí, nodo 3 y 4) serán seleccionados. Sigue eligiendo los mejores nodos de manera similar, hasta que llega al nodo raíz.

Ahora, definamos formalmente los pasos del algoritmo:

  1. Construye el árbol del juego completo
  2. Evaluar las puntuaciones de las hojas utilizando la función de evaluación
  3. Puntajes de respaldo desde las hojas hasta la raíz, considerando el tipo de jugador:
    • Para jugador máximo, seleccione el niño con la puntuación máxima
    • Para jugador mínimo, seleccione el niño con la puntuación mínima
  4. En el nodo raíz, elija el nodo con el valor máximo y realice el movimiento correspondiente

4. Implementación

Ahora, implementemos un juego.

En el juego, tenemos un montón con n número de huesos . Ambos jugadores deben recoger 1, 2 o 3 huesos en su turno. Un jugador que no puede tomar ningún hueso pierde el juego. Cada jugador juega de manera óptima. Dado el valor de n , escribamos una IA.

Para definir las reglas del juego, implementaremos la clase GameOfBones :

class GameOfBones { static List getPossibleStates(int noOfBonesInHeap) { return IntStream.rangeClosed(1, 3).boxed() .map(i -> noOfBonesInHeap - i) .filter(newHeapCount -> newHeapCount >= 0) .collect(Collectors.toList()); } }

Además, también necesitamos la implementación para las clases Node y Tree :

public class Node { int noOfBones; boolean isMaxPlayer; int score; List children; // setters and getters } public class Tree { Node root; // setters and getters }

Ahora implementaremos el algoritmo. Requiere un árbol de juego para mirar hacia adelante y encontrar el mejor movimiento. Implementemos eso:

public class MiniMax { Tree tree; public void constructTree(int noOfBones) { tree = new Tree(); Node root = new Node(noOfBones, true); tree.setRoot(root); constructTree(root); } private void constructTree(Node parentNode) { List listofPossibleHeaps = GameOfBones.getPossibleStates(parentNode.getNoOfBones()); boolean isChildMaxPlayer = !parentNode.isMaxPlayer(); listofPossibleHeaps.forEach(n -> { Node newNode = new Node(n, isChildMaxPlayer); parentNode.addChild(newNode); if (newNode.getNoOfBones() > 0) { constructTree(newNode); } }); } }

Ahora, implementaremos el método checkWin que simulará una jugada, seleccionando movimientos óptimos para ambos jugadores. Establece la puntuación en:

  • +1, si gana maximizador
  • -1, si el minimizador gana

El checkWin devolverá verdadero si el primer jugador (en nuestro caso, maximizador) gana:

public boolean checkWin() { Node root = tree.getRoot(); checkWin(root); return root.getScore() == 1; } private void checkWin(Node node) { List children = node.getChildren(); boolean isMaxPlayer = node.isMaxPlayer(); children.forEach(child -> { if (child.getNoOfBones() == 0) { child.setScore(isMaxPlayer ? 1 : -1); } else { checkWin(child); } }); Node bestChild = findBestChild(isMaxPlayer, children); node.setScore(bestChild.getScore()); }

Aquí, el método findBestChild encuentra el nodo con la puntuación máxima si un jugador es un maximizador. De lo contrario, devuelve al niño con la puntuación mínima:

private Node findBestChild(boolean isMaxPlayer, List children) { Comparator byScoreComparator = Comparator.comparing(Node::getScore); return children.stream() .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed()) .orElseThrow(NoSuchElementException::new); }

Finalmente, implementemos un caso de prueba con algunos valores de n (la cantidad de huesos en un montón):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal() { miniMax.constructTree(6); boolean result = miniMax.checkWin(); assertTrue(result); miniMax.constructTree(8); result = miniMax.checkWin(); assertFalse(result); }

5. Mejora

Para la mayoría de los problemas, no es factible construir un árbol de juego completo. En la práctica, podemos desarrollar un árbol parcial (construir el árbol hasta un número predefinido de niveles solamente) .

Luego, tendremos que implementar una función de evaluación, que debería poder decidir qué tan bueno es el estado actual para el jugador.

Incluso si no construimos árboles de juego completos, calcular movimientos para juegos con alto factor de ramificación puede llevar mucho tiempo.

Afortunadamente, existe una opción para encontrar el movimiento óptimo, sin explorar cada nodo del árbol del juego. Podemos omitir algunas ramas siguiendo algunas reglas, y no afectará el resultado final. Este proceso se llama poda . La poda alfa-beta es una variante frecuente del algoritmo minimax.

6. Conclusión

El algoritmo Minimax es uno de los algoritmos más populares para juegos de mesa de computadora. Se aplica ampliamente en juegos por turnos. Puede ser una buena opción cuando los jugadores tienen información completa sobre el juego.

Puede que no sea la mejor opción para los juegos con un factor de ramificación excepcionalmente alto (por ejemplo, el juego de GO). No obstante, dada una implementación adecuada, puede ser una IA bastante inteligente.

Como siempre, el código completo del algoritmo se puede encontrar en GitHub.