C++ 4连续AlphaBeta算法不是很聪明

Question

我正在为学校项目制作 AI 控制的 alpha-beta 算法，但我的算法非常不一致。有时它成功地阻止了我所有的动作，有时它只是忽略了我的连续 3 个动作，如 here 所示。怎么会发生这种情况，我该如何解决这个问题？

int alphaBeta(const State board, int alpha, int beta, const Player player, int depth)
{
    //Max player = Player::O
    //Min player = Player::X

    std::vector<Move> possibleMoves = getMoves(board);

    if(eval(board)==Player::X){return 9999-depth;}      //Player X wins
    else if(eval(board)==Player::O){return -9999+depth;}    //Player O wins
    else if(possibleMoves.size()==0){return 0;}     //Tie
    else{   //Zoek verder
        depth++;
        State nextBoard = board;
        int result;

        if(player==Player::O){
            for (Move move: possibleMoves) {
                nextBoard = doMove(nextBoard, move);
                result = alphaBeta(nextBoard, alpha, beta, Player::X, depth);
                if (result > alpha){    
                    alpha = result; 
                    if (depth == 1){
                                    choice = move; //The actual move he will do
                    }
                }
                else if (alpha >= beta){ 
                    return alpha; 
                }
            }
            return alpha;
        }

        else{
            for (Move move: possibleMoves) {
                nextBoard = doMove(nextBoard, move);
                result = alphaBeta(nextBoard, alpha, beta, Player::O, depth);
                if (result < beta){ 
                    beta = result;
                    if (depth == 1){
                                    choice = move;
                    }
                }
                else if (beta <= alpha){ 
                    return beta;
                }
            }
            return beta;
        }
    }
}

Answer 1

您重复修改 nextBoard，向其添加（可能是非法的）移动：

nextBoard = doMove(nextBoard, move);

但你应该在原来的棋盘上依次尝试每一步：

State nextBoard = doMove(board, move);

（免责声明：可能还有其他问题。）

Answer 2

1) 不要评估递归调用中的每个节点，那样会花费太多时间。仅评估叶节点。

2) 在minimax递归调用中使用边界条件，如果深度超过一定值则终止；每个分支都不会导致获胜，并且搜索太大，程序可能会挂起。

3) 考虑在顶级分支上使用 multi-thread 以加快搜索速度。

int alphaBeta(const State board, int alpha, int beta, const Player player, int depth)
{
    std::vector<Move> possibleMoves = getMoves(board);

    if(CheckForWinX(board))
    {
        return 9999;
    }      
    else 
        if(CheckForWinO(board))
    {
        return -9999;
    }   
    else 
        if(possibleMoves.size()==0)
    {
        return 0;
    }     
    else 
        if( depth >= 5)   // without this boundary condition, the search tree will too big 
    { 
        return eval(board);    // evaluate ( which is more time expensive than CheckForWin() ) only the leaf node, not every nodes 
    }
    else{   
        depth++;
        State nextBoard = board;
        int result;

        if(player==Player::O){
              /**/
            return alpha;
        }
        else{
             /**/
            return beta;
        }
    }
}

C++ 4连续AlphaBeta算法不是很聪明

C++ 4 In a row AlphaBeta algorithm is not very smart

c++

algorithm

artificial-intelligence

coderef

alpha-beta-pruning