algoritmo negamax para un juego de 3 en fila en una cuadrícula de 3x4 (filas x columnas)

Question

Estoy luchando con el algoritmo negamax para el juego de 3 en una fila en una cuadrícula de 3x4 (filas x columnas). Se juega como el conocido 4 en raya, es decir, las piezas se sueltan (NO como TicTacToe). Llamemos a los jugadores R y B. R tuvo el primer movimiento, los movimientos de B están controlados por negamax. Los movimientos posibles son 1, 2, 3 o 4. Esta es la posición en cuestión que se alcanzó después de R: movimiento 3 -> B: movimiento 1 -> R: movimiento 3:

  1   2   3   4

|   |   |   |   |

|   |   | R |   |

| B |   | R |   |

Ahora, para defenderse del movimiento 3 de R, B tiene que jugar el movimiento 3 en sí mismo, pero se niega a hacerlo. En su lugar, juega el movimiento 1 y el juego termina después del siguiente movimiento de R.

Pasé todo el día buscando un error en mi implementación negamax que, por cierto, funciona perfectamente para una cuadrícula de 3x3, pero no pude encontrar ninguno.

Entonces comencé a pensar: otra explicación del comportamiento del algoritmo negamax sería que B se pierde en todas las variaciones, pase lo que pase, después de que R comienza el juego con el movimiento 3 en una cuadrícula de 3x4.

¿Alguien puede refutar esta proposición o señalarme una prueba (que preferiría ;-))?

Gracias, RSel

Answer 1

Prueba de que B3 también pierde:

B3: R (1, 2, 4) -> R1;B (1,2,4) -> B2 (pierde), entonces B1;R (2,4) -> R2 pierde, entonces R4;B (2,4) -> B2 pierde, entonces B4;R pierde en cualquier opción ahora ... entonces R1 perderá por R - entonces R no lo elegirá.

B3: R (1,2,4) -> R2 pierde desde B2, por lo que R no lo elegirá B3: R (1,2,4) -> R4;B2 (forzado);R2 (forzado);B pierde en el próximo movimiento de R

... entonces, B3 pierde tanto para B como para B1 ... entonces B ha perdido en esta situación.

EDITAR : en caso de que alguien se pregunte acerca de las otras opciones B (2,4) al final de "B3: R (1,2,4) -> R1; B (1, 2,4) -> B2 (pierde), entonces B1 "... son irrelevantes, ya que tan pronto como Rojo elige R1, este escenario muestra que B (computadora) puede elegir B1 y ganar.Realmente no importa lo que suceda con las otras opciones de B: esta opción ganará, por lo que Red no puede elegir R1 o perderá.

Answer 2

Es, de hecho, un juego ganado desde el principio.Y se puede jugar con bastante facilidad a mano.Asumiré que B evita todas las victorias de 1 movimiento para R, marcaré los movimientos por color y señalaré en la cuadrícula donde ocurre la jugada.

1. R3,1
  ... B1,1  2. R3,2 B3,3  3. R4,1 B2,1  4. R2,2 (and R1,2 or R4,2 wins next)
  ... B2,1  2. R3,2 B3,3  3. R2,2 B2,3  4. R1,1 (and R1,2 or R1,3 wins next)
  ... B3,2  2. R2,1 (and R1,1 or R4,1 wins next)
  ... B4,1  2. R2,1 B1,1  3. R3,2 B3,3  4. R2,2 (and R1,2 or R4,2 wins next)

En cuanto a su algoritmo, voy a sugerir que lo modifique para preferir las ganancias a las pérdidas y prefiera las pérdidas distantes a las pérdidas cercanas.Si lo hace, se "esforzará más" para evitar la pérdida inevitable.