Coevolving Game-Playing Agents: Measuring Performance and Intransitivities

Coevolution is a natural choice for learning in problem domains where one agent's behavior is directly related to the behavior of other agents. However, there is a known tendency for coevolution to produce mediocre solutions. One of the main reasons for this is cycling, caused by intransitivities among a set of players. In this paper, we explore the link between coevolution and games, and revisit some of the coevolutionary literature in a games and measurement context. We propose a set of measurements to identify cycling in a population and a new algorithm that tries to minimize cycling in strictly competitive (zero sum) games. We experimentally verify our approach by evolving weighted piece counter value functions to play othello, a classic two-player perfect information board game. Our method is able to find extremely strong value functions of this type.