Saturday, 3 January 2009

Light-Bot in 131 commands

Over the Christmas holidays I worked on a brute-force solver for the game Light Bot. This is a game where you must move a robot around a maze and turn on some lights by giving commands such as 'Move forward', 'Turn left' and 'Turn right'.

Already a lot of people have worked on improving their score for this game. I wanted to either beat the best known score (132 commands) or prove it to be minimal by trying every possible solution for every level and seeing if it completes the level.

To cut a long story short, the solver managed to beat the best known solution for level 8, reducing it from 10 commands to 9 commands. The solution is complex and I find it difficult to imagine how a human could discover this solution without assistance from a computer.

Here are the solutions that the brute forcer found.

In particular the crazy solution to level 8 starts here.

The rest of the post describes how I approached the problem and optimized the solver so that it could run fast enough to solve the harder levels at the end of the game.

I named the commands by single character abbreviations: F, R, L, J, X, 1, 2, in the same order that the icons appear in the game. To prove that the length 17 solutions to the hardest levels are optimal I will need to check all possibilities up to length 16 and show that they do not work. A quick calculation shows that there are 33,232,930,569,601 different unique 16 letter string containing only these 7 characters. This is further complicated because they can be put into the three functions in many different ways, for example 5 symbols in main, 7 in F1 and and the remaining 4 in F2. For any given 16 character string there are 71 ways to separate the parts into the three functions. This gives a total of 2,359,538,070,441,671 possible programs to test. This is far more than can reasonably be brute forced. So what can we do?

An important observation is that if a sequence is a valid solution, then by removing all occurrences of the 'light' command (which I call X) I get a shorter sequence that doesn't light any lights, but still must walk onto them. I can therefore first test all solutions without any X commands to see whether or not all lights are reached. If I find a program that walks onto all the lights, I can then retest it by adding the Xs in all the possible positions. The effect of this is that now there are only 6 possible commands in the majority of the sequences I test instead of 7. I can also search to one search depth fewer, because if I find a solution of length 15 without any Xs, then this will grow to at least 16 when I start adding Xs.

6 ** 15 multiplied by the 74 different ways of splitting each is sequence into three functions is now "only" 34,793,688,858,624. A factor 100 improvement! But it's still not enough...

At this point I decided I will consider programs containing a loop, and programs not containing a loop separately. It seems that in most cases a solution containing a loop will be the best solution to a level. For looping solutions there are a few more tricks I can use.

A looping solution contains a function which calls itself. I can define that this function will be F1. I then know that the last command in main, and the last command in F1 will both be '1' and 1 cannot occur anywhere else in the program. This reduces the search depth by a further two levels, and removes one more command from the list of possible commands.

5 ** 13 * 74 = 451,660,156,250.

OK, so if we forget non-looping solutions for the moment, and consider only looping it's almost managable now... but it's still about a factor 100 more than I'd like. What more can we do?

I noticed that any functions containing the sequences LR or RL are obviously not optimal, because these two commands together result in no effect. So these possibilities can be discarded. Similarly, there is no point checking both LL and RR, since they do the same thing - so I discard all potential solutions containing LL. RRR is identical to L, so sequences containing RRR are also discarded.

This is the code that generates the functions:

`def functions(prefix, n, choice):  if n == 0:    yield prefix  else:    last = prefix and prefix[-1]    for c in choice:      if c == 'L' and (last == 'L' or last == 'R'): continue      elif c == 'R' and (last == 'L' or prefix[-2:] == 'RR'): continue      for p in functions(prefix + c, n - 1, choice):        yield p`

For example, this call generates the 18980 possible functions of length 8 containing the commands 'FLRJ'.

functions('', 8, 'FLRJ')

This is a lot less than the naïve 4**8 = 65536 possibilities. Similarly, the main function and function 1 provide similar savings, giving another order of magnitude optimization.

Several other smaller optimizations are possible.

For example, if there is a solution where F2 contains zero commands, there is also another solution where F2 contains 1 command and F1 contains one fewer command, so we don't need to check both these possibilities.

Another example is that the first command in main will only be called once, so if it has no effect then it might as well not be there. On any map, only one of the commands F or J can have an effect, never both, so for example we can always immediately discard any solutions where main starts with J if the ground in front of the starting position is flat. This gives 20% fewer solutions to check. Not much, but it's simple to implement and will save a few hours computation, so I'll take it.

The end result of all this is that I can check all looping solutions with up to 16 commands in just a couple days on a single computer. And the levels with a solution length of 10 or less take just a few seconds to brute force.

The search is much slower for the non-looping solutions because there are fewer constraints on the positions of the commands. Because of this, for the later levels I have only been able to check the solutions containing loops, and have not tested the non-looping solutions. It could be that there is an even shorter solution for level 10, 11 or 12 with a non-looping program (although I doubt it for level 11). To find such a solution or prove that one does not exist is left as an exercise for the reader as now my holiday has come to an end.

*Update: Before I wrote that there was no looping solution of length 16 for level 12, but I just ran the program again to double-check that and it turns out that there are in fact many such solutions, for example "Main = FJ1, f1 = X2XR22R1, f2= JXJXJ".

Noogie said...

I'm impressed. I love to see a good scientific mind being applied to something low-brow.

hughes_meister said...

How were you able to interact with the game programmatically, and determine if a solution worked? Did you have to write a simulator that mimics the game, then input the levels yourself?

sushant said...

can you implement lightbot in visual basic,please?
where will I get d code of it??

Jan-Jaap said...

Nice work. I tried both genetic algorithms and a brute force solver similar to yours.
My brute force solver, however, finds a solution for level 11 in 16 commands!

So now it is

"Light-Bot in 130 commands" !

Here are my solutions. I use '*' for switch light on/off.

Genetic Algorithm
=================
1. main=FF* f1= f2= (3)
2. main=FR2F2* f1= f2=FLF (9)
3. main=F2L22 f1= f2=JJF* (9)
4. main=1R11F* f1=FJJF f2= (10)
5. main=1 f1=22L*21 f2=JF (9)
6. main=11RR1 f1=22R2 f2=FFJF* (14)
7. main=1 f1=F221 f2=R*FR (9)
8. main=1 f1=2LF*21 f2=FJ (9)
9. main=1 f1=2*2L1 f2=J*F (9)
10. main=1J11 f1=2F222L2L f2=L*JFRJF (19)
11. main=111111 f1=2L2R2L22 f2=F*FF*FJR (22)
12. main=FJ2222L222 f1=J* f2=111R (16)
Total commands: 138

Brute Force
===========
1. main=FF* f1= f2= (3)
2. main=1 f1=L221 f2=FFF* (9)
3. main=1 f1=2J2L1 f2=JF* (9)
4. main=1 f1=22R1 f2=FFJF* (10)
5. main=1 f1=22L21 f2=JF* (9)
6. main=1 f1=22R21 f2=FJLFFFR* (14)
7. main=1 f1=F221 f2=RFR* (9)
8. main=1 f1=21 f2=J*FJJL (9)
9. main=1 f1=2*2L1 f2=J*F (9)
10. main=1 f1=FFLF22J1 f2=*JLJLFRJ (17)
11. main=1 f1=2*22*2F1 f2=JLJJ*JJ (16)
12. main=FJ1 f1=*2*2L21 f2=J*J*JR (16)
Total commands: 130