How should I weight the factors that affect the choice of an action in a strategy board game with multiple actions?

Question

I have written an AI that plays a strategy board game. There are lots of different types of moves (e.g. attack, defend, help ally colony, etc.).

I calculate the best moves to do depending on a variety of factors, such as the value of nearby enemy colonies, the number of armies the colony currently has, etc (each of these has separate weightings). I'm trying to find the optimal weighting for each of the different factors.

Currently, I decide the best configuration of parameters in a King of the Hill style tournament. I choose random values between a suitable range for each of the different parameters and then play two of these AI against each other 20 times. I have a total of 100 AI that play against the king, and then take the final king as the best AI.

The problem is that this is quite slow and I feel it's very inefficient, as a lot of the AI don't play well at all (probably due to the randomness of parameter values).

I'm wondering if there's a more efficient way to determine the optimal value of parameters?

Answer 1

You could use a genetic algorithm to optimise the parameter settings. Here you don't choose random parameters all the time, but only at the beginning. Each AI (which is a vector of parameter settings) plays each other one for a ranking (you can probably reduce the number of total games by using a ladder-style ranking where only neighbours play against each other). Also, you don't need 100 to start with, as you might come across better combinations than those present initially throughout the processing.

Then you discard the worst AIs (ie parameter vectors), and recombine the best ones, adding some random mutations into the mix. In theory this should converge faster, as you preserve good parameter settings (depending on how interdependent they are) and remove bad ones from the 'pool'.

You can also have a higher rate of mutations initially, which slowly goes down as you progress through the generations.