Aprendizaje por refuerzo (RL) — Capítulo 4: Min-Max y Alpha-Beta Pruning — Parte 1: Min-Max
Arrancamos el cuarto capítulo de esta serie sobre aprendizaje por refuerzo.
Min-Max y Min-Max con Alpha-Beta Pruning son dos algoritmos que, lejos de entrar en la categoría de aprendizaje por refuerzo, van a ser super útiles para comprender el resto de algoritmos que vamos a ver de aquí en adelante y que son una herramienta esencial para tener en nuestro repertorio.
Empecemos por una breve introducción.
Introducción
Como mencionaba anteriormente, los dos próximos algoritmos que exploraremos no se ajustan estrictamente a la categoría de aprendizaje por refuerzo; de hecho, no se pueden considerar algoritmos de aprendizaje en ningún sentido, ya que abordan los problemas mediante un enfoque de fuerza bruta, es decir, explorando todos los estados posibles o la mayoría de ellos. A pesar de no formar parte de la serie de algoritmos de aprendizaje por refuerzo, es crucial reconocer que estos dos algoritmos han tenido un impacto significativo en la resolución de problemas, especialmente en el ámbito de los juegos de mesa.
Además, comprender estos algoritmos a fondo resulta fundamental, ya que sienta las bases para el entendimiento de numerosos modelos de aprendizaje por refuerzo que se abordaremos en esta serie. Entre los ejemplos notables de estos modelos se encuentra AlphaZero.
Antes de sumergirnos en la explicación detallada de estos algoritmos, es importante contextualizarlos históricamente. Su influencia más destacada se puede observar en el caso de Deep Blue, una máquina desarrollada por IBM que logró una hazaña memorable: derrotar al campeón mundial de ajedrez, Garry Kasparov, el 10 de febrero de 1996.
La historia de Deep Blue y Garry Kasparov es un capítulo legendario en la evolución de la inteligencia artificial y el ajedrez. En 1997, Deep Blue, una supercomputadora desarrollada por IBM, desafió al campeón mundial de ajedrez, Garry Kasparov, en una partida histórica. Fue la primera vez que una máquina derrotó a un campeón mundial en una partida de ajedrez bajo las reglas estándar. La partida fue un enfrentamiento intelectual épico que atrajo la atención mundial.
La victoria de Deep Blue marcó un hito en la historia de la inteligencia artificial y demostró la capacidad de las máquinas para superar a los humanos en tareas complejas. Sin embargo, también generó debates sobre la relación entre la mente humana y la inteligencia artificial. A pesar de su derrota, Kasparov continuó siendo un campeón destacado y se convirtió en un defensor activo de la colaboración entre humanos y máquinas en el ajedrez. La partida entre Deep Blue y Kasparov sigue siendo un momento icónico en la historia de la IA y el ajedrez, destacando el potencial de la tecnología para desafiar y mejorar nuestras habilidades humanas.
El porqué traemos la historia de Deep Blue a todo esto es, por un lado que es un momento histórico en la era de humanos vs máquinas, y por otro lado que en el núcleo de este sistema se encuentra Min-Max con Alpha-Beta Pruning, que es uno de los algoritmos que vamos a discutir en este capítulo.
Los métodos de búsqueda heurística
Los métodos que estudiaremos en este capítulo son reconocidos bajo el término “búsqueda heurística”. En el ámbito de la búsqueda heurística, se despliega un vasto árbol de posibles secuencias para cada estado que se encuentra. En este proceso, se aplica una función de valor, la cual puede ser aproximada o precisa (si se dispone de información exacta), a los nodos hoja del árbol. A partir de ahí, la evaluación retrocede desde los nodos hoja hasta el estado actual en la raíz del árbol. Finalmente, se selecciona la acción óptima entre todas las opciones y se descartan las demás.
Un algoritmo emblemático de esta categoría es el Min-Max, que se puede resumir como la estrategia de “simular todas las posibles jugadas y seleccionar aquella que garantiza la victoria” o, en caso contrario, optar por la alternativa más ventajosa para nosotros. En esencia, el Min-Max representa una aproximación de fuerza bruta, ya que no implica un componente de inteligencia artificial.
Para ilustrar este concepto, consideremos el juego del TaTeTi, también conocido como TicTacToe en función de la región geográfica. Imaginemos que estamos enfrentando a un adversario, y en cada turno, tomamos un papel y anotamos todas las jugadas posibles que podríamos hacer, seguido por las jugadas disponibles para nuestro oponente, y así sucesivamente, hasta llegar al desenlace del juego. Este enfoque nos proporcionaría la jugada que nos lleva a la victoria. Sin embargo, es importante destacar que esta estrategia no necesariamente refleja habilidad en el juego; más bien, representa una solución forzada mediante la exploración exhaustiva de todas las posibles secuencias futuras.
Para los mas nerds (alerta de spoiler!), se podría decir que el personaje de Dr. Strange realizó una búsqueda Min-Max en el minuto 83 de la película “Avengers: Infinity War”. En esa escena, exploró un asombroso total de 14,000,605 futuros posibles con el propósito de determinar la mejor estrategia para ganar la batalla, eso es Min-Max!.
Algoritmo Min-Max
Vamos a explicar el algoritmo Min-Max con un ejemplo, que creo que es la forma mas fácil de entender su funcionamiento. Tómese un minuto para ver la siguiente figura:
Imaginemos que nos encontramos frente al tablero representado en la parte superior de lo que podríamos considerar como un árbol de decisiones (podemos visualizarlo como un árbol invertido, o incluso como las raíces de un árbol en crecimiento). En este escenario, nos tomamos el tiempo en nuestro turno para simular todas las posibles secuencias futuras y construimos este diagrama.
Ahora, ¿Qué elección debemos hacer en este punto?, lo más sensato sería no dejar nada al azar y suponer que nuestro oponente está siguiendo la misma estrategia, es decir, también está manejando este mismo árbol de decisiones en su mente. Bajo esta suposición, adoptamos la idea central del algoritmo Min-Max, que consiste en asumir que el otro jugador siempre tomará la decisión que mejor le convenga.
Entonces, en este contexto, parece que la elección óptima sería colocar un círculo en la casilla superior central, que corresponde a la rama izquierda del árbol de decisiones. Ahora, profundicemos en esta elección. Si optamos por esta decisión, independientemente de la respuesta de nuestro oponente, en el peor de los casos llegaríamos a un empate. Por otro lado, si optamos por la segunda decisión (colocar un círculo en la casilla inferior izquierda), nuestro jugador automáticamente ganaría la partida. Lo mismo ocurre si tomamos la tercera decisión.
En consecuencia, la elección de colocar un círculo en la parte superior central del tablero parece ser indiscutiblemente la estrategia más acertada en este contexto. Esta elección minimiza el riesgo de perder y, en el peor de los casos, nos garantiza un empate.
Felicidades!, ya sabe Min-Max, pero un minuto, ¿Cómo implementamos esto en forma de algoritmo?. Para responder esto vamos a resolver el mismo problema que vimos recién, pero esta vez pensando como una maquina.
Vamos a hacerle unas modificaciones a nuestra árbol de decisiones de la figura anterior. Primero vamos a marcar cada turno del jugador con Min y Max, para representar que un jugador (nosotros) queremos maximizar la recompensa, y el otro (el contrincante) busca minimizar nuestra recompensa. Bien, ahora se entiende de donde viene el nombre Min-Max.
La siguiente modificación es marcar la recompensa de los estados finales con +1 si la victoria es nuestra, -1 para la victoria del contrincante y 0 en caso de empate. Finalmente nuestro árbol de decisiones quedaría así:
Ahora nuestro algoritmo lo que va hacer es propagar las puntuaciones desde la capa inferior a la capa superior. Como en este turno solo hay una decisión posible, propagamos el único valor disponible al nodo superior, pero tenga en cuenta que si existieran mas, como en el estado final es el turno del jugador “Max’’ (nosotros), vamos a propagar el valor máximo.
Luego de este paso el árbol de decisiones queda:
Ahora es el turno del jugador ‘’Min’’ (el contrincante), por lo tanto vamos a propagar las puntaciones al nodo superior, pero esta vez el menor de los valores ya que nuestro adversario busca minimizar nuestras recompensas:
Finalmente, propagamos una capa más hacia arriba. Nuevamente, como es nuestro turno, propagamos el valor más alto posible de todos los movimiento. El valor mas alto en esta posición es 0, lo que significa que bajo el supuesto que nuestro contrincante es extremadamente hábil en este juego y toma siempre la mejor decisión, lo máximo a lo que podemos aspirar es a un empate:
Todos estos pasos son tareas repetitivas y si de algo estamos seguros es que las maquinas son excelentes para hacer tareas repetitivas y de forma extremadamente rápida. Este algoritmo si bien es simple, requiere cierta destreza mental y concentración, pero esto se puede programar en unas pocas líneas de código. Este método se resuelve en dos partes. Por un lado tenemos la función que calcula el valor de un estado, que viene dada por:
Esta es una función recursiva que dado el estado del juego y si es el turno del jugador Max o Min (nosotros o el contrincante), nos devuelve el valor esperado de estar en dicho estado. Esto es en escénica el algoritmo de Min-Max, pero para darle uso no podemos calcular simplemente el valor del estado en el que estamos parados, ya que además queremos saber que acción tomar para llegar a ese estado.
Para esto lo que vamos a hacer es calcular el valor del estado, pero en vez de hacerlo para el estado en el que estamos parados, lo hacemos para los estados del paso siguiente. De esta forma tenemos el valor pero para cada una de las acciones, y luego simplemente elegimos la acción que nos lleve a aquel estado con el mayor valor:
Y ya lo tenemos, con un par de líneas tenemos implementado Min-Max. ¿Puede adivinar que sucedería si ponemos a jugar TaTeTi entre dos agentes de Min-Max?, efectivamente, empatarían.
En la teoría de juegos, el “juego perfecto’’ es el comportamiento o la estrategia de un jugador que conduce al mejor resultado posible para ese jugador, independientemente de la respuesta del oponente. El juego perfecto para un juego se conoce cuando el juego “está resuelto”.
Por ejemplo el TaTeTi es uno de estos casos, donde el juego termina en un empate si no se cometen errores. Otro ejemplo son las damas, que fue resuelto en 2007 por el equipo de Jonathan Schaeffe, donde desde la posición inicial estándar ambos jugadores pueden garantizar un empate con un juego perfecto. El 4 en raya (o Connect Four), resuelto en 1988, el primer jugador puede forzar una victoria. Por otro lado la resolución completa del ajedrez sigue siendo difícil de alcanzar, y se especula que la complejidad del juego puede impedir que se resuelva alguna vez.
Y hasta aquí esta parte, en la siguiente parte potenciaremos este algoritmo tomando unas tijeras y podando el árbol de decisiones para que la búsqueda sea mas rápida, acelerando el proceso hasta unas 14 veces. Intrigado?, no te pierdas la próxima parte.
Mientras tanto puedes ir consultando la notebook con la implementación de Min-Max y Alpha-Beta Pruning en el repositorio de Git:
Y si no entiendes algo, no te preocupes, en la última parte de esta capítulo vamos a explorar el código pieza por pieza.
Lecturas sugeridas
- Ve a la siguiente parte de este capítulo: Aprendizaje por refuerzo (RL) — Capítulo 4: Min-Max y Alpha-Beta Pruning — Parte 2: Alpha-Beta Pruning
- Ve al capítulo anterior: Aprendizaje por refuerzo (RL) — Capítulo 3: Multi-armed bandit — Parte 1: Epsilon-greedy y epsilon-decreasing
Y también puedes visitar el resto de artículos sobre Aprendizaje por refuerzo:
