[en] Coevolutionary algorithms search for test cases as part of the search process. The resulting adaptive evaluation function takes away the need to define a fixed evaluation function, but may also be unstable and thereby prevent reliable progress. Recent work in coevolution has therefore focused on algorithms that guarantee progress with respect to a given solution concept. The Nash Memory archive guarantees monotonicity with respect to the game-theoretic solution concept of the Nash equilibrium, but is limited to symmetric games. We present an extension of the Nash Memory that guarantees monotonicity for asymmetric games. The Parallel Nash Memory is demonstrated in experiments, and its performance on general sum games is discussed.
Disciplines :
Sciences informatiques
Identifiants :
UNILU:UL-ARTICLE-2011-712
Auteur, co-auteur :
Oliehoek, Frans A.
de Jong, Edwin D.
VLASSIS, Nikos ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Langue du document :
Anglais
Titre :
The Parallel Nash Memory for Asymmetric Games
Date de publication/diffusion :
2006
Nom de la manifestation :
Proc. Genetic and Evolutionary Computation Conference, Seattle, WA
Date de la manifestation :
2006
Titre de l'ouvrage principal :
Proc. Genetic and Evolutionary Computation Conference, Seattle, WA
R. Axelrod. The evolution of strategies in the iterated prisoner's dilemma. In L. Davis, editor, Genetic Algorithms and Simulated Annealing, Research Notes in Artificial Intelligence, pages 32-41, London, 1987. Pitman Publishing.
A. Bucci and J. B. Pollack. On identifying global optima in cooperative coevolution. In GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, volume 1, pages 539-544, Washington DC, USA, 25-29 June 2005. ACM Press.
D. Cliff and G. F. Miller. Tracking the Red Queen: Measurements of adaptive progress in co-evolutionary simulations. In F. Morán, A. Moreno, J. J. Merelo, and P. Chacón, editors, Proceedings of the Third European Conference on Artificial Life: Advances in Artificial Life, volume 929 of LNAI, pages 200-218, Berlin, 1995. Springer.
D. Cliff and G. F. Miller. Co-evolution of pursuit and evasion II: Simulation methods and results. In P. Maes, M. J. Mataric, J.-A. Meyer, J. B. Pollack, and S. W. Wilson, editors, From Animals to Animals. Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior, SAB-96, volume 4, pages 506-515, Cambridge, MA, 1996. The MIT Press.
E. D. De Jong. The Incremental Pareto-Coevolution Archive. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-04, pages 525-536, 2004.
E. D. De Jong. The maxsolve algorithm for coevolution. In H.-G. Beyer, editor, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-05, pages 483-489, 2005.
E. D. De Jong and J. B. Pollack. Ideal evaluation from coevolution. Evolutionary Computation, 12(2):159-192, 2004.
S. G. Ficici. Solution Concepts in Coevolutionary Algorithms. PhD thesis, Brandeis University, 2004.
S. G. Ficici. Monotonic solution concepts in coevolution. In Genetic and Evolutionary Computation - GECCO-2005, pages 499-506, 2005.
S. G. Ficici and J. B. Pollack. Coevolving communicative behavior in a linear pursuer-evader game. In R. Pfeifer, B. Blumberg, J.-A. Meyer, and S. Wilson, editors, From Animals to Animals. Proceedings of the Fifth International Conference on Simulation of Adaptive Behavior, SAB-98, pages 263-269, Cambridge, MA, 1998. The MIT Press.
S. G. Ficici and J. B. Pollack. A game-theoretic approach to the simple Coevolutionary algorithm. In M. Schoenauer et al., editor, Parallel Problem Solving from Nature, PPSN-VI, volume 1917 of LNCS, Berlin, 2000. Springer.
S. G. Ficici and J. B. Pollack. Pareto optimality in coevolutionary learning. In J. Kelemen, editor, Sixth European Conference on Artificial Life, Berlin, 2001. Springer.
S. G. Ficici and J. B. Pollack. A game-theoretic memory mechanism for coevolution. In Genetic and Evolutionary Computation - GECCO-2003, pages 286-297, 2003.
D. Floreano, S. Nolfi, and F. Mondada. Competitive coevolutionary robotics: From theory to practice. In R. Pfeifer, B. Blumberg, J.-A. Meyer, and S. Wilson, editors, From Animals to Animals. Proceedings of the Fifth International Conference on Simulation of Adaptive Behavior, SAB-98, pages 512-524, Cambridge, MA, 1998. The MIT Press.
P. Funes. Evolution of Complexity in Real-World Domains. PhD thesis, Brandeis University, Waltham, MA, 2001.
D. W. Hillis. Co-evolving parasites improve simulated evolution in an optimization procedure. Physica D, 42:228-234, 1990.
H. Juillé and J. B. Pollack. Coevolutionary learning: a case study. In Proceedings of the 15th International Conference on Machine Learning, pages 251-259, San Francisco, CA, 1998. Morgan Kaufmann.
H. Juillé and J. B. Pollack. Coevolving the "ideal" trainer: Application to the discovery of cellular automata rules. In Proceedings of the Third Annual Genetic Programming Conference, Madison, Wisconsin, 1998.
D. Koller, N. Megiddo, and B. von Stengel. Fast algorithms for finding randomized strategies in game trees. In Proc. of the 26th ACM Symposium on Theory of Computing (STOC), pages 750-759, 1994.
D. Koller and A. Pfeffer. Representations and solutions for game-theoretic problems. Artificial Intelligence, 94(1-2):167-215, 1997.
J. R. Koza. Genetic evolution and co-evolution of computer programs. In C. Langton, C. Taylor, J. Farmer, and S. Rasmussen, editors, Artificial Life II, volume X of SFI Studies in the Sciences of Complexity, pages 603-629. Addison-Wesley, Redwood City, CA, 1992.
H. Kuhn. Extensive games and the problem of information. Annals of Mathematics Studies, 28:193-216, 1953.
K. Lindgren. Evolutionary phenomena in simple dynamics. In C. Langton, C. Taylor, J. Farmer, and S. Rasmussen, editors. Artificial Life II, volume X of SFI Studies in the Sciences of Complexity, pages 295-312. Addison-Wesley, Redwood City, CA, 1992.
J. Miller. The coevolution of automata in the repeated prisoner's dilemma. Santa Fe Institute working paper 89-003, 1989.
F. A. Oliehoek. Game theory and AI: a unified approach to poker games. Master's thesis, University of Amsterdam, Sept. 2005.
F. A. Oliehoek, M. T. J. Spaan, and N. Vlassis. Best-response play in partially observable card games. In Benelearn 2005: Proceedings of the 14th Annual Machine Learning Conference of Belgium and the Netherlands, pages 45-50, Feb. 2005.
F. A. Oliehoek, N. Vlassis, and E. D. de Jong. Coevolutionary Nash in poker games. In BNAIC 2005: Proceedings of the 17th Belgian-Dutch Conference on Artificial Intelligence, pages 188-193, Oct. 2005.
M. J. Osborne and A. Rubinstein. A course in game theory. The MIT Press, Cambridge, MA, 1994.
L. Pagie and P. Hogeweg. Evolutionary consequences of coevolving targets. Evolutionary Computation, 5(4):401-418, 1998.
L. Pagie and P. Hogeweg. Information integration and Red Queen dynamics in coevolutionary optimization. In Proceedings of the 2000 Congress on Evolutionary Computation, CEC-00, pages 1260-1267, Piscataway, NJ, 2000. IEEE Press.
J. Paredis. Coevolutionary computation. Artificial Life, 2(4), 1996.
J. Paredis. Coevolving cellular automata: Be aware of the Red Queen. In T. Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms, ICGA-97, San Francisco, CA, 1997. Morgan Kaufmann.
J. B. Pollack and A. D. Blair. Co-evolution in the successful learning of backgammon strategy. Machine Learning, 32(1):225-240, 1998.
R. Porter, E. Nudelman, and Y. Shoham. Simple search methods for finding a Nash equilibrium. Games and Economic Behavior, (to appear).
M. A. Potter and K. A. De Jong. Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1):1-29, 2000.
M. L. Puterman. Markov Decision Processes - Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, 1994.
C. W. Reynolds. Competition, coevolution and the game of tag. In R. A. Brooks and P. Maes, editors, Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems, pages 59-69, Cambridge, MA, 1994. The MIT Press.
R. T. Rockafellar. Convex analysis. Princeton, N.J., Princeton University Press, 1970.
C. D. Rosin. Coevolutionary Search among Adversaries. PhD thesis, University of California, San Diego, CA, 1997.
L. M. Schmitt. Theory of coevolutionary genetic algorithms. In M. Guo and L. T. Yang, editors, Parallel and Distributed Processing and Applications, International Symposium, ISPA 2003, pages 285-293, Berlin, 2003. Springer.
E. J. Sondik. The optimal control of partially observable Markov decision processes. PhD thesis, Stanford University, 1971.
K. O. Stanley and R. Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21:63-100, 2004.
N. Vlassis. A concise introduction to multiagent systems and distributed AI. Informatics Institute, University of Amsterdam, Sept. 2003. http://www.science.uva.nl/~vlassis/cimasdai.
J. von Neumann and O. Morgenstern. The Theory of Games and Economic Behavior. Princeton University Press, 1947. 2nd edition.
B. Von Stengel. Computing equilibria for two-person games. In R. Aumann and S. Hart, editors, Handbook of Game Theory with Economic Applications, volume 3, chapter 45, pages 1723-1759. Elsevier, 2002. http://ideas.repec.org/h/eee/ gamchp/3-45.html.
R. A. Watson and J. B. Pollack. Symbiotic combination as an alternative to sexual recombination in genetic algorithms. In M. Schoenauer et al., editor, Parallel Problem Solving from Nature, PPSN- VI, volume 1917 of LNCS, Berlin, 2000. Springer.
R. A. Watson and J. B. Pollack. Coevolutionary dynamics in a minimal substrate. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-01, pages 702-709, San Francisco, CA, 2001. Morgan Kaufmann.
R. A. Watson and J. B. Pollack. A computational model of symbiotic composition in evolutionary transitions. Biosystems, 69(2-3):187-209, May 2003. Special Issue on Evolvability, ed. Nehaniv.
R. P. Wiegand. An Analysis of Cooperative Coevolutionary Algorithms. PhD thesis, George Mason University, Fairfax, Virginia, 2003.
