Me encantan los juegos: ajedrez, Scrabble, lo que sea. Sin embargo, uno en el que soy vergonzosamente malo es el muy simple juego Conecta 4. Por alguna razón, eso, y el deseo de probar suerte en el lado más práctico de la ciencia de datos, me dieron la idea de construir una IA simple capaz de jugar al juego Conecta 4 con un alto nivel de habilidad.
El problema evidente aquí es que, si soy terrible en Conecta 4, ¿cómo puedo construir una IA capaz de jugarlo? Entran en escena las simulaciones de Monte Carlo. Las simulaciones de Monte Carlo son una herramienta poderosa en la ciencia de datos que utiliza un muestreo aleatorio para estimar resultados complejos. Este sólido enfoque tiene una gama sorprendentemente amplia de aplicaciones, desde la integración numérica hasta el modelado financiero y, como exploraremos, el juego de Conecta 4.
En este artículo, haré una breve introducción a las simulaciones de Monte Carlo y luego profundizaré en los detalles de cómo hacer que funcionen en Conecta 4, antes de juntar todo y compartir algo de código. Y si quieres, te daré la oportunidad de jugar con la IA tú mismo y ver cómo te va.
¡Vamos!
La idea del muestreo de Montecarlo es bastante simple: si tienes un problema que no puedes resolver analíticamente, ¿por qué no realizas experimentos aleatorios e intentas estimar una respuesta numérica? Si eso no tiene sentido todavía, no te preocupes, veremos un ejemplo en un momento. Pero primero, pongamos en orden nuestra historia.
La historia de los métodos de Monte Carlo es bastante interesante. El principal desarrollador del método fue Stanislaw Ulam, un físico tan destacado que trabajó en el Proyecto Manhattan para desarrollar la bomba atómica. Sin embargo, para nuestra historia es importante el tío de Stanislaw, que tenía un desafortunado hábito de juego que llevó a Stanislaw a bautizar el nuevo método de cálculo con el nombre del famoso casino de Monte Carlo en Mónaco.
Ahora, volvamos al ejemplo que les prometí sobre lo que significa generar muestras aleatorias.
Un ejemplo práctico
Supongamos que queremos hallar el área dentro de un círculo de radio 1. El área real de dicho círculo es, por supuesto, nuestra amiga πr² y, dado que r es 1, el área es simplemente π. Pero ¿qué sucede si no conocemos π? ¿Cómo podemos llegar a esta respuesta generando experimentos aleatorios como prescribe el método de Monte Carlo?
En primer lugar, simule puntos aleatorios en la región -1 < x < 1 y -1 < y < 1. Luego, para cada punto, observe si se encuentra dentro o fuera del círculo. A continuación, he creado simulaciones de este tipo para 10, 100, 1000 y 10 000 coordenadas aleatorias.
Lo que puedes ver es que con solo 10 puntos, el área del círculo (o la proporción que ocupa) es muy aproximada, pero a medida que agregamos más y más puntos, la proporción de puntos que se encuentran en el círculo se vuelve más consistente.
Ahora probablemente te estarás preguntando: “Bueno, estos gráficos son muy bonitos, pero ¿cuál es la verdadera conclusión?”. Es una pregunta muy acertada.
¿Observa que obtenemos una estimación de la proporción de simulaciones que dan como resultado un punto dentro del círculo? Bueno, sabemos que el área del cuadrado será 2 x 2 = 4, por lo que podemos estimar π multiplicando esta proporción por 4, porque el área del círculo es simplemente π.
La siguiente tabla resume los resultados. Observe cómo la estimación de π se acerca cada vez más al valor real a medida que aumenta el número de simulaciones.
Por supuesto, podemos hacerlo aún mejor con más simulaciones. El siguiente fragmento de código, que ejecuta cien millones de muestras, generalmente arroja un número correcto con tres decimales:
import numpy as npn = 100_000_000
points = np.random.rand(n, 2)
inside_circle = np.sum(points[:,0]**2 + points[:,1]**2 <= 1)
pi_estimate = (inside_circle / n) * 4
print(pi_estimate) # prints 3.141x
La conclusión clave aquí es que al generar simulaciones aleatorias (nuestros pares de coordenadas), podemos lograr una estimación sorprendentemente precisa para una cantidad conocida. Nuestro primer ejemplo del método de Monte Carlo en acción.
Esto es genial, pero no queremos calcular π, ¡queremos crear una IA capaz de jugar a Conecta 4! Afortunadamente, la lógica que acabamos de usar para calcular π también se puede aplicar al juego de Conecta 4.
En el ejemplo anterior hicimos dos cosas: primero generamos muestras aleatorias (pares de coordenadas) y, luego, aproximamos una cantidad (π).
Bueno, aquí haremos lo mismo. Primero, generamos muestras aleatorias como antes, pero esta vez esas muestras aleatorias elegirán movimientos aleatorios, lo que simulará juegos completos de Conecta 4.
Luego, en segundo lugar, nuevamente aproximaremos una cantidad, pero la cantidad que perseguimos es la probabilidad de ganar con cada movimiento.
Un breve repaso de las reglas
Antes de comenzar a crear simulaciones, repasemos rápidamente las reglas de Conecta cuatro. Los jugadores se turnan para colocar sus fichas de colores en cualquier columna vacía de un tablero de juego de 7 x 6. El juego termina cuando un jugador alinea cuatro fichas en cualquier dirección o cuando el tablero está lleno y se llega a un empate.
El método Monte Carlo para Conecta Cuatro
Bien, ahora que ya sabemos la teoría, es hora de ponerla en práctica y enseñarle a una IA a jugar al Conecta 4. Para encontrar el movimiento correcto en el juego del Conecta 4, debemos:
- Tome una muestra aleatoria de cada uno de los posibles movimientos legales (en qué columna colocar una ficha).
- Luego simula todo el juego desde este punto asumiendo que ambos jugadores hacen sus movimientos. completamente al azar.
- Realice un seguimiento del resultado de cada uno de los juegos aleatorios para calcular las probabilidades de ganar para cada movimiento.
- Por último, seleccione el movimiento con la mayor probabilidad de ganar.
Eso suena muy simple ¡y en realidad lo es!
Para ver este método en acción, aquí hay una implementación en Python de esta lógica que escribí para jugar al juego Conecta 4. Hay un poco de información, pero no te preocupes si no tiene todo sentido: los detalles de implementación reales son menos importantes que el concepto.
Dicho esto, para aquellos interesados el enfoque hace uso de programación orientada a objetos, con una clase Jugador capaz de realizar movimientos en una clase Tablero.
En la práctica, funciona de la siguiente manera: empezamos con una lista de posibles movimientos válidos y los extraemos al azar. Para cada movimiento, llamamos a la función `_simulate_move`, que simulará un juego completo a partir de ese punto y devolverá el símbolo ganador. Si ese símbolo coincide con el del jugador de la IA, incrementamos las ganancias. Después de ejecutar numerosas simulaciones, calculamos las tasas de ganancias para cada movimiento y, finalmente, devolvemos el movimiento correspondiente a la tasa de ganancias más alta.
def _get_best_move(self, board: Board, num_sims: int):# Get a list of all viable moves
win_counts = {column: 0 for column in range(board.width) if board.is_valid_move(column)}
total_counts = {column: 0 for column in range(board.width) if board.is_valid_move(column)}
valid_moves = list(win_counts.keys())
for _ in range(num_sims):
column = random.choice(valid_moves) # Pick a move a random
result = self._simulate_move(board, column) # Simulate the game after making the random move
total_counts[column] += 1
if result == self.symbol: # Check whether the AI player won
win_counts[column] += 1
win_rates = {column: win_counts[column] / total_counts[column] if total_counts[column] > 0 else 0 for column in valid_moves}
best_move = max(win_rates, key=win_rates.get) # Find the move with the best win rate
return best_move
En resumen, al simular movimientos aleatorios y rastrear el juego desde ese punto, este enfoque de Monte Carlo ayuda a la IA a comenzar a realizar movimientos mucho más inteligentes que si simplemente estuviera adivinando.
Algunos ejemplos prácticos:
¡Basta de código! Pongamos a prueba la IA y veamos cómo se comporta en un par de posiciones. A continuación, analizaremos dos posiciones diferentes y mostraremos el resultado del bloque de código anterior. La primera situación es bastante simple y la segunda tiene un poco más de matices.
Es el turno del rojo y la mejor jugada obvia es jugar en la quinta columna. Si simulamos 1000 partidas aleatorias desde esta posición utilizando el método anterior, el jugador de IA crea las siguientes tasas de ganancias. Colocar una ficha en la columna 5 da como resultado una victoria cada vez (¡como debería ser!) y es elegido.
¡Fantástico! Nuestra IA puede identificar un movimiento ganador cuando está disponible. Es un escenario simple, sí, pero para ser honesto, me he perdido muchas victorias en el juego antes…
Ahora, veamos otra posición. Esta es un poco más complicada. ¿Tienes una idea de lo que debería jugar Rojo para evitar que Amarillo obtenga una ventaja ganadora?
La clave aquí es evitar que el amarillo cree una formación de 3 en raya abierta, lo que llevaría a una victoria. ¡El rojo necesita bloquear esto jugando en la 3.ª o la 6.ª columna! Simulando 1000 juegos desde esta posición obtenemos las siguientes tasas de victorias. Observe que la IA identifica correctamente los dos movimientos de bloqueo (columnas 3 y 6) como los que tienen las tasas de victorias más altas. Además, se dio cuenta de que la columna 6 tiene la mayor probabilidad de ganar y la selecciona.
¡Compruébelo usted mismo! Puede desafiar a la IA aquí: https://fourinarowgame.online/ La dificultad se basa en ajustar la cantidad de simulaciones. Fácil simula 50 juegos, moderado simula 500 juegos y difícil simula 1500 juegos. Personalmente, puedo superar el modo fácil con bastante regularidad, ¡pero eso es todo!
Bien, vamos a ponerlo todo junto. Al escribir este artículo, quería hacer dos cosas. Primero, quería demostrar el poder del método de Monte Carlo para un cálculo sencillo como estimar π mediante la simulación de coordenadas aleatorias.
A continuación, y lo que es más interesante, quería mostrar la fuerza de este mismo enfoque en los juegos de mesa. Lo fascinante es que, a pesar de no saber nada de la estrategia de Conecta 4, es perfectamente posible simular partidas aleatorias y terminar con un oponente controlado por IA capaz de jugar a un nivel bastante alto.
Como siempre, gracias por leer y hasta la próxima.