Jugar al tres en raya usando el aprendizaje por refuerzo

Sobre mí

Soy un científico de datos experimentado y desarrollador web con más de 4 años de experiencia. Me especializo en el uso de análisis de datos para ayudar a las empresas a tomar decisiones más inteligentes y, por lo tanto, ayudarlas a escalar. Además, ofrezco servicios de desarrollo de sitios web de extremo a extremo para ayudarlo a establecer una presencia en línea y así maximizar el alcance de su negocio y expandir su base de clientes. Además, puedo ayudarlo a integrar los servicios de IA en su pila, independientemente del tamaño de su organización. Siempre trato de integrar mis aplicaciones con principios de diseño de interfaz de usuario modernos y minimalistas que ayuden a su cliente a correlacionar su marca con la calidad.

El problema que quería resolver.

Siempre me ha fascinado el increíble trabajo realizado por OpenAI. El que más me llamó la atención fue un robot de IA que podía jugar el juego enormemente popular: Dota 2. Dota 2 solía ser el escape del mundo real para mí y mis amigos mientras estaba en la escuela secundaria. Esto me inspiró a aprender más sobre el campo de RL. Quería empezar de a poco, así que empecé con Tic Tac Toe.

El proceso de construcción Playing Tic Tac Toe usando el aprendizaje por refuerzo

‘Resolviendo Tic-Tac-Toe con un montón de código’. Un espectador entusiasta podría notar que usé la frase ‘montón de código’ simplemente porque no quería centrarme solo en las técnicas de aprendizaje por refuerzo para resolver los juegos, sino también explorar otras técnicas, aunque ineficientes, como Tree Search, Genetic Algoritmos, etc. Me hubiera encantado optar por un juego más complejo como el ajedrez, pero siendo un principiante en el campo, decidí matar mi ego y comenzar con un juego con uno de los espacios de estado más pequeños: Tic-Tac-Toe. .

Echemos un vistazo a nuestro primer gladiador:

1. El Algoritmo Minimax

El Algoritmo Minimax es una regla de decisión formulada para juegos de suma cero de 2 jugadores (Tic-Tac-Toe, Chess, Go, etc.). Este algoritmo ve unos pasos por delante y se pone en la piel de su oponente. Sigue jugando y explorando posibles estados posteriores hasta que alcanza un estado terminal que resulta en un empate, una victoria o una pérdida. Estar en cualquiera de estos posibles estados terminales tiene alguna utilidad para la IA, como estar en un estado ‘Ganador’ es bueno (la utilidad es positiva), estar en un estado ‘Pérdida’ es malo (la utilidad es negativa) y estar en un empate en ni bueno ni malo (la utilidad es neutral).

En nuestra ejecución del algoritmo Minimax para resolver Tic-Tac-Toe, funciona visualizando todos los estados futuros posibles del tablero y lo construye en forma de árbol. Cuando el estado actual del tablero se le da al algoritmo (la raíz del árbol), se divide en ‘n’ ramas (donde n denota la cantidad de movimientos que puede elegir la IA/la cantidad de celdas vacías donde la IA puede ser metido). Si alguno de estos nuevos estados es un estado terminal, no se realizan más divisiones para este estado y se le asigna una puntuación de la siguiente manera:

  • puntuación = +1 (si la IA gana)
  • puntuación = -1 (si la IA pierde)
  • puntuación = 0 (si ocurre un empate)

Sin embargo, si no hay estados terminales, cada uno de estos nuevos estados se considera como nuevas raíces y dan lugar a un árbol propio. Pero hay una trampa: dado que este es un juego de 2 jugadores y los jugadores se turnan alternativamente, por lo tanto, cada vez que avanzamos una capa más en la red, debemos cambiar el jugador que se colocaría en una de las celdas vacías. De esta manera podemos visualizar qué movimientos haría el otro jugador como resultado de nuestro movimiento. El algoritmo evalúa el mejor movimiento a realizar eligiendo el movimiento que tiene la puntuación máxima cuando es el turno de la IA y eligiendo la puntuación mínima cuando es el turno del Humano.

Código para la implementación de Minimax

Dado que el espacio de estado de Tic-Tac-Toe es tan pequeño, no podemos tener un árbol con una profundidad superior a 9. Por lo tanto, no necesitamos usar técnicas como la poda alfa-beta aquí. Lo que pasa con Minimax, sin embargo, es que asume una forma particular de jugar por parte del oponente. Por ejemplo, un jugador minimax nunca alcanzaría un estado de juego desde el cual podría perder, incluso si de hecho siempre ganara desde ese estado debido a un juego incorrecto del oponente.
Aquí hay un juego de muestra:

New Game!
----------------
|   ||   ||   |
----------------
|   ||   ||   |
----------------
|   ||   ||   |
----------------
Choose which player goes first - X (You - the petty human) or O(The mighty AI): O
AI plays move: 2
----------------
|   || O ||   |
----------------
|   ||   ||   |
----------------
|   ||   ||   |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 3
----------------
|   || O || X |
----------------
|   ||   ||   |
----------------
|   ||   ||   |
----------------
AI plays move: 9
----------------
|   || O || X |
----------------
|   ||   ||   |
----------------
|   ||   || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 5
----------------
|   || O || X |
----------------
|   || X ||   |
----------------
|   ||   || O |
----------------
AI plays move: 7
----------------
|   || O || X |
----------------
|   || X ||   |
----------------
| O ||   || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 6
----------------
|   || O || X |
----------------
|   || X || X |
----------------
| O ||   || O |
----------------
AI plays move: 4
----------------
|   || O || X |
----------------
| O || X || X |
----------------
| O ||   || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 1
----------------
| X || O || X |
----------------
| O || X || X |
----------------
| O ||   || O |
----------------
AI plays move: 8
----------------
| X || O || X |
----------------
| O || X || X |
----------------
| O || O || O |
----------------
Draw!
Wanna try again BIYTACH?(Y/N) : n

2. Aprendizaje por refuerzo

Siento que este algoritmo es más fácil de comprender, ya que podría estar usándolo todos los días sin siquiera darse cuenta. Pongamos un ejemplo práctico:

Digamos que usted es dueño de un perro. Molestaste a tu cónyuge durante meses y finalmente conseguiste al pequeño, pero esta bola de pelo (nuestro agente) necesita aprender a ir al baño. El mundo físico donde nuestro agente puede interactuar y bueno, vaya doodoo, es su entorno. El problema es simple: queremos que nuestro amigo canino haga sus necesidades en el lugar que deseamos. Pero, ¿cómo le decimos qué lugar es bueno o malo, sin intentar ‘hablar como un perro’ y parecer estúpido? Correcto, usamos un sistema de recompensas. Cada vez que nuestro agente caga en nuestra elegante alfombra, obtiene una recompensa negativa (llamándolo chico malo, revocando un premio, un golpe violento en la nariz, etc.). Cada vez que hace una caca frente a la puerta de nuestro vecino que te parece realmente molesto, obtiene una recompensa positiva (llamándolo padrino, su golosina favorita, caricias en la barriga, etc.). Con el tiempo, el agente aprende que cada vez que quiere hacer un basurero (un estado determinado), es mejor ensuciar el pavimento del vecino que la alfombra preciosa, ya que resultaría en un mejor estado, el que otorga un positivo. premio.

Explotación vs Exploración

Una de las compensaciones fundamentales en el aprendizaje por refuerzo es la compensación entre explotación y exploración. La explotación significa elegir la acción que maximiza nuestra recompensa (puede llevarnos a quedar atrapados en un óptimo local). Explorar significa elegir una acción independientemente de la recompensa que proporcione (esto nos ayuda a descubrir otros óptimos locales que nos pueden acercar al óptimo global). Hacer todo lo posible en cualquiera de ellos es dañino, toda explotación puede conducir a un agente subóptimo, y toda exploración solo nos daría un agente estúpido que sigue tomando acciones al azar.

Una estrategia ampliamente utilizada para abordar este problema, que también he utilizado en mi implementación, es la estrategia de disminución de épsilon. Funciona de la siguiente manera:

  1. Inicialice una variable ‘epsilon’, con un valor entre 0 y 1 (generalmente alrededor de 0.3)
  2. Ahora con probabilidad = épsilon, exploramos y con probabilidad = 1-épsilon, explotamos.
  3. Disminuimos el valor de épsilon con el tiempo hasta que se vuelve cero

Con esta estrategia, el agente puede explorar mejores acciones durante las primeras etapas del entrenamiento y luego explota las mejores acciones en las últimas etapas del juego. Es un poco similar a cómo funcionamos los humanos: exploramos diferentes opciones y buscamos nuevas experiencias a los 20 años (exploración), y luego decidimos una carrera profesional establecida y seguimos avanzando en ese camino (explotación).

Aprendizaje de diferencias temporales

El método de aprendizaje por refuerzo utilizado en esta implementación se denomina aprendizaje por diferencia temporal. Funciona según el principio de que cada estado tiene un valor asociado. Digamos, si un estado hace que la IA gane, tendrá un valor positivo (valor = 1). Si AI pierde en algún estado, tendrá un valor negativo (valor = -1). Todos los demás estados tendrían un valor neutral (valor = 0). Estos son los valores de estado inicializados.

Una vez que se inicia un juego, nuestro agente calcula todas las acciones posibles que puede realizar en el estado actual y los nuevos estados que resultarían de cada acción. Los valores de estos estados se recopilan de un vector state_value, que contiene valores para todos los estados posibles del juego. El agente puede entonces elegir la acción que lleva al estado con el valor más alto (explotación), o elige una acción aleatoria (exploración), dependiendo del valor de épsilon. En el transcurso de nuestro entrenamiento, jugamos varios juegos, después de cada movimiento, el valor del estado se actualiza usando la siguiente regla:

donde, V(s) — el estado actual del tablero de juego, V(s^f) — el nuevo estado del tablero después de que el agente realiza alguna acción, y alfa — parámetro de tasa de aprendizaje/tamaño de paso.

Usando esta regla de actualización, los estados que conducen a una pérdida también obtienen un valor de estado negativo (cuya magnitud depende de la tasa de aprendizaje). El agente se entera de que estar en ese estado puede provocar una pérdida en el futuro, por lo que intentará evitar aterrizar en este estado a menos que sea necesario. Por otro lado, los estados que conducen a una victoria obtienen un valor de estado positivo. El agente se entera de que estar en ese estado puede conducir a una victoria en el futuro, por lo que se animaría a estar en este estado.

Hay 2 versiones del código para este algoritmo:

  1. El código de prueba — Puedes jugar contra la IA entrenada: Enlace GitHub

  2. El código de entrenamiento – ambos jugadores son AI, donde cada uno de ellos ayuda a entrenarse mutuamente. Este es para mi escuadrón perezoso. Si prefieres tomar unas palomitas de maíz y dejar que las dos IA peleen entre ellas, aquí está el código: Enlace GitHub

El siguiente es un juego de muestra contra un bot entrenado durante ~10000 épocas.

New Game!
----------------
|   ||   ||   |
----------------
|   ||   ||   |
----------------
|   ||   ||   |
----------------
Choose which player goes first - X (You - the petty human) or O(The mighty AI): X
Oye Human, your turn! Choose where to place (1 to 9): 5
----------------
|   ||   ||   |
----------------
|   || X ||   |
----------------
|   ||   ||   |
----------------
Possible moves = [1, 2, 3, 4, 6, 7, 8, 9]
Move values = [-0.218789, -0.236198, -0.147603, -0.256198, -0.365461, -0.221161, -0.234462, -0.179749]
AI plays move: 3
----------------
|   ||   || O |
----------------
|   || X ||   |
----------------
|   ||   ||   |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 1
----------------
| X ||   || O |
----------------
|   || X ||   |
----------------
|   ||   ||   |
----------------
Possible moves = [2, 4, 6, 7, 8, 9]
Move values = [-0.633001, -0.625314, -0.10769, -0.543454, -0.265536, 0.034457]
AI plays move: 9
----------------
| X ||   || O |
----------------
|   || X ||   |
----------------
|   ||   || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 6
----------------
| X ||   || O |
----------------
|   || X || X |
----------------
|   ||   || O |
----------------
Possible moves = [2, 4, 7, 8]
Move values = [-0.255945, 0.003558, -0.2704, -0.25632]
AI plays move: 4
----------------
| X ||   || O |
----------------
| O || X || X |
----------------
|   ||   || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 2
----------------
| X || X || O |
----------------
| O || X || X |
----------------
|   ||   || O |
----------------
Possible moves = [7, 8]
Move values = [0.0, 0.03941]
AI plays move: 8
----------------
| X || X || O |
----------------
| O || X || X |
----------------
|   || O || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 7
----------------
| X || X || O |
----------------
| O || X || X |
----------------
| X || O || O |
----------------
Draw!
Wanna try again?(Y/N) : n
Suit yourself!

es la hora del show

Ahora que tenemos a nuestros 2 campeones listos, arrojémoslos al Coliseo virtual y dejemos que peleen mientras observamos con asombro. Como solo tenemos 2 de ellos en este momento, solo tendremos una batalla de TKO 1v1. Básicamente, este fue el resultado:

Results(10 games):
Minimax Wins = 0
RL Agent Wins = 10

(He convocado a un monstruo, ¿no?)

Reflexiones finales y próximos pasos

Si quieres ver el partido completo, aquí tienes el código: Código completo

Estos son los únicos algoritmos con los que he jugado todavía. Podría buscar otros algoritmos interesantes como los algoritmos genéticos, pero eso es para más adelante. Si encuentras mi escritura remotamente útil o incluso lo suficientemente divertida como para hacerte reír un poco, aplaude y deja una respuesta a continuación.

Gracias por leer ❤

Similar Posts

Leave a Reply

Your email address will not be published.