Jump to content
  • Advertisement
Sign in to follow this  
Peng1993

Alpha-Beta Pruning and MoveOrdering

This topic is 927 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!