algoritmo negamax per un gioco 3 di fila su una griglia 3x4 (righe x colonne)

Question

Sto lottando con l'algoritmo negamax per il gioco 3 di fila su una griglia 3x4 (righe x colonne). Si gioca come il famoso 4 di fila, cioè i pezzi vengono lasciati cadere (NON come TicTacToe). Chiamiamo i giocatori R e B. R ha avuto la prima mossa, le mosse di B sono controllate da negamax. Le mosse possibili sono 1, 2, 3 o 4. Questa è la posizione in questione che è stata raggiunta dopo R: mossa 3 -> B: mossa 1 -> R: mossa 3:

  1   2   3   4

|   |   |   |   |

|   |   | R |   |

| B |   | R |   |

Ora, per difendersi dalla mossa 3 di R, B deve giocare la mossa 3 stessa, ma si rifiuta di farlo. Invece gioca la mossa 1 e il gioco finisce dopo la mossa successiva di R.

Ho passato l'intera giornata a cercare un errore nella mia implementazione negamax che funziona perfettamente per una griglia 3x3, tra l'altro, ma non sono riuscito a trovarne nessuno.

Poi ho iniziato a pensare: un'altra spiegazione per il comportamento dell'algoritmo negamax sarebbe che B si perde in tutte le varianti, non importa quale, dopo che R inizia il gioco con la mossa 3 su una griglia 3x4.

Qualcuno può confutare questa proposizione o indicarmi una prova (cosa che preferirei ;-))?

Grazie, RSel

Answer 1

Prova che anche B3 perde:

B3: R (1,2,4) -> R1;B (1,2,4) -> B2 (perde), quindi B1;R (2,4) -> R2 perde, quindi R4;B (2,4) -> B2 perde, quindi B4;La R perde ora su entrambe le scelte ... quindi R1 perderà per R, quindi R non lo sceglierà.

B3: R (1,2,4) -> R2 perde da B2, quindi R non lo sceglierà B3: R (1,2,4) -> R4;B2 (forzato);R2 (forzato);B perde alla prossima mossa di R

... quindi, B3 perde per B così come B1 ... quindi B ha perso in questa situazione.

MODIFICA : nel caso qualcuno si chiedesse delle altre opzioni B (2,4) alla fine di "B3: R (1,2,4) -> R1; B (1, 2,4) -> B2 (perde), quindi B1 "... sono irrilevanti, poiché non appena il Rosso sceglie R1, questo scenario mostra che B (computer) può scegliere B1 e vincere.Non importa cosa succede con le altre scelte di B: questa scelta vincerà, quindi il Rosso non può scegliere R1 o perderà.

Answer 2

È, infatti, una partita vinta fin dall'inizio.E può essere giocato abbastanza facilmente a mano.Assumerò che B eviti tutte le vittorie di 1 mossa per R e segnerà le mosse in base al colore e al punto della griglia in cui si svolge il gioco.

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)

Per quanto riguarda il tuo algoritmo, ti suggerisco di modificarlo per preferire le vittorie alle sconfitte e preferire le perdite lontane rispetto alle perdite vicine.Se lo fai, "tenterà di più" per evitare l'inevitabile perdita.