Advisor: Dr. Chris Pollett (cpollett@yahoo.com)

Description:

While the graphical aspect of video games has seen much improvement, A.I. in video games has mostly remained the same. The standard for video game A.I. has been based on elaborate finite state machines (FSMs). The use of FSMs for video game A.I. leads to static behavior in the computer controlled non-player characters (NPCs). In turn, this static behavior detracts from the playability and entertainment value of the game.

The purpose of this thesis is to develop an A.I. system for a computer game, which will allow the NPCs to learn and adapt their behavior to the player. The game itself will be a 3D one-on-one fighting game. The player will control one character while the computer A.I. system will control the other. Each character will have a variety of fighting moves, which can be used to defeat the opponent. The goal is to have the A.I. fighters (AI-bots) be indistinguishable in their behavior from a human player. The AI-bots will dynamically learn and adjust their behaviors according to the behavior of the human player. In essence, the AI-bots will attempt to predict the actions of the human player, much like what a human player tries to do. To achieve this, Hidden Markov Models and/or n-grams will be used to recognize patterns and formulate predictions.

Schedule:

Deliverables:

The full project will be done when CS299 is completed. The following will be done by the end of CS297:

1. N-grams will be studied, and a small program using n-grams will be developed to illustrate and examine the use of n-grams in machine learning. The program will use documents authored by an individual as input to learn the writing patterns of that individual. Then, given some string as input, the program should be able to predict the next word(s) based upon the author's writing pattern.

2. A payoff matrix for the fighting game will be constructed. As such, the possible actions of each player will be determined along with the rewards or setbacks associated with each possible pairing of actions. In essence, this will be the rules of the game.

3. A set of 3D models will be created for the characters of the game, including animations for each of their possible actions.

4. HMMs will be studied and compared to the n-gram approach in the context of the game. A program similar to deliverable 1 will be developed, except using HMMs.

5. The final CS297 report will be produced.

References:

[Charniak96] Statistical Language Learning. Charniak, E. MIT Press. 1996.

[Choi04] Maya Character Animation 2nd ed. Choi, Jae-jin. Sybex. 2004.

[Evans04] Varieties of learning. From AI Game Programming Wisdom. Evans, R. Charles River Media Inc. 2002.

[Ghahramani01] An introduction to Hidden Markov Models and Bayesian networks. Ghahramani, Z. World Scientific Publishing Co. Pte. Ltd. 2001.

[Kaukoranta04] Understanding pattern recognition methods. From AI Game Programming Wisdom 2. Kaukoranta, T., Smed, J., and Hakonen, H. Charles River Media Inc. 2004.

[Laramee04] Using n-gram statistical models to predict player behavior. From AI Game Programming Wisdom. Laramee, F. D. Charles River Media Inc. 2002.

[Manslow02] Learning and adaptation. From AI Game Programming Wisdom. Manslow, J. Charles River Media Inc. 2002.

[Manslow04] Using reinforcement learning to solve AI control problems. From AI Game Programming Wisdom 2. Manslow, J. Charles River Media Inc. 2004.

[Mitchell97] Machine Learning. Mitchell, T. M. McGraw-Hill Companies Inc. 1997.

[Mommersteeg04] Pattern recognition with sequential prediction. From AI Game Programming Wisdom. Mommersteeg, F. Charles River Media Inc. 2002.

[Tozour04] Introduction to Bayesian networks and reasoning under uncertainty. From AI Game Programming Wisdom. Tozour, P. Charles River Media Inc. 2002.

[Ueda04] Simplified Training Algorithm for Hierarchical Hidden Markov Models. Ueda, N. and Sato, T. John Wiley and Sons Inc. 2004.

[Yang94] Hidden Markov model-based learning controller. Yang, J., Xu, Y., and Chen, C.S. IEEE. 1994.

[Yamamoto03] Multi-class composite N-gram language model. Yamamoto, H., Isogai, S., and Sagisaka, Y. Elsevier. 2003.