I have created a Gomoku (5 in a row) AI using Alpha-Beta Pruning. It makes moves on a not-so-stupid level. First, let me vaguely describe the evaluation 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 out of 4 possible values depending on its usefulness as a threat, which is decided by length. 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 evaluation 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?

  3. When initially creating chromosomes, random generation, following standard distribution is said to be the most optimal. However, genes in my case have a large deviation. Would it still be okay to generate chromosomes randomly?

  • 1
    $\begingroup$ Why exactly four values for the score? What do these values exactly represent? $\endgroup$ Dec 4, 2017 at 22:44

1 Answer 1

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

Sure, the fitness is 1 for the winner and 0 for the loser. You're using some kind of the Tournament selection.

It might be better to use more chromosomes and let A play against B, C, D... and define the fitness as the number of wins. Or not, as such an evaluation is more precise but also more time-consuming.

  1. ... Infinity ... Do I also need to add this score to the chromosome?

Why should you? The exact value doesn't matter (as it only needs to be big enough), so there's nothing to evolve there. You don't represent the number of players either, right? Just use common sense.

  1. ... Would it still be okay to generate chromosomes randomly?

I guess so, but a distribution providing values closer to the expected outcome should be better. This depends on how you mutate them (adding a small random value won't bring you far, multiplying by 1 + small_random_value would).

Alternatively, you can generate values from some fixed interval and scale them up.

Your values are IMHO far too big. Whatever your 5 and 40000 mean, I guess, that 5 and 400 would work the same.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .