private BiPredicate < Integer, Node > searchLimitingPredicate;
private int depth;
public AlphaBetaSearch(BiPredicate < Integer, Node > searchLimitingPredicate) {
this.searchLimitingPredicate = searchLimitingPredicate;
}
public Pair < Node, Double > search(Node start, Function < Node, Double > evalFunction) {
Node winner = start;
double value = Double.NEGATIVE_INFINITY;
double alpha = Double.NEGATIVE_INFINITY;
double beta = Double.POSITIVE_INFINITY;
for (Node n: start.adjacent()) {
double temp = min(n, evalFunction, alpha, beta);
if (temp > value) {
value = temp;
winner = n;
}
depth = 0;
}
return new Pair < Node, Double > (winner, value);
}
private double min(Node node, Function < Node, Double > evalFunction, double alpha, double beta) {
if (node.isLeaf() || !searchLimitingPredicate.test(depth + 1, node)) {
return evalFunction.apply(node);
}
depth++;
double value = Double.POSITIVE_INFINITY;
for (Node n: node.adjacent()) {
value = Math.min(value, max(n, evalFunction, alpha, beta));
if (value <= alpha) break;
beta = Math.min(beta, value);
}
depth--;
return value;
}
private double max(Node node, Function < Node, Double > evalFunction, double alpha, double beta) {
if (node.isLeaf() || !searchLimitingPredicate.test(depth + 1, node)) {
return evalFunction.apply(node);
}
depth++;
double value = Double.NEGATIVE_INFINITY;
for (Node n: node.adjacent()) {
value = Math.max(value, min(n, evalFunction, alpha, beta));
if (value >= beta) break;
alpha = Math.max(alpha, value);
}
depth--;
return value;
}
Subscribe
Please login to comment
0 Comments