Bewertung bei KI ( Alpha Beta)

Fischkopf2009

Hallo.

Ich programmiere gerade an einem Nullsummenspiel ( 4 Gewinnt ), und bin dabei die KI zu erstellen. Ich möchte gerne einen Alpha Beta Algorithmus verwenden, da er gegenüber MinMax deutlich effktiver arbeitet. Aber nun meine Frage : Wie kann ich eine beliebige Spielposition bewerten. Ich habe mir gedacht, dass ich mir ausrechne wieviele Gewinnmöglickeiten es gibt ( also für jede Situation) und das als Bewertung nutze. Demnach wir ein Zug bevorzugt, wo es 2 Chancen gibt zu gewinnen, gegen über einem der nur eine Gewinnchance hat. Nun meine Frage ist das sinnvoll und habt ihr manchmal noch andere Ideen ?

Vielen Dank

krümelkacker

Eine Bewertungsfunktion, die ich mal benutzt habe:
http://www.c-plusplus.net/forum/p1956943#1956943

Bzgl Alpba-Beta vs Minimax: Alpha-Beta bringt einen großen Geschwindigkeitsvorteil, wenn man die möglichen Züge in einer bestimmten Reihenfolge durchprobiert (die "besseren" zuerst). Eine Möglichkeit ist zB das iterative Erhöhen der Suchtiefe, wobei man sich den besten Pfad merkt und ihn bei der nächsten Suchtiefe wieder zuerst einschlägt. So hat die KI immer einen aktuellen besten Zug, der ggf bei der Suche mit einer höheren Suchtiefe nochmal geändert wird. Das ist praktisch, wenn man die KI vor Beendigung mit voller Suchtiefe zu einem Zug zwingen will.

mngbd

Fischkopf2009 schrieb:

Demnach wir ein Zug bevorzugt, wo es 2 Chancen gibt zu gewinnen, gegen über einem der nur eine Gewinnchance hat. Nun meine Frage ist das sinnvoll [...] ?

Ja. Aber ausprobieren ist immer das beste.

Fischkopf2009 schrieb:

Aber nun meine Frage : Wie kann ich eine beliebige Spielposition bewerten.

Für den Anfang am besten eine einfache und einleuchtende Heuristik aufstellen. Z.B. ist es gut, wenn zwei Steine in einer Reihe sind, und sie noch vier werden könnten. Dafür z.B. einen Punkt. Wenn aber drei in einer Reihe sind, und sie noch vier werden können, ist das viel besser, also z.B. drei Punkte oder so. Ein Sieg muss natürlich jedenfalls die maximale Punkezahl ergeben.

Wenn du lange genug daran arbeitest, wird deine Suchfunktion sicherlich immer ausgefeilter werden. Es ist dann nicht immer einfach, vorauszusagen, welche Änderungen an der Heuristik gut wären, weil die Such-Funktion und die Bewertungsfunktion eng zusammenspielen (wahrscheinlich wirst du mithilfe der heuristischen Bewertung versuchen, eine gute Sortierung der Züge zu bekommen). Also ausprobieren und wieder ausprobieren.

Fischkopf2009

Hallo. Ich habe nun einen Min Max Algorithmus implementier. Als Suchfunktion habe ich folgendes verwendet :

Berechne für jede Stein die Anzahl an Möglichkeiten, um 4 in einer Reihe zu bekommen.
Wenn ich als MAX Spieler starte (1.Ebene) und in der 3 Ebene (wieder MAX Spieler) eine Möglichkeit habe zu gewinnen, wird dies doch durch den MIN Spieler weggefischt.

ALs Beispiel : Wenn der MAX Spieler gewinnt gibt es 1000 Punkte gewinnt der MIN Spieler gibt es -1000 Punkte. Wenn jetzt in der 3 Ebene festgestellt wird das der MAX spieler gewinnen kann, kehrt die Funktion mit 1000 zurück. der Min Spieler in der 2.Ebene nimmt aber den min wert von all seinen kindern. Wenn nun ein weiteres kind einen kleineren wert als 1000 Punkte ( max wert) zurück gibt, so wrid das an das wurzelelement (MAX Spieler) zurückgegeben. somit kann es passieren, das eine gewinnchance in einer unteren tiefe für den spieler verloren geht.

ich hoffe das war nicht zu komliziert. kann mir da jemand auf die sprünge helfen.

Christoph

Fischkopf2009 schrieb:

Wenn ich als MAX Spieler starte (1.Ebene) und in der 3 Ebene (wieder MAX Spieler) eine Möglichkeit habe zu gewinnen, wird dies doch durch den MIN Spieler weggefischt.

ALs Beispiel : Wenn der MAX Spieler gewinnt gibt es 1000 Punkte gewinnt der MIN Spieler gibt es -1000 Punkte. Wenn jetzt in der 3 Ebene festgestellt wird das der MAX spieler gewinnen kann, kehrt die Funktion mit 1000 zurück. der Min Spieler in der 2.Ebene nimmt aber den min wert von all seinen kindern. Wenn nun ein weiteres kind einen kleineren wert als 1000 Punkte ( max wert) zurück gibt, so wrid das an das wurzelelement (MAX Spieler) zurückgegeben. somit kann es passieren, das eine gewinnchance in einer unteren tiefe für den spieler verloren geht.

ich hoffe das war nicht zu komliziert. kann mir da jemand auf die sprünge helfen.

Das ist völlig korrekt.
Wenn es einen Sieg für den ersten Spieler gibt, der zweite Spieler aber diesen Spielablauf verhindern und stattdessen selbst gewinnen kann, dann ist das so. Vielleicht kann der erste Spieler sogar gar nicht mehr gewinnen, wenn der zweite Spieler das verhindern kann.

Der Minimax-Algorithmus ist gerade dafür da, um solche Situationen zu erkennen. Minimax wählt auch für den Gegenspieler immer den (für den Gegenspieler) besten Zug. Dieser Zug ist natürlich für den ersten Spieler der denkbar schlechteste, aber das ist genau die Idee: Der zweite Spieler möchte dem ersten Spieler ja nicht helfen zu gewinnen.

Th69

Außerdem sollte man in der Bewertungsfunktion noch den Level (d.h. die Zugnumemr) einbauen, so daß ein Sieg in weniger Zügen mehr gewichtet wird, z.B. 1000 + (MaxLevel - Level). Die Level-Variable dann vor jedem rekursiven Aufruf hochsetzen und nachher wieder runtersetzen.

P.S. Meine Bewertungsfunktion bei meinem eigene "Vier Gewinnt"-Spiel sieht folgendermaßen aus:

const int WinLine = 4; // Vier gewinnt -)

if(nCheckLine<=WinLine/2) return 1+random(10);
if(nCheckLine>WinLine) nCheckLine=WinLine;
int f = MaxLevel*nCheckLine-(nLevel-1);
return -(5*f+random(5));

Noch ein bißchen Zufall, damit nicht immer die selben Züge entstehen...

Th69 schrieb:

Außerdem sollte man in der Bewertungsfunktion noch den Level (d.h. die Zugnumemr) einbauen, so daß ein Sieg in weniger Zügen mehr gewichtet wird, z.B. 1000 + (MaxLevel - Level). Die Level-Variable dann vor jedem rekursiven Aufruf hochsetzen und nachher wieder runtersetzen.

P.S. Meine Bewertungsfunktion bei meinem eigene "Vier Gewinnt"-Spiel sieht folgendermaßen aus:
const int WinLine = 4; // Vier gewinnt -)

if(nCheckLine<=WinLine/2) return 1+random(10);
if(nCheckLine>WinLine) nCheckLine=WinLine;
int f = MaxLevel*nCheckLine-(nLevel-1);
return -(5*f+random(5));
Noch ein bißchen Zufall, damit nicht immer die selben Züge entstehen...

Kannst du deinen Bewertungsfunktion mal etwas erklären

mngbd

55522 schrieb:

Kannst du deinen Bewertungsfunktion mal etwas erklären

Ich rate davon ab, auf Leute zu hören, die ihren Variablen ein n vorstellen. Mit der gewonnenen Zeit kann man die tollsten Sachen anstellen.