T
Tequila82
Gast
Hi,
ich habe einen Minimax algorithmus implementiert nach Wikipedia Pseudocode. Jetzt will ich den bestehenden code in eine Alpha-Beta-Suche (Alpha-Beta-Pruning) umwandeln.
Hier der original Minimax:
Und hier mein Versuch, ihn umzuwandeln:
Das Problem dabei ist nun, dass nicht dasselbe ergebnis rauskommt wie wenn der Minimax läuft. Es sollte aber das gleiche sein.
Der Spieler (für ein 4 Gewinnt Spiel) setzt normal seine Steine erst in der Mitte (also mit dem Minimax), und mit der Optimierung zur Alpha-Beta-Suche setzt er den Stein nur ganz links in der Spalte.
Weiss jemand, woran das liegen könnte?
Bin für jeden Tip dankbar
Vielen Dank im Voraus.
Gruß Tequila82
ich habe einen Minimax algorithmus implementiert nach Wikipedia Pseudocode. Jetzt will ich den bestehenden code in eine Alpha-Beta-Suche (Alpha-Beta-Pruning) umwandeln.
Hier der original Minimax:
Code:
/**
* Die Method (max) search for the best next step with the MiniMax-Algorithmus
* @param board - Das Spielfeld
* @param restTiefe - die restliche Tiefe
* @param suchTiefe - die gewünschte Suchtiefe
* @return - der ermittelte Zugwert
*/
private int maxWert(int restTiefe, int alpha, int beta) {
int ermittelt = 0;
int zugWert = 0;
int counter = 0;
if(id==1) {
int oppId = 4;
} else {
int oppID = 1;
}
ermittelt= Integer.MIN_VALUE;
for(int i=0; i<cols; i++) {
counter = 0;
if(board.isValidMove(i)) {
board.move(i,id);
if(restTiefe<=1 || board.isFull()) {
for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
if(board.isOccupied(ii,i)) {
counter++;
} else {
zugWert = countPoints(i, counter, id);
break;
}
}
}
else {
zugWert = minWert(restTiefe-1,alpha,beta);
}
board.unmove(i,id);
if(zugWert>ermittelt) {
ermittelt = zugWert;
if(restTiefe == suchTiefe) {
if(board.isValidMove(i)) {
nextMove = i;
}
}
}
}
}
return ermittelt;
}
/**
* Die Method for the best result --> (min) of the MiniMax-Algorithmus
* @param board - Das Spielfeld
* @param restTiefe - die restliche Tiefe
* @param suchTiefe - die gewünschte Suchtiefe
* @return - der ermittelte Zugwert
*/
private int minWert(int restTiefe, int alpha, int beta) {
int ermittelt = 0;
int zugWert = 0;
int counter = 0;
ermittelt = Integer.MAX_VALUE;
//cols
for(int i=0; i<cols; i++){
counter=0;
if(board.isValidMove(i)) {
board.move(i,oppId);
if(restTiefe<=1 || board.isFull()) {
for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
if(board.isOccupied(ii,i)) {
counter++;
} else {
zugWert = -countPoints(i, counter, oppId);
break;
}
}
}
else {
zugWert = maxWert(restTiefe-1,alpha,beta);
}
board.unmove(i,oppId);
if(zugWert<ermittelt) {
ermittelt = zugWert;
}
}
}
return ermittelt;
}
Und hier mein Versuch, ihn umzuwandeln:
Code:
/**
* Die Method (max) search for the best next step with the MiniMax-Algorithmus
* @param board - Das Spielfeld
* @param restTiefe - die restliche Tiefe
* @param suchTiefe - die gewünschte Suchtiefe
* @return - der ermittelte Zugwert
*/
private int maxWert(int restTiefe, int alpha, int beta) {
int ermittelt = 0;
int zugWert = 0;
int counter = 0;
if(id==1) {
int oppId = 4;
} else {
int oppID = 1;
}
ermittelt= Integer.MIN_VALUE;
for(int i=0; i<cols; i++) {
counter = 0;
if(board.isValidMove(i)) {
board.move(i,id);
if(restTiefe<=1 || board.isFull()) {
for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
if(board.isOccupied(ii,i)) {
counter++;
} else {
zugWert = countPoints(i, counter, id);
break;
}
}
}
else {
zugWert = minWert(restTiefe-1,alpha,beta);
}
board.unmove(i,id);
//WURDE HINZUGEFÜGT
if (zugWert >= beta)
return beta;
if(zugWert>ermittelt) {
ermittelt = zugWert;
if(restTiefe == suchTiefe) {
if(board.isValidMove(i)) {
nextMove = i;
}
}
}
}
}
return ermittelt;
}
/**
* Die Method for the best result --> (min) of the MiniMax-Algorithmus
* @param board - Das Spielfeld
* @param restTiefe - die restliche Tiefe
* @param suchTiefe - die gewünschte Suchtiefe
* @return - der ermittelte Zugwert
*/
private int minWert(int restTiefe, int alpha, int beta) {
int ermittelt = 0;
int zugWert = 0;
int counter = 0;
ermittelt = Integer.MAX_VALUE;
//cols
for(int i=0; i<cols; i++){
counter=0;
if(board.isValidMove(i)) {
board.move(i,oppId);
if(restTiefe<=1 || board.isFull()) {
for (int ii=0; ii<rows; ii++) { //get the height(row) of the new stone
if(board.isOccupied(ii,i)) {
counter++;
} else {
zugWert = -countPoints(i, counter, oppId);
break;
}
}
}
else {
zugWert = maxWert(restTiefe-1,alpha,beta);
}
board.unmove(i,oppId);
//WURDE HINZUGEFÜGT
if (zugWert <= alpha)
return alpha;
if(zugWert<ermittelt) {
ermittelt = zugWert;
}
}
}
return ermittelt;
}
Das Problem dabei ist nun, dass nicht dasselbe ergebnis rauskommt wie wenn der Minimax läuft. Es sollte aber das gleiche sein.
Der Spieler (für ein 4 Gewinnt Spiel) setzt normal seine Steine erst in der Mitte (also mit dem Minimax), und mit der Optimierung zur Alpha-Beta-Suche setzt er den Stein nur ganz links in der Spalte.
Weiss jemand, woran das liegen könnte?
Bin für jeden Tip dankbar
Vielen Dank im Voraus.
Gruß Tequila82