java - 使用字母修剪进行搜索时，迭代深化代码不会增加深度

Question

我正在为我的国际象棋游戏编写 AlphaBeta 剪枝算法。我试图实现迭代加深，以便搜索比我的 maxDepth 更深，但即使添加或不添加计时器，搜索实际上也不会超过 maxDepth。这就是搜索结果的样子。注意* alphabeta 修剪工作正常。

thinking...
Depth: 1 Score: 91 Move: null Nodes: 21
Depth: 1 Score: 52 Move: B/1 -> A/3 Nodes: 42
Depth: 1 Score: 52 Move: B/1 -> C/3 Nodes: 63
Depth: 1 Score: 91 Move: G/1 -> F/3 Nodes: 84
Depth: 1 Score: 100 Move: G/1 -> H/3 Nodes: 105
Depth: 1 Score: 105 Move: A/2 -> A/3 Nodes: 126
Depth: 1 Score: 115 Move: A/2 -> A/4 Nodes: 147
Depth: 1 Score: 110 Move: B/2 -> B/3 Nodes: 168
Depth: 1 Score: 121 Move: B/2 -> B/4 Nodes: 189
Depth: 1 Score: 111 Move: C/2 -> C/3 Nodes: 210
Depth: 1 Score: 81 Move: C/2 -> C/4 Nodes: 231
Depth: 1 Score: 62 Move: D/2 -> D/3 Nodes: 252
Depth: 1 Score: 81 Move: D/2 -> D/4 Nodes: 273
Depth: 1 Score: 62 Move: E/2 -> E/3 Nodes: 294
Depth: 1 Score: 121 Move: E/2 -> E/4 Nodes: 315
Depth: 1 Score: 111 Move: F/2 -> F/3 Nodes: 336
Depth: 1 Score: 115 Move: F/2 -> F/4 Nodes: 357
Depth: 1 Score: 110 Move: G/2 -> G/3 Nodes: 378
Depth: 1 Score: 100 Move: G/2 -> G/4 Nodes: 399
Depth: 1 Score: 105 Move: H/2 -> H/3 Nodes: 420
Depth: 2 Score: 43 Move: H/2 -> H/4 Nodes: 515
Depth: 2 Score: 4 Move: B/1 -> A/3 Nodes: 632
Depth: 2 Score: 4 Move: B/1 -> C/3 Nodes: 722
Depth: 2 Score: 43 Move: G/1 -> F/3 Nodes: 808
Depth: 2 Score: 52 Move: G/1 -> H/3 Nodes: 893
Depth: 2 Score: 57 Move: A/2 -> A/3 Nodes: 995
Depth: 2 Score: 67 Move: A/2 -> A/4 Nodes: 1081
Depth: 2 Score: 62 Move: B/2 -> B/3 Nodes: 1167
Depth: 2 Score: 73 Move: B/2 -> B/4 Nodes: 1268
Depth: 2 Score: 63 Move: C/2 -> C/3 Nodes: 1356
Depth: 2 Score: 33 Move: C/2 -> C/4 Nodes: 1451
Depth: 2 Score: 14 Move: D/2 -> D/3 Nodes: 1548
Depth: 2 Score: 33 Move: D/2 -> D/4 Nodes: 1652
Depth: 2 Score: 14 Move: E/2 -> E/3 Nodes: 1727
Depth: 2 Score: 73 Move: E/2 -> E/4 Nodes: 1791
Depth: 2 Score: 63 Move: F/2 -> F/3 Nodes: 1856
Depth: 2 Score: 67 Move: F/2 -> F/4 Nodes: 1922
Depth: 2 Score: 62 Move: G/2 -> G/3 Nodes: 1988
Depth: 2 Score: 52 Move: G/2 -> G/4 Nodes: 2052
Depth: 2 Score: 57 Move: H/2 -> H/3 Nodes: 2118
Depth: 3 Score: 95 Move: H/2 -> H/4 Nodes: 3201
Depth: 3 Score: 56 Move: B/1 -> A/3 Nodes: 3994
Depth: 3 Score: 56 Move: B/1 -> C/3 Nodes: 5714
Depth: 3 Score: 95 Move: G/1 -> F/3 Nodes: 7260
Depth: 3 Score: 146 Move: G/1 -> H/3 Nodes: 8570
Depth: 3 Score: 109 Move: A/2 -> A/3 Nodes: 10160
Depth: 3 Score: 119 Move: A/2 -> A/4 Nodes: 11009
Depth: 3 Score: 154 Move: B/2 -> B/3 Nodes: 12387
Depth: 3 Score: 125 Move: B/2 -> B/4 Nodes: 13290
Depth: 3 Score: 115 Move: C/2 -> C/3 Nodes: 14363
Depth: 3 Score: 85 Move: C/2 -> C/4 Nodes: 15382
Depth: 3 Score: 109 Move: D/2 -> D/3 Nodes: 17492
Depth: 3 Score: 85 Move: D/2 -> D/4 Nodes: 18629
Depth: 3 Score: 109 Move: E/2 -> E/3 Nodes: 19949
Depth: 3 Score: 125 Move: E/2 -> E/4 Nodes: 20916
Depth: 3 Score: 115 Move: F/2 -> F/3 Nodes: 22122
Depth: 3 Score: 119 Move: F/2 -> F/4 Nodes: 22764
Depth: 3 Score: 154 Move: G/2 -> G/3 Nodes: 23392
Depth: 3 Score: 146 Move: G/2 -> G/4 Nodes: 24258
Depth: 3 Score: 142 Move: H/2 -> H/3 Nodes: 25192
Depth: 4 Score: 1 Move: H/2 -> H/4 Nodes: 34503
Depth: 4 Score: 1 Move: B/1 -> A/3 Nodes: 45971
Depth: 4 Score: 1 Move: B/1 -> C/3 Nodes: 64274
Depth: 4 Score: 28 Move: B/1 -> C/3 Nodes: 86799
Depth: 4 Score: 56 Move: G/1 -> H/3 Nodes: 97618
Depth: 4 Score: 61 Move: A/2 -> A/3 Nodes: 106232
Depth: 4 Score: 36 Move: A/2 -> A/4 Nodes: 111788
Depth: 4 Score: 72 Move: B/2 -> B/3 Nodes: 124438
Depth: 4 Score: 57 Move: B/2 -> B/4 Nodes: 136293
Depth: 4 Score: 47 Move: C/2 -> C/3 Nodes: 147439
Depth: 4 Score: 12 Move: C/2 -> C/4 Nodes: 162826
Depth: 4 Score: -7 Move: D/2 -> D/3 Nodes: 183505
Depth: 4 Score: -8 Move: D/2 -> D/3 Nodes: 220089
Depth: 4 Score: -18 Move: D/2 -> D/3 Nodes: 258502
Depth: 4 Score: 87 Move: D/2 -> D/3 Nodes: 270509
Depth: 4 Score: 67 Move: F/2 -> F/3 Nodes: 286283
Depth: 4 Score: 36 Move: F/2 -> F/4 Nodes: 295990
Depth: 4 Score: 68 Move: G/2 -> G/3 Nodes: 312581
Depth: 4 Score: 56 Move: G/2 -> G/4 Nodes: 321997
Depth: 4 Score: 61 Move: H/2 -> H/3 Nodes: 333876
Depth: 5 Score: 114 Move: H/2 -> H/4 Nodes: 594470
Depth: 5 Score: 103 Move: B/1 -> A/3 Nodes: 713022
Depth: 5 Score: 108 Move: B/1 -> C/3 Nodes: 942106
Depth: 5 Score: 156 Move: G/1 -> F/3 Nodes: 1128907
Depth: 5 Score: 150 Move: G/1 -> H/3 Nodes: 1260303
Depth: 5 Score: 127 Move: A/2 -> A/3 Nodes: 1429234
Depth: 5 Score: 137 Move: A/2 -> A/4 Nodes: 1560847
Depth: 5 Score: 166 Move: B/2 -> B/3 Nodes: 1776377
Depth: 5 Score: 148 Move: B/2 -> B/4 Nodes: 1915797
Depth: 5 Score: 140 Move: C/2 -> C/3 Nodes: 2169729
Depth: 5 Score: 123 Move: C/2 -> C/4 Nodes: 2437277
Depth: 5 Score: 141 Move: D/2 -> D/3 Nodes: 2605302
Depth: 5 Score: 98 Move: D/2 -> D/4 Nodes: 2851051
Depth: 5 Score: 141 Move: E/2 -> E/3 Nodes: 3041992
Depth: 5 Score: 177 Move: E/2 -> E/4 Nodes: 3186381
Depth: 5 Score: 124 Move: F/2 -> F/3 Nodes: 3374198
Depth: 5 Score: 137 Move: F/2 -> F/4 Nodes: 3579920
Depth: 5 Score: 189 Move: G/2 -> G/3 Nodes: 3823175
Depth: 5 Score: 150 Move: G/2 -> G/4 Nodes: 3974273
Depth: 5 Score: 153 Move: H/2 -> H/3 Nodes: 4216318
Done thinking! best move is: H/2 -> H/4

这是包含我的迭代深化的代码片段:

public Move getBestMove() {

    System.out.println("getting best move");
    chessConsole.printCurrentGameState(this.chessgame);
    System.out.println("thinking...");

    int alpha = -INFINITY;
    int beta = INFINITY;

    Move bestMove = null;

    int bestScore = 0;

    List<Move> validMoves = evalFun.generateMoves(false);


    //startTime = System.nanoTime();

    for(currentDepth = 1; currentDepth <= maxDepth; currentDepth++){

        int bestResult = -1;

        evalFun.EvaluatePieceScore(validMoves.size(),currentDepth);


        for(int i = 0; i < validMoves.size(); i++){

            executeMove(validMoves.get(i));

            bestScore = AlphaBeta(alpha, beta,currentDepth, validMoves);

            undoMove(validMoves.get(i));

            System.out.println("Depth: "+currentDepth+" Score: "+bestScore+" Move: "+bestMove+" Nodes: "+nodes+"\n");


            if(bestScore > bestResult){
                bestMove = validMoves.get(i);
                bestResult = i;
            }
        }


    }           

    System.out.println("Done thinking! best move is: "+bestMove);
    return bestMove;
}

Answer 1

for(currentDepth = 1; currentDepth <= maxDepth; currentDepth++){

您专门切断了 maxDepth 处的加深。如果要更深入地搜索，则需要更改终止条件。