Hello guys,
I am programming a checkers engine and have implemented the negamax version of alpha beta pruning and transposition tables so far.
Transposition tables seem to work very well, specially in the endgame. To further improve the search I want to search the moves first, that were stored as the best reply in my Transposition table.
For some reason that doesn't work at all. I counted the number of nodes visited during search with and without searching the best reply first.
There was no difference at all.
I wonder whether I implemented it correctly.
Here is my implementation:
public int alphabeta(final CheckerBoard board,int alpha,int beta,int depth,boolean nullMoveAvailable){
nodeCount++;
int alphaOrig=alpha;
Transposition entry =table.find(board.key);
if(entry!=null && entry.depth>=depth){
if(entry.flag==Transposition.EXACT){
return entry.value;
}else if(entry.flag==Transposition.UPPER){
beta = Math.min(beta,entry.value);
}else if(entry.flag == Transposition.LOWER){
alpha =Math.max(alpha,entry.value);
}
if(alpha>=beta){
return entry.value;
}
}
if(depth==0 || board.isTerminalState()){
return quiesceneSearch2(board,alpha,beta);
}
ArrayList<Move>sucessors =MGenerator.getMoves(board);
for( int i=0;i<sucessors.size();i++){
if(entry!=null && entry.depth<depth && entry.flag == Transposition.EXACT && sucessors.get(i).equals(entry.best)){
Collections.swap(sucessors, i, 0);
break;
}
}
Move currentBest=null;
for(Move move : sucessors){
board.makeMove(move);
int value =-alphabeta(board, -beta, -alpha, depth - 1, true);
board.undoMove(move);
if(value>=beta){
break;
}
if(value>alpha){
currentBest = move;
alpha=value;
}
}
Transposition next =new Transposition();
next.depth=depth;
next.value =alpha;
next.zobrisKey=board.key;
next.best = currentBest;
if(alpha<=alphaOrig){
next.flag =Transposition.UPPER;
}else if(alpha>=beta){
next.flag = Transposition.LOWER ;
}else{
next.flag = Transposition.EXACT;
}
table.insert(next);
return alpha;
}