Light-Bot is a swell little web game. The gist of it is that you compose a list of instructions, like a simple computer program, which guides a little robot dude through each level.
I’ve experimented with EAs generating sequences of instructions, typically with simple custom virtual machines, and I figured I could design an EA to solve these puzzles. It could be interesting just to see the strange but effective solutions generated, especially because they would be played out fully animated in the game.
I succeeded; my EA is able to solve every level in the game, although a few are clearly a little tricky for it. Solutions are evaluated as follows: most important is the number of tiles lit; second, how close the bot came to each tile during its run, and how close the bot is to the nearest unlit tile when the instructions end; finally, how many total instructions execute.
Level 10 exposes a weakness in the evaluation scheme which I haven’t fully addressed: the distance-to-tiles criteria do not properly take into account insurmountable heights. A reasonable heuristic is to simply sum the altitude difference with the linear distance, but a true measure of distance would involve a path-finding algorithm of some kind. Since the EA is already able to solve all the levels, I haven’t bothered to pursue that improvement.
The code is available for download, although I’m not sure if it’s in some kind of strange experimental upgrade state.
I’ve supplied some representative results below.
This is a fine example of the least-instructions criteria at work. The level is fairly simple, and the solution is direct and efficient.
Main: F J J F ! L F ! F !
This solution isn’t totally direct, but it’s correct.
Main: F J J R J 1 R F F F R 1
Func1: J ! 2 R !
Func2: J L F F F
I mentioned above that this level is especially hard for the EA to crack. This solution is wacky.
Main: 2 L F 1 R J L J 1 F F !
Func1: L J J F R J J
Func2: F F F J 1 F L !
Finally, here’s a great solution to a relatively complex level.
Main: F 2 1 1 1 2 2 J 1 1 2 2
Func1: 2 2 2 R
Func2: J !