Evolutionary Algorithm game/breeding game?

[simplicity]

I'm in the process of modifying the current ant game to be like polyworld. However, it's not going well. But, I should have more time in the summer holiday coming up in two weeks.

If you haven't seen it there is a good google talk http://www.youtube.com/watch?v=_m97_kL4ox0

If you looked at the link you will see that polyworld is a game where you have a population of triangles. Each triangle has certain genetic structure that produces action and each triangle has a metabolism so they need to eat or they will die. The triangles can reproduce(which, cost energy or you get a bug where they all have a massive orgy and just eat the kids) and they have their life capped.

So what I propose is a game similar to that, but instead you have about 500 triangles each on a 2D level, but with multiple people playing against each other. The winner is the person with the most triangles at the end.

So where is the AI in this?

I think if we allow the person to only control how they breed and what genetics they can choose from breeding(you could say choose only move forward for the genetics of the offspring or even choose not to mate if the partner has crap genes). So the AI would be choosing what genes get passed on to offspring. This is different from other games as you aren't controlling the character, but instead you are controlling what they produce and hence controlling the evolution of the triangles. Saying that I suppose you should force the AI to choose 50/50 from both partners.

So there would be like 20 generic genetic codes like move forward, ability to move backwards. Then useful abilities like being able to tell if someone wants to mate or they will try to eat you. Then overpowered abilities like being able to stop opponent triangles or forcing someone to mate with you or even teleporting a short distance. I suppose I should add that the player can't choose the genes of the triangle at the start and we just make it random at the beginning, so for example if you get no information to move the triangle would sit there.

The genetic information will cost metabolism and the more overpowered the more metabolism it would use. I suppose you could also allow the ability to mate with other opponents and have the person with the most metabolism have the child so it counts as there.

P.S. Sorry if that was vague. However, if you think about it you have big potential for tactics. More importantly it's something different. Also, I think it won't be that hard to program with, for example you could just make the AI just choose the gene move forward and nothing else. But, yeah the AI could choose how much of a certain gene it wants in a population. If it loosing really badly you might make the AI, then choose genes that are good for surviving but aren't that powerful.

P.P.S. So in short can we have a breeding game? A game that you are only controlling what genes get passed down to offspring.

[Kettling]

It sounds interesting to me. There's a whole stack of growth-simulation games, such as plant growth where you need to figure out whether to grow longer stems (like a vine) or more branches (like a sage bush) and smaller leaves (like a pine tree) or bigger leaves (like a palm). Then you need to juggle resources (e.g. sunlight, water, soil, nutrients, etc). It makes rendering the plant growth pretty cool from a graphical point of view (better than triangles).

I sort of feel that a genetic approach should be optional. If players want to do everything on a traditional rule-based approach then let them do that, or if they want to work off some sort of genetic code then let them do that too (hand-optimized coding vs machine-optimized coding).

[delt0r]

The problem with many of these optimization problems is that you can in fact solve them or that there are a lot of very good heuristics that approximately solve the np cases.

[Kettling]

I've been thinking about this one again, and come up with a bit of a different angle on it.

Suppose you have some sort of multi-dimensional optimization problem (e.g. food, water, territory, combat, nutrients, etc) which can be solved by a number of different approaches. For example breeding fast and eating fast gives you good coverage but you end up as weak rabbits and prey to some other creature that breeds slowly but is optimized towards eating rabbits. Then you could deploy spines to make yourself more difficult to eat, but that reduces your efficiency for breeding and eating.

To some extent then a winning strategy depends on which strategy your opponent chooses (and that may be some sort of mixed strategy perhaps). In some ways it might be a bit like an elaborate rock/paper/scissors because nothing is unbeatable against an opponent forewarned about the strategy you are going to use.

So to make it one step more difficult, suppose there are always three players: two genuine contestants and one "house" player who always runs a fixed and well published algorithm. Note that the "house" player would indeed be running an evolutionary algorithm which is simple enough to be reasonably easily understood. However since the evolutionary algorithm takes in a stream of random numbers (mutations) the exact outcome on any particular game cannot be predicted but the genuine contestants could make plausible guesses as to how this evolutionary algorithm would respond.

This would be difficult to approach with a brute-force min/max for two reasons: firstly your min/max can only properly optimize once you have some reasonable estimate of your opponent strategy, and secondly the existence of a third player opens up co-evolution approaches that require creativity rather than brute force. For example, if the "house" player is evolving towards a weak herbivore then I can encourage that by selectively killing out anything that seems to be evolving some fighting capabilities, I can also defend some of those herbivores from the other team and use them as a food source myself. Or the reverse strategy might also work in other situations.

Mind you, both of the genuine players would be looking for co-evolution opportunities.