Merged and pushed :)

Great, looks good to be merged! :-)

You're right, forgot to remove the plugin. This is fixed now.

Does this compile? ipc_max_evaluator.{h,cc} are gone, but I see no changes to
the Makefiles. Shouldn't those disappear from the cmake files, too?

I should have explained the motivation for the experiments better. The goal was 
to see if the performance of the max() evaluator is comparable to the ipc_max() 
hack. I have updated the pull request by backing out of the last changeset and 
removing IPCMaxHeuristic. Can this be merged?

Some things I don't understand:

1. Why do we need ipc_max_evaluator? I thought one of the points of this issue
was to get rid of this hack?

2. Looking at the pull request, it's not clear to me what you want to merge. The
version that I'm looking at right now isn't the one that was reviewed, and
definitely shouldn't be merged: it runs against the design of CombiningEvaluator
and contains two implementations of the maximum, of which only one is used.

Can you update the pull request so that it reflects the version of the code you
want to merge?

I ran some experiments. Here is the comparison between the max() implementation 
you (Malte) reviewed and ipc_max() (with heuristic caching disabled for better 
comparability):

http://ai.cs.unibas.ch/_tmp_files/seipp/issue182-v1-no-cache-compare.html

Since max() is a little slower than ipc_max() I tried to find the reason for the 
slowness and thought that maybe creating the temporary vector in 
combining_evaluator.cc could be the cuplrit. However, this doesn't seem to be the 
case:

http://ai.cs.unibas.ch/_tmp_files/seipp/issue182-v2-compare.html

Then I did what I should have done in the first place and profiled the code. It 
turns out that max() is slower because it has to report the progress for all 
heuristics instead of simply the ipc_max heuristic.

Given these findings, I'd propose to revert the code to the version you reviewed, 
remove the ipc_max implementation and merge the code. What do you think?

Thanks for looking into this, Jendrik! Code looks good to me.

I have created a small pull request for resurrecting the original max() plugin. 
Malte, can you have a look at the code please?

https://bitbucket.org/jendrikseipp/downward/pull-requests/45

If the code looks ok, I will run experiments comparing max() to ipc_max(). 
Afterwards, I'll remove ipc_max().

During a discussion about issue77 we noted that a fix for the issue at hand 
should take into account that heuristics should not be evaluated multiple times 
for the same state.

> => If the current version works already, then this means you just have to change
> the class name, file names and option name and I'll merge.

On second thought, the option name should be "max" so that Chris doesn't have to
change the wrapper script around again. The existing "max" plugin should then be
commented out with a link to this issue or whatever other issue is relevant for
this.

But please do change the file name and class names to document that this is a
temporary hack for the IPC.

OK, then this applies:

> So Erez, if you want to push this solution, feel free to add it to the relevant
> branch again under a different name (ipc_max_heuristic.cc). I'll then take a
> look at it later. I'd also like to look at alternative solutions, though.

=> If the current version works already, then this means you just have to change
the class name, file names and option name and I'll merge.

What I mean is that I don't think it's worth the trouble of 
making the ScalarEvaluator implementation of max work.
We could use the Heuristic implementation, which I think is the right thing to do 
for now, and switch to the ScalarEvaluator implementation after we take care of 
storing the values of all heuristics.

This is turning out to be trickier than I thought.
The main problem is that a Heuristic and a ScalarEvaluator behave differently 
under evaluate(g,preferred) - the Heuristic ignores this, and the 
ScalarEvaluator updates its value based on the component evaluators. 

This means that before, when we had (when we reopen a node):

heuristics[0]->set_evaluator_value(...)
open_list->evaluate(...)

everything worked fine. If we replace heuristics[0] with a ScalarEvaluator, this 
doesn't work, and would require complicating the Evaluator/evaluate structure 
even more. 

So I think it's not worth the trouble, and we will eventually fix this by saving 
all the heuristic values.

If anyone disagrees, or has a better suggestion about how to do this - let me 
know.

I haven't looked at the code properly enough to really understand all the issues
fully, but with that caveat: this idea sounds very good to me.

What we can do for now is to add another parameter to GeneralEagerBestFirstSearch 
- main_evaluator - which will replace anywhere heuristics[0] is used in the code.
Then the A* creation code will pass the h argument, and we'll find something that 
won't break the code for the other cases.
If that sounds good, I can work on this tomorrow.

> This is the reason I implemented max() as a heuristic.

I don't think this is a solution; in particular, max(...) should not call
reach_state and evaluate(state) of the component evaluators since things like
"max(sum(h1, h2), sum(h1, h3), sum(h2, h3))" won't work correctly. (Actually, I
think max(sum...) won't work at all because that implementation of max(...) only
worked for heuristics, not arbitrary scalar evaluators.)

Supporting maxes of sums is something we need for the PDB heuristics that some
people here are working on at the moment (not for the IPC, of course) and also I
think it's something that a flexible planner should support.

> Generally, I don't see any non-ugly way of doing this, since the search
> basically gets an open-list, and does not know what the "main" evaluator is.
> I  also can't think of a reasonable way to define the "main" evaluator, which
> would not have many special cases (for A*, it's the second in the
> tie-breaking open list, for GBFS it's the first, with alternation ... who
> knows?)

There certainly isn't an obvious solution.

I'll think about this again later tonight, after finishing the h^CG and h^cea
code. For the IPC, the main thing is that A*, weighted A*, greedy BFS, and
alternation over such evaluators are handled correctly, so maybe one or two
special cases are sufficient for now until we've found a way to handle this more
cleanly.

If I can be convinced that implementing max(...) as a heuristic does the right
thing in the cases we care about for the IPC, I wouldn't be averse to
implementing that solution *for the IPC only* under a special name and
command-line option (e.g. ipcmax). It really goes against the intended
architecture of the code, so we should make sure it's not turned into a
permanent or semi-permanent solution.

So Erez, if you want to push this solution, feel free to add it to the relevant
branch again under a different name (ipc_max_heuristic.cc). I'll then take a
look at it later. I'd also like to look at alternative solutions, though.

This is the reason I implemented max() as a heuristic.
Generally, I don't see any non-ugly way of doing this, since the search 
basically gets an open-list, and does not know what the "main" evaluator is. I 
also can't think of a reasonable way to define the "main" evaluator, which would 
not have many special cases (for A*, it's the second in the tie-breaking open 
list, for GBFS it's the first, with alternation ... who knows?)

> The problem is that the SearchSpace currently supports storing only 1
> heuristic value per node, so we use heuristic[0].

Sure, I remember that discussion. But in the case of something like sum(h1, h2)
or max(h1, h2), we have heuristics.size() == 2 (since h1 and h2 must be
evaluated), yet there is still only one value to be considered (the sum or max,
respectively). In this case, heuristics[0] refers to h1, I think, which is the
wrong thing to put into the search space. I'd appreciate it if someone could do
a complete check of the code to test that really the correct thing happens in
this case.

I'm not too worried about the output at this stage, although we should work on
that too eventually, but something like astar(max(...)) should work.

> We talked about this a long time ago, and said we would assign each node an
> ID, and have the heuristics keep track of the heuristic values in a hash_map.

Right. Small correction: I think this should be a vector, not a hash_map. If we
use consecutive IDs (no reason not to), that's much faster and much more
memory-efficient.

Also - this is just a display bug. 
What happens is that we report the f-value when a node is removed from the open 
list. When this happens, we only have the h-value of the first heuristic, so we 
get that value from the SearchNode, while the value of the other heuristic stays 
the same (i.e., from the last state), and so this is displayed.

The f-evaluator is only for display, so it isn't a problem for the search, but I 
agree we should do something about this (see msg1034).

The problem is that the SearchSpace currently supports storing only 1 heuristic 
value per node, so we use heuristic[0].
We talked about this a long time ago, and said we would assign each node an ID, 
and have the heuristics keep track of the heuristic values in a hash_map.

Maybe this is related to the fact that are various places in the eager search
code that refer to "heuristics[0]" exclusively -- this looks very fishy to me in
cases like max(h1,h2) where we have two heuristics.

When I run

../translate/translate.py ../../benchmarks/mystery/prob13.pddl
../preprocess/preprocess < output.sas
./downward-debug < output --heuristic 'h1=ff()' --heuristic 'h2=cea()' --search
'astar(sum(h1, h2))'

I get the output f = 2147483647 [697 evaluated, 32 expanded, t=2.88s]
at some point. This happens both in master and in the new SumEvaluator code in
the issue181 branch.

This should not happen. I wonder if this is just a display bug, i.e., if it's
something to do with the f_evaluator, but it should nevertheless be fixed.