We consider this a minor success. But we wanted a bigger success. So, why did we not do better?
Two main reasons:
First, we made the mistake not to acquire enough “domain knowledge”, not to study the game in all its subtle details in order to fully understand it. If I watch bocsimacko’s bot, I admire how elegant and efficient it plays, but I don’t understand why exactly it is winning all the time. You can't really solve a problem that you don't know very well. I wrote in an earlier post, that problem parameters are needed to give the GP an undistorted and complete view of the problem. In an effort to speed up our evolution process, we threw away about half the parameters we had originally defined, because we thought that they are probably not needed. It is likely that we made mistakes here.
Second, we did not manage to get sufficient evolution speed. There is a fair amount of “noise” in the game. Bot A wins against bot B on certain maps and loses on other. There are often circular bot orders (A beats B, B beats C and C beats A on the same map). Bocsimacko is leading by a huge margin now, but it took him almost 30 games in the finals to get to #1. We had to tune the evolution process so that it often decided after 4 or 5 games whether to “promote” a bot or not. That means we often actually promoted an inferior bot. Therefore our quality increase from one generation to the next was relatively slow, two steps forward, one step back. We had no other choice, because otherwise we could have played only 20-30 generations in the one week we had reserved for our evolution run. Our final bot is from generation 159. We know from our evolution process indicators that it would have improved for another few hundred generations. All other participants have certainly suffered from that “noise” too, but we believe that our exclusive dependency on test runs (as opposed to analytical investigation of game results) made us particularly vulnerable.
We have been asked: "Would it have been possible for you to win if you had unlimited CPU power?"
Our answer is: No.
Actually, our answer is a bit longer. Sure, it would have resulted in a better bot, but even ten Google data centers running our final version of the GP would not have won the contest. However, more CPU power would have enabled us to go far enough in the evolution to recognize more of the remaining shortcomings in our setup and hopefully get rid of them. So, if we have had the CPU power and the time to improve our settings, could we have won then? Now the answer changes to: It depends on a very simple question. How far is the winning bot away from the optimum? GP often shows its strength where hand-made algorithms or other AI techniques don’t give perfect or “good enough” results. If they are perfect, then it’s hard to be better. We hereby risk to be kicked out of this website forever, but we say it: Perhaps Planet Wars was not difficult enough for Genetic Programming. Anyway, as you can see from the mistakes we made, it was difficult enough for us.
We are often involved in discussions about GP, and we would like to use this opportunity to address some of the most common wrong assumptions.
Wrong assumption: Genetic Programming is just playing with randomness. Nothing useful can ever come out of this.
The contrary has been proven a lot of times. Actually, I’m tired to answer that one.
Wrong assumption: In Genetic Programming, all you need is a genetic engine, a fitness function and time. A solution will come out of that sooner or later.
This is true only for very simple problems. We are convinced, however, that the key to successful application of GP lies in problem-specific adaptions. The unique feature of GP to generate programs makes it very easy to integrate the output (the generated program) into a larger environment. It makes it easy to combine GP with other approaches, particularly with hand-written programs, to get the best result. But not much will come out just by itself. Sorry to disappoint anyone.
Wrong assumption: GP needs a well-defined fitness function. It doesn’t work with a fitness function that contains random elements or hidden information.
A well-defined fitness function is indeed an ideal scenario for GP (and for all other optimization algorithms). But GP actually also works quite well outside that best case. One great property of GP is that it is very error tolerant, because its optimization process is based on a huge number of small decisions. If some reasonable percentage of these decisions are wrong (e.g. due to some random component in the fitness function), then the optimization process is slower, but it still works. We have generated a decent Poker Bot. Poker is a problem that has randomness not only in the fitness function, but needs it also as part of the solution.
Wrong assumption: GP doesn’t work in competition scenarios. The generated programs can never play much better than their sparring partner, and without sparring partners they don’t develop useful skills. It looks good as long as they just play against each other, but they are not competitive when they face challenges outside their little island. Like English footballers.
Competition scenarios are indeed more difficult (for GP, and also for most other AI techniques), but it doesn’t mean that it can’t be done. As long as one of the key challenges in GP, generating and maintaining genetic diversity, can be managed, there is no reason why it would not work. Standard GP techniques like varying population sizes and sub-populations can be used to achieve that diversity. In a competition scenario, the ability of GP to find totally unexpected solutions can actually be quite an advantage.
We enjoyed very much participating in this contest. We have used it as a perfect opportunity to stress-test our genetic engine, and to find improvements for it. We have been using GP for a long time, and we hope that our little contribution here can help to generate interest in that technique. GP has been around for a long time, but we are convinced that the advancements in processing power start to make it applicable in more areas than ever before. Our own work on GP includes:
•We have built a genetic engine.
•We use a built-in hill-climbing optimization in our genetic engine via a mechanism which we call numerical mutation.
•We have defined key indicators in our evolution process that enable us to automatically optimize the evolution settings. A self-learning evolution process, if you want.
•We have applied GP in scenarios that need human intervention for fitness evaluation via an approach that we call co-evolution. Another “can’t be done with GP”.
•We can combine genetically generated and hand-written programs (as long as they follow a structure that we support). We can put this approach to an extreme by starting with a supposedly good hand-written solution, feed it into our genetic engine in a pool with genetic programs, and try to improve it. Just imagine that we adapt the winning bot to our structure, and let the magic begin. The bot may be improving, literally while you are sleeping. If you think this is not exciting, then I have found a difference between you and me.
If anyone would like to get in touch with us: <genetic.programmers gmail.com>. We are looking for new challenges.
It has been a pleasure to have your attention.
Statistics: Posted by space.invaders — Mon Nov 29, 2010 3:54 pm