Gomoku (5 Gewinnt) - Beta Version

[alzaimar]

Das Minimax-Verfahren findet rekursiv den Zug, der die gegnerischen Vorteile MINImiert und die eigenen Vorteile MAXimiert. Der Beste (MAX) eigene Zug ist dabei der, der den schwächsten (MIN) gegenerischen Zug zulässt.

Deine Zugbewertung ist eine 'Heuristik' ohne Rekursion, quasi eine Mustererkennung. Du versuchst, bestimmte Muster zu erzwingen (Zwickmühlen) und Linienüberkreuzungen: Eine sehr gute Idee, die Dein Spiel schon mal recht stark macht. Es könnte reichen, mit dieser Funktion eine MiniMax-Strategie aufzubauen:

Hier mal ein Pseudocode für eine einfache rekursive Suche mit Minimax (aus dem Gedächtnis)

Delphi-Quellcode:

Function FindeBestenZug (Level : Integer; Spieler, Gegner : TSpieler: Brett : TSpielfeld) : Integer;
Begin
  L := ErzeugeListeAllerZüge;
  MaxS := -999999;
  Foreach Z in L Do Begin
    MakeTheMove (Brett, Spieler, Gegner, Z);                                           // Zug ausführen
    If Level = MaxZugTiefe Then
      S := BewerteStellung (Brett, Spieler, Gegner)              // Je höher der Wert, desto besser ist
    Else                                                              // die Stellung für den 'Spieler'
      S := -FindeBestenZug (Level + 1, Gegner, Spieler, Brett);     // Und dann besten Gegnerzug finden
// Hier wird der beste Gegnerzug geliefert. Wir wollen aber den Zug, der S minimiert! Deshalb das MINUS
    UndoMove  (Brett, Spieler, Gegner, Z);                                     // Zug rückgängig machen
    If S > MaxS Then Begin                 // Ist der Zug besser als alle bisherigen in diesem Versuch?
      MaxS := S;                                                                             // Merken!
      MaxZ := Z;                                               // MaxZ in Stufe 0 ist der gesuchte Zug!
    End;
  End;
 Result := MaxS; 
End;

Wie Du siehst, wird bei Zugtiefe 0 genau der Zug ermittelt, bei dem die Stellung dann am Besten ist.
Bei Zugtiefe 1 wird für jeden der möglichen Züge die Anwort des Gegners ermittelt. Gewonnen hat der Zug, bei dem die Antwort des Gegners am Schlechtesten ist. Es ist interessant, das Verhalten bei verschiedenen Werten für 'MaxZugTiefe' zu analysieren. Das Problem, was Du haben wirst ist die Liste L der möglichen Züge. Denn es gibt anfangs ja 361 davon. Danach immer noch 324 etc. Das ist zu viel!

Des weiteren spielt der sog. Horizonteffekt eine entscheidende Rolle. Nehmen wir an, durch einen perfiden Zug wird der Computer in 6 Zügen gewinnen. Wenn die Suchtiefe auf 5 eingestellt ist, würde der Computer diesen Zug einfach übersehen, weil während der Analyse die Win-Situation unentdeckt bleibt. Deshalb ist eine gute Stellungsfunktion entscheidend, die auch strategische Muster (offene 4er, doppelte 3er, Zwickmühlen etc.) korrekt bewertet und strategische Vorteile besser darstellt. Dadurch wird der Horizonteffekt zwar nicht vollständig vermieden, hier jedoch mit Sicherheit fast bedeutungslos: Eine Stellung, die 'gleich' gewonnen wird, ist leicht zu erkennen.

Ich bin mir sicher, das Du bald ein Programm hast, an dem wir uns alle die Zähne ausbeißen werden.