c - Alpha beta 修剪根移动

Question

我目前正在编写一个国际象棋引擎并且已经取得了很大的进步，但是我遇到了一个问题并且想就这种方式提出一些意见。好吧，我的问题是我的国际象棋 AI 没有做出“最佳”举动，它似乎看不到简单的事情，比如它的棋子可能被收回等等。我的 alpha beta 修剪过程如下。

int Search (TREE *tree, int ply, int wtm, int alpha, int beta) { 
    if (0 == ply) { 
        return quiesce(tree, ply, wtm, alpha, beta); 
    } 

    movePointer = GenCaptures(tree, MAXPLY, wtm, moves); 
    movePointer = GenNonCaptures(tree, wtm, movePointer); 
    for (move = &moves[0]; move < movePointer; move++) { 
        MakeMove(tree, &tree->movePath[ply], wtm); 
        score = -Search(tree, ply - 1, Flip(wtm), -beta, -alpha); 
        UnmakeMove(tree, &tree->movePath[ply], wtm); 
        tree->movePath[ply].move = 0; 
        if (score >= beta) { 
            return beta; 
         } 
         if (score > alpha) { 
             alpha = score; 
         } 
    } 

我认为我的 alpha beta 修剪效果很好，因为它确实返回了合理的移动，我认为问题出在我尝试获取我的 rootMove 时。我试图通过 (

int searchRoot( TREE *tree, int ply, int wtm ) { 
    //int depth = 1; 
    int moves[220]; 
    int *movePointer = 0; 
    int *move = 0;
    int rootAlpha = -MATE - 1; 
    int rootValue = -MATE - 1; 
    int rootBeta = MATE + 1; 
    MOVE currentMove; 
    currentMove.move = 0; 
    currentMove.capture = 0; 
    movePointer = GenCaptures( tree, MAXPLY, wtm, moves ); 
    movePointer = GenNonCaptures( tree, wtm, movePointer ); 
    for ( move = &moves[0]; move < movePointer; move++ ) { 
        currentMove.move = *move; 
        tree->movePath[MAXPLY] = currentMove; 
        MakeMove( tree, &currentMove, wtm ); 
        int lastValue = -Search( tree, MAXPLY -1, Flip(wtm), rootAlpha, rootBeta ); 
        UnmakeMove( tree, &currentMove, wtm ); 
        if ( lastValue > rootValue ) { 
            tree->rootMove = *move; rootValue = lastValue; 
        } 
    } 
} 

任何想法都会有所帮助，谢谢。

Answer 1

您的 searchRoot 没有正确实现 negamax 的想法。你的线路

int lastValue = -Search( tree, MAXPLY -1, Flip(wtm), rootAlpha, rootBeta );

应该阅读

int lastValue = -Search( tree, MAXPLY -1, Flip(wtm), -rootBeta, -rootAlpha );