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;
    }

There are probably other problems with your code, but about your specific question, why are you restricting the use of the move to situations where entry.flag is EXACT? If a move was good enough to give you a beta cut in the past, that's good enough to try it first.

There is another problem that makes your code incorrect, unless there is something I am not seeing: You should first check if (value > alpha), update currentBest and alpha, and only then check for a beta cut. Otherwise, whenever a beta cut happens alpha and currentBest have the wrong value.