Hi there,
I got an instance of a reversi gameboard up and running but I am having trouble implementing a simple alpha-beta pruning algorithm for determining the best move. So far I have implemented a basic Min-Max algorithm to do just that, and so far we think it does what it was supposed to do :) As I have now spent a lot of time on this particular matter and I dont seem to get anywhere, I thought I could ask you pros. The algorithm looks like this:
public int evaluate(int depthleft, int maxplayer, int actualplayer, long stime, int safetytime, int timeout, int alpha, int beta) throws TimeoutException
{
long ctime = System.currentTimeMillis();
if (timeout !=-1 && ctime-stime >= timeout - safetytime)
throw new TimeoutException();
if (depthleft==0)
return this.evaluateSituation(maxplayer);
ArrayList<int[]> possibleMoves = this.getPossibleMoves(actualplayer);
if (possibleMoves.size()==0)
{
//pass
LLGameBoard copyBoard = this.clone();
return copyBoard.evaluate(depthleft-1, maxplayer, enemy(actualplayer), stime, safetytime, timeout, alpha,beta);
}
int bestEvaluation = (actualplayer==maxplayer) ? MINIMUM_EVALUATION : MAXIMUM_EVALUATION;
for (int[] move : possibleMoves)
{
//copy board situation and make move
LLGameBoard copyBoard = this.clone();
copyBoard.makeMove(actualplayer, move);
int evaluation = copyBoard.evaluate(depthleft-1, maxplayer, enemy(actualplayer), stime, safetytime, timeout, alpha, beta);
if (actualplayer==maxplayer)
{
//max plays
if (evaluation>bestEvaluation)
{
bestEvaluation = evaluation;
}
}
else
{
//min plays
if (evaluation<bestEvaluation)
{
bestEvaluation = evaluation;
}
}
}
return bestEvaluation;
}
I know the general idea of alpha-beta pruning, but for some reason I am unable to implement it in this specific method. Hope there is epiphany soon.
Thank you very much for helping!
EDIT:
Ok, I've made a few changes and changed the algorithm to a negamax model. The thing is, I don't know whether I'm doing the right thing :)
public int negamax(int depthleft, int maxplayer, int currentplayer, long stime, int safetytime, int timeout, int alpha, int beta) throws TimeoutException
{
long ctime = System.currentTimeMillis();
if (timeout !=-1 && ctime-stime >= timeout - safetytime)
throw new TimeoutException();
if (depthleft==0)
return this.evaluateSituation(maxplayer);
//get all possible moves for currentplayer
ArrayList<int[]> possibleMoves = this.getPossibleMoves(currentplayer);
//if there's no move for currentplayer to be done
if (possibleMoves.size()==0)
{
//pass, a.k.a enemy will use the same board as actualplayer
LLGameBoard copyBoard = this.clone();
return -copyBoard.negamax(depthleft-1, maxplayer, enemy(currentplayer), stime, safetytime, timeout, -beta, -alpha);
}
//iterate over all possible moves
for (int[] move : possibleMoves)
{
LLGameBoard copyBoard = this.clone();
copyBoard.makeMove(currentplayer, move);
int evaluation = -copyBoard.negamax(depthleft-1, maxplayer, enemy(currentplayer), stime, safetytime, timeout, -beta, -alpha);
if (evaluation>=beta)
{
return beta;
}
else if (evaluation > alpha)
{
alpha = evaluation;
}
}
return alpha;
}
I'd be very grateful if someone, who actually knows what he's (I'm not :)) doing, could give me a short feedback.
Thank you.
[Edited by - AwesomeSauce on May 14, 2010 5:36:16 AM]
