Negamax-Algorithmus

[alex.h]

Hallo,

ich programmiere 4 gewinnt in Java 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?

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;

}

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.

al3x ist gerade online Beitrag melden Beitrag bearbeiten/löschen

[flashpixx]

Der Algorithmus liefert Dir keine Spalte, sondern eine Bewertung des Zuges.

Phil

[alex.h]

und wie bekomm ich einen spaltenwert?

[flashpixx]

Das kann Dir hier wohl keiner so recht beantworten.

Du hast eine aktuelle Spielsituation und simulierst nun einen neuen Zug durch den Computer. Der Algorithmus sagt dann aus, wie gut dieser Zug ist. Im Grunde weißt Du doch, welchen Zug Du machst. Du musst eben mehrere Spielzüge simulieren und dann die Ergebnisse des Algorithmus vergleichen und eben den "besten" Zug (Zug mit der größten Gewinnchance) durchführen

Phil

[alex.h]

wie schon geschrieben wie sich der algorithmus verhält und was er macht hab ich soweit verstanden aber wo genau ich den besten spaltenwert abfangen kann ahb ich noch nicht rausgefunden... der algorithmus allein bringt ja nichts wenn er nur spielsituatioen bewertet und dann die bewertung nicht in ein ergebnis/handlung umgesetzt wird.

[AndiE]

Ich habe eine Idee.

Nehmen wir mal an, der Algortihmus setzt den Stein "scheinbar" in Spalte 1, und berechnet dir die Bewertung dafür. Wenn er nun den Stein in die zweite Spalte setzte, dann erhält er eine zweite Bewertung. Ist die Bewertung von Spalte 1 höher, setzt er nicht Spalte 2.

So probiert er alle Spalten durch, und in die mit den meisten "Bewertungspunkten" setzt er den Stein.

Dazu übergibt er die Bewertungszahl und in DoNext die Spalte.

So habe ich das bei "Minimax" unter Wikipedia verstanden.