5 ms·
Ricochet Robots Solver
- jszymborski 3y agoSuch a treat to see this! I only played Ricochet Robots once, and it was when a colleague who was a board game buff brought it for a regular after-hours board game night in one of the conference rooms. This was ages ago. We were all developpers, and the first thought so many of us had after the rules were explained was that it would be a lot of fun to code up a solver. So glad that someone worked it out, what a pleasure to read!
- xoxxala 3y agoGreat game. Sadly, out of print at the moment but used copies are relatively easy to find. Definitely not for everyone, but most devs I've played it with have really enjoyed it. Fortunately, another dev friendly game, the classic Robo Rally was just republished with improved rules and components compared to the last edition. It's similar to Ricochet Robots but different enough that I have both in my collection.
- drewcoo 3y agoNew version of Robo Rally? With expansion sets soon, too, looks like? You made my day!
- xoxxala 3y agoYep, two map expansions came out at GenCon and more expansions are planned for next year. Good time to be a Robo Rally fan!
- adamredwoods 3y agoFun game. I own it. The problem is the skillset to play is very high, and people who are not good at it are blocked out. I highly recommend as a casual thing, and also great for those who only observe.
- kevincox 3y agoIt can be bad if you have someone super experienced and a first time player. But I've found that you can make it work ok. 1. Let the new player play a game on their own. This lets them get the feel of finding any solutions. (If you can start two people at once it is also more fun to do that instead.) 2. Play but have the new player win ties. Normally whoever says the lower number first wins it. But this way if they can match your number within the timer they still win. There are almost always a handful of "easy" puzzles per game so this will ensure that they get a handful of tokens each game and have some fun. It isn't perfect but I think for most people who would really love the game this is enough to keep them interested while they ramp up to speed.
- tirutiru 3y agoAh this is great. I wrote my own solver in Python+Numba. You've probably seen Robot Reboot https://www.robotreboot.com/challenge https://www.robotreboot.com/challenge. I had a parser that could take a screenshot of the daily puzzles and feed them into my engine. Your post might just give me the kick in the pants to put it up online. Curious if think this made you better at RR. I started out absolutely terrible, and actually got to the point where I could occasionally match the best scores on Reboot (but not their times of course!).
- kevincox 3y agoI think it has made be better. At the very least it shows some techniques like moving forward and back and highlights some approaches that I missed. I generally solve the puzzle "backwards", looking at how the robot can approach the goal. So if you miss a possible approach it can definitely result in me missing a solution. Filling these gaps is valuable. It also provides some intuition about how long puzzles are in different scenarios which helps you decide how to look. But overall I would say that it is mainly curiosity why I use the solver. It is interesting to know if we actually found the best solution or how often we miss it.
- wenderen 3y agoAnother cool solver for the same game https://www.michaelfogleman.com/projects/ricochet-robot/ https://www.michaelfogleman.com/projects/ricochet-robot/
- tantalor 3y agoThe "Chrome warning" is obnoxious spam.
- Kiuhrly1 3y agoEspecially since I see it on a FOSS privacy-enhanced fork, Vanadium
- nullc 3y agoA friend of mine used their very fast solver to determine the number of moves required to solve a worst case configuration (and, of course, also to determine one of those worst case configurations). Pretty slick.
- simonbw 3y agoI discovered this game at a board game convention earlier this year and quickly fell in love. After coming home and realizing it was fairly hard to get a copy these days, I decided to make my own web version of it so I could play with my friends. I also tried to implement a solver just to be able to check if the solutions we found were the best, but I didn't spend much time on it, and I never went past a breath first search that can really only check about 5 levels deep in a realistic amount of time. This might inspire me to revisit it and try to improve my solver. So thank you for posting this!
- derf_ 3y agoI wrote one of these to solve the daily challenge at the now-defunct <https://www.robotreboot.com/challenge https://www.robotreboot.com/challenge>. Four robots, no mirrors. I did not bother with an A* search or robot sorting, because each daily challenge contains five different goals searched for from the same starting board configuration. Instead I search for all of them at once with the same breadth-first search. Even without those algorithmic optimizations, it can find a 17-move solution---like the following puzzle from Nov. 25th, 2022 (the "r" square is the goal for the red robot)---in about 30 seconds on my laptop using less than 400 MB of memory. I'm sure it would be faster on a faster machine. +---+-----------------+---------+ | | | | | + +-+ + + | | | | | | + +-+ +-+ | | | | | + + | | | | | +-+ + | | R | | | +-+ +-+ +-+ | | | +-+ + + +-+ | | | |r | | +-+ +---+ + | | | | | | | | | | | | | | +-+ +-+ +---+ +-+ | |Y | G | | | | + + + +-+ | | +-+ | | B | | +-+ | | | | | + + + | | | | | | + +-+ + +-+ | | | | | | +-+ + +-+ + | | | | | +-----------+---------------+---+ Solving this board required examining 30,427,896 unique states. One of the things I found that improved the speed the most was simply reducing the memory usage. The "visited states" test is just a 2**32 bit (2**27 byte) table indexed by the 32-bit combined robot positions. For most problems, most of the pages in that table will never even get mapped, but at worst the whole thing is 128 MB. There are probably clever ways to permute the indices of the robot positions to get better cache coherency in the table lookups, but I did not bother. The state in the breadth-first search queue is just the 32-bit combined robot positions. No back-pointers are stored to recover the solution(s). Instead, a side-table keeps track of the index in the queue where the number of moves increases (since all entries are ordered by the number of moves required to get there), and upon reaching a goal the solution is recovered by back-tracking one move at a time and searching the relevant portion of the queue for a state plus a move that gets us to the next state. This sounds slow (and it is! printing the solution now takes a non-negligible fraction of the runtime), but it is actually faster than storing back-pointers in the queue. The queue size grows exponentially with the number of moves¹, but you do not need to search for the last move in your solution, because you were just making it when you reached that goal. So you avoid having to read through a large portion of the queue just by skipping that last level, and you avoid having to write the extra data for the whole queue. Assuming your back pointer would have been a 32-bit queue index, that cuts the data written in half. You also don't have to check the "visited states" table during back-tracking, so you avoid lots of cache pressure that was present when filling the queue the first time. ¹: At least for long enough to reach any single robot goal... if you search for all reachable combinations of robot positions, eventually you run out of unvisited states and the number of newly reachable states starts shrinking again until it hits almost nothing, at somewhere approaching 100 moves. For a given board, roughly 2/3rds of the 3,937,437,000 possible combinations of robot positions are reachable, giving a maximum memory usage of about 10 GB.