Hallo, ich möchte 4 Gewinnt mit einer KI programmieren und benutze dazu den Negamax-Algorithmus.
Der Algorithmus funktioniert soweit, spuckt jedoch noch keine wirklichen logischen Züge aus. 3 senkrecht stehende steine erkennt er nicht. nicht von mir und nicht von ihm…
Was ist denn falsch?
/**
* Der beste Spielzug wird mit Hilfe des Negamax-algorithmus gesucht.
* Jeder Spielbaum wird bis zur Tiefe "depth" ausgewertet und dann eine Feldbewertung vorgenommen.
*
* @param depth die Tiefe des Spielbaumes
* @return max Der Wert des Zuges
*/
private int negamax(int depth, int alpha, int beta)
{
if(depth == 0 //Abbruchbedingun der Rekursion (Tiefe erreicht,
|| pf.possibleMovesInt()+1 == 0) //aktueller spieler hat keine möglichen Züge -> Feld ist voll
{
if (pf.checkfourBoolean(2)) //Gewonnen?
return 10;
else if (pf.checkfourBoolean(1)) //Verloren?
return -10;
else //Unentschieden
return 0;
}
for(int s = 0; s < pf.getSpalten(); s++) //for(int s = 0; s < pf.getSpalten(); s++) //Alle Züge durchprobieren
{
if (pf.columnFree(s)) //Alle möglichen Züge durchprobieren
{
player = player == 1 ? 2 : 1;
pf.set(s, player); //Zug simulieren
int value = -negamax(depth-1,-beta,-alpha); //Rekursionsaufruf
pf.removeHighestField(s); //Zug rückgängig machen
//Betacut
//if (value >= beta)
//{
// return beta;
//}
//Alphacut
if (value > alpha)
{
alpha = value;
doNext = s;
}
}
}
return alpha;
}```
Hallo Marco. Danke schonmal für den Hinweis.
Wie jedoch würde das am konkreten Beispiel bei mir aussehen?.
Leider arbeite ichhier nicht mir Objekten deswegen kann ichs mir grad nicht vorstellen und da es ein Schulprojekt ist, hab ich leider nicht mehr die Zeit das zu ändern…
Ah, sorry, das “doNext” ist wohl der Zug, der irgendwo im nicht-geposteten Teil liegt, und dann ausgeführt werden soll. Ein bißchen mehr Code, vielleicht?
Hey Marco. Was bräuchtest du denn noch?
Also es ist ja 4Gewinnt. der Negamax-Alg soll mir als die günstigste Spalte errechnen. Dieser Wert wird in doNext gespeichert und dann an die GUI übergeben um den, für die KI, günstigsten Zug auszuführen. der komplette Negamax-Alg kannst du hier sehn.
Was fehlt sind die einzelnen Funktionen teilweise.
possibleMovesInt(): Gibt die Gesamtzahl der noch möglichen Züge zurück
columnFree(): Schaut ob die Spalte frei ist(konkret nur das oberste Feld, da dann ja mindestens 1 Feld frei ist)
getSpalten(): gibt im konrekten fall 7 zurück(spaltenanzahl und bei 4 gewinnt is der standard 7, aber kann beliebig bis 10 eingestellt werden)
Die anderen hab ich dir mal hier:
pf.set()
* set-Methode zum setzen der Spielsteine f�r Spieler1 oder Spieler2 und
* der Reihenfolge des Spielzuges
*
* @param spalte
* -> Spalte, in die der Stein gesetzt werden moechte. Angabe des
* Indexes.
* @param spieler
* -> Welcher Spieler den Spielstein setzen moechte. (Darf nur
* den Wert 1 oder 2 annehmen)
*
* @Rueckgabewert -> Der R�ckgabewert ist die Zeile in die der Spielstein
* geflogen ist. "11" bedeutet, dass die Spalte voll ist.
*/
public void set(int spalte, int spieler)
{
for (int z = 0; z < FeldSpieler[0].length; z++)
{
if (FeldSpieler[spalte][z] == 0)
{
FeldSpieler[spalte][z] = spieler;
zaehler++;
return;
}
}
}```
removehighestField()
```/**
* Entfernt den angegeben Spielstein(setzt das Feld auf 0). Ist u.a. für den
* Negamax-Algorithmus notwendig
*
* @param s
* @param z
*/
public void removeHighestField(int s)
{
for (int z = this.getZeilen() - 1; z >= 0; z--)
{
if (this.getOneField(s, z) != 0)
{
this.removeField(s, z);
zaehler--;
return;
}
}
}```
checkfourBoolean() (überprüft auf 4 spielsteine in einer reihe)
```/**
*
* @param spieler
* @return
*/
public boolean checkfourBoolean(int player)
{
// Horizontal ueberpruefen
for (int s = 0; s < spalten - 3; s++)
{
for (int z = 0; z < zeilen; z++)
{
if (FeldSpieler[s][z] == player
&& FeldSpieler[s + 1][z] == player
&& FeldSpieler[s + 2][z] == player
&& FeldSpieler[s + 3][z] == player)
return true;
}
}
// Vertikal ueberpruefen
for (int s = 0; s < spalten; s++)
{
for (int z = 0; z < zeilen - 3; z++)
{
if (FeldSpieler[s][z] == player
&& FeldSpieler[s][z + 1] == player
&& FeldSpieler[s][z + 2] == player
&& FeldSpieler[s][z + 3] == player)
return true;
}
}
// Diagonal - von links unten nach rechts oben
for (int s = 0; s < spalten - 3; s++)
{
for (int z = 0; z < zeilen - 3; z++)
{
if (FeldSpieler[s][z] == player
&& FeldSpieler[s + 1][z + 1] == player
&& FeldSpieler[s + 2][z + 2] == player
&& FeldSpieler[s + 3][z + 3] == player)
return true;
}
}
// Diagonal - von oben links nach unten rechts
for (int s = 0; s < spalten - 3; s++)
{
for (int z = 3; z < zeilen; z++)
{
if (FeldSpieler[s][z] == player
&& FeldSpieler[s + 1][z - 1] == player
&& FeldSpieler[s + 2][z - 2] == player
&& FeldSpieler[s + 3][z - 3] == player)
return true;
}
}
return false;
}```
Vielen Dank schonmal im voraus.
Gruß Alex
Hmja, sorry, ich habe zwar einen Compiler im Kopf, aber der ist faul, und wie Compiler nunmal so sind: Wenn was fehlt, meckern sie :rolleyes:
Das sind jetzt ein paar Methoden, die rekursiv-verschachtelt in IREGENDeinem Zusammenhang ausfgerufen werden, und IRGENDwas funktioniert dabei nicht. Ich habe jetzt zwei Alternativen: Entweder, ich Kopiere die Schnipsel zusammen in eine Datei, und versuche, daraus etwas Compilierbares zu machen (auf die Gefahr hin, dass das dann funktioniert, d.h. der Fehler, der eigentliche Fehler dann nicht mehr auftritt), oder ich lese mir den Code zeilenweise durch, und versuche, wild zu spekulieren, WAS an WELCHER Stelle die Ursache für eine Fehlfunktion sein KÖNNTE.
Beides würde mehr Zeit in Anspruch nehmen, als ich mir für dieses Problem zu nehmen bereit bin.
Zusammengefasst: Kannst du was posten (EDIT: GGf. als Dateianhang), was man mit Copy&Paste direkt rauskopieren, Compilieren und starten kann?
Nein, weder noch. Habe zwar gerade mal den ersten beschriebenen Ansatz versucht, aber … jo, das kann man vergessen, da muss man SO viel raten… Was spricht gegen einen Anhang hier?
Aber egal ich schicks dir komplett über eMail, möchte nicht das komplette Programm an jeden freigeben da stecken 3Monate-Arbeit drin und sobalds komplett fertig ist, werd ichs auch frei stellen und Open Source .