ABP – Alpha-Beta Pruning

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;
}
0 0 vote
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments