Fitness Function altenatives in Genetic Algorithms for game AI

Question

I have created a Gomoku(5 in a row) AI using Alpha-Beta Pruning. It makes move on a not-so-stupid level. First let me describe the grading function of the Alpha-Beta algorithm. When it receives a board as an input, it first finds all repetitions of stones and gives it a score depending on its usefulness as an threat. And it will return the summation of all the repetition scores.

But, the problem is that I explicitly decided the scores(4 in total), and they don't seem like the best choices. So I've decided to implement a genetic algorithm to generate these scores. Each of the genes will be one of 4 scores. So for example, the chromosome of the hard-coded scores would be: [5, 40000,10000000,50000]

However, because I'm using the genetic algorithm to create the scores of the grading function, I'm not sure how I should implement the genetic fitness function. So instead, I have thought of the following:

Instead of using a fitness function, I'll just merge the selection process together: If I have 2 chromosomes, A and B, and need to select one, I'll simulate a game using both A and B chromosomes in each AI, and select the chromosome which wins.

1.Is this a viable replacement to the Fitness function?

2.Because of the characteristics of the Alpha-Beta algorithm, I need to give the max score to the win condition, which in most cases is set to infinity. However, because I can't use Infinity, I just used an absurdly large number. Do I also need to add this score to the chromosome? Or because it's insignificant and doesn't change the values of the grading function, leave it as a constant?

Answer 1

Disclaimer: I've got no practical experience with genetic algorithms but a bit of an interest...

So your strategy is to pair individuals and have them compete against each other. Eliminate the losers and breed the rest? I'd say this is a reasonable approach in theory. I just have a few reservations/suggestions:

• Single Elimination might not give you a good impression of an individual's strength. If processing power permits it you could run a multiple rounds of competitions using swiss pairing. The advantage of the swiss pairing system is that you get an increasingly accurate ranking of the candidates without having to pair everyone against everyone.
• Using only 4 chromosomes with such huge ranges seems to me like it would require either a huge starting population or result in relatively few potential values. Instinctively I'd expect an algorithm using scores calculated from multiple simpler chromosomes to fare better. For Example: 4*24 chromosomes with each group of 24 chromosomes being the binary representation of a score. Or you could do 4*6 chromosomes with every group of 6 chromsomes being the binary representation of a number and the score being calculated as 2^number. There's probably a sweet spot between population size, gene complexity and score resolution.

Some more information about swiss tournament system

• Each round the paired contestants are put through a number of games. This number is up to you. Best of three is common.
• Each match up can result in a winner (which get 3 points) or draw (both get 1 point)
• In successive swiss rounds each participant it matched against someone they've never played against and is as close to their own score as possible.

This way it shouldn't matter too much if you get some draws. If however all you get are draws you have a problem...