Hallo,
ich wollte mich mal an dem Alpha-beta Algorithmus versuchen. Für mich ist es eines der schwierigst zu verstehenden Dinge wie es funktioniert. Ortientiert habe ich mich an dem Beispiel bei Wikipedia (
https://de.wikipedia.org/wiki/Alpha-Beta-Suche Abschnitt "Die NegaMax-Variante lautet:").
Trotzdem komme ich nicht wirklich auf einen Nenner und mit Raten komme ich nicht wirklich weiter
Vielleicht kann mir von euch jemand weiterhelfen?
Die Alpha-Beta Suche möchte ich in einem Schachprogramm umsetzen (scheint vielleicht zu kompliziert, aber ich kenne die Regeln von Schach. In anderen Spielen wie Damen, Go & Go kenne ich die Regeln nicht) .
Erstmal die eigentliche Funktion (siehe oberen Wikipedia abschnitt):
Delphi-Quellcode:
// In Wikipedia wird die Funktion mit Variable "Spieler" begonnen => was ist denn damit gemeint in meinem Fall?! Das Brett zur Bewertung?! eine ID ?? Farbe?!
// am_zug habe ich hinzugefügt => w / b für weiß oder schwarz
function miniMax(id:integer; tiefe:integer;alpha:integer;beta:integer;am_zug:string;stellung_lang:string): integer;
var
maxWert,a,wert: integer;
begin
if (tiefe = 0 {OR keine zügemehr}) then begin result := bewertung(zugliste[id].stellung_lang ,am_zug); end;
maxWert := alpha;
zuggenerator(stellung_lang,am_zug,id);
for a := 0 to length(zugliste)-1 do begin
// Zug vor?!
wert := -miniMax(id,tiefe-1,-beta,-maxWert,farbwechsel(am_zug),zugliste[a].stellung_lang);
// Zug zurück?!
if (wert > maxWert) then begin
maxWert := wert;
if maxWert >= beta then begin break; end;
//if tiefe = anfangstiefe then begin end; // Was soll hier geschehen?!
end;
end;
result := maxWert;
end;
Wie man sieht ist es dem Wikipedia Artikel sehr ähnlich. Ich habe bei der Umsetzung Kommentare rein gemacht, wo ich mir Unklar bin.
Der Zuggenerator entwirft eine Möglichkeit aller Züge und fügt sie ein ein Zugliste ein "array of Tzugliste (=Record)".
Delphi-Quellcode:
type
Tzugliste = record
id: integer;
kommt_von_id: integer;
zug: string;
stellung_lang: string;
wert: integer;
{es ginge noch mehr, wenn ich nur wüsste was ich bräuchte}
end; // of Record
var
zugliste: array of Tzugliste;
Daher bin ich mir bei der Funktion mit "Zug vor/zurück" unklar. Ich habe das in eine Forschleife gemacht und nicht in einer while wie im Pseude Code - daher brauche ich das nicht?!?
Die untere Zeile tiefe = anfangstiefe verstehe ich gleich überhaupt nicht.
Und wie ich auf das "Ergebnis" komme, weiß ich auch nicht. Wie stelle ich fest was denn letztendlich der beste Zug ist und mit welcher Bewertung, in der Funktion? (Zweitrang aber evtl. für Fehleranalysen Interessant: Kann ich das evtl. grafisch nachvollziehen wie er den Baum durchlaufen hat?!)
Eine Stellung bewertung - geschieht das in der Alpha-Beta Funktion, oder muss dies bereits vorher geschehen?
Viele Fragen,... ich hoffe das meine obige Funktion und Auschnitt ausreicht um mir weiterzuhelfen. Andernfalls lade ich den derzeitgen Stand das Schachprogramm hoch für den Download (wäre hier sonst zu großer TExt).
"Schach spielen" kann das Programm übrigens noch nicht. Mir ging es per Se nur um die Alpha Beta Funktion und habe das Programm nur soweit ausgebaut um ein paar Figuren zu bewegen. Trotzdem sollte aber schon diese Funktion "greifen". Erst wenn das funktioniert sehe ich auch einen Grund das ganze auszubauen. Aber diese Funktion ist ja praktisch der Kern des Programms
Wäre für Hilfe sehr dankbar.
Umgebung ist Lazarus.
LG
Monda