Negamax-Algorithmus

Status
Nicht offen für weitere Antworten.

al3x

Mitglied
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.
 
Zuletzt bearbeitet von einem Moderator:

Marco13

Top Contributor
Klick ggf. mal auf
java.png
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.
 

babuschka

Top Contributor
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

Mitglied
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?
 
Zuletzt bearbeitet von einem Moderator:

hdi

Top Contributor
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

Top Contributor
Hab' den Code jetzt nicht nachvollzogen, aber was ich mit der ersten Antwort meinte war grob sowas wie
Code:
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

Top Contributor
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.
 
Status
Nicht offen für weitere Antworten.

Ähnliche Java Themen


Oben