Ricochet Robots

From Chaos Communication Camp 2007

1 Ricochet Robots

[edit] Ricochet Robots

[edit] the idea

we, this is melle, karsten and me, love to play ricochet robots (in german: "rasende roboter"). it's a board game where the goal is to find optimal (= with a minimum number of moves) routes to a given target, for fairly dumb 'robots'. they operate on a 16x16 grid with some obstacles. robots can only stop when they hit obstacles, and you can utilize spare robots to build obstacles where needed. (wtf??? check here for a better explanation)

seems a great game for a computer to play, and so we already discussed for a while to program

solver
webversion to play (user-user or user-machine)

unfortunately finding a way for a robot it is a fairly complex problem, with exponentional growth of search space. some random ideas:

find strategies to cut off search trees or let the machine identify equivalent problems (for which a solution may be known)
build up a database of solutions/possible moves (this would probably require distributed computing - a nice project by itself)
another idea was to use a neural network approach to design a learning system

as you may guess we did not get very far yet, and probably it's too ambibious anyway. but if you want to discuss these ideas, have experience with similar problems, or just want to play the game (we'll bring along the board) - would be nice to meet.

[edit] some theory

Nicolas Butko, Katharina A. Lehmann, Veronica Ramenzoni: Ricochet Robots - A Case Study for Human Complex Problem Solving
Birgit Engels, Tom Kamphans: Randolphs Robot Gameis NP-complete! Technical Report 005, December 2005

Abstract We introduce a new type of movement constraints for a swarm of robots in a grid environment. This type is inspired by Alex Randolphs board game Ricochet Robot and may be used to model robots with very limited abilities for self localization: We assume that once a robot starts to drive in a certain direction, it does not stop its movement until it hits an obstacle wall or another robot. We give some lower bounds on the number of robots needed to reach every cell. Especially, it is easy to see that three robots are necessary and sufficient to reach every cell in a rectangular environment. Further, we show that the question, whether a certain cell can be reached is NP-complete for arbitrary environments.