algorithm - toe - ¿Qué algoritmo para un juego de tres en raya puedo usar para determinar el "mejor movimiento" para la IA?

ultimate tic tac toe c#

Question

En una implementación de tres en raya creo que la parte más difícil es determinar el mejor movimiento para que la máquina juegue.

¿Cuáles son los algoritmos que se pueden perseguir? Estoy buscando implementaciones desde simples a complejas. ¿Cómo abordaría esta parte del problema?

Answer 1

Aquí hay una solución que considera todos los movimientos posibles, y las consecuencias de cada movimiento para determinar el mejor movimiento posible.

necesitaremos una estructura de datos que represente a la junta. Representaremos al tablero con una matriz bidimensional. La matriz externa representa toda la placa y una matriz interna representa una fila. Aquí está el estado de un tablero vacío.

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

Vamos a poblar el tablero con caracteres ''x'' y ''o''.

Luego necesitaremos una función que pueda verificar el resultado. La función verificará una sucesión de caracteres. Sea cual sea el estado del tablero, el resultado es una de las 4 opciones: Incompleto, jugador X ganado, Jugador O ganado o empate. La función debería devolver cuál es el estado de la placa.

const SYMBOLS = {
  x:''X'',
  o:''O''
}
const RESULT = {
  incomplete: 0,
  playerXWon: SYMBOLS.x,
  playerOWon: SYMBOLS.o,
  tie: 3
}
  function getResult(board){
      // returns an object with the result

      let result = RESULT.incomplete
      if (moveCount(board)<5){
        {result}
      }

      function succession (line){
        return (line === symbol.repeat(3))
      }

      let line

      //first we check row, then column, then diagonal
      for (var i = 0 ; i<3 ; i++){
        line = board[i].join('''')
        if(succession(line)){
          result = symbol;
          return {result};
        }
      }

      for (var j=0 ; j<3; j++){
        let column = [board[0][j],board[1][j],board[2][j]]
        line = column.join('''')
        if(succession(line)){
          result = symbol
          return {result};
        }
      }

      let diag1 = [board[0][0],board[1][1],board[2][2]]
      line = diag1.join('''')
      if(succession(line)){
        result = symbol
        return {result};
      }

      let diag2 = [board[0][2],board[1][1],board[2][0]]
      line = diag2.join('''')
      if(succession(line)){
        result = symbol
        return {result};
      }

      //Check for tie
      if (moveCount(board)==9){
        result=RESULT.tie
        return {result}
      }

      return {result}
    }

Ahora podemos agregar la función getBestMove, proporcionamos cualquier tablero dado, y el siguiente símbolo, la función se ejecutará, verifica todos los movimientos posibles con la función getResult. Si es un triunfo, le otorgará un puntaje de 1. Si es un puntaje flojo obtendrá un puntaje de -1, un empate obtendrá un puntaje de 0. Si no está determinado, usaremos la función obtener MáximoMovimiento recursivamente para descubrir el puntaje del siguiente movimiento. Como el siguiente movimiento es del oponente, su victoria es la pérdida del jugador actual, y el puntaje será negado. Al final, el movimiento posible recibe un puntaje de 1,0 o -1, podemos ordenar los movimientos y devolver el movimiento con el puntaje más alto.

  function getBestMove (board, symbol){

    function copyBoard(board) {
      let copy = []
       for (let row = 0 ; row<3 ; row++){
        copy.push([])
        for (let column = 0 ; column<3 ; column++){
          copy[row][column] = board[row][column]
        }
      }
      return copy
    }

    function getAvailableMoves (board) {
      let availableMoves = []
      for (let row = 0 ; row<3 ; row++){
        for (let column = 0 ; column<3 ; column++){
          if (board[row][column]===""){
            availableMoves.push({row, column})
          }
        }
      }
      return availableMoves
    }

    let availableMoves = getAvailableMoves(board)

    let availableMovesAndScores = []

    for (var i=0 ; i<availableMoves.length ; i++){
      let move = availableMoves[i]
      let newBoard = copyBoard(board)
      newBoard = applyMove(newBoard,move, symbol)
      result = getResult(newBoard,symbol).result
      let score
      if (result == RESULT.tie) {score = 0}
      else if (result == symbol) {
        score = 1
      }
      else {
        let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x
        nextMove = getBestMove(newBoard, otherSymbol)
        score = - (nextMove.score)
      }
      if(score === 1)
        return {move, score}
      availableMovesAndScores.push({move, score})
    }

    availableMovesAndScores.sort((moveA, moveB )=>{
        return moveB.score - moveA.score
      })
    return availableMovesAndScores[0]
  }

Algoritmo en acción , Github , explicando el proceso en más detalles

Answer 2

Clasifica cada uno de los cuadrados con puntajes numéricos. Si se toma un cuadrado, avance a la siguiente opción (ordenada en orden descendente por rango). Vas a tener que elegir una estrategia (hay dos principales para ir primero y tres (creo) para el segundo). Técnicamente, podría simplemente programar todas las estrategias y luego elegir una al azar. Eso haría un oponente menos predecible.

Answer 3

El método de fuerza bruta de generar cada tablero posible y calificarlo basado en las tablas que luego produce más abajo no requiere mucha memoria, especialmente una vez que reconoces que las rotaciones de 90 grados son redundantes, como lo son las vueltas verticales, eje horizontal y diagonal.

Una vez que llegas a ese punto, hay algo así como menos de 1k de datos en un gráfico de árbol para describir el resultado y, por lo tanto, el mejor movimiento para la computadora.

-Adán

Answer 4

Esta respuesta supone que usted comprende la implementación del algoritmo perfecto para P1 y discute cómo lograr una victoria en condiciones contra jugadores humanos normales, quienes cometerán algunos errores más comúnmente que otros.

El juego, por supuesto, debe terminar en empate si ambos jugadores juegan de manera óptima. A nivel humano, jugar P1 en una esquina produce victorias con mucha más frecuencia. Por la razón psicológica que sea, P2 cree que jugar en el centro no es tan importante, lo cual es desafortunado para ellos, ya que es la única respuesta que no crea un juego ganador para P1.

Si P2 se bloquea correctamente en el centro, P1 debería jugar en la esquina opuesta, porque de nuevo, por cualquier razón psicológica, P2 preferirá la simetría de jugar en una esquina, lo que a su vez generará un tablero perdedor para ellos.

Para cualquier movimiento que P1 pueda hacer para el movimiento inicial, hay un movimiento que P2 puede hacer que creará una victoria para P1 si ambos jugadores juegan de manera óptima después de eso. En ese sentido, P1 puede jugar donde sea. Los movimientos de borde son más débiles en el sentido de que la fracción más grande de posibles respuestas a este movimiento produce un empate, pero todavía hay respuestas que crearán una victoria para P1.

Empíricamente (más precisamente, anecdóticamente), los mejores movimientos iniciales de P1 parecen ser la primera esquina, el segundo centro y el último borde.

El siguiente desafío que puede agregar, en persona o a través de una GUI, no es mostrar la pizarra. Un ser humano definitivamente puede recordar todo el estado, pero el desafío adicional lleva a una preferencia por tableros simétricos, que requieren menos esfuerzo para recordar, lo que lleva al error que describí en la primera rama.

Soy muy divertido en las fiestas, lo sé.

Answer 5

La estrategia de Wikipedia para jugar un juego perfecto (ganar o empatar todas las veces) parece ser un pseudocódigo directo:

Cita de Wikipedia (Estrategia Tic Tac Toe #)

Un jugador puede jugar un juego perfecto de Tic-tac-toe (para ganar o, al menos, dibujar) si elige el primer movimiento disponible de la siguiente lista, cada turno, como se usa en Newell y Simon en 1972 tic-tac-toe programa. [6]

1. Ganar: si tienes dos en una fila, juega el tercero para obtener tres en una fila.

2. Bloque: si el oponente tiene dos seguidos, juega el tercero para bloquearlos.

3. Tenedor: crea una oportunidad donde puedas ganar de dos maneras.

4. Bloque del tenedor del oponente:

   Opción 1: crea dos en una fila para forzar al oponente a defenderse, siempre y cuando no resulte en que creen un tenedor o ganen. Por ejemplo, si "X" tiene una esquina, "O" tiene el centro, y "X" también tiene la esquina opuesta, "O" no debe jugar en una esquina para ganar. (Jugar en una esquina en este escenario crea una bifurcación para que "X" gane).

   Opción 2: si hay una configuración donde el oponente puede bifurcar, bloquea esa bifurcación.

5. Centro: Juega el centro.

6. Esquina opuesta: si el oponente está en la esquina, juega en la esquina opuesta.

7. Esquina vacía: juegue una esquina vacía.

8. Lado vacío: juega un lado vacío.

Reconocer cómo se ve una situación de "tenedor" podría hacerse de una manera bruta como se sugiere.

Nota: Un oponente "perfecto" es un buen ejercicio pero no vale la pena jugar contra él. Sin embargo, podría alterar las prioridades anteriores para dar debilidades características a las personalidades adversarias.

Answer 6

Lo que necesitas (para tic-tac-toe o un juego mucho más difícil como el ajedrez) es el algoritmo minimax , o su variante ligeramente más complicada, la poda alfa-beta . Sin embargo, el minimax ingenuo ordinario funcionará bien para un juego con un espacio de búsqueda tan pequeño como el tic-tac-toe.

En pocas palabras, lo que quiere hacer no es buscar el movimiento que tenga el mejor resultado posible para usted, sino más bien el movimiento donde el peor resultado posible sea lo mejor posible. Si asumes que tu oponente está jugando de manera óptima, debes asumir que tomarán el movimiento que sea peor para ti y, por lo tanto, debes realizar el movimiento que minimice su ganancia máxima.

Answer 7

Puede hacer que la IA se reproduzca en algunos juegos de muestra para aprender. Use un algoritmo de aprendizaje supervisado para ayudarlo.

Answer 8

Un algo típico para tic-tac-toe debería verse así:

Tablero: un vector de nueve elementos que representa el tablero. Almacenamos 2 (indicando Blanco), 3 (indicando X) o 5 (indicando O). Turn: un entero que indica qué jugada del juego está por jugarse. El primer movimiento se indicará con 1, último con 9.

El algoritmo

El algoritmo principal usa tres funciones.

Make2: devuelve 5 si el cuadrado central de la placa está en blanco, es decir, si la placa [5] = 2. De lo contrario, esta función devuelve cualquier cuadrado que no sea esquina (2,4,6 u 8).

Posswin (p): devuelve 0 si el jugador p no puede ganar en su próximo movimiento; de lo contrario, devuelve el número de cuadrados que constituye un movimiento ganador. Esta función permitirá ganar tanto al programa como a los oponentes. Esta función funciona al verificar cada una de las filas, columnas y diagonales. Al multiplicar los valores de su cuadrado por una fila entera (o columna o diagonal), se puede verificar la posible situación de victoria. Si el producto es 18 (3 x 3 x 2), entonces X puede ganar. Si el producto es 50 (5 x 5 x 2), entonces O puede ganar. Si se encuentra una fila ganadora (columna o diagonal), se puede determinar el cuadrado en blanco y esta función devuelve el número de ese cuadrado.

Ir (n): hace un movimiento en el cuadrado n. este procedimiento establece la placa [n] en 3 si Turn es impar, o 5 si Turn es par. También aumenta el turno por uno.

El algoritmo tiene una estrategia incorporada para cada movimiento. Hace el movimiento de número impar si juega X, el movimiento de número par si juega O.

Turn =1 Go(1)   (upper left corner).
Turn =2 If Board[5] is blank, Go(5), else Go(1).
Turn =3 If Board[9] is blank, Go(9), else Go(3).
Turn =4 If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn =5 if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn =6 If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn =7 If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn =8 if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn =9 Same as Turn=7.

Lo he usado Déjame saber cómo te sientes.

Answer 9

Un intento sin usar un campo de juego.

1. para ganar (tu doble)
2. si no, no perder (doble del oponente)
3. si no, ¿ya tienes un tenedor (tiene un doble doble)
4. si no, si el oponente tiene un tenedor
   
   1. buscar en puntos de bloqueo para un posible doble y tenedor (victoria final)
   2. si no busca bifurcaciones en puntos de bloqueo (lo que le da al oponente la mayor cantidad de posibilidades de perder)
   3. si no solo puntos de bloqueo (no perder)
5. si no busca el doble y el tenedor (victoria final)
6. si no busca solo tenedores que le den al oponente la mayor cantidad de posibilidades de perder
7. si no busca solo un doble
8. si no es callejón sin salida, empate, al azar.
9. si no (significa su primer movimiento)
   
   1. si es el primer movimiento del juego;
      
      1. darle al oponente la posibilidad más perdedora (el algoritmo da como resultado solo las esquinas, lo que da 7 posibilidades de perder el oponente)
      2. o para romper el aburrimiento al azar.
   2. si es el segundo movimiento del juego;
      
      1. encuentra solo los puntos que no pierden (da un poco más de opciones)
      2. o encuentre los puntos en esta lista que tenga la mejor oportunidad de ganar (puede ser aburrido, ya que solo da como resultado todas las esquinas o las esquinas adyacentes o centro)

Nota: Cuando tienes doble y tenedor, comprueba si tu doble da al oponente un doble. Si esto te da, comprueba si tu nuevo punto obligatorio está incluido en tu lista de tenedores.

Answer 10

Ya que solo está tratando con una matriz de 3x3 de posibles ubicaciones, sería muy fácil simplemente escribir una búsqueda a través de todas las posibilidades sin gravar su poder de cómputo. Para cada espacio abierto, calcule a través de todos los resultados posibles después de marcar ese espacio (recursivamente, diría), luego use el movimiento con la mayor cantidad de posibilidades de ganar.

Optimizar esto sería una pérdida de esfuerzo, de verdad. Aunque algunos más fáciles podrían ser:

• Verifique primero las posibles victorias para el otro equipo, bloquee la primera que encuentre (si hay dos juegos de todos modos).
• Siempre toma el centro si está abierto (y la regla anterior no tiene candidatos).
• Tome las esquinas por delante de los lados (de nuevo, si las reglas anteriores están vacías)