negamax algorithme pour un jeu 3-in-a-rangée sur une grille de 3x4 (lignes x colonnes)

Question

Je lutte avec le negamax algorithme de jeu 3-in-a-rangée sur une grille de 3x4 (lignes x colonnes). Il se joue comme le bien connu 4 en une rangée, à savoir les pièces tombent (pas comme morpion). Appelons les acteurs de la R et B. R a le premier mouvement, les mouvements de B sont contrôlés par negamax. mouvements possibles sont 1, 2, 3 ou 4. Cette position en question qui a été atteint après R: mouvement 3 -> B: déplacer 1 -> R: mouvement 3:

  1   2   3   4

|   |   |   |   |

|   |   | R |   |

| B |   | R |   |

, afin de se défendre contre 3 mouvement par R, B doit jouer 3 déplacer lui-même, mais il refuse de le faire. il joue au lieu 1 mouvement et le jeu est terminé après le prochain mouvement de R.

J'ai passé toute la journée à la recherche d'une erreur dans ma mise en œuvre negamax qui fonctionne parfaitement pour une grille 3x3, en passant, mais je ne pouvais pas trouver.

Alors je commencé à penser: Une autre explication pour le comportement de l'algorithme negamax serait que B est perdue dans toutes les variantes, peu importe ce que, après R commence le jeu avec mouvement 3 sur une 3x4 grille

.

Quelqu'un peut-il réfuter cette proposition ou me pointer vers une preuve (que je préférerais ;-))?

Merci, RSEL

Answer 1

La preuve que B3 perd ainsi:

B3: R (1,2,4) -> R1; B (1,2,4) -> B2 (perd), de sorte B1; R (2,4) -> R2 perd, alors R4; B (2,4) -> B2 perd, donc B4; R perd maintenant de chaque choix ... alors R1 perd R -. Si R ne choisir

B3: R (1,2,4) -> R2 perd depuis B2, alors R ne sera pas choisir B3: R (1,2,4) -> R4; B2 (forcé); R2 (forcé); B perd le prochain mouvement de R

... alors, B3 perd B ainsi que B1 ... si B a perdu dans cette situation.

modifier : Au cas où quelqu'un se demande sur les autres options B (2,4) à la fin de « B3: R (1,2,4) -> R1; B (1 , 2,4) -> B2 (perd), de sorte que B1 » ... ils ne sont pas pertinentes, car dès que Red choisit R1, ce scénario montre que B (ordinateur) peut choisir B1 et gagner . Il ne compte pas vraiment ce qui se passe avec d'autres choix de B -. Ce choix va gagner, si rouge ne peut pas choisir R1 ou il perdra

Answer 2

Il est, en fait, un jeu gagné dès le départ. Et peut être joué par assez facilement à la main. Je suppose que B évite toutes les victoires 1 déplacement pour R, et marquerai se déplace par couleur, et repérer dans la grille où le jeu se passe.

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 ce qui concerne votre algorithme, je vais suggérer que vous modifiez à préférer des victoires sur les pertes, et préfèrent les pertes lointaines sur les pertes près. Si vous faites cela, il va « essayer plus fort » pour éviter la perte inévitable.