Better heuristic

[Kelsonk]

Hi! Don't know if you'll see this but I'm currently implementing a solver for Ricochet Robots. I wouldn't have gotten very far without your help!

I was wondering if you had any thoughts on making it faster. I've implemented a lot of 6x6 and fewer puzzle-solutions (with multiple goals!) but trying to get boards as close to the original game (16x16, 4 or 5 robots, 1 goal) is very slow. What kind of speed are you getting? I've tried messing with the bestimate heuristic but it's not helping much. Any ideas off the top of your head? I'm wondering if prioritizing game states where non target robots have a min dist of 2 to the target goal and off by 1 on the row or column (so that the target piece could bounce off it) would be much higher priority.

I know I can test a lot of this yourself, just wondering if you had anything off hand.

[johnnoel]

Hi there! Glad to hear you're trying out a solver, it's a fun problem!

In terms of my implementation speed, you can see an example on https://solver.orthog.uk/ (just click on any square then click "Solve"). On my machine (an average 2018 desktop) in Firefox that gets solved in less than a second and looks at around 24,000 states to come up with a solution (check the devtools console for the gameBuilder/finishSolving action, the next state object contains details).

What language/runtime are you implementing your solver in? Are you sure it's the heuristic that's causing the slowness you're experiencing? When I was developing this, the main speed ups came from:

• pre-calculating the moves for every square - this made next-state calculation a lot quicker as you just needed to interpolate the current robot positions
• filtering out seen board states - each state is given a "key" that encodes non-target robot positions and if the same state is seen again during solving, it's pruned as not worth exploring
• the "bestimate" as you've already mentioned

I was fairly happy with the speed so haven't really thought of any further speed ups but it'd be worth knowing which parts of your solver are contributing the most to the time taken.

[Kelsonk]

Thanks for responding! I'm currently using actionscript. it I actually figured out I was using the default implementation of array.sort (I wasn't sure exactly what a flatqueue was) and it was causing most of the slowdown. It's working pretty good now but I'm sure there's room for improvement. Thanks again!