java - Minimax は左端の葉にのみ下がります

Question

それで、オセロ ゲーム用の小さなボード ゲームを手に入れました。このゲームでは、AI は Alpha Beta Prune 検索アルゴリズムを使用して何を移動するかを決定する必要があります。私は次の疑似コードフォームgeeksforgeeksを使用しました：

function minimax(node, depth, isMaximizingPlayer, alpha, beta):

    if node is a leaf node :
        return value of the node

    if isMaximizingPlayer :
        bestVal = -INFINITY 
        for each child node :
            value = minimax(node, depth+1, false, alpha, beta)
            bestVal = max( bestVal, value) 
            alpha = max( alpha, bestVal)
            if beta <= alpha:
                break
        return bestVal

    else :
        bestVal = +INFINITY 
        for each child node :
            value = minimax(node, depth+1, true, alpha, beta)
            bestVal = min( bestVal, value) 
            beta = min( beta, bestVal)
            if beta <= alpha:
                break
        return bestVal

これが私がそれを実装した方法です：

//Called when it's the AI's turn to make a move. 
    public Board makeMove(Board board) {
        setRoot(board);
        int alpha = Integer.MIN_VALUE;
        int beta = Integer.MAX_VALUE;

        int val = alphaBetaSearch(tree.getRoot(), 0, true, alpha, beta);
        Board resultBoard = //Should be AI Board/move

        setRoot(resultBoard);
        return resultBoard;
    }

    private int alphaBetaSearch(Node node, int depth, boolean maximizing, int alpha, int beta) {
        currentDepth = depth;
        if (node.isLeaf()) {
            return evaluateUtility(node.getBoard());
        }

        if (maximizing) {
            int bestValue = Integer.MIN_VALUE;
            for (Node child : node.getChildren()) {
                int value = alphaBetaSearch(child, depth + 1, false, alpha, beta);
                bestValue = Integer.max(bestValue, value);
                alpha = Integer.max(alpha, bestValue);
                if (beta <= alpha) {
                    break;
                }
                return alpha;
            }

        } else {
            int bestValue = Integer.MAX_VALUE;
            for (Node child : node.getChildren()) {
                int value = alphaBetaSearch(child, depth + 1, true, alpha, beta);
                bestValue = Integer.min(bestValue, value);
                beta = Integer.min(beta, bestValue);
                if (beta <= alpha) {
                    break;
                }
                return beta;
            }
        }
        return 0; //Not sure what should be returned here
    }

    private int evaluateUtility(Board board) {
        int whitePieces = board.getNumberOfWhiteCells();
        int blackPieces = board.getNumberOfBlackCells();
        int sum = (blackPieces - whitePieces);
        return sum;
    }

私のボードはかなり小さい (4x4) ので、ゲームが始まる前に約 20 秒で完全な検索ツリーを計算することができました。プレイ中に何も構築していないため、これにより検索が改善されるはずです。私のツリーの各ノードには、セルの 2D 配列を持つボードが含まれています。ルート ノード/ボードは次のようになります。

EMPTY EMPTY EMPTY EMPTY
EMPTY WHITE BLACK EMPTY
EMPTY BLACK WHITE EMPTY
EMPTY EMPTY EMPTY EMPTY

ゲームを開始すると、これがスターティング ボードであり、AI を呼び出して動きを出します。ミニマックス呼び出しが実行されると、深さ 12 で値 2 が返されます。深さ 12 は、ツリー内のリーフ ノード/ボードです。デバッガーで実行した後、私の実装はツリーをたどらないようです。一番左のツリーに降りて、その評価を返すだけです。