使用Alpha-Beta算法的国际象棋人工智能

Question

我已经为我的棋类游戏实现了alpha beta算法，然而它花费了很多时间（4层深度需要几分钟）才能最终做出相当愚蠢的移动。

我一直在努力找到错误（我认为我犯了一个错误），已经尝试了两天了。如果您能提供代码方面的外部帮助，我将不胜感激。

getMove函数是为根节点调用的，它为所有子节点（可能的移动）调用alphaBeta函数，然后选择得分最高的移动。

Move AIPlayer::getMove(Board b, MoveGenerator& gen)
{
    // defined constants: ALPHA=-20000 and BETA= 20000
    int alpha = ALPHA; 
    Board bTemp(false); // test Board
    Move BestMov;
    int i = -1; int temp;
    int len = gen.moves.getLength();  // moves is a linked list holding all legal moves
    BoardCounter++; // private attribute of AIPlayer object, counts analyzed boards
    Move mTemp;     // mTemp is used to apply the nextmove in the list to the temporary test Board
    gen.mouvements.Begin();   // sets the list counter to the first element in the list
    while (++i < len && alpha < BETA){
        mTemp = gen.moves.nextElement();
        bTemp.cloneBoard(b);
        bTemp.applyMove(mTemp);
        temp = MAX(alpha, alphaBeta(bTemp, alpha, BETA, depth, MIN_NODE));
        if (temp > alpha){
            alpha = temp;
            BestMov = mTemp;
        }
    }
    return BestMov;
}

alphaBeta 函数：

int AIPlayer::alphaBeta(Board b, int alpha, int beta, char depth, bool nodeType)
{
    Move m;
    b.changeSide();
    compteurBoards++;
    MoveGenerator genMoves(b); // when the constructor is given a board, it automatically generates possible moves
    // the Board object has a player attribute that holds the current player
    if (genMoves.checkMate(b, b.getSide(), moves)){ // if the current player is in checkmate
        return 100000;
    }
    else if (genMoves.checkMate(b, ((b.getSide() == BLACK) ? BLACK : WHITE), moves)){ // if the other player is in checkmate
        return -100000;
    }
    else if (!depth){
        return b.evaluateBoard(nodeType);

    }
    else{
        int scoreMove = alpha;
        int best;
        genMoves.moves.Begin();
        short i = -1, len = genMoves.moves.getLength();
        Board bTemp(false);

        if (nodeType == MAX_NODE){
            best = ALPHA;
            while (++i < len){
                bTemp.cloneBoard(b);
                if (bTemp.applyMove(genMoves.moves.nextElement())){ 
                    scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
                    best = MAX(best, scoreMove);
                    alpha = MAX(alpha, best);

                    if (beta <= alpha){ 
                        std::cout << "max cutoff" << std::endl;
                        break;
                    }
                }
            }
            return scoreMove;
        //return alpha;
        }
        else{
            best = BETA;
            while (++i < len){
                bTemp.cloneBoard(b);
                if (bTemp.applyMove(genMoves.moves.nextElement())){ 
                    scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
                    best = MIN(best, scoreMove);
                    beta = MIN(beta, best);
                    if (beta <= alpha){ 
                        std::cout << "min cutoff" << std::endl;
                        break;
                    }
                }
            }
            return scoreMove;
            //return beta;
        }
        return meilleur;
    }
}

编辑：我应该指出，evaluateBoard仅评估棋子的流动性（可能移动的步数，捕获移动根据被捕获的棋子而获得更高的分数）

谢谢。

- user34853

---

我认为你应该在Code Review或Game Development上询问。这里不是相关话题。 - Burkhard

我已经尝试了材料评估，但是具有不同可能移动的棋盘（但相同的棋子）都具有完全相同的价值。 - user34853

@Burkhard 不，Code-Review 更注重一般的编码风格。他的问题更涉及到国际象棋编程理论。例如，一个人需要哈希和棋盘本身不应该被重新创建。 - ABCD

@Douglas Zare 评估也是至关重要的。然而，即使有完美的评估器，我们仍不应该对树中的每个节点都进行评估。 - ABCD

@学生T：我或其他人在哪里说过你必须评估树中的每个节点？如果你说的话与我说的话没有对比，请不要说“然而”。我不明白为什么你提到了我或我的评论。 - Douglas Zare

Answer 1

我看到你在尝试实现一个mini-max算法。然而，代码中有些地方让我感到怀疑。我们将与开源的Stockfish棋类引擎进行比较。请参考https://github.com/mcostalba/Stockfish/blob/master/src/search.cpp中的搜索算法。

1. 传递Board b值

你的代码如下：

alphaBeta(Board b, int alpha, int beta, char depth, bool nodeType)

我不知道"Board"具体是什么。但是它看起来不对。让我们看一下Stockfish：

Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode)

在Stockfish中，位置对象以引用方式传递。如果"Board"是一个类，则程序每次调用alpha-beta函数都需要创建一个新副本。在国际象棋中，当我们必须评估许多节点时，这显然是不可接受的。

2. 没有哈希

Stockfish中的哈希处理如下所示：

ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;

没有哈希，您将需要一遍又一遍地评估相同的位置。没有实现哈希，你将无法前进。

3. 检查将军

可能不是最显著的减速因素，但我们永远不应该在每个单独的节点中检查将军。在Stockfish中：

// All legal moves have been searched. A special case: If we're in check
// and no legal moves were found, it is checkmate.
if (InCheck && bestValue == -VALUE_INFINITE)
    return mated_in(ss->ply); // Plies to mate from the root

当所有可能的移动都被搜索完之后，这一步才会执行。我们这样做是因为我们通常拥有的非将死节点比将死节点要多得多。

4. Board bTemp(false);

这看起来像一个主要的减速点。让我们看看 Stockfish：

  // Step 14. Make the move
  pos.do_move(move, st, ci, givesCheck);

您不应该在每个节点中创建临时对象（创建bTemp对象）。机器需要分配一些堆栈空间来保存bTemp，这可能会对性能造成严重的影响，尤其是如果bTemp不是主要变量（即不太可能被处理器缓存）。 Stockfish只是修改内部数据结构而不创建新的。

5. bTemp.cloneBoard(b);

与4类似，更糟糕的是，在节点中的每个移动中都会执行此操作。

6. std :: cout <<“max cutoff”<< std :: endl;

也许很难相信，打印到终端比处理要慢得多。这里您正在创建一个潜在的减速，字符串需要保存到IO缓冲区中。该函数甚至可能（我不是100％确定）阻止程序直到文本显示在终端上。 Stockfish仅用于统计摘要，肯定不是每次出现故障高或故障低时都会发生。

7. 不排序PV（主要变例）移动

可能不是您在解决其他问题之前想要做的事情。在Stockfish中，他们有：

std :: stable_sort（RootMoves.begin（）+ PVIdx，RootMoves.end（））;

这是在迭代深度框架中的每次迭代中执行的。

- SmallChess

---

嗨，学生T，感谢您的意见。我已经在过去的两天里努力实现置换表和移动排序，虽然还没有完成，但我希望能看到一些改进。我也采纳了您的建议，直接将移动应用于棋盘，而不是克隆它，实际上我正在努力删除所有不必要的值传递，由于这一点，程序速度显著提高了。 - user34853

干得好！你很快就会掌握国际象棋编程。如果你有兴趣，请关注talkchess.com上的讨论，那里有所有引擎程序员，包括我自己。另外，请考虑接受我的答案。 - ABCD

我正在使用位棋盘和自定义链表来存储走法。为了进行移动排序，我在Move类中有一个属性来保存移动的分数。当找到一个移动时，根据它是否是捕获以及哪个棋子被捕获等情况，给它分配一个分数，然后将其添加到列表中的排序位置，以消除在添加所有移动后需要对列表进行排序的需要。 - user34853

虽然我不认为Stockfish能做到你所做的事情，但你所做的也足够好了。 - ABCD

我已经接受了你的答案。感谢你的帮助。 我会尝试在今天剩下的时间里继续研究评估函数，如果到那时我仍需要帮助，我会发起一个新的问题。 - user34853

Answer 2

我只会讨论你的算法运行时成本问题，因为我不知道你的棋盘评估函数的实现细节。

为了尽可能简单，我将假设算法的最坏情况。

getMove函数调用alphaBeta函数len1次，而alphaBeta函数又调用自身len2次，然后再调用自身len3次，以此类推，直到深度达到0并停止递归。由于最坏情况的假设，假设n = max(len1, len2, ...)，因此您有

n * n * n * ... * n次调用alphaBeta，乘法次数取决于深度d，这导致n^d次调用alphaBeta，这意味着您具有指数级的运行时行为。这非常缓慢，仅被阶乘运行时行为所超越。

我认为您应该查看大O符号，并尝试优化您的算法，以获得更快的结果。

此致
OPM

- OnePunchMickey

---

嗨OPM，感谢您的输入。 Alpha Beta剪枝是最小化算法的优化，其中不能改善解决方案的树枝不会被分析，从而显著减少要分析的节点数。 尽管它是指数级的，但我认为这不是问题，因为它仍然应该比现在快。 - user34853

嗨user34853，我知道极小化极大算法的alpha-beta剪枝，这个算法的一个常见问题是移动集合排序不好。在最坏的情况下，截断将发生在最后检查的节点处，这使它与极小化极大算法相同。为了避免这种情况，有几件事情可以做。最简单的方法是存储所谓的杀手着法，这些着法产生了截断并首先进行评估。另一个常见的优化是使用置换表来存储分析过的位置，以防止对同一棋盘进行多次分析。此致，OPM - OnePunchMickey

顺便提一下，在alphaBeta函数中看一下你的?-运算符 :) - OnePunchMickey

嗨OPM，我做了更多的研究，我相信你是对的，我会加入杀手启发式和置换表。 感谢你指出?运算符的问题。^^ 再次感谢你的帮助。 - user34853

当然，杀手着和对PV着进行排序会有所帮助。但是一个简单的alpha-beta搜索仍然不会太糟糕。请参考我的回答。 - ABCD