采用alpha-beta算法的国际象棋AI

Question

我已经为我的国际象棋游戏实现了alpha-beta算法，但是要最终做出一个相当愚蠢的动作需要很多时间（4-ply需要几分钟）。

我已经试图找到错误（我假设我犯了一个）2天了，我非常感谢对我的代码的一些外部输入。

getMobile函数：为根节点调用，它为所有子节点调用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;
    }
}

编辑：我应该注意到，评估板只评估棋子的机动性（可能的移动次数，捕获移动根据捕获的棋子获得更高的分数）

非常感谢。

Answer 1

我只想解决你的算法的运行时成本问题，因为我不知道你的board求值函数的实现细节。

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

getMobile函数对alphaBeta函数进行len1调用，alphaBeta函数反过来对自己进行len2调用，反过来对自己进行len3调用，依此类推，直到深度达到0并且递归停止。因为最坏的情况假设，假设n=max（len1， len2，...），所以你有

n*n*n*...*n调用alphaBeta，乘法次数取决于深度d，这导致n^d调用alphaBeta，这意味着您具有指数级运行时行为。这是超慢的，只有阶乘运行时行为才能击败。

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

向您致意，OPM

Answer 2

我可以看出您正在尝试实现一个mini-max算法。然而，代码中有一些东西让我怀疑。我们将把代码与开源的Stockfish象棋引擎进行比较。请参考以下搜索算法：https://github.com/mcostalba/Stockfish/blob/master/src/search.cpp

1、按值通过b板

您的代码中包含以下内容：

alphaBeta（Board b、int alpha、int beta、char depth、bool nodeType）

我不知道“董事会”到底是什么。但在我看来不太对劲。让我们看看斯托克菲什：

值搜索（位置

位置对象在Stockfish中是通过引用传递的。如果“Board”是一个类，那么每次调用alpha-beta函数时，程序都需要制作一个新的副本。在国际象棋中，当我们必须评估许多节点时，这显然是不可接受的。

2、无散列

在Stockfish中进行哈希处理，如下所示：

#value_from_tt

如果不使用哈希，您将需要反复计算相同的位置。如果不实现哈希，您将无法到达任何地方。

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.clone（b）；

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

6、std：：cout

也许很难相信，打印到终端要比处理慢得多。在这里，您创建了一个潜在的减速，该字符串需要保存到IO缓冲区。该函数可能（我不是百分之百确定）甚至会阻止您的程序，直到文本显示在终端上。Stockfish只做统计摘要，绝对不是每次你有失败高或失败低的时候。

7.不排序PV移动

在解决其他问题之前，您可能不想做什么。在Stockfish中，它们有：

std：：stable\u sort（RootMoves.begin（）PVIdx，RootMoves。结束（））；

这是在迭代深化框架中为每个迭代完成的。