0

当使用带有 Alpha-Beta 修剪的 Minimax 时，是否可以将 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 算法，这应该不会有任何区别，但对于我的棋手来说，确实如此。我做错什么了吗？

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

4

1 回答 1

4

你真的不能这样做。AlphaBeta 是一种递归算法。这意味着它会调用自己。每次它调用自己时，它都会使用（可能）不同的 alpha 和 beta 值。每个递归都需要自己的变量版本，这些变量将保存不同的值。如果您在类中包含变量，您将只有一组变量在对 AlphaBeta 的所有（递归）调用之间共享。

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

于 2011-11-25T13:16:20.040 回答