Some time ago i linked to a programming contest based on the well known boardgame RoboRally. Its also some time ago the results got presented on the page of freiesMagazin. I sent in a KI-player written in C#/Mono, which is disliked by a part of the free-software community – maybe for a good reason?! (Im not into this discussion – im programming in C#/.NET/Mono for a lot of other good reasons…) However, i could make my robot win the tournament! My robot and me are very proud of it cause there were a lot of good approaches and programs to resolve the task.
At the beginning my algorithm was just a straight forward Ford-Bellmann after transforming the board and the possible positions of the roboter into a stategraph. I tried to keep the probability in mind while implementing it but after a while i noticed that searching for the best path couldnt get me rid of the problem of not knowing which cards will be next and whether the roboter would be able to follow the path by these cards. But a good friend of mine, Georg Hofmann, gave me a good advice: Monte-Carlo-Simulation. And he also provided the idea of the actual algorithm (i suggest reading the rules of the contest before).
The aim: To get the expected value of needed rounds to reach the target for every field.
Starting values: 1 on every field, 0 for the target field.
Simulation: Draw 8 cards. Calculate for EVERY field (A), which fields can be reached by
these cards and choose the one with the actual lowest expectation value (B). Correct the
expectation value for A as follows: E(A) = 0.9 * E(A) + 0.1 * E(B)
Do the simulation as often as possible to get a good result...
(Of course you have to take care of fields that leads to the dead of the robot – they need some kind of penalty as well as they dont need to be simulated)
After running these little piece of algorithm (very(!) often) the roboter “knows” what to do: Always choose those 5 cards that leads to the field with the lowest expectation value – its statistically best!
I wrote a more detailed article (in german) about this approach in combination with an introduction into C#/Mono for freiesMagazin. The article will be available at the May 2010 edition of freiesMagazin. But this is not the end of the roboters… be prepared 😉