I documented the behaviour in the wiki. -> resolved.

> Gabi, if you're also reasonably happy with the changes, feel free to set this to
> resolved.

Actually, no, we should also document the changed behaviour on the wiki and
explain that this is different from the "The More, The Merrier" tech report.

*Then* this can be marked as resolved.

Gabi, if you're also reasonably happy with the changes, feel free to set this to
resolved.

I've had a look, and everything seems to be ok.
I think we can close this issue, and keep issue207 open.

Lazy search appears to work correctly after the changes to the evaluators and
heuristics -- I did test it. But of course it'd still be great if you would have
another look.

I've had a brief look, and it seems fine.
I think lazy search should also be changes - I'll take a look tomorrow.

I've merged this with the IPC repository already since it looks like an
improvement in any case, but I'll leave this at "reviewing" since I'd like to
hear your input on this.

There were several places in the code that had to be changed to accommodate
this, and since the search code is such a mess, I'm not confident it is all
correct (although it does seem to work).

Can you look at http://codereview.appspot.com/4045041/ and comment if you see
any potential problems? In particular, I'd like Gabi to comment on the change to
the insert method of alternation open queues. (I already added a comment there
to point out what I want to know.)


Here's the log message for that change:

Adressed issue206 and fixed some related and unrelated bugs:
 * alternation search will now expand a state this is considered
   a dead end by some but not all heuristics when all dead end
   reports are unreliable.
 * eager search no longer gets preferred operators from heuristics
   that think they are in a dead end (this could happen in cases
   where some heuristics reported dead ends but the state was still
   considered good).
 * fixed a bug in the alternation queue which would pick an empty
   queue in some cases (queue 0 is empty and has the highest priority)
 * Heuristic::get_heuristic() may now be called on dead ends and will
   return numeric_limit<int>::max(). However, this is a HACK and was
   only put in place to make the code work. I hope that the places that
   currently call this code without checking for dead ends first are
   benign (progress evaluator, and the code that stores h value in
   the search space in cases where we don't care about it because
   we don't reopen).

ARGH! The overridden versions of are_dead_ends_reliable for our heuristics were
never actually called since the base class version was declared const but the
derived versions were not, so that the derived versions were seen as *completely
different methods*. A compiler warning would have been nice there...

(The behaviour of the alternation heuristic still needs to be changed, but at
least we're now one step further.)

Note: the tech report for the "The More, The Merrier" paper agrees with the
current implementation (the paper itself doesn't discuss dead ends), so if we
change that, we should clearly document this difference in the wiki.

I made some tests with alternation on the IPC-2008 benchmark set and get some
very nice results except for combinations involving h^cea in Sokoban, which all
only solve 5 or 6 problems. For pure h^cea, the reason for this is that it
returns a huge amount of wrong infinite heuristic values, which is not a
surprise in Sokoban.

The surprise is that a combination like h^FF with h^cea should suffer from this
to this large extent. I checked the code, and currently a state is considered a
dead end by alternation as soon as any heuristic considers it a dead end.

I would expect that a state is only considered a dead end if *all* heuristics
consider it a dead end or if a *reliable* heuristic considers it a dead end. If
a state that is considered a dead end by some but not all heuristics is
expanded, it should then only be expanded in the sub-open-lists that don't
consider it a dead end.

Gabi agrees that this would be the behaviour she'd consider correct.

So I'll make this change.