国际象棋AI与alpha beta算法

2018-06-30 08:28:04

我已经实施了我的国际象棋游戏的alpha beta算法，但是它需要很长时间（4分钟的时间）才能最终做出一个相当愚蠢的举动。

我一直在努力寻找2天内发现的错误（我假设我做了一个错误），我非常感谢我的代码的一些外部输入。

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;
    }
}

编辑：我应该注意到，评估板只评估棋子的移动性（可能棋步数量，拍摄棋子取决于拍摄的棋子得分较高）

谢谢。

我可以看到你正试图实现一个迷你最大算法。然而，代码中有些东西让我感到怀疑。我们将比较代码和开放源代码盘问引擎。请参阅https://github.com/mcostalba/Stockfish/blob/master/src/search.cpp中的搜索算法

1.按价值传递董事会b

你的代码中有这个：

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

我不知道“董事会”究竟是什么。但它看起来并不适合我。让我们看看干鱼：

值搜索（位置和位置，堆栈* ss，值alpha，值beta，深度深度，bool cutNode）

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

2.没有散列

哈希是在干鱼中完成的：

ttValue = ttHit？ value_from_tt（tte-> value（），ss-> ply）：VALUE_NONE;

如果没有散列，您需要一次又一次地评估相同的位置。没有执行哈希，你将不会去任何地方。

3.检查将军

可能不是最重要的减速，但我们不应该在每个节点检查将军。在干鱼：

// 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.董事会bTemp（false）;

这看起来像是一个主要的放缓。让我们采取干扰：

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

你不应该在每个节点中创建一个临时对象（创建一个bTemp对象）。该机器需要分配一些堆栈空间来保存bTemp。这可能是一个严重的性能损失，特别是如果bTemp不是主变量（即不可能被处理器缓存）。干鱼只是修改内部数据结构而不创建新的数据结构。

5. bTemp.cloneBoard（b）;

类似于4，更糟糕的是，这是针对节点中的每一次移动完成的。

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

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

7.不分类PV移动

可能不是你在解决其他问题之前想做的事情。在干鱼，他们有：

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

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

我只会解决算法的运行时成本问题，因为我不知道板评估函数的实现细节。

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

getMove函数使得对lenBeta函数进行len1调用，然后对自身进行len2调用，这反过来又对自己进行len3调用等等，直到深度达到0并且递归停止。由于最坏情况的假设，我们假设n = max（len1，len2，...），所以你有

n * n * n * ... * n根据深度d调用alphaBeta并进行乘法运算，这会导致对nB d的调用，这意味着您具有指数运行时行为。这是超慢的，并且只能被阶乘运行时行为殴打。

我认为你应该为此目的看一下Big O符号，并试着相应地优化你的算法以获得更快的结果。

最好的问候，OPM

链接地址: http://www.djcxy.com/p/84689.html

上一篇: Chess AI with alpha beta algorithm

下一篇: Alpha beta pruning in Checkers (test cases to prove the efficiency)