Wee-Chong Oon
Singapore
Toa Payoh
Unspecified
-
...Well, almost. We should finish computing all possible board configurations in about 5 days. This means that we will have found a solution with the minimum number of moves for all possible Ricochet Robots (3rd edition) starting positions.
The solution technique is pretty straightforward: we just bought a lot of RAM and did a complete retrograde analysis for each board. The final database is going to have over 10 trillion (10^13) positions. Just a few years ago, this would have required special hardware or a supercomputer, but now we can do it on a standard PC. The amount of power that's in the hands of us mere mortals these days is amazing.
So far, all positions we've checked have a solution, and the hardest position (in terms of the number of moves) we've found takes 25 moves. We also verified that the 24-move solution posted on the thread http://www.boardgamegeek.com/thread/308557/hardest-ricochet-... is optimal.
The version we're close to solving uses the most basic rules: no silver robot, and the active robot does not need to ricochet. We're also computing a solution to the version where the active robot must ricochet at least once, but that one will take a bit longer to compute.
We're going to write a short paper on this and send it to the ICGA journal. Any comments and suggestions are welcome.
Incidentally, in my opinion, this work in no way makes Ricochet Robots any less fun as an over-the-board game. After all, millions of people play Sudoku even though it can be solved instantaneously with basic constraint programming.
-
Russ Williams
Poland
Wrocław
Dolny Śląsk
-
UmExcuseMe wrote: ...Well, almost. We should finish computing all possible board configurations in about 5 days.
Er, so how many days will the entire computation have lasted (assuming it indeed finishes in 5 days)?
Quote: The final database is going to have over 10 trillion (10^13) positions.
A lot indeed! 
Out of curiosity, I want to compute it:
3! * 4^4 = 1536 board configurations (factoring out the 4 board rotations by supposing one specific board is always in the upper left)
times
256^4 = 4 294 967 296 initial robot configurations
times
17 possible goals
= 1.12150186 × 10^14 positions
Hmm, I get higher than you by a factor of 10. Am I overcounting somewhere? Or do you factor out a factor of 6 to not bother distinguishing colors of the 3 robots whose color is not that of the goal?
-
Wee-Chong Oon
Singapore
Toa Payoh
Unspecified
-
russ wrote:
Er, so how many days will the entire computation have lasted (assuming it indeed finishes in 5 days)?
It takes about 4-5 hours a board. With 96 boards, the whole computation takes about 20 days. Right now, we're running the computation on 3 separate threads on a multi-core machine.
Actually, we were running it for a couple of weeks on a single machine before we found a silly bug in our code (we didn't write the results of the final iteration onto the disk - d'oh!), so we've got partial results to 60+ positions. Just fixed the bug and started re-running everything yesterday.
Quote: The final database is going to have over 10 trillion (10^13) positions.
A lot indeed! :)
Out of curiosity, I want to compute it:
3! * 4^4 = 1536 board configurations (factoring out the 4 board rotations by supposing one specific board is always in the upper left)
This should be 3! * 2^4 = 96. There are only 2 sides to every board piece.
Quote: times
256^4 = 4 294 967 296 initial robot configurations
Slightly overstated. There are only 252 * 251 * 250 * 249 robot configurations (the 4 central squares are blocked).
Quote: Or do you factor out a factor of 6 to not bother distinguishing colors of the 3 robots whose color is not that of the goal?
Yes, we factor out the colors of the non-active robots. Assuming we didn't make a mistake in our calculations, the number of positions should be 10,237,336,200,000. (Don't forget that all the robot colors are irrelevant for cosmic vortex positions)
-
Russ Williams
Poland
Wrocław
Dolny Śląsk
-
UmExcuseMe wrote: This should be 3! * 2^4 = 96. There are only 2 sides to every board piece.
Ah yes; I was bogusly thinking of rotating each board section (1 of 4 rotations), forgetting that in fact they have fixed orientation due to the center fastener, and that they are double-sided boards. This is a sign that it's been too long since I've played this game.
-
Timothy Hunt
United States
St Louis
Missouri
-
what about adding the optional silver robot?
-
-
Did you try to solve other board games with this technique?
-
Wee-Chong Oon
Singapore
Toa Payoh
Unspecified
-
Timotheous wrote: what about adding the optional silver robot?
That would multiply the number of game states by about 60 times, which would require more RAM than you could get on a standard PC. There may be some tricks that we could do to handle the problem (parallel programming comes to mind), but right now it seems to be just out of reach for us. In academic papers, this would be classified under "future work". 
-
Wee-Chong Oon
Singapore
Toa Payoh
Unspecified
-
tocoking wrote: Did you try to solve other board games with this technique?
Retrograde analysis is a standard technique for solving board games. Awari is another game that was strongly solved with retrograde analysis, and also many chess endgames.
-
Wee-Chong Oon
Singapore
Toa Payoh
Unspecified
-
UmExcuseMe wrote: The final database is going to have over 10 trillion (10^13) positions.
Oops. Turns out I added an extra zero to my calculations. The database only has 1,023,733,620,000 positions, which is about one trillion (10^12). :blush:
-
-
UmExcuseMe wrote: Oops. Turns out I added an extra zero to my calculations. The database only has 1,023,733,620,000 positions, which is about one trillion (10^12). 
Did your program find just one or all optimal solutions per board configuration?
How many terabytes is your database?
What will it be used for?
-
|
|
