Author: Don Dailey
Date: 17:11:57 05/21/98
> Could you describe your methods and results to me? I'm very interested! Hi Stan, I'm going to post this email because it might get others interested in GA's too. But I'll also send it via email. Essentially, I set up about 100 "individuals" with random weights for a few of the evaluation terms. I gave each guy a fitness number which essentially was an elo rating. I started the first group exactly the same for everyone. I did not proceed by going from 1 generation to a completely new generation. Instead, I just played games pretty much selected at random. I tried to choose the opponents based on how many games they had played so that new individuals would be more likely to play than ones who had played more. The openings were selected at random from among 200 possbile opening positions and so was the color. After each game I would rate them incrementally using a simple linear version of the elo chess rating formula. I used 4 percent of the rating difference as a handicap and 16 points to the winner. Handicap was limited to 16 points. After every n games, (I think I used approximately 50 games here) I would select 2 fit parents and produce a child. The child would replace an UNFIT member of the population. I used a method I call "best of n" to make these selections. Here is how it works: To determine parent A, pick 3 candidates completely at random. Then choose the highest rated one as parent A. Do the same for parent B. A similar procedure determines which member of the general population to "kill" off to make room for baby (worst of 3.) Here is how the "mating" process works. For each term, I would choose randomly whether to select it from parent A or parent B. Occasionally I allowed a "mutation" which was simply picking 1 or 2 terms and making a random adjustment to it. The adjustment was not unusually large or small, but I thought it made more sense than just changing it to a completely random value. I don't have any reason other than my own superstitions for believing this though. Some other details. The pawns were fixed at 100 points as a reference point. I limited the range of possible adjustments/values to something like 2000 points for any piece. "Babies" inherited a rating which was the average of their parents rating. I figured that since their parents were likely to be fit, this would give them time to establish a rating and not get killed off too soon. Of course sometimes they would prove to be fitter than both parents and other times they would be less fit than either parent. I thought this model was reasonable. Each "guy" was fighting for his life, your rating gets too low and suddenly you're in danger of getting deleted! If you do well you are rewarded with the right to have children! Now that's a lot of pressure to have to endure! I am sorry to report that I do not have a record of the results. It was pretty encouraging though and I had eventually planned to follow up on it. But from memory I can tell you that the values of the pieces converged to very reasonable values. I remember that they were not quite the values I would pick, but they were not unreasonable. It's unclear what would have happened if I had run it long enough. It was quite interesting to watch over time. I would observe strong individuals survive into old age, only to eventually weaken and get replaced by the stronger and smarter younger generations who were decendants. After a while I almost mourned their deaths! I kept around members of the original group, preserved in ice, so that later I could thaw them out and let them have it out with the new guys. The difference in strength was enormous. The real problem as I see it is that there is a lot of imprecision in the actual fitness function. Any given individual can get seriously underrated or overrated by having a little bad or good luck. Even though the selection process itself is a litte random and murky, I believe the fitness function itself should be solid and in this case it was really very very fuzzy. Measuring small differences is almost impossible. To be really robust, I believe a hierarchy might work well. You breed small groups independently, let the best individuals move out of these small towns to compete with the big boys (who themselves came from small towns.) In this way, you will create individuals who have what it takes to beat a wide variety of opponents. Also you would be constantly refreshing the gene pool. - Don
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.