MM – MinMax Search

	private BiPredicate < Integer, Node > searchLimitingPredicate;
	private int depth;

	/**
	 * To limit the extent of the search, this implementation should honor a
	 * limiting predicate. The predicate returns 'true' as long as we are below
	 * the limit, and 'false', if we exceed the limit.
	 * 
	 * @param searchLimitingPredicate
	 */
	public MinMaxSearch(BiPredicate < Integer, Node > slp) {
	    this.searchLimitingPredicate = slp;
	    depth = 0;
	}

	public Pair < Node, Double > search(Node start, Function < Node, Double > evalFunction) {
	    Node winner = start;
	    double value = Double.NEGATIVE_INFINITY;

	    for (Node n: start.adjacent()) {
	        double temp = min(n, evalFunction);
	        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) {
	    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));
	    }
	    depth--;
	    return value;
	}

	private double max(Node node, Function < Node, Double > evalFunction) {
	    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));
	    }
	    depth--;
	    return value;
	}
0 0 vote
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments