我正在写使用极小与α-β剪枝一个黑白棋引擎。 它的工作不错，但我发现了以下问题：

I'm writing a Othello engine using minimax with alpha-beta pruning. It's working ok, but i found the following problem:

当的算法发现的位置被丢失，它返回-INFINITY如预期的，但在 这种情况下，我不能够跟踪'最好'的举动......的位置已经输了，但无论如何应该返回一个有效的举措（preferably一个是存活更长的举动，因为良好的国际象棋引擎一样）。

When the algorithm finds that a position is lost, it returns -INFINITY as expected, but in this case i'm not able to track the 'best' move...the position is already lost, but it should return a valid move anyway (preferably a move that survives longer, as the good chess engines does).

下面是code：

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{             
    OthelloMove garbage = new OthelloMove();             
    int currentPlayer = board.getCurrentPlayer();

    if (board.checkEnd())
    {                        
        int bd = board.countDiscs(OthelloBoard.BLACK);
        int wd = board.countDiscs(OthelloBoard.WHITE);

        if ((bd > wd) && currentPlayer == OthelloBoard.BLACK)                
            return INFINITY;
        else if ((bd < wd) && currentPlayer == OthelloBoard.BLACK)                           
            return -INFINITY;            
        else if ((bd > wd) && currentPlayer == OthelloBoard.WHITE)                            
            return -INFINITY;            
        else if ((bd < wd) && currentPlayer == OthelloBoard.WHITE)                            
            return INFINITY;            
        else                             
            return 0.0f;            
    }
    //search until the end? (true during end game phase)
    if (!solveTillEnd )
    {
        if (depth == maxDepth)
            return OthelloHeuristics.eval(currentPlayer, board);
    }

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer);             

    for (OthelloMove mv : moves)
    {                        
        board.makeMove(mv);            
        float score = - minimax(board, garbage, -beta,  -alpha, depth + 1);           
        board.undoMove(mv);             

        if(score > alpha)
        {  
            //Set Best move here
            alpha = score;                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());                              
        }

        if (alpha >= beta)
            break;                

    }                
    return alpha;
}

我把它用：

AI ai = new AI(board, maxDepth, solveTillEnd);

//create empty (invalid) move to hold best move
OthelloMove bestMove = new OthelloMove();
ai.bestFound = bestMove;
ai.minimax(board, bestMove, -INFINITY, INFINITY, 0);

//dipatch a Thread
 new Thread(ai).start();
//wait for thread to finish

OthelloMove best = ai.bestFound();

在失去位置（想象它失去了10后移动为例）进行搜索，最好的变量上面等于作为参数传递的空无效的举动......为什么？

When a lost position (imagine it's lost 10 moves later for example) is searched, best variable above is equal to the empty invalid move passed as argument...why??

感谢您的帮助！

推荐答案

您的问题是，你使用-INFINITY和+ INFINITY为胜/负比分。你应该有得分输/赢是高于/低于任何其他位置评价得分较低，但不等于你的无穷价值。这将保证此举甚至会在已经​​彻底失去了位置进行选择。

Your problem is that you're using -INFINITY and +INFINITY as win/loss scores. You should have scores for win/loss that are higher/lower than any other positional evaluation score, but not equal to your infinity values. This will guarantee that a move will be chosen even in positions that are hopelessly lost.