Construyendo un algoritmo de IA para el desafío Tic-Tac-Toe

Como parte del plan de estudios de freeCodeCamp, tuve el desafío de crear una aplicación web Tic-Tac-Toe. Ha sido un verdadero placer.

La aplicación incluye un reproductor de computadora definitivo. Puede optimizar cualquier situación dada en el tablero Tic-Tac-Toe. El resultado me sorprendió.

Incluso en un juego tan simple, el jugador de la computadora me enseñó algunos movimientos nuevos. En cuanto al código que escribí, es algo único e interesante de explorar.

Echale un vistazo

Visita este enlace y elige jugar contra la computadora. Te desafío a ganar . Puede encontrar ... que no puede.

Sin embargo, si eres duro con la defensa, es posible que descubras que la computadora tampoco puede ganar. Aprendí por experiencia que Tic-Tac-Toe tiene una estrategia simple de no perder .

Esto significa que si logra empatar, está tomando las decisiones defensivas correctas. La computadora todavía optimiza sus movimientos. Por lo tanto, el mejor resultado que puede lograr contra un jugador como tú podría ser solo un empate.

Pasos principales de la solución

1. estructura de datos del tablero

_gameBoard: [[“”, “”, “”],[“”, “”, “”],[“”, “”, “”]]

La placa Array contiene 3 matrices, cada una de las cuales representa una fila.

Cada matriz de filas contiene 3 elementos de caracteres o cadenas.

Estos elementos son:

  • "" Como una cadena vacía, que representa una celda vacía
  • "X" que representa al jugador X
  • "O" que representa al jugador O

2. función getResult

Comienza en la línea 59

En cualquier estado dado, el tablero estará en uno y solo uno de estos estados posibles:

  • Incompleto
  • el jugador X ganó
  • El jugador O ganó
  • o una corbata

La getResultfunción recibe una matriz de tablero, itera sobre todas las filas, a través de todas las columnas y en ambas diagonales. Comprueba la sucesión de símbolos. Luego nos permite conocer el estado actual de esa placa.

3. Función getBestMove

Aquí se vuelve más difícil. Cuando el tablero está vacío es muy difícil identificar la mejor jugada posible. Eche un vistazo a este tablero.

¿Cuál es la mejor jugada posible?

Cuando el tablero se llena, el mejor movimiento posible aparece ante nuestros ojos.

Usemos este tablero poblado como nuestro punto de partida. Decidamos que el próximo movimiento es nuestro y que nuestro símbolo es una "X".

Intentemos identificar el mejor movimiento posible con las herramientas que ya tenemos. Hay 3 celdas vacías que se corresponden con 3 movimientos posibles. Comprobemos el resultado de cada una de estas opciones.

Podemos hacer esto iterando sobre los posibles movimientos y para cada uno de ellos:

  • Crea un tablero nuevo
  • Agrega nuestro símbolo a la celda vacía correspondiente
  • Envía este tablero a la getResultfunción

De los 3 tableros de la figura anterior, cuando enviemos el segundo tablero a la getResult función, recibiremos nuestro trofeo.

Concéntrese en los siguientes pasos esenciales:

  1. Necesitamos calificar los posibles movimientos para poder compararlos. Decidamos que si un movimiento da como resultado una tabla ganadora, la calificaremos 1. Si da como resultado una tabla perdedora, recibirá la calificación de -1. Un empate recibirá una calificación de 0.
  2. El movimiento 2 recibirá una calificación de 1. Cuando encontremos un movimiento calificado con 1, podemos ignorar todos los demás movimientos posibles. No hay otro movimiento mejor posible que una victoria definitiva.
  3. Pero en aras de la comprensión, ¿cómo calificaríamos los movimientos 1 o 3, o cualquier otro movimiento con un resultado incompleto?

Centrémonos en el movimiento 3. La solución es enviar la placa correspondiente de forma recursiva a la getBestMovefunción.

Quizás esté pensando, “¡Pero espere! Nuestro oponente juega el siguiente movimiento ". Así es. Averigüemos qué calificación obtiene nuestro oponente por su mejor movimiento futuro.

Nuestro oponente solo tiene dos movimientos posibles:

El movimiento 3-1 ganará el juego a favor de nuestro oponente. Dado que estamos utilizando exactamente la misma getBestMovefunción, Move 3–1 recibirá una calificación de 1.

Esto puede resultar un poco confuso, ya que tanto nuestra victoria como nuestra derrota recibirán una calificación de 1. Debemos recordar que esta llamada a función pertenece a nuestro oponente, y su victoria es nuestra pérdida y viceversa.

Debemos negar cualquier calificación devuelta a la getBestMovefunción por la getBestMovefunción.

Move 3–1 recibe una calificación de 1. La getBestMovefunción devuelve una calificación de 1, y podemos calificar Move 3 con -1.

De esta manera, la getBestMovefunción continúa explorando movimientos y movimientos consiguientes. Este proceso continuará hasta que:

  1. Encuentra un movimiento calificado con 1, en cuyo caso devolverá el movimiento inmediatamente
  2. Continuará hasta que cada posible movimiento tenga una calificación. Los posibles movimientos (con grados 0 y -1) se almacenan en una matriz
  3. La matriz será entonces:

    [a] aleatorizado

    [b] ordenados de mayor a menor

    [c] se devolverá el primer elemento

Estos pasos garantizan que:

  1. Se evitará un movimiento perdedor a menos que sea la única opción
  2. El reproductor de la computadora puede jugar de forma diversa

Notas finales:

  1. Existen fuertes preocupaciones legítimas sobre los riesgos que conlleva la inteligencia artificial (IA).

    Usemos la IA en beneficio de todos.

    El mejor software de IA posible es el que puede evitar que hagamos un mal uso de la IA.

  2. Consulté a Assaf Weinberg en el proceso de redacción de la aplicación.

Ver mi código en GitHub.