Jugar contra una máquina: minimax y la poda alfa-beta
Cómo juega una máquina que no pierde: minimax supone lo peor del rival y la poda alfa-beta da la misma jugada mirando menos. Curso de IA, 0.6.

Curso de IA › Nivel 0 — Cómo ve el mundo una máquina parte 6 de 6
Para buscar un camino en un mapa basta con elegir bien en qué orden se miran las casillas, como cuenta Buscar un camino. En un juego hay algo más: un rival que también elige, y que no va a dejarte ganar. La búsqueda clásica lo resuelve con minimax, que supone siempre lo peor del rival, y con la poda alfa-beta, que llega a la misma jugada mirando muchas menos posiciones.
Toca esto primero
Abre la pestaña Juego de la herramienta Búsqueda, en Tres en raya. Pulsa Que empiece la máquina. Pone su X en una esquina, y debajo cuenta lo que ha tenido que mirar para decidirlo: 34 203 posiciones miradas, con poda, frente a las 549 946 que habría mirado sin poda, «×16 menos trabajo, y la misma jugada».
Cómo leer el tablero. Es un tres en raya normal, con una diferencia: la herramienta enseña lo que piensa la máquina. En cada casilla libre escribe lo que vale jugar ahí si los dos jugáis a la perfección: quién gana si es seguro, tablas si acaba en empate, y un número cuando solo lo estima (más alto, mejor). Un rótulo encima del tablero dice para quién son esos valores. Sin pistas, en naranja, «Valores para la máquina»: son los que calculó ella para elegir su jugada, y por eso dicen gana ella o pierde ella. Ahí están las «tablas» de cada casilla libre de la captura: la máquina jugó en la esquina, pero cualquier otra primera jugada también acababa en empate. Cuando juegas contra una persona, no ves lo que piensa; aquí ves lo que ha pensado la máquina y por qué elige esa jugada.
Ahora abre la misma partida con las pistas (la casilla Ver lo que vale cada jugada en mi turno) y pulsa otra vez Que empiece la máquina. El rótulo se vuelve verde, «Valores para ti», y cada casilla libre dice lo que vale para ti esa jugada si los dos jugáis a la perfección: todas dicen pierdes, menos el centro, que dice tablas y va recuadrado como lo que sería tu mejor jugada. En este ejemplo, solo el centro te salva de perder.
Qué acaba de pasar
Un juego se puede dibujar como un árbol, como el de la figura de un poco más abajo: arriba, la posición actual; debajo, todas las jugadas posibles de quien mueve; debajo de cada una, todas las respuestas del rival. Cada turno es un nivel del árbol, y así hasta que la partida termina en victoria, derrota o tablas. En tres en raya, el árbol entero tiene 255 168 partidas distintas (Game complexity, en la Wikipedia en inglés), y la herramienta cuenta 549 946 posiciones si se mira todo desde el tablero vacío (muchas son el mismo tablero al que se llega por caminos distintos: tableros distintos hay 5478).
Minimax recorre ese árbol de abajo arriba. Las posiciones finales valen «gana», «pierde» o «tablas». En su turno, la máquina se queda con la jugada que más vale para ella; en el tuyo, supone que tú eliges la que menos vale para ella, es decir, lo mejor para ti. Así sube el valor hasta la posición actual. La máquina se queda con la jugada que más le conviene aunque tú respondas siempre lo mejor para ti: de todas sus jugadas, la que menos le perjudica. Por eso no pierde nunca en tres en raya: ha mirado todas las respuestas posibles a cada jugada.
Míralo en un final de partida: es solo la punta de abajo del árbol, porque por encima quedarían todos los niveles de las jugadas anteriores. En la figura, empieza por arriba: ese tablero es la posición actual, la que la máquina tiene delante. Le toca a ella, que juega con las X, y quedan libres las tres casillas de abajo. El rival, que juega con las «O», tiene dos fichas en la diagonal que baja desde la esquina de arriba a la derecha, y le falta la de abajo a la izquierda. Si la máquina tapa ahí (la jugada A), al rival le quedan dos respuestas, y las dos acaban en tablas: A vale «tablas». Si juega en cualquiera de las otras dos casillas (B o C), el rival completa la diagonal y gana: valen «pierde». Minimax se queda con A.
La poda alfa-beta ahorra trabajo sin cambiar el resultado. La idea se entiende sin árbol: si ya tienes una jugada que te asegura el empate, y en la siguiente que miras el rival puede ganarte con su primera respuesta, no hace falta mirar el resto de sus respuestas, porque esa jugada ya no la vas a elegir. En el árbol, al mirar B, la primera respuesta del rival ya gana, y la otra, en gris, se queda sin mirar: con esa primera respuesta, B ya es peor que las tablas que consigue con A, y mirar el resto no sirve de nada. Con C pasa lo mismo. En la primera jugada del tablero vacío, la máquina cortó 13 124 ramas así, y miró 16 veces menos posiciones para llegar a la misma X en la esquina.
Ese árbol no hace falta imaginarlo: la herramienta lo enseña. Abre el tres en raya, pulsa Que empiece la máquina y baja hasta El árbol que ha mirado la máquina. Sale cada jugada posible con lo que vale y cuántas posiciones miró debajo de ella. Si pulsas una, se despliegan las respuestas del rival, y las ramas que la poda no llegó a mirar salen aparte, con su valor calculado solo para enseñártelo. Seguir la línea que espera recorre la partida que la máquina cree que se va a jugar.
Con un juego más grande, el árbol es demasiado grande para mirarlo entero: Conecta 4 tiene unos 4,5 billones de posiciones distintas (Connect Four, en la Wikipedia en inglés), y recorrerlas en cada jugada llevaría demasiado tiempo y demasiada memoria. Abre Conecta 4 y deja que empiece la máquina: ahora mira solo 6 jugadas por delante (la profundidad) y, donde corta, estima cuánto vale la posición con una puntuación, que es lo que sale en las columnas (números como −18 o 0) en vez de «gana ella» o «pierde ella». Esa estimación hace el papel de la heurística de A*: un atajo escrito por una persona. Aun así, la poda le ahorra mucho: 7000 posiciones en vez de 137 257. Y sigue con la partida avanzada: en la captura, después de cuatro jugadas tuyas, miró 6567 posiciones en vez de 130 558, y encima de cada columna escribe lo que estima que vale para ella jugar ahí.
El error típico
Podrías pensar que podar es arriesgarse: que, por mirar menos, la máquina a veces se salta la mejor jugada. Con la poda alfa-beta no pasa. Solo corta las ramas que, valgan lo que valgan, no van a cambiar la jugada que elige, y llega a la misma que minimax mirando todo (Alpha–beta pruning, en la Wikipedia en inglés). Lo que sí cambia el resultado es la profundidad: con un árbol demasiado grande para mirarlo entero, la máquina juega tan bien como le permiten lo lejos que mira y lo buena que es su estimación.
Pruébalo tú mismo
- En tres en raya, intenta ganar a la máquina. Antes de cada jugada, mira las pistas: ¿hay alguna casilla que diga «ganas»?
- Empieza tú en una esquina y mira qué hace la máquina. ¿Juega en el centro?
Ponte a prueba
En Conecta 4 mirando 3 jugadas, deja que empiece la máquina. ¿Cuántas veces menos trabajo le ahorra la poda? Repítelo con 7 jugadas.
Con 3, la poda le ahorra ×___; con 7, ×___.
Debajo del tablero: «menos trabajo, y la misma jugada».
Ver la respuesta
Respuestas: 2,7 y 60.
Cuanto más hondo mira, más ramas hay que cortar, y la poda rinde más: con 7 jugadas mira 15 939 posiciones en vez de 960 793. Por eso una máquina con poda puede mirar más lejos en el mismo tiempo.
Abre los palillos: hay 13, cada uno coge de 1 a 3 por turno y gana quien coge el último. Quita Ver el análisis y juega antes de contestar.
Ponte a prueba
Empiezas tú con 13 palillos. ¿Cuántos tienes que coger para no perder?
Coges [1 / 2 / 3].
Vuelve a activar Ver el análisis y mira los números en rojo: son las posiciones en las que pierde quien tiene que mover.
Ver la respuesta
Respuesta: 1.
Pierde quien tiene que mover con 0, 4, 8, 12… palillos: los múltiplos de 4. Si dejas 12, coja lo que coja el otro, tú completas hasta 4 y le dejas en 8, luego en 4 y luego en 0. La máquina ha encontrado esa regla buscando, sin que nadie se la diera, y con ella ya no hace falta buscar.
Ponte a prueba
Marca Quien coge el último, pierde (o abre esa variante) y empieza tú otra vez con 13. ¿Quién gana ahora con juego perfecto?
Gana [tú / la máquina]. Las posiciones en las que pierde quien mueve son las que dejan resto ___ al dividir entre 4.
Ver la respuesta
Respuestas: la máquina y 1.
Ahora pierde quien se queda con el último palillo, así que las posiciones malas se desplazan una: 1, 5, 9, 13… Con 13 empiezas en una de ellas, y la máquina, que ha buscado hasta el final, no te deja salir.
Con varios montones el juego se llama Nim: en cada turno coges los palillos que quieras, pero de un solo montón. Aquí la regla ya no es contar de 4 en 4.
Ponte a prueba
Abre el Nim con montones de 3, 4 y 5 y mira el análisis. La herramienta escribe cada montón en binario y hace el «o exclusivo» de cada columna: la suma nim. ¿Cuánto vale aquí? ¿Quién gana si empiezas tú?
La suma nim vale ___, y gana [tú / la máquina]. Para ganar, del montón de 3 coges ___.
Con suma 0, pierde quien mueve. Busca la jugada que deja la suma en 0: compruébalo con los montones de 1, 4 y 5.
Ver la respuesta
Respuestas: 2, tú y 2.
3, 4 y 5 en binario son 011, 100 y 101; columna a columna, el «o exclusivo» da 010, que es 2. Si coges 2 del montón de 3, quedan 1, 4 y 5 (001, 100 y 101), y la suma es 0: cualquier jugada del otro la estropea, y tú siempre puedes volver a dejarla en 0. Es la regla de Charles Bouton, de 1901 (Nim, en la Wikipedia en inglés), y la máquina llega a lo mismo buscando: lo dice debajo del análisis.
Si quieres más
- Alpha–beta pruning, en la Wikipedia en inglés: cómo funciona la poda con un ejemplo dibujado, y su historia: John McCarthy la propuso en el taller de Dartmouth de 1956.
- Hasta dónde mira una máquina, del mismo curso: qué pasa cuando la máquina corta a medio cambio de piezas (el efecto horizonte) y cómo deciden los motores mirando menos.
- Buscar un camino, del mismo curso: la otra mitad de la búsqueda clásica, cuando no hay rival, con la misma herramienta.
- Aprender por recompensa: una máquina que aprende a jugar sola con premios y castigos, sin reglas para buscar.
«Jugar contra una máquina: minimax y la poda alfa-beta», de Ramón Invarato en jarroba.com, con licencia Creative Commons Reconocimiento-NoComercial-CompartirIgual 3.0. Obra registrada en Safe Creative.

Te puede interesar
Buscar un camino: una IA que no aprende nada
Cómo busca un camino una IA que no aprende: anchura, profundidad, coste uniforme, voraz y A*, paso a paso en una cuadrícula. Curso de IA, 0.5.
Qué es un modelo (y por qué una recta ya cuenta como uno)
Qué es un modelo, entrenar y predecir, con una recta que ajustas arrastrando puntos. Y por qué un modelo no entiende sus datos. Curso de IA, 0.4.







Deja un comentario