-2

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

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

2 回答 2

2

你反复修改nextBoard，添加（可能是非法的）移动到它：

nextBoard = doMove(nextBoard, move);

但是你应该在原板上依次尝试每一步：

State nextBoard = doMove(board, move);

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

于 2018-03-27T12:29:15.923 回答
0

1）不要评估递归调用中的每个节点，这将花费太多时间。仅评估叶节点。

2）如果深度大于某个值，则在minimax递归调用中使用边界条件终止；每个分支都不会导致获胜的举动，搜索会太大，程序可能会挂起。

3）考虑在顶级分支上使用多线程来加快搜索速度。

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;
        }
    }
}
于 2018-03-28T12:06:21.523 回答