The task of keyhole (unobtrusive) plan recognition is central to adaptive game AI. "Tech trees" or "build trees" are the core of real-time strategy (RTS) game strategic (long term) planning. This paper presents a generic and simple Bayesian model for RTS build tree prediction from noisy observations, which parameters are learned from replays (game logs). This unsupervised machine learning approach involves minimal work for the game developers as it leverage players' data (com- mon in RTS). We applied it to StarCraft1 and showed that it yields high quality and robust predictions, that can feed an adaptive AI.
@cite_13: We present an approach to keyhole plan recognition which uses a dynamic belief (Bayesian) network to represent features of the domain that are needed to identify users‘ plans and goals. The application domain is a Multi-User Dungeon adventure game with thousands of possible actions and locations. We propose several network structures which represent the relations in the domain to varying extents, and compare their predictive power for predicting a user‘s current goal, next action and next location. The conditional probability distributions for each network are learned during a training phase, which dynamically builds these probabilities from observations of user behaviour. This approach allows the use of incomplete, sparse and noisy data during both training and testing. We then apply simple abstraction and learning techniques in order to speed up the performance of the most promising dynamic belief networks without a significant change in the accuracy of goal predictions. Our experimental results in the application domain show a high degree of predictive accuracy. This indicates that dynamic belief networks in general show promise for predicting a variety of behaviours in domains which have similar features to those of our domain, while reduced models, obtained by means of learning and abstraction, show promise for efficient goal prediction in such domains.
@cite_18: Real-time strategy games present an environment in which game AI is expected to behave realistically. One feature of realistic behaviour in game AI is the ability to recognise the strategy of the opponent player. This is known as opponent modeling. In this paper, we propose an approach of opponent modeling based on hierarchically structured models. The top-level of the hierarchy can classify the general play style of the opponent. The bottom-level of the hierarchy can classify specific strategies that further define the opponent’s behaviour. Experiments that test the approach are performed in the RTS game Spring. From our results we may conclude that the approach can be successfully used to classify the strategy of an opponent in the Spring game.
@cite_9: Abstract We argue that the problem of plan recognition, inferring an agent's plan from observations, is largely a problem of inference under conditions of uncertainty. We present an approach to the plan recognition problem that is based on Bayesian probability theory. In attempting to solve a plan recognition problem we first retrieve candidate explanations. These explanations (sometimes only the most promising ones) are assembled into a plan recognition Bayesian network , which is a representation of a probability distribution over the set of possible explanations. We perform Bayesian updating to choose the most likely interpretation for the set of observed actions. This approach has been implemented in the Wimp3 system for natural language story understanding.
@cite_6: Developing computer-controlled groups to engage in combat, control the use of limited resources, and create units and buildings in real-time strategy (RTS) games is a novel application in game AI. However, tightly controlled online commercial game pose challenges to researchers interested in observing player activities, constructing player strategy models, and developing practical AI technology in them. Instead of setting up new programming environments or building a large amount of agentpsilas decision rules by playerpsilas experience for conducting real-time AI research, the authors use replays of the commercial RTS game StarCraft to evaluate human player behaviors and to construct an intelligent system to learn human-like decisions and behaviors. A case-based reasoning approach was applied for the purpose of training our system to learn and predict player strategies. Our analysis indicates that the proposed system is capable of learning and predicting individual player strategies, and that players provide evidence of their personal characteristics through their building construction order.
@cite_3: Artificial Intelligence techniques have been successfully applied to several computer games. However in some kinds of computer games, like real-time strategy (RTS) games, traditional artificial intelligence techniques fail to play at a human level because of the vast search spaces that they entail. In this paper we present a real-time case based planning and execution approach designed to deal with RTS games. We propose to extract behavioral knowledge from expert demonstrations in form of individual cases. This knowledge can be reused via a case based behavior generator that proposes behaviors to achieve the specific open goals in the current plan. Specifically, we applied our technique to the W ARGUS domain with promising results.
@cite_0: While several researchers have applied case-based reasoning techniques to games, only Ponsen and Spronck (2004) have addressed the challenging problem of learning to win real-time games. Focusing on Wargus, they report good results for a genetic algorithm that searches in plan space, and for a weighting algorithm (dynamic scripting) that biases subplan retrieval. However, both approaches assume a static opponent, and were not designed to transfer their learned knowledge to opponents with substantially different strategies. We introduce a plan retrieval algorithm that, by using three key sources of domain knowledge, removes the assumption of a static opponent. Our experiments show that its implementation in the Case-based Tactician (CaT) significantly outperforms the best among a set of genetically evolved plans when tested against random Wargus opponents. CaT communicates with Wargus through TIELT, a testbed for integrating and evaluating decision systems with simulators. This is the first application of TIELT. We describe this application, our lessons learned, and our motivations for future work.
@cite_5: In this paper we explore the use of Hierarchical-Task-Network (HTN) representations to model strategic game AI. We will present two case studies. The first one reports on an experiment using HTNs to model strategies for Unreal Tournament® (UT) bots. We will argue that it is possible to encode strategies that coordinate teams of bots in first-person shooter games using HTNs. The second one compares an alternative to HTNs called Task-Method-Knowledge (TMK) process models. TMK models are of interest to game AI because, as we will show, they are as expressive as HTNs but have more convenient syntax. Therefore, HTN planners can be used to generate correct plans for coordinated team AI behavior modeled with TMK representations.
@cite_15: In this work we aim to narrow the gap between plan recognition and planning by exploiting the power and generality of recent planning algorithms for recognizing the set G* of goals G that explain a sequence of observations given a domain theory. After providing a crisp definition of this set, we show by means of a suitable problem transformation that a goal G belongs to G* if there is an action sequence π that is an optimal plan for both the goal G and the goal G extended with extra goals representing the observations. Exploiting this result, we show how the set G* can be computed exactly and approximately by minor modifications of existing optimal and suboptimal planning algorithms, and existing polynomial heuristics. Experiments over several domains show that the suboptimal planning algorithms and the polynomial heuristics provide good approximations of the optimal goal set G* while scaling up as well as state-of-the-art planning algorithms and heuristics.
@cite_10: Artificial Intelligence (AI) techniques have been successfully applied to several computer games. However, in the vast majority of computer games traditional AI techniques fail to play at a human level because of the characteristics of the game. Most current commercial computer games have vast search spaces in which the AI has to make decisions in real-time, thus rendering traditional search based techniques inapplicable. For that reason, game developers need to spend a big effort in hand coding specific strategies that play at a reasonable level for each new game. One of the long term goals of our research is to develop artificial intelligence techniques that can be directly applied to such domains, alleviating the effort required by game developers to include advanced AI in their games.
@cite_11: In Real-Time Strategy (RTS) video games, players (controlled by humans or computers) build structures and recruit armies, fight for space and resources in order to control strategic points, destroy the opposing force and ultimately win the game. Players need to predict where and how the opponents will strike in order to best defend themselves. Conversely, assessing how the opponents will defend themselves is crucial to mounting a successful attack while exploiting the vulnerabilities in the opponent's defence strategy. In this context, to be truly adaptable, computer-controlled players need to recognize their opponents' behaviour, their goals, and their plans to achieve those goals. In this paper we analyze the algorithmic challenges behind behaviour recognition in RTS games and discuss a generic RTS behaviour recognition system that we are developing to address those challenges. The application domain is that of RTS games, but many of the key points we discuss also apply to other video game genres such as multiplayer first person shooter (FPS) games.
This work was encouraged by the reading of weber Data Mining Approach to Strategy Prediction and the fact that they provided their dataset. They tried and evaluated several machine learning algorithms on replays that were labeled with strategies (supervised learning). There are related works in the domains of opponent modeling @cite_6 @cite_18 @cite_11 . The main methods used to these ends are case-based reasoning (CBR) and planning or plan recognition @cite_0 @cite_10 @cite_3 @cite_5 @cite_15 . There are precedent works of Bayesian plan recognition @cite_9 , even in games with @cite_13 using dynamic Bayesian networks to recognize a user's plan in a multi-player dungeon adventure. Also, Chung05 describe a Monte-Carlo plan selection algorithm applied to Open RTS.