1

私は Nine Men's Morris ゲームを書いていますが、これまでのところ 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 プライ) でのみ移動順序を保存しているように見えますが、反復的な深化検索を非常に高速にするには、これまでに検索されたすべての深さで移動順序が必要です。反復深化には、時間を考慮に入れるという利点があるだけでなく (x 秒後に終了する)、適切な移動順序を生成するという利点もあります。そして、alphabeta または negascout アルゴリズムは、適切な移動順序付けの恩恵を受けます (以前の検索ではこの移動が最良だったので、最初にこの移動を試してください)。移動順序を実装する一般的な方法は、転置テーブルです。

Bruce Morelandの The Main Transposition TableとIterative Deepeningのドキュメントは私にとって非常に役に立ちました。リンクがあなたにも役立つことを願っています!

于 2013-03-20T22:32:14.573 に答える