基于二叉搜索树的java Alpha-Beta剪枝
我正在使用Alpha-Beta剪枝示例here完成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();
}
//Base Case #2: if reached a leaf node, return the value of the current node
if (nodeIndex.getLeft() == null && maximizingPlayer == false) {
return nodeIndex.getValue();
} else if (nodeIndex.getRight() == null && maximizingPlayer == true) {
return nodeIndex.getValue();
}
//Mini-Max Algorithm
if (maximizingPlayer) {
int best = MIN;
//Recur for left and right children
for (int i = 0; i < 2; i++) {
int val = minimax(depth + 1, nodeIndex.getLeft(), false, alpha, beta);
best = Math.max(best, val);
alpha = Math.max(alpha, best);
//Alpha Beta Pruning
if (beta <= alpha) {
break;
}
}
return best;
} else {
int best = MAX;
//Recur for left and right children
for (int i = 0; i < 2; i++) {
int val = minimax(depth + 1, nodeIndex.getRight(), true, alpha, beta);
best = Math.min(best, val);
beta = Math.min(beta, best);
//Alpha Beta Pruning
if (beta <= alpha) {
break;
}
}
return best;
}
}
}
输出:
Game Tree:
-1 ~ 0 ~ 1 ~ 2 ~ 3 ~ 5 ~ 6 ~ 9 ~
Game Results:
Optimal Value: 2
# 1 楼答案
您的问题是迭代依赖于循环控件2,而不是nodeIndex的node==null查找。getRight()(用于最大值)getLeft(用于最小值)
记住一棵树 1人(一级)
第二级=2
第三级=4
第4节8 等等因此,循环算法甚至不会下降3级
更改循环以正确控制迭代,您应该很容易找到最高值