我正在尝试在 java 中实现 Mini Max & Alpha Beta Pruning 算法,由于某种原因,尽管算法访问了 24,911 个节点,但 Pruning 算法不执行单个修剪。GameNode 值初始化为 MaxNodes 的 -99 和 MinNodes 的 99 以及 Alpha=-99 \ Beta=99。游戏称为“Nim”,数值为 1 或 -1,输赢,不得分。知道为什么修剪不会发生吗?
这是修剪的代码:
public static int Prune(GameNode n){
if(n.getSuccessors()==null)
return n.GetUtilityValue();
else if(n.getPlayer().equals(GameNode.Player.MAX)) // A's move
{
int value;
if(n.getFather()!=null){
if(n.getFather().getAlpha()>n.getAlpha())
n.setAlpha(n.getFather().getAlpha());//Pass down alpha value
if(n.getFather().getBeta()<n.getBeta())
n.setBeta(n.getFather().getBeta());//Pass down beta value
}
for(GameNode s : n.getSuccessors())
{
if(n.getValue() > n.getBeta()) // if Current value > Beta => then prune this node
{
GameNode.prune++;
break;
}
if(s!=null){
GameNode.counter++;
value = MiniMax(s);
if(value>n.getValue()){// Is leaf bigger then current value ? then set value and Alpha value
n.setValue(value);
if(value > n.getAlpha())
n.setAlpha(value);
}
}
}
return n.getValue();
}
else // B's move
{
int value;
if(n.getFather().getAlpha()>n.getAlpha())
n.setAlpha(n.getFather().getAlpha());//Pass down alpha value
if(n.getFather().getBeta()<n.getBeta())
n.setBeta(n.getFather().getBeta());//Pass down beta value
for(GameNode s : n.getSuccessors())
{
if(n.getValue() < n.getAlpha())// if Current value < Alpha => then prune this node
{
GameNode.prune++;
break;
}
if(s!=null) {
GameNode.counter++;
value = MiniMax(s);
if(value<n.getValue()){// Is leaf smaller then current value ? then set value and Beta value
n.setValue(value);
if(value < n.getBeta())
n.setBeta(value);
}
}
}
return n.getValue();
}
}