I have predicate, that enumerates through backtracking list of values. I want to find highest value from this list.

For example:

ranked_move(X,Y,R) :- between(0,10,Y), between(0,10,X), rank_move(X,Y,R).
top_move(X,Y) :- % X, Y for highest R

Right now, I have it solved by using findall and custom predicate that goes through the list and remembers highest value it comes across. But I would like to know if there is way to do it without first turning the moves into a list. Eg. do the picking predicate directly on ranked_move.

I know about https://stackoverflow.com/questions/1701693/max-out-of-values-defined-by-prolog-clauses . I haven't tried it, but I assume Prolog is not going to go through the predicates efficiently.

  • I just noticed I posted this on Programmers, not on SO. – Euphoric Apr 20 '13 at 5:50

As long as you don't have any way of judging your moves except calling ranked_move/3, no, there is no more efficient way than calling it on everything and finding the maximum of the resulting list.

It would be possible to avoid the findall by writing your own predicates that generate the values systematically and remember the maximum so far, and so avoid the overhead of creating a list. But that overhead is very likely insignificant next to the cost of judging the moves (no heuristic worth implementing could possibly be cheaper than a cons operation).

So the only really useful improvement would be to have a different, cheaper, weaker heuristic that influences the order in which the moves are generated, and iterate over them in an order more likely to have the maximum first. (Even then, of course, you would still not terminate any quicker unless you set a cutoff value that is "good enough" rather than "optimal".)

| improve this answer | |
  • You are right. I was focusing on wrong part of the problem. – Euphoric Apr 20 '13 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.