当前位置: 动力学知识库 > 问答 > 编程问答 >

artificial intelligence - Java : Alpha Beta Pruning

问题描述:

I'm trying to implement a Mini Max & Alpha Beta Pruning algorithm in java, for some reason the Pruning algorithm does not perform a single prune although the algorithm visits 24,911 Nodes.

The GameNode values are initiated to -99 for MaxNodes and 99 for MinNodes aswell as Alpha=-99 \ Beta=99.

The game is called "Nim" and the value is either 1 or -1, win or lose, no score.

Any idea why pruning does not happen ?

Here's the Code for the Pruning :

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();

}

}

分享给朋友:
您可能感兴趣的文章:
随机阅读: