# Negamax-Algorithmus



## al3x (28. Mrz 2009)

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 (29. Mrz 2009)

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 (30. Mrz 2009)

Marco13 hat gesagt.:


> Klick ggf. mal auf
> 
> 
> 
> ...


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

Ebenius


----------



## babuschka (30. Mrz 2009)

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 (31. Mrz 2009)

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 (31. Mrz 2009)

> 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 (31. Mrz 2009)

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 (1. Apr 2009)

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.


----------

