Can I use a genetic algorithm for balancing character builds?

Question

I'm starting to build a online PVP (duel like, one-on-one) game, where there is leveling, skill points, special attacks and all the common stuff. Since I have never done anything like this, I'm still thinking about the math behind the levels/skills/specials balance.

So I thought a good way of testing the best builds/combos, would be to implement a Genetic Algorithm. It'd be like this:

• Generate a big group of random characters
• Make them fight, level them up accordingly to their victories(more XP)/losses(less XP)
• Mate the winners, crossing their builds, to try and make even better characters
• Add some more random chars, emulating new players
• Repeat the process for some time, or util I find some chars who can beat everyone's butt

I could then play with the math and try to find better balances to make sure that the top x% of chars would be a mix of various build types.

So, is it a good idea, or is there some other, easier method to do the balancing?

Edit: Interesting thoughts in all those answers, still waiting to mark just one as resolved. I can see the problem with the AI implementation, but in my specific case, the AI is pretty straightforward. It'll be based directly on the opponent build and chosen parameters for the duel. (The human player will not have access to those info, so can not foresee the enemy stats and strategy). I've read a topic about testing, and I think I'll starting with simple automated tests and in the future evolve it to a genetic algorithm.

Answer 1

The problem with this approach is in this statement -

"Add some more random chars, emulating new players"

The task of randomly generating every permutation of character builds is trivial compared to making the AI that would actually use that build appropriately. It would be extremely difficult to tell the difference between a poor build and a poor AI in this setup - an amazing build in the hands of a dumb AI is still a dumb build.

Since the builds are a finite set, it would be possible to simply map each one out, assign potential damage, etc to each and simply work it out procedurally rather than using a genetic algorithm.

Answer 2

This approach would only work out when your gameplay consists only of character customization and leaves players little or no tactical choices during actual combat.

Many game-breakers require not just having a specific character build, but also require that the player plays it in an unconventional way the developers did not expect. It depends on your actual gameplay, but when it isn't that trivial, developing an AI which can come up with unconventional tactics on its own might be a project magnitudes more complex than the entire rest of your game.

Answer 3

As ultrahuman pointed out AI for this would be very hard to do. In addition your algorithm would balance the game for the AI players. :-) What I mean is that human players will often behave quite unexpectedly and will tend to exploit weaknesses etc.

However, you are somewhat on the right track. Except you should use real players instead of AI. :-) Or in other words it is called a beta. So, I suggest you should create a reasonable set of starting conditions. Then with each level of testing you should get more people involved and with each iteration you should refine the rules.

It is actually exactly what you propose, except instead of spending months on test AI, you let humans replace AI players. As a bonus, they can comment on the fun factor of the game/balance, something AI players cannot.

Answer 4

I recommend taking a look into the "Genetic Algorithms: Evolving the Perfect Troll" chapter from AI Game Programming Wisdom. I remember that the author describes using a genetic algorithm to create the proper parameters that will give him the best troll to launch at players and the process he followed to achieve the result.

The summary from my recollections (i don't have the book available anymore and read it at least 3 years ago) is that is quite likely you will find surprising results on your first attempts because your fitness function will not really describe what you want. In the example, the author used "time alive" as the first measure of how good a given individual performed, and after several generations he ended up with a bunch of coward and hard-to-find trolls that indeed gave him the best "survivability" :P. The lesson here, is that it is possible to use genetic algorithms in order to look for the "best set of parameters to maximize X", but you have to take into account that your fitness will prepare your character exactly to do X, and sometimes that's not what you want.

With that said, I think is a good starting point for your purpose. My guess is that you will have to run several simulations using different fitness functions in order to generate your "current objective oriented" best character. For example the "hardest hitting" character or the "magic user" character.