I wonder if the A* search is actually faster than a somewhat optimized SAT encoding like the one published in “Logic-Based Encodings for Ricochet Robots” (DOI:10.1007/978-3-319-65340-2_54). There’s been a lot of work put into optimizing SAT solvers over the years, and I have been quite often surprised at how well they can solve problems where there’s technically a more optimal than NP algorithm.
Thanks for bringing this to my attention! It is really cool to see papers on this.
I took a quick look at the paper and it seems hard to reproduce.
The experimental evaluation was performed using the 256 benchmark
instances used by Gebser et al. [12]. These benchmarks are based on an authen-
tic 16 × 16 Ricochet Robots board. In the initial state of the board, each of
the four robots is placed on one of the four corners. The instances of the prob-
lem were generated by placing the target on each of the 256 possible positions.
The target is to be reached always by the same robot. The experiments were
run on a Linux machine with Intel Xeon CPU E5-2630 v2 2.60 GHz processors,
considering a time limit of 600 s.
The problem IIUC is that the original game had 4 double-sided tiles. So there are 2^4 options for flipping tiles and 3*2 different tile arrangements (ignoring rotation), so 96 possible boards in the original game. So I “scientifically” used the first map I could find for the original game. They also don’t say what target colour they used, so we don’t know which corner that robot was put in.
Our benchmark set is based on an authentic board designed by Alex Randolph of size
16×16. The initial robot positions are in the corners of the board, and the red robot
must reach some target position. Given this setting, we obtain a collection of 256 bench-
mark instances by considering all available fields as target positions.
So they say the target is red, but doesn’t say which corner they put the red robot in so that doesn’t actually give us any more information.
However they do say:
With very few exceptions, the resulting instances are satisfiable when given enough steps, where about
twelve steps are required on average.
So we can use this to see if we are benchmarking something similar to them.
I got an average solve time of 87.68ms with average solution length of 10.4 moves. If I remove the 4 “dead cells” in the middle that is 89.07ms with average solution length of 10.5 moves. Interestingly my solver could find a solution for all targets (other than the center cells), so their failures were just timeouts, not actually impossible solutions.
I ran on a AMD Ryzen 9 5950X which is surely faster than their old Xeon. But it seems unlikely that this is responsible for the 600x difference in performance. Especially considering that their timeout rule obscures the average by not counting the hardest puzzles.
I didn’t re-run their numbers. But I think https://potassco.sourceforge.net/apps.html is a live link to their encodings. I’m not very familiar with SAT solvers so don’t have to time right now to reproduce but it would be interesting to try the latest and greatest. However it seems unlikely that the SAT solver is faster for most puzzles.
Yeah, it indeed seems hard to reproduce. The original paper isn’t actually SAT, but ASP (Answer Set Programming), which is a somewhat related but different method for modeling and solving difficult problems. And the SAT paper I mentioned was trying to improve on it by utilizing SAT.
The encodings linked in the ASP page do have their board, goals and robots written in a human-readable format, in Facts directory of the archive. The robot used is red, starting at 1,1, and the 256 goals are every single possible tile.
I might try to reproduce the SAT solution myself, but yeah, as far as it seems your solution is likely quite a bit faster.
Ah! I accidentally downloaded the encodings file for the wrong project! I can see the board pretty clearly in the Ricochet Robots encodings archive. I entered the board and found a match with the stock tiles according to my solver. (Assuming I or they didn’t make typos.)
I reran the numbers (raw data) and my solver actually does even better. Average time was 35.79ms and average length was 11.4. This is largely because the hardest solution for the previous was 22 moves and took 5.4s while the new hardest is 21 moves and 1.2s. But in general it seems that even though the average number of moves is longer the distribution is much more even. The new slowest solution is found faster than the previous 3 slowest.
Makes you wonder if this board was selected for this reason or they just got lucky. However these slow puzzles are also not necessarily an important benchmark as they all involve stacking robots into the middle of nowhere. A situation that doesn’t happen with the default targets which are all in corners. However some people do find these fun and I think it is important for a solver to handle them. Plus worst-case performance is often more important than average performance for things like this. Moving the average to 200ms to move the worst-case to 0.5s would probably improve the user experience overall.
Thanks for the fun read! I like how the A* heuristic (even the fancier version) just boils down to a precomputed table lookup, without any dependencies on the other robots.
Yeah, it is shockingly simple for how big of a difference it makes. I have been racking my brain to try and determine if I can get something more accurate than 1 penalty but it seems that trying to solve if you can take off 2 moves with a single other robot branches out far too quickly. So for now mostly a table lookup seems like a good strategy.
The fancier one does depend on other robots (their position is considered when actually attempting to hit the shortest path).
Warning! You appear to be using Chrome
Chrome is harmful for the web. Google abuses its dominace to push user-harmful features. In order to reduce Google’s ability to push harmful features ot the web platform you should use any other browser.
For an example of a harmful API being pushed by Google read my post about the Web Environment Integrity API.
Here are some recomendations in order of preference
Firefox
Mozilla has been a long-time supporter of the open web and fights hard for user freedom. Using Firefox gives them more barganing power to keep the web open.
Additionally Firefox is a fantasitc browser. It uses less resources than Chrome to ensure that you can open as many tabs as you want and navigate the web browser. I also recomend trying out bookmark keywords for easy access to common sites. Firefox’s password and history syncing also uses End-to-End Encryption to provide far more secure password management. Mozilla can’t even see your passwords!
Click here to install Firefox
Chromium Derivatives
Chromium derivatives still provide some power to Google but they have the ability to block harmful APIs. Unfortuantely by default they inherit all of the harmful features that Google ships.
Desipte this flaw Chromium derivatives can be an attractive option as they will support almost all of the extensiosn that you currently rely on.
I wonder if the A* search is actually faster than a somewhat optimized SAT encoding like the one published in “Logic-Based Encodings for Ricochet Robots” (DOI:10.1007/978-3-319-65340-2_54). There’s been a lot of work put into optimizing SAT solvers over the years, and I have been quite often surprised at how well they can solve problems where there’s technically a more optimal than NP algorithm.
Thanks for bringing this to my attention! It is really cool to see papers on this.
I took a quick look at the paper and it seems hard to reproduce.
The problem IIUC is that the original game had 4 double-sided tiles. So there are 2^4 options for flipping tiles and 3*2 different tile arrangements (ignoring rotation), so 96 possible boards in the original game. So I “scientifically” used the first map I could find for the original game. They also don’t say what target colour they used, so we don’t know which corner that robot was put in.
The resulting board is https://ricochetrobots.kevincox.ca/#s=EBCBEAmAQQIBAAEgEQIFAMEDgQMJEAFAAQCBAAUEESAFEBEEQUABAAUCIYAJAQEQgQOhAwUgAQABBAEAIYAFBEEQAAV3APAP_wAB.
The referenced paper says not much more:
So they say the target is red, but doesn’t say which corner they put the red robot in so that doesn’t actually give us any more information.
However they do say:
So we can use this to see if we are benchmarking something similar to them.
I got an average solve time of 87.68ms with average solution length of 10.4 moves. If I remove the 4 “dead cells” in the middle that is 89.07ms with average solution length of 10.5 moves. Interestingly my solver could find a solution for all targets (other than the center cells), so their failures were just timeouts, not actually impossible solutions.
All timings: https://gist.github.com/kevincox/1468a1b3dffa54e882b451518bd56dae
I ran on a AMD Ryzen 9 5950X which is surely faster than their old Xeon. But it seems unlikely that this is responsible for the 600x difference in performance. Especially considering that their timeout rule obscures the average by not counting the hardest puzzles.
I didn’t re-run their numbers. But I think https://potassco.sourceforge.net/apps.html is a live link to their encodings. I’m not very familiar with SAT solvers so don’t have to time right now to reproduce but it would be interesting to try the latest and greatest. However it seems unlikely that the SAT solver is faster for most puzzles.
Yeah, it indeed seems hard to reproduce. The original paper isn’t actually SAT, but ASP (Answer Set Programming), which is a somewhat related but different method for modeling and solving difficult problems. And the SAT paper I mentioned was trying to improve on it by utilizing SAT.
The encodings linked in the ASP page do have their board, goals and robots written in a human-readable format, in
Factsdirectory of the archive. The robot used is red, starting at 1,1, and the 256 goals are every single possible tile.I might try to reproduce the SAT solution myself, but yeah, as far as it seems your solution is likely quite a bit faster.
Ah! I accidentally downloaded the encodings file for the wrong project! I can see the board pretty clearly in the Ricochet Robots encodings archive. I entered the board and found a match with the stock tiles according to my solver. (Assuming I or they didn’t make typos.)
https://ricochetrobots.kevincox.ca/#s=EBBBEAUEAYCBAAMEAQARIIEDgQcBQIEQCQABAIEEAyARAgUEEUAFCIEAAQABAAlAgQuBAxEABSEBCAFAQQAJBBEQAAV4APAP_wAB
I reran the numbers (raw data) and my solver actually does even better. Average time was 35.79ms and average length was 11.4. This is largely because the hardest solution for the previous was 22 moves and took 5.4s while the new hardest is 21 moves and 1.2s. But in general it seems that even though the average number of moves is longer the distribution is much more even. The new slowest solution is found faster than the previous 3 slowest.
Makes you wonder if this board was selected for this reason or they just got lucky. However these slow puzzles are also not necessarily an important benchmark as they all involve stacking robots into the middle of nowhere. A situation that doesn’t happen with the default targets which are all in corners. However some people do find these fun and I think it is important for a solver to handle them. Plus worst-case performance is often more important than average performance for things like this. Moving the average to 200ms to move the worst-case to 0.5s would probably improve the user experience overall.
Thanks for the fun read! I like how the A* heuristic (even the fancier version) just boils down to a precomputed table lookup, without any dependencies on the other robots.
Yeah, it is shockingly simple for how big of a difference it makes. I have been racking my brain to try and determine if I can get something more accurate than 1 penalty but it seems that trying to solve if you can take off 2 moves with a single other robot branches out far too quickly. So for now mostly a table lookup seems like a good strategy.
The fancier one does depend on other robots (their position is considered when actually attempting to hit the shortest path).
Warning! You appear to be using Chrome Chrome is harmful for the web. Google abuses its dominace to push user-harmful features. In order to reduce Google’s ability to push harmful features ot the web platform you should use any other browser.
For an example of a harmful API being pushed by Google read my post about the Web Environment Integrity API.
Here are some recomendations in order of preference
Firefox Mozilla has been a long-time supporter of the open web and fights hard for user freedom. Using Firefox gives them more barganing power to keep the web open.
Additionally Firefox is a fantasitc browser. It uses less resources than Chrome to ensure that you can open as many tabs as you want and navigate the web browser. I also recomend trying out bookmark keywords for easy access to common sites. Firefox’s password and history syncing also uses End-to-End Encryption to provide far more secure password management. Mozilla can’t even see your passwords!
Click here to install Firefox Chromium Derivatives Chromium derivatives still provide some power to Google but they have the ability to block harmful APIs. Unfortuantely by default they inherit all of the harmful features that Google ships.
Desipte this flaw Chromium derivatives can be an attractive option as they will support almost all of the extensiosn that you currently rely on.
Brave Browser Opera Vivaldi Edge