   Reversi/Othello Alpha-Beta-Pruning
  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){//passLLGameBoard 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 moveLLGameBoard 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 playsif (evaluation>bestEvaluation){bestEvaluation = evaluation;}}else{//min playsif (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 currentplayerArrayList<int[]> possibleMoves = this.getPossibleMoves(currentplayer);//if there's no move for currentplayer to be doneif (possibleMoves.size()==0){//pass, a.k.a enemy will use the same board as actualplayerLLGameBoard copyBoard = this.clone();return -copyBoard.negamax(depthleft-1, maxplayer, enemy(currentplayer), stime, safetytime, timeout, -beta, -alpha);}//iterate over all possible movesfor (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]
  Assuming that code works and that you are calling it correctly, you only need this change:if (actualplayer==maxplayer){//max playsif (evaluation>bestEvaluation){bestEvaluation = evaluation;alpha = evaluation;if (evaluation>=beta)break;}}else{//min playsif (evaluation<bestEvaluation){bestEvaluation = evaluation;beta = evaluation;if (evaluation<=alpha)break;}};Quote:Original post by alvaroAssuming that code works and that you are calling it correctly, you only need this change:*** Source Snippet Removed ***It's negamax, so the code should be written as if it's always seen from the maximizing player.   ;Quote:Original post by lingforsQuote:Original post by alvaroAssuming that code works and that you are calling it correctly, you only need this change:*** Source Snippet Removed ***It's negamax, so the code should be written as if it's always seen from the maximizing player.It wasn't negamax when I replied: He edited the original post, which is bad because it generates this kind of confusion.