|
Learning
Player Modeling for Adaptive Games
Topics: Learning; Genres: General
Abstract: This article describes a lightweight, flexible machine learning technique we call player modeling, designed to help add adaptivity to your game AI. The basic idea is simple: the game maintains a profile of each player that captures the skills, weaknesses, preferences, and other characteristics of that player. This model is updated by the game as it interacts with the player. In turn, the game AI can query the player model to determine how best to adapt its behavior to that particular player - for example, by asking which of several possible tactics will be most challenging to the player. Using player modeling, a game's AI can adapt both during the course of a single play as well as over multiple sessions, resulting in a computer opponent that changes and evolves with time to suit the player.
The article first defines the player model concept in more detail and then discusses strategies for designing a model to suit your game. It then presents a basic player model implementation. Subsequent sections describe how to actually integrate the modeling system with your game, including both how to update the model and how to make use of the information that it contains. The remainder of the article presents several advanced concepts, including a hierarchical player model, alternate model update methods, and other uses for the player model.
Constructing a Decision Tree Based on Past Experience |  |
Topics: Learning, Decision-Trees; Genres: General
Abstract: In recent years, decision trees have gained popularity within the game development community as a practical learning method that can help an AI adapt to a player. Instead of picking from a canned set of reactions to player action, the AI has the opportunity to do something much more powerful: anticipate the player's action before he acts. In this article, we discuss a decision tree learning algorithm called ID3, which constructs a decision tree that identifies the telltale features of an experience to predict its outcome. We then establish ID3's role in Black & White, building on an earlier article in the first edition of AI Game Programming Wisdom. Finally, we consider some important aspects and extensions to the approach, and provide s ample code which implements a simple form of ID3.
Understanding Pattern Recognition Methods
Topics: Learning; Genres: General
Abstract: The task of pattern recognition is to abstract relevant information from the game world and, based on the retrieved information, construct concepts and deduce patterns for the use of higher level reasoning and decision-making systems. We view pattern recognition in computer games from two perspectives: functional and methodological. In the functional approach, we analyze what is required from pattern recognition. We conclude that it can act in different roles, which in turn affect the choice of a method and its implementation. These roles depend on the level of decision-making, the stance toward the player, and the use of the modeled knowledge. In the methodological approach, we review a branch of pattern recognition techniques arising from soft computing. We discuss methods related to optimization, adaptation, and uncertainty. Our intention is to clarify where these methods should be used.
Using Reinforcement Learning to Solve AI Control Problems | |
Topics: Learning; Genres: General
Abstract: During the development of a game's AI many difficult and complex control problems often have to be solved. How should the control surfaces of an aircraft be adjusted so that it follows a particular path? How should a car steer to follow a racing line? What sequences of actions should a real time strategy AI perform to maximize its chances of winning? Reinforcement learning (RL) is an extremely powerful machine learning technique that allows a computer to discover its own solutions to these types problems by trial and error. This article assumes no prior knowledge of RL and introduces the fundamental principles of it by showing how it can be used to allow a computer to learn how to control a simulated racing car. C++ source code for RL and a skeleton implementation of racing game AI are included with the article.
Getting Around the Limits of Machine Learning
Topics: Learning; Genres: General
Abstract: To some AI programmers, the Holy Grail of AI would be a game that learns in the field and gets better the more it is played. Multiplayer network games especially would become challenging to the most skillful players as the AI learns and uses the best plays from the best players. This article examines some of the limitations of machine learning and some of the ways around them. It analyzes learning in three current games. It considers technical and gameplay issues with learning in games.
Adaptive AI: A Practical Example | |
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Because most game AIs are either hared-coded or based on pre-defined scripts, players can quickly learn to anticipate how the AI will behave in certain situations. While the player will develop new strategies over time, the AI will always act as it did when the box was opened, suffering from strategic arrested development. This article describes the adaptive AI of a simple turn-based game called "Advanced Protection."
This practical example of an adaptive AI displays a number of advantages over a static AI. First, the system can dynamically switch between strategies depending on the actual performance of the player - experts will be treated like experts, and novices will be treated like novices. Next, the rules and parameters of the game will be exactly the same for all strategies, which means the AI will not need to "cheat" in order to challenge expert players. Finally, the system can ensure that the AI's "best" strategies truly are the best for each individual player.
How to Build Neural Networks for Games | |
Topics: Neural Networks, Learning; Genres: General
Abstract: Neural networks are a machine learning technique inspired by the human brain. They are a flexible technique that has a wide range of applications in a variety of industries. This article will first introduce neural networks, describing their biological inspiration. Then, it will describe the important components of neural networks and demonstrate how they can be implemented with example code. Next, it will explain how neural networks can be trained, both in-game and prior to shipping, and how a trained neural network can be used for decision-making, classification and prediction. Finally, it will discuss the various applications of neural networks in games, describing previous uses and giving ideas for future applications. Each of these sections will be illustrated with relevant game examples and sample code where appropriate.
How to Build Evolutionary Algorithms for Games | |
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Evolutionary algorithm is the broad term given to the group of optimization and search algorithms that are based on evolution and natural selection, including genetic algorithms, evolutionary computation and evolutionary strategies. Evolutionary algorithms have many advantages, in that they are robust search methods for large, complex or poorly-understood search spaces and nonlinear problems. However, they also have many disadvantages, in that they are time-consuming to develop and resource intensive when in operation. This article will introduce evolutionary algorithms, describing what they are, how they work, and how they are developed and employed, illustrated with example code. Finally, the different applications of evolutionary algorithms in games will be discussed, including examples of possible applications in different types of games.
Building Better Genetic Algorithms | |
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Genetic algorithms are slowly but surely gaining popularity with game developers. Mostly as an in-house tool for tweaking NPC parameters such as ID used in the development of the bots for Quake3, but we are also beginning to see genetic algorithms used in-game, either as an integral part of the gameplay or as an aid for the user.
Unfortunately, many of today's programmers only know the basics of genetic algorithms, not much beyond the original paradigm devised by John Holland back in the mid sixties. This article will bring them up to date with some of the tools available to give improved performance. Techniques discussed will include various scaling techniques, speciation, fitness sharing, and other tips designed to help speedy convergence whilst retaining population diversity. In short, showing you how to get the most from your genetic algorithms.
Advanced Genetic Programming: New Lessons From Biology
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: Genetic programming is a powerful evolutionary mechanism used to create near-optimal solutions to difficult problems. One of the major issues with traditional GP paradigms has been the relative brittleness of the organisms generated by the process: many source code organisms do not compile at all, or produce other kinds of nonsensical results. Recent advances in genetic programming, namely the grammatical evolution scheme based on such biological concepts as degenerate and cyclical DNA and gene polymorphism, promise ways to eliminate this problem and create programs that converge on a solution faster. This article explains grammatical evolution, its biological underpinnings, and a handful of other ways to refine evolutionary computing schemes, like co-evolution
The Importance of Growth in Genetic Algorithms
Topics: Genetic Algorithms, Learning; Genres: General
Abstract: The purpose of this article is to introduce some newer concepts relating to the field of Genetic Algorithms (GA). GAs can introduce variability and adaptability into a game leading to non-linear gameplay and opponents who tailor their strategies to that of the player. Many limitations of mainstream GA implementations can be overcome with some simple additions. Using growth, co-evolution, speciation and other new techniques can alleviate limitations on complexity, designer bias, premature convergence and many more handicaps. These additions can reduce the disadvantages of current GAs and allow the advantages to make games much more unpredictable and challenging.
Sandbox Strategy Learning in Sports Games
Topics: Learning; Genres: Sports
Abstract: The illusion of intelligence is most easily destroyed by predictable or static behaviour. The ability for game characters to learn and adapt to the game player's actions will become increasinly important as the AI in games develops. Yet in many games, specifically in all sports simulation games, the AI must be kept in a "sandbox": It should not potentially evolve into nonsensical territory. This lecture focuses on a strategy learning experiment as part of an AI architecture under design in collaboration with Electronic Arts for their series of sports games.
Neural Networks in Plain English
Mat Buckland (AI-Junkie)
AI-Junkie.com, 2003.
Topics: Learning, Neural Networks; Genres: General
Abstract: I�ll start off by describing what a neural net actually is and what it�s architecture is, then I�ll
do a little theory on how we get it to perform for us but I�ll try to use as little maths as possible.
(Having some understanding of mathematics is impossible to avoid however and the deeper you get into
this topic the more mathematics you are going to have to learn). Finally, we�ll get to the fun bit.
I�ll come up with a little project I will program and take you through one step at a time. It will
be in this last phase of the tutorial where I hope you get the same "eureka" feeling for neural nets
as I did back in rainy old Scotland. Until then just sit back, absorb and be patient.
Genetic Algorithms in Plain English
Mat Buckland (AI-Junkie)
AI-Junkie.com, 2003.
Topics: Learning, Genetic Algorithms; Genres: General
Abstract: The aim of this tutorial is to explain genetic algorithms sufficiently for you to be able to use
them in your own projects. This is a stripped-down to-the-bare-essentials type of tutorial. I'm not
going to go into a great deal of depth and I'm not going to scare those of you with math anxiety by
throwing evil equations at you every few sentences. In fact, I'm not going to throw any nasty equations
at you at all!
Learning and Adaptation in Games | |
Topics: Learning; Genres: General
Abstract: It is anticipated that the widespread adoption of learning in games will be one of the most important advances ever to be made in game AI. Genuinely adaptive AIs will change the way that games are played by forcing the player to continually search for new strategies to defeat the AI. This article presents a detailed examination of the different approaches available for adding learning and adaptation to games and draws on the author's experiences of AI development to provide numerous practical examples. The reader is guided through the decisions that must be made when designing an adaptive AI, and summaries of the problems that are most frequently encountered with practical implementations are provided along with descriptions of effective solutions. The CD that accompanies the book contains source code for a genetic programming class, which can be used to evolve rule-based AI, and genetic algorithm and population-based incremental learner classes, which can be used to evolve AI more generally. The practical application of all these classes is illustrated by evolving an AI that successfully navigates a simple environment.
Varieties of Learning
Topics: Learning; Genres: General
Abstract:
GoCap: Game Observation Capture
Topics: Learning; Genres: General
Abstract:
Pattern Recognition with Sequential Prediction | |
Topics: Learning, Pattern Matching; Genres: General
Abstract: This article provides a simple but efficient algorithm for recognizing repetitive patterns in number sequences. Pattern recognition is something that humans are very good at, but for a computer this is not so easy. Too often a game AI can be beaten by repeatedly performing the same trick, just because it is unable to perceive the pattern. This article explains how to deal with this problem and shows you how to map game events onto useful number sequences. Furthermore, it describes a few possible applications of the algorithm in computer games.
Using N-Gram Statistical Models to Predict Player Behavior
Topics: Learning, Pattern Matching; Genres: General
Abstract: N-Grams are statistical constructs used to predict sequences of events in situations that exhibit the property of local structure. Language is one such context: the probability of hearing the word "fries" is higher if one has just heard the word "french" than if one has just heard the word "fruit". Some games, specifically fighting games in which players develop signature move combinations, also exhibit this property. The article describes how to train an AI to recognize patterns and predict the human player's next move using N-Gram models.
Practical Natural Language Learning
Topics: Learning, NLP; Genres: General
Abstract: The perception of intelligence seems to be directly related to the observation of behavior that is surprising yet sensible. Natural language interfaces were common features of computer entertainment software prior to the advent of sophisticated computer graphics, but these were often repetitive in nature: encountering the same scripted conversation over and over again quickly becomes boring. Stochastic language models have the ability to acquire various features of a language from observations they make, and these features can be used generatively to produce novel utterances that have the properties of being both surprising and sensible. In this article we show how such a system, when used to host in-game socially-oriented conversations, can greatly contribute towards the subjective impression of intelligence experienced by the player.
Testing Undefined Behavior as a Result of Learning
Topics: Learning, Testing; Genres: General
Abstract: We consider learning to be the essence of Artificial Intelligence. Non-player characters, when granted the ability to learn, are given the potential to surprise and entertain the player in completely unexpected ways. This is very reinforcing from the player's point of view, but a nightmare for a testing department. How can they assure the quality of a game that may behave completely differently depending on the who's playing it? In this article we show, via a case study of the computer game "Black & White", exactly how a testing department can achieve their goals when the product they're testing features unpredictable learning AI.
Imitating Random Variations in Behavior using a Neural Network | |
Topics: Learning, Neural Networks; Genres: General
Abstract: As game AI has increased in sophistication, it has become possible to create computer controlled agents that display remarkably human-like behavior. One of the few indications that an agent is non-organic is the frequently clinical nature of their actions, an effect exacerbated by the often ad hoc mechanisms used to add random variations. This article shows how neural networks can be taught to imitate the actual random variations in behavior that are exhibited by real people. This makes it possible to simulate the playing styles of different sports personalities in unprecedented detail - even the extent to which, for example, the cueing direction and position of the cue ball relative to the cushion affect the accuracy of a pool player's shots. The article assumes minimal knowledge of neural networks and illustrates the techniques through their application to a real game. The CD that accompanies the book contains all the source code for the game, along with that for the neural network class, which is designed as a plug-in component that can easily be transferred to other applications.
Genetic Algorithms: Evolving the Perfect Troll | |
Topics: Learning, Genetic Algorithms; Genres: General
Abstract: Genetic Algorithms mimic the process of natural selection to evolve solutions to problems that cannot be solved analytically. Candidate solutions, generated at random, are tested and evaluated for their fitness; the best of them are then bred and the process repeated over many generations, until an individual of satisfactory performance is found. This article explains the biological foundations of genetic algorithms and illustrates their behavior with an example: evolving a troll for a fantasy game.
The Dark Art of Neural Networks
Topics: Learning, Neural Networks; Genres: General
Abstract:
Training an AI to Race
Topics: Driving, Learning; Genres: Racing
Abstract: This is the final article of the three article series, and shows ways to train the AI to race optimally around a racetrack. Issues covered include tuning the car handling (adjusting parameters, converging on optimum values, modifying parameter values, modifying the range, training at high simulation speeds) and real-time editing (real-time track modification, user control overriding AI).
Optimized Machine Learning with GoCap
Topics: Learning; Genres: General
Abstract:
Machine Learning in Games Development
Nick Palmer
AI-Depot.com, September 2002.
Topics: Learning; Genres: General
Abstract: This article explains the current perceptions of ML in the games industry, some of the
techniques and implementations used in present and future games, and offers suggestions for
further exploration.
Decision Trees and Evolutionary Programming
Kirk Delisle
AI-Depot.com, December 2002.
Topics: Learning; Genres: General
Abstract: Commonly used in pattern recognition and AI decision systems, the basic structure of DT
allows application of IF...THEN type rules to classification, which are easily utilized and interpreted.
This article presents a unique method of developing such trees using Evolutionary Programming.
Bot Navigation: Neural Networks for Obstacle Avoidance
Alex J. Champandard
AI-Depot.com, October 2001.
Topics: Bots, Learning; Genres: FPS
Abstract: A practical insight into applying machine learning to a common first person game. These
few pages will use your theoretical understanding of neural networks, and allow you to tackle a
concrete problem with it.
Using a Neural Network in a Game: A Concrete Example | |
Topics: Neural Networks, Learning; Genres: General
Abstract: Neural networks are a powerful artificial intelligence technique that are based on an abstraction of the neurocomputational functions of the human brain. One of their most important characteristics is that they can learn by example, and do not need to be programmed in the conventional sense. For example, Codemasters (the developers of Colin McRae Rally 2.0) discovered that a neural network could learn how to drive a rally car by imitating the developers' play, thus avoiding the need to construct a complex set of rules. This article guides the reader through all the steps that are necessary to incorporate neural networks into their own game. Assuming no prior understanding, the article presents a case study of applying one of the most popular, easy to use, and effective neural networks, the multilayer perceptron, to a real game. All the steps required for successful neural network development are described, as are the most common problems, and their solutions. The CD that accompanies the book includes all the source code for the game, and the neural network class that lies at the heart of its AI. The class is designed to be used as a drop-in module in other games and hence contains no application specific code.
The Future of AI in Games: A Personal View
Richard Evans (Lionhead Studios)
Game Developer Magazine, August 2001.
Topics: Architecture, Learning, History; Genres: General
Abstract:
Designing AI Engines with Built-in Machine Learning Capabilities
Zhimin Ding
Game Developers Conference Proceedings, 1999.
Topics: Architecture, Learning; Genres: General
Abstract: A game engine usually consists of a set of 3D environments and a collection of simulated
interactive characters. The behaviors of these characters are often specified in an ad hoc fashion
with if...then... statements. This is both tedious and inflexible. An alternative solution
is to assign an AI engine to each of these characters and let their behaviors evolve. This is
possible if the AI engine has built-in learning capabilities. This presentation introduces machine
learning technologies that combine system identification and optimal control into an integrated AI engine.
The AI engine does not assume any prior knowledge abou the system under its control and synthesize
an optimal control strategy at run time. Once you have completed the interface of the AI engine with
the characters through the simulated sensors and actuators, you can assign a goal to each of the
characters and let them evolve interesting interactive behaviors.
Autonomous Agents: A Matter of Life and Death
Peter de Bourcier
Computer Game Developers Conference Proceedings, 1997.
Topics: A-Life, Learning; Genres: General
Abstract:
|
