landman@hanami.Eng.Sun.COM (Howard A. Landman) (11/08/90)
Consider using genetic algorithms to solve the following problem: You are to design a six-sided die which has the maximum chance of winning and minimum chance of losing when rolled against another die in the population. The total number of pips on the die must be 21 (same as a normal die). It is known that there exist dice A, B, and C such that A will (on average) beat B, B will beat C, and C will beat A. That is, the relationship "X beats Y" is not transitive. When we think about "strength", we often think about it as a one-dimensional numerical quantity; but that implies that "X is stronger than Y" MUST be transitive. Thus, one-dimensional "strength" CANNOT model what actually happens among dice A, B, and C. For complex games, there are a huge number of dimensions of playing strength. Thus I think this sort of intransitivity will rear its ugly head often when one attempts to use genetic algorithms to evolve game playing programs. For example, in the dice problem, if you start off with a population of all A, the first C to occur would probably spread like wildfire and drive all As out of the population. But then, the first B to occur might spread like wildfire and drive all Cs out of the population; and then the first A to occur might wipe out all the Bs. So you could cycle endlessly, the population churning violently without any real progress being made. This might give a the "sawtooth" behavior that was mentioned in an earlier post One thing that might prevent this would be keeping a few copies of previous "successful" versions around longer, so that they couldn't be completely wiped out quickly. Then we might end up with a more stable, "punctuated equilibrium" form of evolution. I wonder if this is one of the advantages of having recessive genes? Certainly, genes are extraordinarily conservative entities by human standards. Why else would people still have many of the genes needed to make gills? Howard -- Howard A. Landman landman@eng.sun.com -or- sun!landman
kingsley@hpwrce.HP.COM (Kingsley Morse) (11/09/90)
/ hpwrce:comp.ai.neural-nets / landman@hanami.Eng.Sun.COM (Howard A. Landman) / 4:43 pm Nov 7, 1990 / Consider using genetic algorithms to solve the following problem: You are to design a six-sided die which has the maximum chance of winning and minimum chance of losing when rolled against another die in the population. The total number of pips on the die must be 21 (same as a normal die). It is known that there exist dice A, B, and C such that A will (on average) beat B, B will beat C, and C will beat A. That is, the relationship "X beats Y" is not transitive. When we think about "strength", we often think about it as a one-dimensional numerical quantity; but that implies that "X is stronger than Y" MUST be transitive. Thus, one-dimensional "strength" CANNOT model what actually happens among dice A, B, and C. For complex games, there are a huge number of dimensions of playing strength. Thus I think this sort of intransitivity will rear its ugly head often when one attempts to use genetic algorithms to evolve game playing programs. For example, in the dice problem, if you start off with a population of all A, the first C to occur would probably spread like wildfire and drive all As out of the population. But then, the first B to occur might spread like wildfire and drive all Cs out of the population; and then the first A to occur might wipe out all the Bs. So you could cycle endlessly, the population churning violently without any real progress being made. This might give a the "sawtooth" behavior that was mentioned in an earlier post One thing that might prevent this would be keeping a few copies of previous "successful" versions around longer, so that they couldn't be completely wiped out quickly. Then we might end up with a more stable, "punctuated equilibrium" form of evolution. I wonder if this is one of the advantages of having recessive genes? Certainly, genes are extraordinarily conservative entities by human standards. Why else would people still have many of the genes needed to make gills? Howard -- Howard A. Landman landman@eng.sun.com -or- sun!landman ----------