Background
The concepts of speciation and competition are two of the most important phenomena that drive evolution in natural ecosystems. Without these mechanisms, a fairly static selection function would exist; one that was dictated solely by the environment. Eventually, organisms would eventually converge at a local or global maximum fitness, and evolution would cease.Othello strategies for success can provide a fairly complex evolutionary landscape consisting of hypotheses variations. However, the dimensionality of the landscape is reduced when a particular deterministic opponent is utilized, as in the case of only deploying Edgar. Because of the potential for a very rugged landscape, it is very likely that Edgar-evolved players would become trapped in a local minimum only, and hypothesis variation would be diminished as the population becomes homogenous.
In this project, a static environment would correspond to the evolution of players against Edgar as the White opponent. There are several problems with this kind of approach. First, because of Edgar's degree of determinism, Black players would be generated that could consistently defeat Edgar based on Edgar's weaknesses. However, these Black players would not necessarily indicate a global maximal fitness, only a local maximal fitness corresponding to Edgar's selection function. Therefore, even a novice human player would likely be able to defeat the evolved GP that can defeat Edgar.
Implementation
We therefore applied the biological notion of speciation and competition in evolving globally optimal Othello players. In our implementation, we used three different species that co-evolve; one corresponding to only a Black strategy (Black Team), one corresponding to only a White strategy (White Team), and finally, a population subset that can play either color (Both Team).Our approach in creating these subsets of the populations (representing species) was to first disallow any chance of migration from one species to another. This is based on the biological definition of species, and would serve to eliminate homonogeniety among all three subsets. The second implementation consideration concerned the fitness evaluation function. We therefore implemented a system where fitness is measured by picking each individual in a deme, and testing the individual against the other subsets several times, and computing the average fitness.
It was absolutely necessary to use several matches to evaluate an individual's fitness because of the potentially tremendous disparity in performance among individuals in each of the subsets. In other words, we are now using a relative fitness measure, not an absolute fitness as defined by playing only against Edgar. The ramifications of using this sort of evaluation are quite significant. First, we have now introduced the concept of co-evolution, where populations are dynamically and constantly evolving over time to compete against the other species. Second, because of this dynamic evolution, the probability of finding a global optimum over enough generations is unity. The important consideration however, is to allow non-crossover mutational operators and new individual creation to constantly introduce novel genetic material into the population. Finally, because Edgar only plays as a White opponent, using three different species corresponding to different color strategies also rectified this shortcoming in the package.
Generating three species, employing co-evolution, and using a relative fitness measure, though very interesting, can have drawbacks. The first drawback is in the extremely slow absolute fitness increase. Even though the populations may be evolving sufficiently against each other, in terms of absolute fitness (against perhaps either Edgar or a human player), the evolution rate was not high. The reason for this is obvious; the evolving players will not see an optimal strategy until eons of generations have passed. The second drawback to using this sort of approach is the related but very interesting phenomena of inter-special relationships. For example, if the White species evolves a particular strategy, Black will optimize for it until White changes, and so forth. Therefore, the strategies that are evolved may not even represent any sort of optimal Othello playing, only the capitilization of the weaknesses of a specific species.
In order to address these drawbacks, we used a hybrid approach to evaluating players. First, we only played against Edgar in the initial generations during which a large number of randomly generated individuals simply are not capable of playing Othello to any reasonable degree. Through this process of chaffing, we evolve populations that by the early generations are already capable of defeating Edgar. However, species migration still is, and always will be, disallowed. In the later generations, we then introduce the actual co-evolution process, by playing players from each team against those from other species. However, an important modification was that if the individual being evaluated was from either the Black or Both species, then there was a probability that they would play against Edgar.
We hypothesize that this approach would likely yield dynamic, evolving populations that are constantly seeking the global maximal fitness hypothesis. By using a relative fitness during evaluation, we are maintaining this dynamic state. In addition, by using Edgar at a finite probability, we are also ensuring that we are also measuring the absolute fitness. Therefore, the composition of these two fitness evaluation procedures over many generations should yield species that are constantly seeking maximums in a relative fitness landscape; but the ultimate direction of movement through this many dimensional space is towards the absolute maximum, or one that is capable of defeating Edgar or a human player.
Performance
In trials where Edgar was not utilized at all in the fitness evaluation procedure, the resulting players were quite poor, as measured by testing the best players against Edgar. In addition, when Edgar fitness evaluation was introduced at some probability, this did not seem to affect this phenomena, and occasionally exacerbated the performance. We therefore concluded that Edgar was effectively weeding out the better players in the Both or Black species by presenting a challenge much greater than the White species. We then modified the evaluation function so that Edgar was always played against individuals of the Black species. The results were then much better, and produced trees in all categories with fair performance, with of course the best Black players consistently defeating Edgar. We also compared the results of not using Edgar at all against the White or Both teams, and the results were also more encouraging.In all of our trials, we used a standard parameter list consisting of 150 individuals, over 10 generations. Complexity did not affect fitness; and as indicated earlier, when inter-species competition was utilized, the average of five different matches was used as the fitness meaasure.