Finding the highest possible evaluation in prolog

Question

I'm working on a problem where I have to evaluate the outcome of a gametree. The problem is that I would like to compare the result of the tree. For this I have something like this:

bestOption(SomeVariables, Result) :-
   generateOption(SomeVariables, Result),
   evaluate(Result). % dark magic ensures that Result is the highest possible value

However, I would now like to find the Result that is optimal. Preferably with some clever caching.Any idea?

This is prolog in the goal programming language.

Any idea how to do this?

What do you mean when you speak of "gametree"? Minimax or alpha-beta-pruning, perhaps? Or rather something different? — repeat, Jan 06 '16 at 11:37
The gametree contains a list of variables which have to be tried in pretty much every possible configuration, it's a list of some 10-5 variables that all have to be included or excluded (2^10-2^15 options) and I can easily test how good they are, but I just want to find which one is best. — Thijser, Jan 06 '16 at 11:40
I copy that. Which domain do you use for modeling the problem and how are potential candidates evaluated? — repeat, Jan 06 '16 at 11:54
OTOH it appears to me that you are referring to a **Boolean vector** with size `N` (and thus `2^N` variations). Are there by any chance **algebraic properties** that are guaranteed to hold? Something like: "adding an item to a bag does not make the bag any *lighter*" or "removing an item from a bag does not make the bag any *heavier*". — repeat, Jan 06 '16 at 11:58
There are some properties but the full evaluation only makes sense once we have completed the entire list. — Thijser, Jan 06 '16 at 12:00
If the evaluation of *partially instantiated* candidates does not make sense (e.g., too complex, too slow, too little domain propagation, etc.), then "brute force" is your weapon of choice. Good for you: Prolog is **strong** at that! — repeat, Jan 06 '16 at 12:06
If a good estimator is available, consider using branch-and-bound search. — repeat, Jan 06 '16 at 12:07
Well "brute force" is my weapon of choice but how do I pick the highest value out of all possible assignments? — Thijser, Jan 06 '16 at 12:15
I'll prepare an answer that only cares about **that** specific point. Wishes? Suggestions? — repeat, Jan 06 '16 at 12:30
No that would be fine, I just don't want the answer to have to go over every possible assignment more then once. — Thijser, Jan 06 '16 at 12:32
I'm using the one included in the standard goal IDE. Not sure which one that is. — Thijser, Jan 06 '16 at 13:01

score 3 · Accepted Answer · edited May 23 '17 at 12:23

In this answer we're searching for Boolean lists of length N having a maximum Hamming weight¹.

:- use_module(library(clpfd)).

:- set_prolog_flag(toplevel_print_anon, false).

length_Booleans_weight_(Length, Booleans, Weight, [Weight|Booleans]) :-
   length(Booleans, Length),
   Booleans ins 0..1,
   sum(Booleans, #=, Weight).

Let's use call_time/2 for runtime measurements² of different problem instance sizes:

?- member(Length, [10,20,30,40,50,60,70,80,90,100]),
   call_time(once((length_Booleans_weight_(Length,Booleans,Weight,_Zs),
                   labeling([max(Weight)],_Zs))),
             T_ms).
   Len = Weight, Weight =  10, T_ms =    4, Booleans = [1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  20, T_ms =   32, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  30, T_ms =   58, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  40, T_ms =  124, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  50, T_ms =  234, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  60, T_ms =  376, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  70, T_ms =  580, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  80, T_ms =  845, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight =  90, T_ms = 1178, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
;  Len = Weight, Weight = 100, T_ms = 1619, Booleans = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1].

^{Footnote 1: Of course, we know that all maxima fulfill the goal Weight = Length, maplist(=(1), Booleans).

Footnote 2: Using SWI-Prolog 7.3.14 (64-bit).}

If I understand this correctly set_prolog_flag is used to govern the limit of the size of the output. But I'm not sure I can follow how this works after all I understand that Length Becomes the number of booleans we try, Booleans are either a set of 0's and 1's and that the Weight is the total weight of the Booleans but how are you making sure that the call itself only finds the highest value? — Thijser, Jan 06 '16 at 13:46
Use rather `library(lambda)` to suppress the display of the answersubstitution of `_Zs` — false, Jan 06 '16 at 13:48
@false. I consider switching to using SICStus Prolog in this answer. Then I could "legitimately" bend most links to the better User's manual / documentation. I'm on the fence. — repeat, Jan 06 '16 at 13:57
@Thijser. Look at the documentation of `labeling/2`! (I included links in the answer above.) The first argument is a list of arguments used for fine-tuning the constraint based enumeration. Consider: `labeling([max(Weight)],_Zs)`. — repeat, Jan 06 '16 at 13:59
Ah so we can use something like `bestOption(SomeVariables, Result,Value) :- generateOption(SomeVariables, Result), evaluate(Result,Value),labelling([max],value).`? — Thijser, Jan 06 '16 at 14:06

score 0 · Answer 2 · answered Jan 06 '16 at 18:09

0

library(aggregate) could help:

bestOption(Vars, Result) :-
   aggregate(max(Res, Vars), (generateOption(Vars, Res), evaluate(Res)), max(Result, _)).

answered Jan 06 '16 at 18:09

CapelliC

59,646
5
47
90

Finding the highest possible evaluation in prolog

2 Answers2