使用二叉搜索树进行 Alpha Beta 剪枝

Question

我正在使用此处找到的 Alpha-Beta 修剪示例来研究 Minimax 算法。在示例中，他们使用数组来实现搜索树。我遵循了这个例子，但也尝试用二叉搜索树来实现它。以下是我在树中使用的值：3、5、6、9、1、2、0、-1。

最后的最佳值应该是 5。使用 BST 实现，我一直得到 2。

我认为这是问题所在，但我不知道如何解决它：

如果在尝试检查下一个值时看到叶节点停止获取空指针异常，我编写了代码以退出递归。但是相反，我认为它过早地停止搜索（基于我在使用调试器单步执行代码时看到的内容）。但是，如果我删除检查，则代码会在空指针上失败。

有人可以指出我正确的方向吗？我究竟做错了什么？

这是代码：

public class AlphaBetaMiniMax {

    private static BinarySearchTree myTree = new BinarySearchTree();

    static int MAX = 1000;

    static int MIN = -1000;

    static int opt;

    public static void main(String[] args) {

        //Start constructing the game

        AlphaBetaMiniMax demo = new AlphaBetaMiniMax();

        //3, 5, 6, 9, 1, 2, 0, -1

        demo.myTree.insert(3);

        demo.myTree.insert(5);

        demo.myTree.insert(6);

        demo.myTree.insert(9);

        demo.myTree.insert(1);

        demo.myTree.insert(2);

        demo.myTree.insert(0);

        demo.myTree.insert(-1);

        //print the tree

        System.out.println("Game Tree: ");

        demo.myTree.printTree(demo.myTree.root);

        //Print the results of the game

        System.out.println("\nGame Results:");

        //run the  minimax algorithm with the following inputs

        int optimalVal = demo.minimax(0, myTree.root, true, MAX, MIN);

        System.out.println("Optimal Value: " + optimalVal);

    }

    /**

     * @param alpha = 1000

     * @param beta = -1000

     * @param nodeIndex - the current node

     * @param depth - the depth to search

     * @param maximizingPlayer - the current player making a move

     * @return - the best move for the current player

     */

    public int minimax(int depth, MiniMaxNode nodeIndex, boolean maximizingPlayer, double alpha, double beta) {

        //Base Case #1: Reached the bottom of the tree

        if (depth == 2) {

            return nodeIndex.getValue();

        }

        }

    }

}

输出：

Game Tree: 

-1 ~ 0 ~ 1 ~ 2 ~ 3 ~ 5 ~ 6 ~ 9 ~ 

Game Results:

Optimal Value: 2

Answer 1

您的问题是您的迭代取决于 2 的循环控制，而不是 node== null 查找 nodeIndex.getRight()(for max) getLeft(for min.)记住一棵树有 1 个头（第一级）第二级 = 2第 3 级 = 44日8等。所以你的循环算法甚至不会下降 3 个级别。for (int i = 0; i < 2; i++) {&nbsp; &nbsp; &nbsp;int val = minimax(depth + 1, nodeIndex.getLeft(), false, alpha, beta);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; best = Math.max(best, val);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; alpha = Math.max(alpha, best);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //Alpha Beta Pruning&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (beta <= alpha) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }更改循环以正确控制迭代，您应该很容易找到最高值。