Negamax-Algorithmus für ein 3-in-a-Row-Spiel in einem 3x4-Raster (Zeilen x Spalten)

Question

Ich habe Probleme mit dem Negamax-Algorithmus für 3-in-a-Row-Spiele in einem 3x4-Raster (Zeilen x Spalten). Es wird wie das bekannte 4-in-a-Row gespielt, d. H. Die Stücke werden fallen gelassen (NICHT wie TicTacToe). Nennen wir die Spieler R und B. R hatte den ersten Zug, B's Züge werden von Negamax gesteuert. Mögliche Züge sind 1, 2, 3 oder 4. Dies ist die fragliche Position, die nach R: Zug 3 -> B: Zug 1 -> R: Zug 3: erreicht wurde

  1   2   3   4

|   |   |   |   |

|   |   | R |   |

| B |   | R |   |

Um sich jetzt gegen Zug 3 durch R zu verteidigen, muss B Zug 3 selbst spielen, weigert sich jedoch, dies zu tun. Stattdessen wird Zug 1 gespielt und das Spiel ist nach Rs nächstem Zug beendet.

Ich habe den ganzen Tag nach einem Fehler in meiner Negamax-Implementierung gesucht, der übrigens perfekt für ein 3x3-Raster funktioniert, aber ich konnte keinen finden.

Dann fing ich an zu denken: Eine andere Erklärung für das Verhalten des Negamax-Algorithmus wäre, dass B in allen Variationen verloren geht, egal was passiert, nachdem R das Spiel mit Zug 3 auf einem 3x4-Gitter gestartet hat.

Kann jemand diesen Vorschlag widerlegen oder mich auf einen Beweis hinweisen (den ich bevorzugen würde ;-))?

Danke, RSel

Answer 1

Beweis, dass auch B3 verliert: B3: R (1,2,4) -> R1;B (1,2,4) -> B2 (verliert), also B1;R (2,4) -> R2 verliert, also R4;B (2,4) -> B2 verliert, also B4;R verliert jetzt bei jeder Wahl ... also wird R1 für R verlieren - also wird R es nicht wählen.

B3: R (1,2,4) -> R2 verliert seit B2, daher wird R es nicht wählen B3: R (1,2,4) -> R4;B2 (gezwungen);R2 (gezwungen);B verliert bei Rs nächstem Zug

... also verliert B3 sowohl für B als auch für B1 ... also hat B in dieser Situation verloren.

BEARBEITEN : Nur für den Fall, dass sich jemand über die anderen B-Optionen (2,4) am Ende von "B3: R (1,2,4) -> R1; B (1" wundert, 2,4) -> B2 (verliert), also B1 "... sie sind irrelevant, da dieses Szenario zeigt, dass B (Computer) B1 wählen und gewinnen kann, sobald Rot R1 wählt.Es spielt keine Rolle, was mit den anderen Entscheidungen von B passiert - diese Wahl wird gewinnen, also kann Rot nicht R1 wählen oder er wird verlieren.

Answer 2

Es ist in der Tat von Anfang an ein gewonnenes Spiel.Und kann ziemlich einfach von Hand durchgespielt werden.Ich gehe davon aus, dass B alle 1-Zug-Siege für R vermeidet und Züge nach Farbe markiert und im Raster die Stelle markiert, an der das Spiel stattfindet.

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)

Was Ihren Algorithmus betrifft, werde ich vorschlagen, dass Sie ihn so ändern, dass Gewinne gegenüber Verlusten bevorzugt werden und entfernte Verluste gegenüber nahen Verlusten bevorzugt werden.Wenn Sie dies tun, wird es "härter versuchen", den unvermeidlichen Verlust zu vermeiden.