Negamax-Algorithmus

[al3x]

Hallo,
ich programmiere 4 gewinnt und benötige dazu den Negamax-Algorithmus. den Algorithmus habe ich soweit verstanden und auch schon implementiert, aber aus dem allgemeinen Pseudocode von Wikipedia lässt sich mir nicht erschließen wie ich daraus schlussendlich einen konkreten Spaltenwert extrahieren kann?

[HIGHLIGHT="Java"]int NegaMax(int tiefe, int alpha, int beta)
{
if (tiefe == 0)
return Bewerten();
GeneriereMoeglicheZuege();
while (ZuegeUebrig())
{
FuehreNaechstenZugAus();
wert = -NegaMax(tiefe-1, -beta, -alpha);
MacheZugRueckgaengig();
if (wert >= beta)
return beta;
if (wert > alpha)
alpha = wert;
}
return alpha;
}


Meine Interpretation lautet wie folgt(funktoniert aber nicht richtig):

private int negamax(int player, int depth, int alpha, int beta)
{
int score = Integer.MIN_VALUE;

if(depth == 0 //Abbruchbedingun der Rekursion (Tiefe erreicht,
|| possibleMovesInt() == 0) //aktueller spieler hat keine möglichen Züge -> Feld ist voll
{
return evaluate(player);
}

for(int s = 0; s < pf.getSpalten(); s++) //Alle Züge durchprobieren
{
if (pf.getOneField(s, pf.getZeilen() - 1) == 0) //Alle möglichen Züge durchprobieren
{
pf.set(s, player); //Zug simulieren
int actualvalue = -negamax(player, depth-1,-beta,-localalpha); //Rekursionsaufruf
//ZUG rückgängig
if(score < actualvalue)
{
score = actualvalue;
doNext = s; // Bester Zug speichern
}
if (actualvalue >= beta)
{
//Betacut
return beta;
}
if (score > alpha)
{
//Alphacut
alpha = score;
}
}
}

return score;
}[/HIGHLIGHT]

doNext soll den konkreten spaltenwert darstellen.

Aber was ist falsch, oder wie kann ich den originial code schnell um doNext erweitern?

Vielen Dank im voraus.

 

[Marco13]

Klick ggf. mal auf

wenn du code einfügst.

Ich glaube, du mußt die Methode für jede deiner aktuell möglichen Züge aufrufen, und dort dann den Zug mit dem besten Ergebnis speichern. Sonst kriegt man potentiell nur irgendwelche Werte aus tieferen Rekursionsstufen. Kann mich aber irren.

 

[Ebenius]

Klick ggf. mal auf

wenn du code einfügst.

Hab ich eben mal gemacht. Das nächste mal macht das al3x sicher selber!

Ebenius

 

[babuschka]

Wie meinst Du das, den originalen Code um doNext erweitern?
Was genau "funktoniert aber nicht richtig"?
Speicherst Du doNext auch korrekt als Attribut Deiner Klasse?

Falls jedoch eine Spielschwäche der KI vorliegt liegt das meistens an einer ungeeigneten/falsch balancierten Bewertungsfunktion.

 

[al3x]

Der Algorithmus an sich, liefert ja immer nur die Bewertung für einen möglichen Zug.
Diese Bewertung muss ich nun aber sinnvoll in einen konkreten Zug(doNext) umwandeln. Die Frage wäre nun wie?
Ich habe die Implementation des Algorothmus nun verbessert bin mir aber noch nicht sicher an der Stelle (//???):

[HIGHLIGHT="Java"]private int negamax(int player, int depth, int alpha, int beta)
{
int value;
int compareValue = Integer.MAX_VALUE; //oder min_value??
if(depth == 0 //Abbruchbedingun der Rekursion (Tiefe erreicht,
|| possibleMovesInt() == 0) //aktueller spieler hat keine möglichen Züge -> Feld ist voll
{
return evaluate(player);
}

for(int s = 0; s < pfki.getSpalten(); s++) //Alle Züge durchprobieren
{
if (pfki.getOneField(s, pfki.getZeilen() - 1) == 0) //Alle möglichen Züge durchprobieren
{
pfki.set(s, player); //Zug simulieren
value = -negamax(player, depth-1,-beta,-alpha); //Rekursionsaufruf
rem_simulate(s); //Zug rückgängig machen
if((value > compareValue) && (DEPTH == depth))//??
{
compareValue = value; //??
doNext = s; //?? // Bester Zug speichern
}

//Betacut
if (value >= beta)
{
return beta;
}
//Alphacut
if (value > alpha)
{
alpha = value;
}
}
}
return alpha;
}[/HIGHLIGHT]

Sind die Bedingungen an den entsprechenden Stellen richtiggesetzt?, compareValue mit min oder max_value initialisieren?


Gruß Alex

PS: Dieses Java-Symbol kann ich bei mir leider nicht finden, deswegen habe ich den Code leider nicht markiert. Wo ist dieses denn zu finden?

 

[hdi]

PS: Dieses Java-Symbol kann ich bei mir leider nicht finden, deswegen habe ich den Code leider nicht markiert. Wo ist dieses denn zu finden?

In der Menüleiste beim Verfassen eines Posts. Die gibt's aber nur wenn
du wirklich auf "Antworten" klickst (oben links), bei "Direkt antworten" ist das nicht verfügbar.

 

[Marco13]

Hab' den Code jetzt nicht nachvollzogen, aber was ich mit der ersten Antwort meinte war grob sowas wie

int bestMoveValue = -1;
int bestMoveIndex = -1;
for (int i=0; i<moves.size(); i++)
{
    Move move = moves.get(i);
    doMove(move);
    int value = negamax(...);
    if (value > bestMoveValue)
    {
        bestMoveValue = value;
        bestMoveIndex = i;
    }
    undoMove(move);
}

 

[babuschka]

So in etwa sollte der NegaMax funktionieren (Pseudocode, evtl noch ein paar Fehler):

[HIGHLIGHT="Java"]int NegaMax(int tiefe, int anfangstiefe, int alpha, int beta){
if (tiefe == 0){
return bewerten();
}
generiereAlleZuege();
while (zuegeUebrig()&&zuegeMoeglich()){
macheNaechsten();
wert = -NegaMax(tiefe-1, anfangstiefe, -beta, -alpha);
undo();
if (wert >= beta){
return beta; //Beta-Cutoff
}
if (wert > alpha){
alpha = wert;
if (tiefe== anfangstiefe) {
//Wieder in der obersten Rekursionstiefe: nächsten Zug (Attribut der Klasse) setzen
next = zugnummer;
}
}
}
return alpha;
}
[/HIGHLIGHT]

alpha ist der minimale Wert für den 1. Spieler, beta ist das maximale Ergebnis für Spieler 2.