Using evolutionary algorithms to make a walkthrough for the light-bot game with C#

Update: code can now be found on github.

The other day, a mate of mine sent me this game to play, saying to me 'you're a programmer - you figure it out!'. I got stuck on level 10 (shown below) and thought 'why not make a program to figure out a solution' - so here's the results: [[posterous-content:oeuhwoseqJdcCJqHBbap]]
Firstly, I needed a way to simulate a given attempt. The game has three functions: main, f1, and f2, of 12, 8, and 8 commands respectively. So my function accepts an array with 28 elements - 0-11 are main, 12-19 are f1, and 20-27 are f2. The possible commands for each element of this array are: enum Cmd { Nothing, Call1, Call2, Jump, Left, Right, Light, Forwards };
So this function to simulate an attempt is called 'TryPath', and it accepts an array of 28 of the above Cmd's.
Next, we need some way of trying many solutions. Firstly i tried simply choosing random solutions over and over until it finds a solution. I tried this and left it running overnight with no success. After that, i remembered a class back at Uni about evolutionary algorithms. The basic idea is that you randomly create a generation of 1000 solutions. You then try and score all those solutions. For the next generation, you make several morphed copies of the prior solutions that had some success, and go from there until you find a solution that succeeds.
Update: Scoring the solutions uses a thing known as a 'fitness function', which is often the crux of a genetic algorithm. In this case, my scoring is boolean: A solution is 'good' if it lights either one of the light pads.
Here is the application in action, as you can see it takes roughly 2 minutes to find a working solution, after trying 14 million possible solutions:

Begin: 20/10/2008 2:16:27 PM
Tries: 14,200,000 Halfway: 236 Fresh: 382 Morphed: 236 Spread: 382
WINNER:
Left,Call1,Call2,Call2,Call1,Right,Forwards,Left,Left,Call2,Call1,Call2
Light,Forwards,Forwards,Right,Forwards,Jump,Forwards,Left
Call1,Nothing,Left,Call1,Jump,Light,Jump,Forwards
End: 20/10/2008 2:18:04 PM

The hilarious thing about this is watching the solution in action - all the solutions i've tried from this application take the most bizarre path when you watch it in the game, but somehow end up working in the end.
The code (C#) and executable are on github (link above). With further work, this could be modified to: * Support more than 2 light squares, so you could find solutions to other levels * Keep running for a week or so, returning a list of all solutions it found, and sorting them by elegance or frugality.
Update - Here are some more solutions that it created:

Call2,Call2,Forwards,Light,Right,Right,Call2,Call1,Jump,Call2,Call1,Call2
Right,Nothing,Jump,Forwards,Light,Forwards,Light,Left
Forwards,Left,Jump,Jump,Forwards,Call1,Right,Jump

Call1,Call1,Call2,Call2,Nothing,Left,Call1,Right,Call1,Right,Call2,Forwards
Left,Light,Forwards,Right,Jump,Forwards,Jump,Forwards
Left,Call1,Left,Jump,Call1,Jump,Forwards,Nothing

Forwards,Call2,Forwards,Call2,Call2,Call1,Call2,Right,Call2,Right,Call1,Nothing
Jump,Nothing,Forwards,Left,Right,Forwards,Left,Light
Call1,Jump,Call1,Left,Left,Light,Light,Call1

Call1,Call1,Nothing,Call1,Right,Jump,Right,Light,Light,Light,Light,Call1
Call2,Jump,Left,Call2,Light,Call2,Jump,Left
Forwards,Right,Forwards,Jump,Light,Forwards,Left,Nothing

Call1,Left,Call2,Forwards,Nothing,Right,Nothing,Call1,Jump,Jump,Left,Call2
Jump,Light,Forwards,Forwards,Forwards,Right,Light,Jump
Jump,Left,Jump,Call1,Forwards,Nothing,Call1,Forwards

Left,Call2,Call2,Call2,Call2,Left,Forwards,Left,Call1,Light,Light,Call2
Left,Light,Jump,Left,Forwards,Right,Jump,Forwards
Call1,Forwards,Nothing,Nothing,Jump,Forwards,Call1,Forwards

Forwards,Jump,Call2,Call2,Call1,Call1,Call2,Right,Forwards,Left,Call1,Call2
Jump,Forwards,Light,Right,Jump,Nothing,Forwards,Jump
Nothing,Call1,Jump,Left,Jump,Left,Call1,Call1

Call1,Call1,Jump,Nothing,Nothing,Call2,Call1,Light,Left,Jump,Left,Call1
Call2,Call2,Forwards,Forwards,Jump,Left,Jump,Call2
Jump,Forwards,Light,Right,Nothing,Jump,Forwards,Forwards

Call2,Left,Light,Light,Call2,Call2,Left,Call1,Call1,Jump,Call1,Call2
Right,Light,Forwards,Jump,Left,Forwards,Right,Left
Light,Call1,Light,Call1,Left,Call1,Call1,Nothing

Call2,Light,Call1,Call2,Call1,Jump,Forwards,Forwards,Nothing,Light,Call1,Nothing
Left,Forwards,Call2,Call2,Call2,Forwards,Left,Forwards
Right,Jump,Forwards,Forwards,Light,Left,Jump,Light

Update: Someone emailed me to say he had ported this to C and D, and it creates solutions in a matter of seconds, not minutes. Definitely interesting! Have a look

Chris Hulbert

(Comp Sci, Hons - UTS)

Software Developer (Freelancer / Contractor) in Australia.

I have worked at places such as Google, Cochlear, Assembly Payments, News Corp, Fox Sports, NineMSN, FetchTV, Coles, Woolworths, Trust Bank, and Westpac, among others. If you're looking for help developing an iOS app, drop me a line!

Get in touch:
[email protected]
github.com/chrishulbert
linkedin

 Subscribe via RSS