Alpha-Beta Suche

[Monday]

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

[frankyboy1974]

hallo,

also erstmal Respekt, ist sicher keine ganz leichte Aufgabe, die du dir gestellt hast. Habs kurz mal überflogen. Vielleicht kann ich ein wenig helfen:

Zitat:

// 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

Spieler meint die Id des Spieler also 1 bzw -1. Beim Schachspiel würde ich das so programmieren, das 1 Weiss meint und -1 entspechend schwarz
Die zusätzlich Information w / b brauchst du dann eigentlich nicht mehr. Wenn du also für weiss den Zug berechnen möchtest, ruftst du Funktion mit 1 ansonsten mit -1 auf

Zitat:

{OR keine zügemehr}

Du musst also eine Funktion programmieren, die ermittelt ob für den aktuellen Spieler, für den du gerade die MinMax ausführst, aus der aktuelle betrachteten Stellung überhaupt noch Zugmöglichkeiten bestehen (Schach-Matt). Du bewertest also immer dann die Stellung, wenn entweder die maximale Zugtiefe erreicht wurde ist oder es eben keine weiteren Züge mehr gibt. Wenn du also eine Zugtiefe von 4 Züge eingestellt hast und der Gegner schon nach 2 Züge Schach-Matt ist, macht es keine Sinn mehr diesen 'Ast' weiter zu durchlaufen.

Zitat:

// Zug vor?!
wert := -miniMax(id,tiefe-1,-beta,-maxWert,farbwechsel(am_zug),zugliste[a].stellung_lang);
// Zug zurück?!

Aus einer gegebenen Schachstellung, berechnest du erstmal alle(erlaubten) neuen Schachstellungen nach einem Zug, dann wählst du eine daraus aus, rufst wiederum rekursiv die minmax-Funktion auf, anschließend musst du natürlich wieder zu deiner Ausgangsstellung zurückkehren. Ich bin mir nicht ganz sicher, ob es reicht sich nur die Ausgangstellung zu merken, und dann jeweils die Züge sich zu merken oder ob es nicht doch erforderlich ist, sich tatsächlich jede Stellung einzeln zu merken (Rückwärtsrechnung beim Schach Möglich?/ Stichwort en Passante). Hab seit Jahren kein Schach mehr gespielt.

Zitat:

//if tiefe = anfangstiefe then begin end; // Was soll hier geschehen?!

Wenn du an diese Stelle kommst speicherst du denn bis dahin besten Zug , dieser wird dann am Ende ausgeführt, es sein denn beim Durchlaufen, findet sich eine noch bessere Alternative.

Zitat:

Eine Stellung bewertung - geschieht das in der Alpha-Beta Funktion, oder muss dies bereits vorher geschehen?

Die Stellungbewertung rufst du mit der Bewerten(Spieler)-Funktion on-the-fly auf. Das ist wahrscheinlich bezogen auf das eigentliche Schachprogramm, die anspruchsvollste Methode.

Ich hoffe zumindestens ein klein wenig geholfen zu haben.

mfg