3

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?

  • Are those really the weights you're using? Because if so, you're really only evaluating the third parameter. If the weights aren't even close to the same order of magnitude, save your self the trouble and don't count the small stuff for now. – Ethan Nov 28 '17 at 22:31
  • The large weight is for a win condition which is certain to win on the next turn. So I've made it large to prevent choosing a move which yields smaller score, insignificant moves instead of the win condition move. – Dashadower Nov 29 '17 at 4:00
3

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...

  • I'll look up more about Swiss pairing, although it seems like it will exponentially increase the time required for each generation. And you're right on: I was also concerned about the large deviation between the genes. However, the constants I provided were just explicitly decided solely by myself, and if I start from random genes ( and a large chromosome population),I'm sure I can get closely grouped results. – Dashadower Nov 28 '17 at 17:43
  • Also, can you elaborate on the second part of bullet #2? What do you mean by "multiple simpler chromosomes"? – Dashadower Nov 28 '17 at 17:46
  • @Dashadower: He means more than 4 chromosomes, using ranges less than 40000,10000000,50000. – Robert Harvey Nov 28 '17 at 17:51
  • @Dashadower: You can use multiple chromosomes, with each one having small bounds (say, between -100 and 100). Then, for your weights you can use some function of different chromosomes for each weight. – Ethan Nov 28 '17 at 22:30
  • Looks like there is a problem with competing 2 sets of chromosomes each. I created each genes completely randomly following standard distribution. However, when I select 2 chromosomes to compete against each other, because the weights of the actual AI grading function are completely random, the 2 AIs fill the board up with completely random moves. Therefore, the simulation will always end up in a tie, so the algorithm is stuck at simulating the first competition between the first 2 chromosomes. – Dashadower Nov 29 '17 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.