我头痛的理解为什么某个节课上的某些节点因为alpha-beta修剪而被打印出来,所以我实现了Peter Norvig的Java版alpha beta修剪。修剪算法
With a tree like this:
max
/ | \
min min min
// | /| \ /| \
3 12 8 2 3 9 14 1 8
教科书上说,应扩大的唯一终端节点
3, 12, 8, 2, 14, 1
的顺序
。
我的算法打印:
visited leaf with value 3
visited leaf with value 12
visited leaf with value 2
visited leaf with value 3
visited leaf with value 14
visited leaf with value 1
visited leaf with value 8
Root value 3
根是极大极小根正确的值。我已经调试了几个小时,似乎无法找到问题。我忽略了一些东西还是教科书不正确?
package alphabeta;
import java.util.ArrayList;
class Node {
boolean isMin;
boolean isMax;
boolean isTerminal;
int value;
int depth;
ArrayList <Node> children = new ArrayList <Node>();
}
public class AlphaBeta {
static Node alphaBetaSearch(Node state){
state.value = max_value(state,-99999,99999);
System.out.println(state.value);
return null;
}
static int max_value(Node state, int alpha, int beta){
if (state.isTerminal){
System.out.println("visited leaf with value " + state.value);
return state.value;
}
state.value = -99999;
for (Node a: state.children){
state.value = Math.max(state.value , min_value(a, alpha, beta));
if (state.value >= beta){
return state.value;
}
alpha = Math.max(alpha, state.value);
}
return state.value;
}
static int min_value(Node state, int alpha, int beta){
if (state.isTerminal)
return state.value;
state.value = 99999;
for (Node a: state.children){
state.value = Math.min(state.value, max_value(a, alpha, beta));
if (state.value >= beta){
return state.value;
}
beta = Math.min(beta, state.value);
}
return state.value;
}
public static void main(String[] args) {
Node t1 = new Node();
// t1.value = 4;
t1.value = 3;
t1.depth =2;
t1.isTerminal = true;
Node t2 = new Node();
// t2.value = 8;
t2.value = 12;
t2.depth=2;
t2.isTerminal= true;
Node t3 = new Node();
// t3.value = 7;
t3.value = 8;
t3.depth=2;
t3.isTerminal= true;
Node min1 = new Node();
min1.isTerminal=false;
min1.depth=1;
min1.children.add(t1);
min1.children.add(t2);
min1.children.add(t3);
Node t4 = new Node();
// t4.value = 5;
t4.value = 2;
t4.depth =2;
t4.isTerminal = true;
Node t5 = new Node();
//t5.value = 2;
t5.value =3;
t5.depth=2;
t5.isTerminal= true;
Node t6 = new Node();
// t6.value = 1;
t6.value=9;
t6.depth=2;
t6.isTerminal= true;
Node min2 = new Node();
min2.isMin=true;
min2.isTerminal=false;
min2.depth=1;
min2.children.add(t4);
min2.children.add(t5);
min2.children.add(t6);
Node t7 = new Node();
// t7.value = 1;
t7.value=14;
t7.depth =2;
t7.isTerminal = true;
Node t8 = new Node();
// t8.value = 6;
t8.value=1;
t8.depth=2;
t8.isTerminal= true;
Node t9 = new Node();
// t9.value = 0;
t9.value=8;
t9.depth=2;
t9.isTerminal= true;
Node min3 = new Node();
min3.isMin=true;
min3.isTerminal=false;
min3.depth=1;
min3.children.add(t7);
min3.children.add(t8);
min3.children.add(t9);
Node max1 = new Node();
max1.isMax=true;
max1.isTerminal=false;
max1.depth=0;
max1.children.add(min1);
max1.children.add(min2);
max1.children.add(min3);
alphaBetaSearch (max1);
}
}
是你对你的算法的理解是否正确的问题,还是你的代码的算法的理解一致? – 2011-12-18 01:17:53
@Oli Charlesworth:我会说,这本教科书正确的是关于极大极小树的alpha-beta修剪输出吗?它是我的代码吗?它既不是? – andandandand 2011-12-18 01:21:42
你能否提供一些关于教科书的参考? – 2011-12-18 01:24:48