I'm writing an AI system for an RTS game which relies on a large set of attribute values which affect the behaviour of the computer player. Until now, I have hand coded these values and tweaked them to react in the way I want to. Most of the attributes are independent, and tweaking one value can affect a large number of different aspects of the player's behaviour. I would like to use an evolutionary algorithm to make the computer play against another version of itself over several generations to find the optimal set of attributes for the strongest behaviour. If the AI's 'personality' is described as a set of real numbers, what would be the best way to employ an evolutionary system? Here was what I was thinking: - Randomly generate a set of say 100 players - Organise a huge 'tournament' where the top 10 players (winners) are put through to the next round - In the next round, for each winner generate 10 new players with slightly different attributes to the winner. - Repeat It is likely that some combinations of attributes will generate broken players incapable of winning the game, so each round must be time limited to eliminate two very weak players. Any other suggestions?

There are two common problems I've observed with using genetic algorithms this way. The first is the possibility that your initial set isn't very good. The "winner" in this case is the best of the first 100 players, but is still not guaranteed to be any good. Since all future iterations are derived from it, you're likely to hit a wall there. The second problem is you might end up with a strategy that is good at soundly defeating itself, but is useless against any other.

For the algorithm, I would take the top 10, generate 10 variations on those (one for each), but then generate 80 brand new strategies and start over. If the initial strategy was good, the strategy should place again, and if there's a more generally good strategy in the new ones, it will userp the old one.

Your best bet is to try a few different methods to see which gives you better results. The method you've described should work. Just make sure you balance exploration and exploitation such that you don't get stuck in a local optimal for too long. Though, in most cases, local optimal are unavoidable.

One things to note is that you may have to play with your evaluation criteria. You may not just want winning the match be the final deciding factor. Down the line, you may need functionality to do a point-wise evaluation system. So, for example, winning the match may give a candidate alot of points, but being able to destroy just about every enemy unit may also be a valuable trait. This way, you open up the process to being able to generate the "optimal" win. It also gives you the ability to evolve different AI's with differing goals. One may want to try to beat the opponent with a rush, while another will just play defensive all the way through.

Just remember, release the game with the values and not the EA system.

One interesting idea to try is to have 2 tournaments. One is to evolve the best strategy to win, while the other tries to evolve strategies to beat those from the first tournament. This way, you're not just trying to find a good strategy, but a robust one that can stand up against different types of attacks.

Nich makes some good points. A tournament based fitness assessment algorithm is good but you need to pick good values for randomness so the AI doesn't get stuck in a ditch. By that i mean, overall fitness of the AI (how well it plays the game) will increase in each generation, however, it will eventually level out at some value because the parameters are "good enough" and any small random value added will make the next generation less fit. Generating 80 brand new strategies as Nich suggests will mean that one of those may be better than "good enough" and will kick start another increase in fitness. I'm not sure if i explained that very well but i can draw a diagram if you like [grin].

EDIT: 'local optimal' was what i was describing there (WeirdoFu beat me to it)

Quote: Original post by jhoward
Here was what I was thinking:
- Randomly generate a set of say 100 players
- Organise a huge 'tournament' where the top 10 players (winners) are put through to the next round
- In the next round, for each winner generate 10 new players with slightly different attributes to the winner.
- Repeat

It seems like a very inefficient use of time where you reject 90% of your potential approaches, some of which might be close to being great or have some amazing sub-strategies, with a slow route towards converging on better strategies. I don't think tournament selection without crossover is a good idea here since you will generate so many completely poor random strategies that many poor strategies will propagate to the top.

I'd probably go for half or a third of the population size, and make each player compete against all the others. Judge fitness on how many matches are won, or the margin of victory/defeat if available. Carry the top few across to the next round (I'd suggest 5 would be a reasonable number) to ensure you keep the cream of the crop, and generate a similar amount of totally random new strategies to bring in fresh 'perspectives' to the system. Then construct the rest out of recombinations of the existing strategies, chosen via a fitness-proportional system, mutating a few values accordingly (maybe changing 1 to 10% of the values). Repeat until improvements start levelling off.

You may find that after evolving a decent strategy this way, you get some good results by using this as a target for a new strategy to beat. Run the system again except this time measure fitness on how well or how often a strategy can beat that previous winner. That way, if you ended up evolving a "Rock" strategy the first time, this next iteration gives you a chance of producing a "Paper" strategy. You can see that this may benefit from further iteration, too.

Hmm, maybe an aspect that should be considered, too - modular presets for certain strategic actions. Your AI values could then stand for different preferences to use these presets and you could save massive amounts of time and cpu load.

Also I disagree with removing the dynamic selection from the final product - as long as it's kept simple it will give the player a unique experience each time he plays and can greatly increase re-playability.

What I like to use is a hierarchical system with a master AI, several city/outpost/army AIs and simple individual AIs for each unit. I mostly add variations to the city/outpost/army AIs, so that an AI player can change tactics and spawn new "children" with different properties to deal with a situation that seemed unsolvable before.

Since AI isn't really all that smart yet these days, trial and error (and keeping the results from game to game for individual maps as well as globally) is probably still the best bet. Of course it makes sense to pre-populate the AIs behavior experience (as stated by the others already), but a good AI should also adapt to individual players - there is no such thing as the perfect strategy (which also makes me like Kylotans "stone and paper" reference there) :)

Oh, i forgot to mention something yesterday. Have a look at Framsticks, it's a genetic simulator. You can define parameters like the percentage of the population that will be mutated, crossed-over, etc. It might give you an idea of the strategies involved (and it's kinda fun too [smile]).