We summarize here the overall results of applying the modifications to the basic Othello genetic programming system.
Symmetry Primitives
The motivation for utilizing symmetrical primitives (corresponding to the minimum set of unique vertices in the baord), stemmed out of our mutual enthusiasm for the game of Go. A basic tenet of Go strategy involves capitalizing on symmetry, such that positions that arise in almost every game are basically translations, rotations, or reflections of each other. Over several thousand years, many of these variations have been tabulated; in this manner, a dictionary corresponding to optimal or near optimal play can be constructed, for local evaluations only.When we first began to test against Edgar without any changes, we were very disappointed with the initial results obtained. It is at this point we realized that if we apply a rationale similar to that used in Go to Othello, we might increase the fitness of the evolved players. Indeed, we were quite amazed just how much of a difference using this set of primitives makes. For example, without exception, we were able to evolve Black players within 3-5 generations that consistently were able to defeat Edgar by substantial margins.
We were even further intrigued when we examined the actual program that had been evolved. A great many consisted of extremely simple depth-1 trees consisting of two terminals. These were sufficient to beat Edgar, as confirmed by using the command-line execution. We therefore conclude from this change what we had expected; the heart of the genetic programming technique is largely in the definition of the primitives. By using primitives that represent the nature of the game, we impart upon the evolved players potential to discover winning Othello strategies. It is also important to note that all of the other terminals corresponding to board positions, such as corners, or near-corners, were eliminated. They were simply unnecessary.
Mobility and Other Primitives
In addition to implementing the symmetry terminals, we also generated two other sets of primitives: the mobility set and various mathematical operators. The mobility set consisted of primitives which represented the state of the game, represented as a parabolic function with the minimum at 32 stones (out of 64 possible).The motivation for using the mobility primitives stemmed from the basic strategies of Othello experts. In the middle game, the object of either player is to limit the number of moves allowed for the opponent. However, the mobility primitives were rarely present in the best individuals, and it was therefore difficult to judge the performance difference using these primitives. Alternatively, the parabolic function representation of mobility may not have been appropriate, as the slope is quite steep, and only values between 0 and 1 are generated.In addition to the mobility primitives, we also tried other mathematical primitives, such as the exponentiation operator and others. However, results indicated that they were both rarely used, and that the best/average fitness of populations actually decreased when these set of terminals was allowed. Given the nature of the game, this behavior is entire understandable. Rarely do situations arise where a particular move should be scored as an exponentiation of board characteristics. In a game such as chess, such an approach may be valid; for example if a pawn can capture a queen. However, in Othello, every board piece is identical, and all have the value of one for scoring purposes. Therefore, we conclude that primitives that attempt to defeat this balance would be detrimental for evolution purposes.
We also deployed a random constant primitive, based on the reasoning that since we are using speciation, programs that can vary moves occasionally would have a survival advantage over those individuals that do not. This follows from the argument that the evolving populations would be static and deterministic, and it would be easy for one species to develop strategies targeted towards the others' weaknesses. However, analyses of the results indicated that this random terminal was never utilized in any of the best individuals from any of the species. Therefore, we conclude that with the parameters we utilized, randomness was not beneficial.
Speciation
Speciation was clearly a powerful concept, but a double-edged sword. As expected, there was always a great degree of dynamism in the species (and hence population) evolution, as judged by the complexity, size, and fitness of the resulting genetic programs. Another intriguing phenomena was that the Both species, with competed against both the White and Black species, almost always had the poorest fitness of the three species.As indicated prior, the primary result of introducing speciation was that evolutionary dynamism was imparted into the population. In the same amount of computation however, evolved Black players were inevitably stronger when evolved solely against Edgar than if evaluated against the other teams. To circumvent this, we used a fitness evaluation process by which the Black team always played Edgar and never the other species. Since the other two species compete against the Black species, this procedure represents an anchoring function, where we are seeking strategies that outperform Edgar's opponents. However, we did not implement measures such as only competing the other species against the best Black player; in this respect, we may have reduced the performance of the other two species. This would also make an interesting extension.
Given the large amount of computational resources required to perform the evolutionary cycle, we are left facing the question as to what the consequences would be of using a much larger population size over many more generations. It is quite conceivable that over time, since the speciation process would constantly change the fitness landscape for each species, the populations would eventually have found the true global optimum. Perhaps this is the tradeoff for reduced short-term maxima.
Further Extensions
The results described here justify the use of a genetic programming approach to the Othello domain. It was observed that the definition of primitives had a tremendous impact on performance. Speciation was able to produce players that were able to play either color with reasonable performance. Several extensions to this work can immediately be considered.First, the primitives employed were symmetry terminals. However, as intimated above, if one were to continue a general geometric analogy between Go and Othello, we would be faced with the observation that though local symmetry can often generate optimal moves, the global board position still has to be examined. We therefore propose the use of general symmetry operators to allow the evolved players to establish a global relationship between the individual local positions.
Second, it would be interesting to allow speciation to occur on-the-fly. Our current implementation used a predetermined species and population structure. Speciation could potentially be performed by randomly generating new species at a low frequency by selecting individuals to group. Alternatively, speciation might be an operator or function encoded as an ADF, to be utilized in certain circumstances, for example, if the fitness for a particular individual is extremely high.