java - Alpha Beta 修剪

Question

我正在构建一个带有 alpha beta 的黑白棋游戏，我需要你在 alpha beta 中的帮助。问题是计算机不断选择位于棋盘低端的方格之一。我有一个计算机可能的移动列表（如您在下面的代码中所见），这意味着计算机几乎总是选择该列表中的最后一个或最后一个移动，即使它不是最好的移动。我的评估函数很简单：黑色块减去白色块。顺便说一句：它在深度 = 1 中工作正常，但我需要它在深度 = 3 中工作。

public int AlphaBeta(int depth,int turn,TreeNode root,int alpha,int beta)
{
    if(depth==0)
        return evaluationFunc(turn,turns,root.board,root);
    else
    {
        buildSons(turn,root);
        TreeNode head =  generateList(root.sons);
        return executeCheckTheSons2(depth,turn,head,alpha,beta);
    }
}

public int executeCheckTheSons2(int depth,int turn,TreeNode head,int alpha,int beta)
    {
        int score;
        if(turn==1)
        {
            while(head!=null)
            {
                head.board=simulateTheMove(head.board,head.getX(),head.getY(),turn);
                score=AlphaBeta(depth-1,turn*-1,head,alpha,beta);
                if(score > alpha)
                {
                    alpha=score;
                    setMove(head);
                }
                if(alpha >= beta)
                    return alpha;
                head=head.next;
            }
                return alpha;
        }
        else
        {
            while(head!=null)
            {
                head.board=simulateTheMove(head.board,head.getX(),head.getY(),turn);
                score=AlphaBeta(depth-1,turn*-1,head,alpha,beta);
                if(score<beta)
                {
                    beta=score;
                    setMove(head);
                }
                if(alpha >= beta)
                    return beta;
                head=head.next;
            }
            return beta;
        }       
    }

    public void setMove(TreeNode root)
    {
        while(root.father.father!=null)
            root=root.father;
        pnt.setX(root.getX());
        pnt.setY(root.getY());
    }

Answer 1

我认为错误出在setMove函数中。我想这是设置最终坐标以设置作品的功能。目前，您正在为树中的每个深度调用它，即使此分支的结果不是全局的最佳结果。

例如，假设您正在评估最后可能的举动。你从 depth=3 开始，然后你递归地调用自己 for depth=2。当您现在进入时，executeCheckTheSons2您将从 0 分开始并评估可能的动作。其中一个移动可能会给你一个大于 0 的分数，因此你将调用setMove(head)并设置坐标以移动到最后一个可能的移动。当你现在从函数返回时，你会记录这个深度的分数，但从全局来看，这不是一个很好的举措。但是，最后一次调用 setMove 仍然处于活动状态，之后您无需更改它。

您应该将此调用移出 executeCheckTheSons2 并将其移至某个上层函数中。或者将 x 和 y 坐标记录在executeCheckTheSons2函数的局部变量中，然后setMove在从函数返回之前调用。

如果这个问题对你有用，请接受这个作为答案。