Nguyen, Truong-Huy Dinh (National University of Singapore) | Hsu, David (National University of Singapore) | Lee, Wee-Sun (National University of Singapore) | Leong, Tze-Yun (National University of Singapore) | Kaelbling, Leslie Pack (Massachusetts Institute of Technology) | Lozano-Perez, Tomas (Massachusetts Institute of Technology) | Grant, Andrew Haydn (Singapore-MIT GAMBIT Game Lab)
We apply decision theoretic techniques to construct non-player characters that are able to assist a human player in collaborative games. The method is based on solving Markov decision processes, which can be difficult when the game state is described by many variables. To scale to more complex games, the method allows decomposition of a game task into subtasks, each of which can be modelled by a Markov decision process. Intention recognition is used to infer the subtask that the human is currently performing, allowing the helper to assist the human in performing the correct task. Experiments show that the method can be effective, giving near-human level performance in helping a human in a collaborative game.
Opponents are characterized by a Bayesian network intended to guide Monte-Carlo Tree Search through the game tree of No-Limit Texas Hold'em Poker. By using a probabilistic model of opponents, the network is able to integrate all available sources of information, including the infrequent revelations of hidden beliefs. These revelations are biased, and as such are difficult to incorporate into action prediction. The proposed network mitigates this bias via the expectation maximization algorithm and a probabilistic characterization of the hidden variables that generate observations.
Recent years have witnessed a growing interest in interactive narrative-centered virtual environments for education, training, and entertainment. Narrative environments dynamically craft engaging story-based experiences for users, who are themselves active participants in unfolding stories. A key challenge posed by interactive narrative is recognizing users' goals so that narrative planners can dynamically orchestrate plot elements and character actions to create rich, customized stories. In this paper we present an inductive approach to predicting users' goals by learning probabilistic goal recognition models. This approach has been evaluated in a narrative environment for the domain of microbiology in which the user plays the role of a medical detective solving a science mystery. An empirical evaluation of goal recognition based on n-gram models and Bayesian networks suggests that the models offer significant predictive power.
For many board and card games, computers have at least matched humans in playing skill. An exception is the game of poker, offering new research challenges. The complexity of the game is threefold, namely poker is (1) an imperfect information game, with (2) stochastic outcomes in (3) an adversarial multi-agent environment. One promising approach used for AI poker players applies an adaptive imperfect information game-tree search algorithm to decide which actions to take based on expected value (EV) estimates (Billings et al. 2006). This technique (and related simulation algorithms) require two estimations of opponent information to accurately compute the EV, namely a prediction of the opponent's outcome of the game and prediction of opponent actions. Therefore learning an opponent model is imperative and this model should include the possibility of using relational features for the game-state and -history. In this paper we consider a relational Bayesian approach that uses a general prior (for outcomes and actions) and learns a relational regression tree to adapt that prior to individual players. Using a prior will both allow us to make reasonable predictions from the start and adapt to individual opponents more quickly as long as the choice of prior is reasonable.
Computer Go presents a challenging problem for machine learning agents. With the number of possible board states estimated to be larger than the number of hydrogen atoms in the universe, learning effective policies or board evaluation functions is extremely difficult. In this paper we describe Cortigo, a system that efficiently and autonomously learns useful generalizations for large state-space classification problems such as Go. Cortigo uses a hierarchical generative model loosely related to the human visual cortex to recognize Go board positions well enough to suggest promising next moves. We begin by briefly describing and providing motivation for research in the computer Go domain. We describe Cortigo’s ability to learn predictive models based on large subsets of the Go board and demonstrate how using Cortigo’s learned models as additive knowledge in a state-of-the-art computer Go player (Fuego) significantly improves its playing strength.