Did not find all solutions

[goundoulf]

Hi, and first of all thanks for your great software!

I think I've stumbled on a small bug in the solver, as it did not find all the solutions:

Another solution in 7 moves is : East - South - West - North - East - South - West

[smack42]

Thanks for your feedback, I'm going to investigate this.

[goundoulf]

Thanks!

[chris0804]

I think the program distinguish distinct solutions by final position. In
other words, if two solutions have the same final position, the program
will think it's the same solution. I think this is a very reasonable
design.

On Sun, Apr 5, 2015 at 5:33 AM, goundoulf notifications@github.com wrote:

Thanks!

—
Reply to this email directly or view it on GitHub
#7 (comment)
.

[smack42]

So I checked the code again and can confirm that the reported behavior is not a bug, but rather a consequence of the extensive optimizations of the search algorithm. It uses a special data structure to remember all evaluated positions (locations of all robots) and avoids to follow any (part of a) path more than once. This is the single, most important optimization idea that makes the solver algorithm run fast.

Other programs use this trick as well. Have a look Michael Fogleman's presentation and program:
https://speakerdeck.com/fogleman/ricochet-robots-solver-algorithms
https://github.com/fogleman/Ricochet
On slide 8 (Memoization?) he says: (emphasis added by me)

If current position has already been searched to an equal or greater depth, prune the search.

The example reported here (FA4D+50+C6F051AA8A+1C) has two possible solutions in 7 moves:
red: E N W N E S W
red: E S W N E S W
The search algorithm follows the first path (E N ...) and stores all robot positions after each move. Then it follows the second path (E S ...). After the 4th move (N) it reaches a position that's already known from the first path. It then discards the second path because it will not result in a better solution.

But we know that the second path results in an equally good solution! I've tested a straightforward code change (in KeyDepthMapTrieSpecial, the lines marked with //putIfGreater use operator >= instead of >) to let the solver find both solutions, and it works just fine.

Unfortunately this modification slows down the search considerably when longer solutions have to be found. For a 10-moves problem (ACDB+52+D9F57C608D+A1) it finds 3 distinct solutions (instead of 2), but search time increases from 0.1 to 6 seconds. And the really hard benchmark tests (like the 24-moves problem 0765+42+2E21BD0F+93) can't even be finished any more, it just runs "forever".

At the moment I can't come up with an idea to implement the requested feature without a performance regression. Maybe I should just add another checkbox to the solver options, a new "thorough, slow search mode" or something like that? What do you think?

[chris0804]

It's crucial that you prune these equally good results, otherwise you
algorithm will be significantly slower for solutions with multiple pieces.
This is because exponentially many solutions can be created just by move
the different colored pieces in different order.

For instance, let's say the solution is Red E, Red S, Red W, Blue S, Blue
W. And the Blue and Red doesn't touch each other until the very last
move. Then all of the following would also be valid solutions.

Blue S, Red E, Red S, Red W, Blue W.
Red E, Blue S, Red S, Red W, Blue W.
Red E, Red S, Blue S, Red W, Blue W.

If there are r moves for red and b moves for blue, r > b, and if they only
touches in the end. There would be this many solutions,

                  (r+b-1)!

r+b-1 choose b-1 = ---------------
r! (b-1)!

This grows exponentially as r and b gets larger.

• Chris

P.S. The number of solutions turn out to be the same as this problem.

http://math.stackexchange.com/questions/150285/what-will-be-total-number-of-solutions-of-abc-n

On Tue, Apr 7, 2015 at 5:13 AM, Michael Henke notifications@github.com
wrote:

So I checked the code again and can confirm that the reported behavior is
not a bug, but rather a consequence of the extensive optimizations of the
search algorithm. It uses a special data structure to remember all
evaluated positions (locations of all robots) and avoids to follow any
(part of a) path more than once. This is the single, most important
optimization idea that makes the solver algorithm run fast.

Other programs use this trick as well. Have a look Michael Fogleman's
presentation and program:
https://speakerdeck.com/fogleman/ricochet-robots-solver-algorithms
https://github.com/fogleman/Ricochet
On slide 8 (Memoization?) he says: (emphasis added by me)

If current position has already been searched to an equal or greater
depth, prune the search.

The example reported here (FA4D+50+C6F051AA8A+1C) has two possible
solutions in 7 moves:
red: E N W N E S W
red: E S W N E S W
The search algorithm follows the first path (E N ...) and stores all robot
positions after each move. Then it follows the second path (E S ...). After
the 4th move (N) it reaches a position that's already known from the first
path. It then discards the second path because it will not result in a
better solution.

But we know that the second path results in an equally good solution!
I've tested a straightforward code change (in KeyDepthMapTrieSpecial, the
lines marked with //putIfGreater use operator >= instead of >) to let the
solver find both solutions, and it works just fine.

Unfortunately this modification slows down the search considerably when
longer solutions have to be found. For a 10-moves problem
(ACDB+52+D9F57C608D+A1) it finds 3 distinct solutions (instead of 2), but
search time increases from 0.1 to 6 seconds. And the really hard benchmark
tests (like the 24-moves problem 0765+42+2E21BD0F+93) can't even be
finished any more, it just runs "forever".

At the moment I can't come up with an idea to implement the requested
feature without a performance regression. Maybe I should just add another
checkbox to the solver options, a new "thorough, slow search mode" or
something like that? What do you think?

—
Reply to this email directly or view it on GitHub
#7 (comment)
.

[goundoulf]

Maybe the first thing to do would be to explain clearly that the solver will not show all the possible solutions, this way users won't be surprised that the solver does not show the solution they have found, and which is equally good :)

But now I know this, it don't think you need to change anything!

[smack42]

Added an optional "slow search" mode that doesn't prune the search tree as aggressively as the standard search. As a result of this, it runs significantly slower, but it finds a larger number of distinct, equally good solutions for some game positions.
It's activated by system property "UseSlowSearchMoreSolutions". (for example in file appstart.properties or as VM parameter -DUseSlowSearchMoreSolutions)

[smack42]

closed by release 1.3.5
https://github.com/smack42/DriftingDroids/releases/tag/1.3.5