Algoritmos de decisión para juegos, a un pip install.

El problema

Los algoritmos de búsqueda como Minimax o Monte Carlo Tree Search son la base de muchos agentes de juego, y la idea de AlphaZero. Pero al analizar el estado del arte comprobé que no había una biblioteca de Python sencilla que los reuniera, y menos aún para juegos de información imperfecta, en los que el agente no lo ve todo: las cartas del rival, el mazo o las piezas ocultas.

El objetivo del trabajo fue crear esa biblioteca, publicarla para que cualquiera pudiera usarla y validar experimentalmente cada algoritmo.

Cuatro algoritmos, una misma interfaz

pyplAI implementa cuatro algoritmos. Para usar cualquiera de ellos, basta con describir el juego mediante unos pocos métodos: obtener los movimientos, aplicar uno, saber si la partida ha terminado y quién gana.

• Minimax con poda alfa-beta, para juegos de información perfecta como las damas.
• MCTS con UCT, que en lugar de explorar todo el árbol simula partidas y se concentra en las jugadas más prometedoras.
• SO-ISMCTS, que construye un único árbol desde el punto de vista del jugador y razona sobre las posibles versiones de la información oculta.
• MO-ISMCTS, que mantiene un árbol por jugador y agrupa los movimientos que el rival no puede distinguir. Es el más fiel cuando hay acciones parcialmente observables.

Así se usa MCTS sobre cualquier juego que implemente esa interfaz:

import pyplAI

mcts = pyplAI.MCTS(
    Juego.aplica_movimiento,
    Juego.obtiene_movimientos,
    Juego.es_estado_final,
    Juego.gana_jugador,
    numeroJugadores=2,
    tiempoEjecucion=1,  # segundos de búsqueda por jugada
)

movimiento = mcts.ejecuta(juego)

Ocho juegos para demostrarlo

Para validar la biblioteca desarrollé ocho juegos completos, que además sirven de ejemplo de uso: tres en raya, Ultimate Tic-Tac-Toe y damas con Minimax y MCTS; escoba, blackjack y Stratego con SO-ISMCTS; y Phantom y Holjjak, con movimientos ocultos, con MO-ISMCTS.

En el Stratego añadí un algoritmo genético que busca la mejor colocación inicial de las piezas, una decisión que el árbol de búsqueda no puede tomar por sí solo.

Resultados

Repetí las pruebas del TFG con la versión 1.1.0 de la biblioteca, después de revisarla a fondo (réplica completa):

• En Ultimate Tic-Tac-Toe, con poco tiempo de cálculo, Minimax gana a MCTS: 62 % de las partidas frente a 25 %. Al dar más tiempo, la ventaja se reduce hasta igualarse.
• SO-ISMCTS gana entre el 78 % y el 92 % de las partidas de escoba contra un agente aleatorio.
• En Stratego, con las colocaciones del algoritmo genético, SO-ISMCTS gana el 55 % de las partidas contra sí mismo con colocaciones aleatorias, que solo gana el 5 %.
• MO-ISMCTS supera a SO-ISMCTS en los juegos con movimientos ocultos. En Holjjak gana entre el 83 % y el 87 % de las partidas.

Juega contra pyplAI

Para que cualquiera pueda probarla sin instalar nada, hice pyplAI Web: un Ultimate Tic-Tac-Toe contra el MCTS de pyplAI, que se ejecuta en el propio navegador con Pyodide. Tiene cuatro niveles, de 25 a 6.400 simulaciones por jugada, calibrados con un torneo de 1.080 partidas entre búsquedas de distinta fuerza. También enseña qué jugadas consideró la IA y con qué porcentaje de victorias.

Lo que aprendí

• Diseñar una API es diseñar para otros. El reto no fue solo implementar los algoritmos, sino que alguien pueda conectarlos a su juego sin leer el código. Por eso la biblioteca incluye un manual completo y los ocho juegos de ejemplo.
• Los tests encuentran lo que los experimentos no ven. Al preparar la versión 1.1.0 escribí un test para cada algoritmo y cada juego, y aparecieron fallos que el TFG no había detectado, como un blackjack en el que el algoritmo veía la carta tapada del croupier. Las conclusiones principales se mantienen, y las cifras de esta página son las de la versión corregida.
• La búsqueda sigue siendo muy competitiva. Lo confirmé después en Connect-X AlphaZero: los agentes basados en pyplAI superaron a PPO y Rainbow DQN, y solo AlphaZero, que combina búsqueda con una red neuronal, los superó.