Quantitative analysis of the hall of fame coevolutionary archives

ABSTRACT

This paper provides an attempt to investigate the properties of the Hall of Fame archive in two-population competitive coevolution environment applied to the game of Othello. Using the measure of expected utility, a round-robin tournament and performance profiles, we show that coevolution can be biased towards playing better with stronger opponents if it is driven by interactions with the past champions kept in the archive, in addition to pure competition among coevolving individuals. Moreover, the Hall of Fame does not necessarily influence the overall perfromance in terms of expected utility, as it trades-off the ability to cope with opponents of various strength, so that the resulting players are more likely to win with a strong opponent than with a weak one.

References

1. S. G. Ficici and J. B. Pollack. Challenges in coevolutionary learning: Arms-race dynamics, open-endedness, and mediocre stable states. In Proceedings of the Sixth International Conference on Artificial Life, pages 238--247. MIT Press, 1998.
2. S. G. Ficici and J. B. Pollack. Pareto optimality in coevolutionary learning. In J. Kelemen and P. Sosík, editors, Advances in Artificial Life, 6th European Conference, ECAL 2001, volume 2159 of Lecture Notes in Computer Science, pages 316--325, Prague, Czech Republic, 2001. Springer.
3. S. G. Ficici and J. B. Pollack. A game-theoretic memory mechanism for coevolution. In E. C.-P. et al., editor, Genetic and Evolutionary Computation - GECCO 2003, volume 2723 of Lecture Notes in Computer Science, pages 286--297, Chicago, IL, 2003. Springer.
4. W. Jaśskowski, P. Liskowski, M. Szubert, and K. Krawiec. Improving Coevolution by Random Sampling. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2013), 2013.
5. K. Krawiec, W. Jaśskowski, and M. Szubert. Evolving small-board go players using coevolutionary temporal difference learning with archive. International Journal of Applied Mathematics and Computer Science, 21(4):717--731, 2011.
6. M. Nogueira, C. Cotta, and A. J. Fernández-Leiva. An analysis of hall-of-fame strategies in competitive coevolutionary algorithms for self-learning in rts games. Learning and Intelligent OptimizatioN Conference (LION 7), 2013.
7. J. Paredis. Coevolving cellular automata: Be aware of the red queen. In Proceedings of the Seventh International Conference on Genetic Algorithms, pages 393--400, 1997.
8. J. B. Pollack and A. D. Blair. Co-evolution in the successful learning of backgammon strategy. Machine Learning, 32(3):225--240, 1998.
9. C. D. Rosin and R. K. Belew. New methods for competitive coevolution. Evolutionary Computation, 5(1):1--29, 1997.
10. M. Szubert, W. Jaśskowski, and K. Krawiec. Coevolutionary temporal difference learning for othello. In IEEE Symposium on Computational Intelligence and Games, pages 104--111, Milano, Italy, 2009.
11. R. A. Watson and J. B. Pollack. Coevolutionary dynamics in a minimal substrate. In L. S. et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 702--709, San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction

  • Machine learning