Evolving explicit opponent models in game playing

ABSTRACT

Opponent models are necessary in games where the game state is only partially known to the player, since the player must infer the state of the game based on the opponents actions. This paper presents an architecture and a process for developing neural network game players that utilize explicit opponent models in order to improve game play against unseen opponents. The model is constructed as a mixture over a set of cardinal opponents, i.e. opponents that represent maximally distinct game strategies. The model is trained to estimate the likelihood that the opponent will make the same move as each of the cardinal opponents would in a given game situation. Experiments were performed in the game of Guess It, a simple game of imperfect information that has no optimal strategy for defeating specific opponents. Opponent modeling is therefore crucial to play this game well. Both opponent modeling and game-playing neural networks were trained using NeuroEvolution of Augmenting Topologies (NEAT). The results demonstrate that game-playing provided with the model outperform networks not provided with the model when played against the same previously unseen opponents. The cardinal mixture architecture therefore constitutes a promising approach for general and dynamic opponent modeling in game-playing.

REFERENCES

• 1: Darse Billings , Denis Papp , Jonathan Schaeffer , Duane Szafron, Opponent modeling in poker, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.493-499, July 1998, Madison, Wisconsin, United States
• 2: Davidson, A., Billings, D., Schaeffer, J., and Szafron, D. Improved Opponent Modeling in Poker. Proceedings of the 2000 International Conference on Artificial Intelligence (ICAI'2000). 1999, 1467--1473.
• 3: Davidson, A. Using Artificial Neural Networks to Model Opponents in Texas Hold 'Em. Unpublished manuscript; http://spaz.ca/aaron/poker/nnpoker.pdf. 1999.
• 4: Anthony Di Pietro , Lyndon While , Luigi Barone, Learning In RoboCup Keepaway Using Evolutionary Algorithms, Proceedings of the Genetic and Evolutionary Computation Conference, p.1065-1072, July 09-13, 2002
• 5: Green, C. Phased Searching with NEAT: Alternating Between Complexification and Simplification. Unpublished manuscript; http://sharpneat.sourceforge.net/phasedsearch.html. 2004
• 6: Gomez, F. and Miikkulainen, R. 2-D Pole Balancing with Recurrent Evolutionary Networks. Proceedings of the International Conference on Artificial Neural Networks (ICANN-98). Springer, Berlin, 1998, 425--430.
• 7: Isaacs, R. A card game with bluffing,. The American MathematicalMonthly, vol. 62. 1955, 99--108.
• 8: Kohonen, T. The Self-Organizing Map. Proceedings of the IEEE, vol. 78. 1990, 1464--1480.
• 9: Korb, K., Nicholson, A., and Jitnah, N. Bayesian Poker. Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI-99). 1999, 343--350.
• 10: Ponsen, M., Munoz-Avila, H., Spronck, P., and Aha, D. Automatically Generating Game Tactics via Evolutionary Learning. AI Magazine, 27(3). AAAI Press, Madison, WI, 2005, 75--84.
• 11: Riley, P., and Veloso, A. Planning for Distributed Execution Through Use of Probabilistic Opponent Models. IJCAI-2001 Workshop PRO-2: Planning under Uncertainty and Incomplete Information. 2001.
• 12: Southey, F., Bowling, M., Larson, B., Piccione, C., Burch, N., and Billings, D. Bayes' Bluff: Opponent Modeling in Poker. Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI-05). 2005, 550--558.
• 13: Pieter Spronck , Marc Ponsen , Ida Sprinkhuizen-Kuyper , Eric Postma, Adaptive game AI with dynamic scripting, Machine Learning, v.63 n.3, p.217-248, June 2006 [doi>10.1007/s10994-006-6205-6]
• 14: Kenneth O. Stanley , Risto Miikkulainen, Continual Coevolution Through Complexification, Proceedings of the Genetic and Evolutionary Computation Conference, p.113-120, July 09-13, 2002
• 15: Whiteson, S., Kohl, N., Miikkulainen, R., and Stone, P. Evolving RoboCup Keepaway Players through Task Decomposition. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003). Kaufmann, San Francisco, 2003, 356--368.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

General Terms:
Algorithms, Experimentation, Theory

Keywords:
AI, artificial intelligence, evolutionary computation, games of imperfect information, neural networks, neuroevolution, opponent modeling