[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Our Genetic Program

It is currently Thu Oct 18, 2018 7:06 pm Advanced search

Our Genetic Program

Share and discuss ideas for your entries here.

Re: Our Genetic Program

Postby space.invaders » Fri Nov 26, 2010 7:40 pm

space.invaders
Lieutenant-Colonel
 
Posts: 41
Joined: Fri Sep 10, 2010 9:19 pm

Re: Our Genetic Program

Postby boegel » Fri Nov 26, 2010 8:21 pm

This is just too cool. Good luck!

I'm playing around with a genetic algorithm to tune the parameters of my current bot as I'm writing this, but seems like it's not giving me that much.
Started too late with it, and my current "default" bot probably doesn't have enough parameter freedom to really get anything good out of it, but it's fun to try it.

I hope you get truly stunning results. Seeing a good rerouting strategy evolve would be truly amazing.

I'll definitely look into GP in the future, and hopefully use it too in future AI contests. But it won't be using PHP though... ;-)
boegel
Cadet
 
Posts: 6
Joined: Tue Sep 28, 2010 1:40 am

Re: Our Genetic Program

Postby space.invaders » Fri Nov 26, 2010 9:30 pm

space.invaders
Lieutenant-Colonel
 
Posts: 41
Joined: Fri Sep 10, 2010 9:19 pm

Re: Our Genetic Program

Postby space.invaders » Mon Nov 29, 2010 3:54 pm

At the time of this posting, our rank is stabilizing in the 250-280 region. That means we are in the top 10%, not counting starter kit bots and first turn crashers. We are leading in our nations ranking.

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.
space.invaders
Lieutenant-Colonel
 
Posts: 41
Joined: Fri Sep 10, 2010 9:19 pm

Re: Our Genetic Program

Postby rangzen » Mon Nov 29, 2010 6:10 pm

Thank you very much for the sharing.
Do you have "starting point" URL to go deeper?
User avatar
rangzen
Lieutenant-Colonel
 
Posts: 42
Joined: Sun Sep 12, 2010 6:14 pm

Re: Our Genetic Program

Postby space.invaders » Mon Nov 29, 2010 7:18 pm

space.invaders
Lieutenant-Colonel
 
Posts: 41
Joined: Fri Sep 10, 2010 9:19 pm

Re: Our Genetic Program

Postby Innominate » Tue Nov 30, 2010 7:06 am

Out of curiosity, did you have any functions available to the organisms for storing and retrieving local variables? I ask because there may be useful functions for a bot that would require state as well as parameter input.

EDIT: It occurs to me now that pruning 'dead' code may be counter-productive in certain situations, from a purist perspective. Consider a bot descended from another bot, where a logical branch occurs in the ancestor whenever x > 10, and in the descendent whenever x > 100. Now any x in the range 10 <= x < 100 will not execute, there it would before. For argument's sake (there's a lot of this in this edit), we'll assume that this means this code will now get marked as dead code. A subsequent reproduction could have introduced a mutation to make the branch x^2 > 100 (allowing x < -10 and x > 10 to execute it), but if this code is removed then that can never happen. An organism would have to make the leap from x > 10 to x^2 > 100 (assuming that we didn't have the function abs(x) available) in one generation, or go via x^2 > 10 - which, assuming again, would be detrimental enough to wipe the organism from contention (maybe because it makes you send all the fleets off your planet, say). This is all very contrived of course, and there are examples where the dead code pruning is advantageous (say, because it lets your reproduction algorithms swap nodes that were actually visited - and are hence likely to produce the greatest change in phenotype - rather than the 'junk' sequences). It's highly unlikely a circumstance would actually arise where it would benefit you to not prune, but the possibility is nonetheless there.
Innominate
Captain
 
Posts: 22
Joined: Wed Oct 06, 2010 3:20 am

Re: Our Genetic Program

Postby space.invaders » Tue Nov 30, 2010 2:54 pm

space.invaders
Lieutenant-Colonel
 
Posts: 41
Joined: Fri Sep 10, 2010 9:19 pm

Previous

Return to Strategy

Who is online

Users browsing this forum: No registered users and 2 guests

cron