Talk:Ricochet Robots
From Chaos Communication Camp 2007
[edit] Just a Suggestion
Sounds interesting. Just finished skimming trough the links, and since as Birgit Engels, Tom Kamphans prooved - you can reduce the 3SAT problem to a restricted version of the game, it means that the solving of the unrestricted game is deffinetely NP-complete. Since we can't find a minimal solution in polinomial time, that leaves us to only heuristical approaches with "relatively good" - if at all - solutions.
So - long intro, nothing new, what i really wanted to suggest is to implement a CRobots-like API / game, in which others can implement in some scripted language heuristic "solvers". The winner is the algorithm which beats most other algorithms on a set of game configurations. ( An agorithm beats another on a given configuration if it solves it in less steps than the other ). As i'm reading this, it starts to sound like a typical algorithmic ( like ACM ) contest, but maybe by introducing game-like elements it might attract some other interested people except algorithm-freaks like us :). You can reach me ... by answering to this comment - i'm watching it.