1

我正在编写一个九人莫里斯游戏，到目前为止，我的 Negascout 搜索工作得很好。但是，我想添加迭代深化，所以我想出了这段代码：

public Move GetBestMove(IBoard board, int depth)
{        
    //Search limits (ms
    this.maxTime = 9000; 

    //Set initial window
    int alpha = -INFINITY, beta = INFINITY;
    int val = 0;

    //The move that will be returned
    Move bestMove = null;      

    //Get list of moves for the current board 
    List<Move> moves = board.getMoves();

    //Get the time search has started
    long startTime = System.nanoTime();

    //Iterate through the depths
    for (curDepth = 1; ; )
    {
        maxDepth = curDepth;

        //Reset alpha
        alpha = -INFINITY;

        //Reset the best score position
        int bestPos = -1;

        //Loop through all the moves
        for (int i = 0, n = moves.size(); i < n; i++)
        {
            //Make the move
            board.make(moves.get(i), true);

            //Search deeper
            val = negascout(board, curDepth, alpha, beta, startTime);

            //Undo the move
            board.undo(moves.get(i));

            //Keep best move
            if (val > alpha)
            {
                bestMove = moves.get(i);
                bestPos = i;
            }

            //Score missed aspiration window
            if (val <= alpha || val >= beta)
            {
                alpha = -INFINITY;
                beta = INFINITY;

                //Go to next iteration
                continue;
            }

            //Set new aspiration window
            alpha = val - ASPIRATION_SIZE;
            if (alpha < -INFINITY)
                alpha = -INFINITY;

            beta = val + ASPIRATION_SIZE;
            if (beta > INFINITY)
                beta = INFINITY;
        }

        //Move the best move to the top of the list
        if (bestPos != -1)
        {
            moves.remove(bestPos);
            moves.add(0, bestMove);
        }

        //Time check
        double curTime = (System.nanoTime() - startTime) / 1e6;
        if (curTime >= maxTime ||
            val == board.getMaxScoreValue() ||
            val == -board.getMaxScoreValue())
            break;

        //Increment current depth
        curDepth++;
    }

    //Return the move
    return bestMove;
}

我也使用抽吸窗口。然而，搜索返回最糟糕的举动！我认为问题在于重新/设置搜索窗口。搜索窗口是否应该移到外循环？

4

2 回答 2

1

由于您使用的是 negascout，因此您的初始调用应如下所示

val = -negascout(board, curDepth - 1, -beta, -alpha, startTime);

与内部节点相比，您的根调用完全相反，因此这就解释了为什么它会返回最糟糕的举动。

于 2013-05-30T04:39:28.780 回答
0

迭代深化策略：

for (depth = 1;; depth++) {
    val = AlphaBeta(depth, -INFINITY, INFINITY); // or negascout
    if (TimedOut())
        break;
}

看起来与您使用GetBestMove. 内部循环（遍历可能的移动）应该是negascout. 此外，您似乎只在第一深度级别（1-ply）存储移动顺序，但为了使迭代加深搜索真正快速，它需要到目前为止搜索的每个深度的移动顺序。迭代深化不仅具有将时间考虑在内的优势（在 x 秒后完成），而且还具有生成良好移动顺序的优势。并且字母表或 negascout 算法受益于良好的移动排序（首先尝试这个移动，因为在之前的搜索中它是最好的）。实现移动排序的常用方法是转置表。

来自 Bruce Moreland的文档The Main Transposition Table和Iterative Deepening 对我很有帮助，我希望这些链接也能帮助你！

于 2013-03-20T22:32:14.573 回答