CODEWITHSUNDEEP
optimizationprolog
Thijser
Thijser

Reputation: 2633

Finding the highest possible evaluation in prolog

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?

Upvotes: 2

Views: 132

Answers (2)

CapelliC
CapelliC

Reputation: 60034

library(aggregate) could help:

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

Upvotes: 0

repeat
repeat

Reputation: 18726

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

:- 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 measurements2 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).

Upvotes: 3

Related Questions