具有α - β剪枝的极大极小;类变量或通过递归发送它们

本文关键字:类变量 递归 极小 具有 | 更新日期: 2023-09-27 18:15:34

当使用Minimax与alpha - beta修剪时,是否有可能将alpha和beta作为类变量而不是通过递归发送它们?

代替:

private ValuedMove AlphaBetaSearch(Board state)
{
    return MaxValue(state, 0, int.MinValue, int.MaxValue);
}
private ValuedMove MaxValue(Board state, int d, int alpha, int beta)
{
    if (d == depth || state.GameRunning == false)
        return new ValuedMove(Heuristic.BoardValue(state, Player));
    ValuedMove v = new ValuedMove(int.MinValue);
    foreach (Move move in LegalMoves)
    {
        ValuedMove minCheck = MinValue(state.ImagineMove(move), d + 1, alpha, beta);
        if (v.Value >= beta)
            return v;
        alpha = Max(alpha, v.Value);
    }
    return v;
}
private ValuedMove MinValue(Board state, int d, int alpha, int beta)
{
    //Minimax and Alpha-Beta logic here
}

我可以写:

int alpha, beta;
private ValuedMove AlphaBetaSearch(Board state)
{
    alpha = int.MinValue;
    beta = int.MaxValue;
    return MaxValue(state, 0);
}
private ValuedMove MaxValue(Board state, int d)
{
    //Minimax and Alpha-Beta logic here
}
private ValuedMove MinValue(Board state, int d)
{
    //Minimax and Alpha-Beta logic here
}
我之所以问这个问题,是因为当我试图通过这样做来优化代码时(我的想法是,如果我不需要将整数发送到每个递归中,我可能会节省一点时间),我的棋手突然变成了一个白痴,牺牲了他的皇后来杀死一个兵,并犯了其他愚蠢的错误。

他的表现总是比他的"常规Alpha-Beta"对手差得多,我猜这是因为他只搜索了树的一小部分(他们都使用相同的深度,但修改后的玩家似乎更有攻击性,从而减少了访问的节点数量)。我已经这样做了两次,以确保我没有改变任何东西,除了我在这里画出来的。

如果我对Alpha-Beta算法的理解是正确的,这应该不会有什么区别,但对于我的棋手来说,这是有区别的。我做错什么了吗?

所以,我现在的主要问题不是这是一个优化明智或代码实践明智的好事情,而是它是否应该可能做或不。

具有α - β剪枝的极大极小;类变量或通过递归发送它们

你不能这么做。AlphaBeta是一个递归算法。这意味着它调用自己。每次它调用自己时,它都(可能)使用不同的alpha和beta值。每个递归都需要自己的变量版本来保存不同的值。如果你在类中包含变量,你将只有一组变量在所有(递归)调用AlphaBeta之间共享。

也就是说,用类成员替换函数参数可能不是一个好的优化。这两种技术都有成本。在调用之前,需要将参数压入堆栈,并且需要通过指针(隐藏的this指针)间接访问成员。让我们忘记哪个成本更高。这个微优化可能太微不足道,根本不会产生任何影响。