Tic Tac Toe en Arduino con AI (algoritmo Minimax): 3 pasos

2024 Autor: John Day | [email protected]. Última modificación: 2024-01-30 08:43

En este Instructable, les mostraré cómo construir un juego Tic Tac Toe con una IA usando un Arduino. Puedes jugar contra el Arduino o ver cómo el Arduino juega contra sí mismo.

Estoy usando un algoritmo llamado "algoritmo minimax", que se puede usar no solo para construir una IA para Tic Tac Toe, sino también para una variedad de otros juegos como Four in a Row, damas o incluso ajedrez. Los juegos como el ajedrez son muy complejos y requieren versiones mucho más refinadas del algoritmo. Para nuestro juego Tic Tac Toe, podemos usar la versión más simple del algoritmo, que no obstante es bastante impresionante. De hecho, la IA es tan buena que es imposible vencer al Arduino.

El juego es fácil de construir. Solo necesitas algunos componentes y el boceto que he escrito. También agregué una explicación más detallada del algoritmo, si quieres entender cómo funciona.

Paso 1: construye y juega

Para construir el juego Tic Tac Toe necesitarás los siguientes componentes:

• Un Arduino Uno
• 9 LED RGB WS2812
• 9 pulsadores
• algunos alambres y cables de puente

Conecte los componentes como se muestra en el croquis de Fritzing. Luego cargue el código en su Arduino.

Por defecto, Arduino toma el primer turno. Para hacer las cosas un poco más interesantes, el primer movimiento se elige al azar. Después del primer movimiento, Arduino usa el algoritmo minimax para determinar el mejor movimiento posible. Comienzas un nuevo juego reiniciando el Arduino.

Puede ver el "pensar" de Arduino abriendo el Serial Monitor. Para cada movimiento posible, el algoritmo calcula una calificación que indica si este movimiento conducirá a una victoria (valor de 10) o una pérdida (valor de -10) para el Arduino o un empate (valor de 0).

También puede ver el juego de Arduino contra sí mismo descomentando la línea "#define DEMO_MODE" al principio del boceto. Si carga el boceto modificado, Arduino hace el primer movimiento al azar y luego usa el algoritmo minimax para determinar el mejor movimiento para cada jugador en cada turno.

Tenga en cuenta que no puede ganar contra Arduino. Cada juego terminará en empate o perderá si comete un error. Esto se debe a que el algoritmo siempre elige el mejor movimiento posible. Como sabrá, una partida de Tic Tac Toe siempre terminará en empate si ambos jugadores no se equivocan. En modo demo, cada juego termina en empate porque, como todos sabemos, las computadoras nunca cometen errores;-)

Paso 2: el algoritmo Minimax

El algoritmo consta de dos componentes: una función de evaluación y una estrategia de búsqueda. La función de evaluación es una función que asigna un valor numérico a las posiciones del tablero. Si la posición es una posición final (es decir, una posición en la que el jugador azul o el jugador rojo ha ganado o donde ningún jugador ha ganado), la función de evaluación es muy simple: digamos que el Arduino juega azul y el jugador humano juega rojo. Si la posición es una posición ganadora para el azul, la función asigna un valor de 10 a esa posición; si es una posición ganadora para el rojo, la función asigna un valor de -10 a la posición; y si la posición es un empate, la función asigna un valor de 0.

Cuando es el turno de Arduino, quiere elegir un movimiento que maximice el valor de la función de evaluación, porque maximizar el valor significa que preferirá una victoria sobre un empate (10 es mayor que 0) y preferirá un empate sobre una pérdida (0 es mayor que -10). Por un argumento análogo, el oponente quiere jugar de tal manera que minimiza el valor de la función de evaluación.

Para una posición no final, el algoritmo calcula el valor de la función de evaluación mediante una estrategia de búsqueda recursiva. Partiendo de la posición actual, simula alternativamente todos los movimientos que pueden realizar el jugador azul y el jugador rojo. Esto se puede visualizar como un árbol, como en el diagrama. Cuando llega a una posición final, comienza a retroceder, llevando el valor de la función de evaluación del nivel de recursividad inferior al nivel de recursividad superior. Asigna el máximo (si en el paso de recursividad correspondiente es el turno del jugador azul) o el mínimo (si en el paso de recursividad correspondiente es el turno del jugador rojo) de los valores de la función de evaluación desde el nivel de recursividad inferior hasta la posición en el mayor nivel de recursividad. Finalmente, cuando el algoritmo ha terminado de retroceder y ha llegado a la posición actual nuevamente, toma ese movimiento (o uno de los movimientos) que tiene el valor máximo de la función de evaluación.

Esto puede sonar un poco abstracto, pero en realidad no es tan difícil. Considere la posición que se muestra en la parte superior del diagrama. En el primer paso de recursividad, hay tres movimientos diferentes que puede realizar el azul. El azul intenta maximizar el valor de la función de evaluación. Para cada uno de los movimientos que puede realizar el azul, hay dos movimientos que puede realizar el rojo. El rojo intenta minimizar el valor de la función de evaluación. Considere el movimiento donde juega el azul en la esquina superior derecha. Si el rojo juega en el área central, el rojo ha ganado (-10). Si, por otro lado, el rojo juega en el cuadro inferior central, el azul ganará en el próximo movimiento (10). Entonces, si el azul se reproduce en la esquina superior derecha, el rojo se reproducirá en el cuadro central, ya que eso minimiza el valor de la función de evaluación. De manera análoga, si el azul juega en el recuadro inferior central, el rojo volverá a jugar en el recuadro central porque eso minimiza la función de evaluación. Si, por el contrario, el azul juega en el cuadro central, no importa qué movimiento tome el rojo, el azul siempre ganará (10). Dado que el azul quiere maximizar la función de evaluación, jugará en el cuadro central, ya que esa posición da como resultado un valor mayor de la función de evaluación (10) que los otros dos movimientos (-10).

Paso 3: Solución de problemas y pasos adicionales

Si presiona un botón y se enciende un LED diferente al correspondiente al botón, probablemente haya mezclado los cables en los pines A0-A2 o 4-6, o conectó los LED en el orden incorrecto.

También tenga en cuenta que el algoritmo no siempre elige necesariamente un movimiento que permitirá que Arduino gane lo más rápido posible. De hecho, pasé algún tiempo depurando el algoritmo porque Arduino no eligió un movimiento que hubiera sido un movimiento ganador. Me tomó un tiempo hasta que me di cuenta de que, en cambio, había elegido un movimiento que garantizaba que ganaría un movimiento más tarde. Si lo desea, puede intentar modificar el algoritmo para que siempre prefiera un movimiento ganador a uno posterior.

Una posible extensión de este proyecto sería utilizar el algoritmo para construir una IA para un 4x4 o incluso un Tic Tac Toe de 5x5. Sin embargo, tenga en cuenta que el número de posiciones que debe examinar el algoritmo crece muy rápidamente. Deberá encontrar formas de hacer que la función de evaluación sea más inteligente asignando valores a las posiciones que no son definitivas, en función de la probabilidad de que la posición sea buena o mala para el jugador en cuestión. También puede intentar hacer la búsqueda más inteligente deteniendo la recursividad antes de tiempo si un movimiento resulta ser menos digno de una exploración más profunda que los movimientos alternativos.

Arduino probablemente no sea la mejor plataforma para tales extensiones debido a su memoria limitada. La recursividad permite que la pila crezca durante la ejecución del programa y, si la pila crece demasiado, puede corromper la memoria del programa, provocando bloqueos o comportamientos erráticos. Elegí Arduino para este proyecto principalmente porque quería ver si se podía hacer y con fines educativos, no porque sea la mejor opción para este tipo de problema.