|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
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; } |