Ideen zur Schach KI

[alzaimar]

IMHO: Nein. Dein Gedankengang ist falsch. Die Bezeichnung 'GetBestMove' auch. Sie findet nicht den besten Zug, sondern nur irgend einen.
Was Du machen solltest:

Delphi-Quellcode:

Function GetBestMove (Board : TBoard; Spieler, Gegner : TSpieler; Level : Integer) : TZug;
Begin
// 1. Erzeuge eine Liste aller möglichen Züge, indem Du über jede Figur iterierst und für jede Figur alle möglichen Züge erzeugst.  
  ZugListe := CreateAllMoves (Board);
  For i:=0 To ZugListe.Count - 1 do begin
// 2. Führe jeden Zug aus und bewerte die sich ergebende Stellung. Das wird nur bei Alpha-Beta-Pruning benötigt.
    Board.Play (ZugListe[i]);
    ZugListe[i].Score := Board.Score;
// 3. Nimm den Zug wieder zurück.
    Board.UnDo (ZugListe[i]);
    End;
// 4. Sortiere die Zugliste anhand der Bewertungen der Zielstellung so, das der 'beste' Zug an erster Stelle steht. Das hilft beim Alpha-Beta-Pruning.
  ZugListe.SortByScore;
// 5. Initialisiere 'SCORE' mit -MAXINT
  Result.Score := -MaxInt;
// 6. Für jeden Zug[i] der Zugliste:
  For i:=0 To Zugliste.Count - 1 do Begin
// 6a.   Führe den Zug aus.
      Board.Play (Zugliste[i]);
// Wenn jetzt  z.B. Schachmatt ist, kann man gleich abbrechen. ZugListe[i].Score enthält ja schon die Bewertung des Matts.
     If Board.Mate Then Begin
        Result := ZugListe[i];
        Break;
        End;
     If Level = MaxLevel Then 
       S := ZugListe[i] 
     Else 
       S := GetBestMove (Board, Gegner, Spieler, Level + 1)
     If Result.Score < S.Score Then Result := ZugListe[i] 
// 6b.    Nimm den Zug[i] zurück
     Board.Undo (ZugListe[i])
    End;
//7. In Result ist jetzt der beste Zug, der mit dieser Stellung möglich ist. Allerdings wollen wir das Vorzeichen umdrehen, da der Vorteil des Spielers der Nachteil des Gegners ist.
  Result.Score := -Result.Score;
End;

Mit anderen Worten: Du führst jeden Zug Z[i] aus und schaust durch einen rekursiven Aufruf nach, was der Beste Zug ist, den der Gegner daraufhin ausführen kann. Die Bewertung dieses Zuges ist dann auch die Bewertung von Z[i] (mit umgekehrtem Vorzeichen).

Bespiel: Zug[i] = Bauer A2-A4... Bester Zug des Gegners = Schachmatt (Bewertung = 10000) --> Zug[i].Bewertung = -100000.

Zu beachten gilt hier der sog. Horizonteffekt. Das o.g. Verfahren arbeitet ja mit einer festen Vorschautiefe (Maxlevel), muss also irgendwann die Vorschau abbrechen. Wenn nun ein scheinbarer Vorteil eines Zuges (z.B. Dame geschlagen) im Folgezug ein Schachmatt zur Folge hat, sieht das Programm das nicht. Dieser Folgezug ist sozusagen jenseits des 'Horizonts'. Das Programm wird also diesen scheinbar optimalen Zug wählen.

Du benötigst also eine Heuristik, um diesen Horizonteffekt zu vermeiden. Dann noch eine Heuristik, um Zugwiederholungen zu vermeiden, ausser, der Rechner ist im Hintertreffen und will somit ein Remis provozieren.

Du nimmst Dir verdammt viel vor, gleich mit Schach anzufangen. Wieso nimmst du nicht erstmal 4-Gewinnt, Dame oder Reversi. Diese verfahren, die Du benötigst (MiniMax, Alpha-Beta-Pruning, Horizonteffektvermeidung, Stellungsbewertung, evolutionäre Optimierung etc.) kannst Du an den reilativ einfachen Spielen ausprobieren und Erfahrungen sammeln. Anschließend ist die Programmierung einer Schach-Engine nicht mehr so schwer, und Du kannst Dich auf die wirklich kniffeligen Aspekte konzentrieren (Mustererkennung, Strategien etc.).

Merke Dir: Deine KI wird entscheidend von der Stellungsbewertung und dem Einsatz von heuristischen Strategiealgorithmen abhängen. Vielleicht schaffst Du es auch noch, das Programm selbstlernend zu machen...

Viel Spass.