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. Billings, D., Papp, D., Schaeffer, J., and Szafron, D. Opponent Modeling in Poker. Proceedings of 15th National Conference of the American Association on Artificial Intelligence. AAAI Press, Madison, WI, 1998, 493--498.
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. DiPietro, A., Barone, L., and While L. Learning In RoboCup Keepaway Using Evolutionary Algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002). Kaufmann, San Francisco, 2002, 1065--1072.
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. Spronck, P., Ponsen, M., Sprinkhuizen-Kuyper, I., and Postma, E. Adaptive Game AI with Dynamic Scripting. Machine Learning, 63. Kluwer, Hingham, MA, 2005, 217--248.
14. Stanley, K. and Miikkulainen, R. Continual Coevolution Through Complexification, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002). Kaufmann, San Francisco, 2002, 113--120.
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

• Applied computing

  • Computers in other domains

    • Personal computers and PC applications

      • Computer games

• Computing methodologies

  • Machine learning

    • Machine learning approaches

      • Neural networks

• Hardware

  • Emerging technologies

    • Circuit substrates

      • Cellular neural networks

• Information systems

  • Information systems applications

    • Multimedia information systems

      • Massively multiplayer online games

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Virtual worlds software

        • Interactive games

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

    • Machine learning theory