阿尔法-贝塔修剪

Question

我已经为我的Android Reversi游戏实现了以下MiniMax算法：

@Override
public Field findBestMove(GameBoard gb, int depth, boolean player) 
{   
/** maximum depth of search reached, we stop */
if(depth >= max_depth) return null;
//player = (depth+1)%2 + 1;
/** getting a list of moves to chose from */
ArrayList <Field> moves = findAllPossibleMoves(gb, player); 
Field best_move = null;
/** iterating over all possible moves, to find the best one */      
for (int i=0; i<moves.size(); i++)
{
    /** board to simulate moves */
    GameBoard temp_board = new GameBoard(gb);
    /** getting the current move */
    Field move = moves.get(i);      
    /** simulating the move for the current node */
    game.move(move, temp_board, player);
    Log.i("board", "Depth:"+depth+" Player:"+player+" Move:"+i+" Rating:"+evaluate(temp_board));
    Log.i("board", ""+moves.get(i).getX()+","+moves.get(i).getY());         
    temp_board.printBoard();
    /** getting to the next inferior node */            
    Field best_deep_move = findBestMove (temp_board, depth + 1, !player);           
    /** if the maximum depth is reached, we have a null, so we evaluate */
    if (best_deep_move == null) 
    {
        move.setRating(evaluate (temp_board));
    }
    /** if we are not the deepest possible, we get the rating from the lower node */
    else 
    {
        move.setRating(best_deep_move.getRating());         
        Log.i("eval", ""+best_deep_move.getRating());
    }           
    if(best_move == null) 
    {
        best_move = move;           
    }
    else
    {   
        Log.i("update", "Current move rating:"+move.getRating());
        Log.i("update", "New move rating:"+best_move.getRating());
        if (depth%2==0)
        {
            Log.i("update", "MAX player");
            /** for us, we look for the maximum */
            if (best_move.getRating() < move.getRating()) 
                {

                best_move = move;
                }
        }
        else
        {
            Log.i("update", "MIN player");
            /** for the opponent, we look for the minimum */
            if (best_move.getRating() > move.getRating())
            { 

                best_move = move;
            }
        }
        Log.i("update", "Updated move rating"+best_move.getRating());
    }
}
return best_move;

}

我已经在理论上熟悉了 Alpha-Beta 修剪，尽管我在继续将该知识应用于该算法时遇到了一些麻烦。提前致谢

Answer 1

需要对代码进行以下更改才能实现 alpha-beta 修剪：-

1. 传递参数public Field findBestMove(GameBoard gb, int depth, boolean player,int aplha_beta)

2. 如果当前best_move永远不会影响先前深度alpha_beta，请停止递归。

   if(player == max && best_move!=null && aplha_beta <= best_move.getRating()) {
              return(best_move);
    }
    if(player == min && best_move!=null && alpha_beta >= best_move.getRating()) {
           return(best_move);
    }
    Field best_deep_move = findBestMove(temp_board,depth+1,!player,best_move.getRating());