Ricochet Robots and interesting game trees
Posted by Nick Johnson | Filed under coding, games
Every Wednesday at work we have a Games Night - people bring along (non-computer) games, we get together, and we play a few. Last Wednesday, someone brought along Ricochet Robots. I wasn't very good at it, but the game intrigues me from a computational point of view.Essentially, it's a puzzle game. You have a board divided into squares. Each square is either empty or has a target. A target consists of one of four colors and a symbol. Walls are (seemingly) randomly scattered around the board, blocking passage between adjacent squares. There are four robot tokens, in the same colors as the targets, which start off scattered around the board randomly.
There's also a set of tokens, one for each target. One of these is drawn randomly and placed face up in the center of the board. It specifies that the robot of that color must make its way to the target with that color and symbol. Robots move like they're on a skating rink - they can move in any of the 4 cardinal directions, but once moving continue until they hit a wall or another robot. Nobody owns a robot - all 4 robots may be used in attempting to solve the puzzle.
As soon as the counter is displayed, all players must try and figure out a sequence of moves that get the target robot to the target square. A move consists of moving the robot any distance in one direction, observing the rules above. As soon as one player thinks they have a solution, they call out the number of moves; other players have about 30 seconds to find a better solution. At the end of that time, the player with the lowest figure has to demonstrate their solution; if they get it right, they get a point, and everyone moves on to the next token (without repositioning the robots from where they ended up).
What interests me about this game isn't so much the physical playing of it, but the algorithms behind solving it. The game tree is fairly simple to calculate; it's also fairly narrow (the worst branching factor is 16, but most of the time it will be far lower than that - somewhere from 4 to 8). More interestingly, it's also very non-obvious - a few moves can get you a long way across the board, and the shortest solution can involve moving several robots in ways that seem unrelated to the eventual target.
So, anyone want to write an AI? ;) Previous Post Next Post