The Role of Behavioral Diversity and Difficulty of Opponents in Coevolving Game-Playing Agents

[Preprint – this paper has been accepted for presentation at EvoApplications 2015] Abstract Generalization performance of learning agents depends on the training experience to which they have been exposed. In game-playing domains, that experience is determined by the opponents faced during learning. This analytical study investigates two characteristics of oppo-nents in competitive coevolutionary learning: behavioral diversity and difficulty (performance against other players). To assess diversity, we propose a generic intra-game behavioral distance measure, that could be adopted to other sequential decision problems. We monitor both charac-teristics in two-population coevolutionary learning of Othello strategies, attempting to explain their relationship with the generalization perfor-mance achieved by the evolved solutions. The main observation is the existence of a non-obvious trade-off between difficulty and diversity, with the latter being essential for obtaining high generalization performance