![]() ![]() This reduces the search depth by a further two levels, and removes one more command from the list of possible commands. 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. I can define that this function will be F1. ![]() For looping solutions there are a few more tricks I can use.Ī looping solution contains a function which calls itself. It seems that in most cases a solution containing a loop will be the best solution to a level. A factor 100 improvement! But it's still not enough.Īt this point I decided I will consider programs containing a loop, and programs not containing a loop separately. 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.Ħ ** 15 multiplied by the 74 different ways of splitting each is sequence into three functions is now "only" 34,793,688,858,624. The effect of this is that now there are only 6 possible commands in the majority of the sequences I test instead of 7. 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. ![]() I can therefore first test all solutions without any X commands to see whether or not all lights are reached. So what can we do?Īn 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. This is far more than can reasonably be brute forced. This gives a total of 2,359,538,070,441,671 possible programs to test. For any given 16 character string there are 71 ways to separate the parts into the three functions. 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. A quick calculation shows that there are 33,232,930,569,601 different unique 16 letter string containing only these 7 characters. 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. 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. 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. In particular the crazy solution to level 8 starts here. Here are the solutions that the brute forcer found. The solution is complex and I find it difficult to imagine how a human could discover this solution without assistance from a computer. 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. 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. 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'.Īlready a lot of people have worked on improving their score for this game. Over the Christmas holidays I worked on a brute-force solver for the game Light Bot. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |