3.0 – ML in Multiplayer Environments

3.1 – Player Modelling

In my previous post I discussed the uses of player modelling in the Forza Motorsport series. Capturing player behaviour allows online games to simulate multiplayer gameplay without the need for both players to be actively involved at the same time. Musick, Bowling, Furnkraz, and Graepel also mention the potential for this technology in MMORPGs (Massively Multiplayer Online Role-Playing Games) where a large persistent universe may require a character to be present regardless of the availability of their human counter-part (Musick, Bowling, Furnkraz, and Graepel, 2006).

3.2 – Match-making

Machine learning has great potential in online match-making. As discussed in Part 1, players enjoy themselves the most when an enemy AI can create just enough challenge to match their skill level and play style. The same ideas hold true for online play, and it become a significant challenge to create a system which can match players and teams together in a way that is satisfying for all.

Xbox live employs a matchmaking system called TrueSkill™. The system addresses some of the major challenges in mutliplayer match making systems. These include the idea that team-based match outcomes need to provide skill information about each individual player, and that estimating the skill level of a team requires knowledge of each members skill and how they may act together. The math may be a little beyond me, but essentially the learning part of TrueSkill™ is when it deals with a player’s skill level. The system uses outcome of a game along with each players estimated performance within their team top update the player’s recorded skill level. TrueSkill™can then use the skill levels for each player to create increasingly more even, fair matches that are enjoyable to all members  (Herbrich, Minka, and Graepel, 2006).

References

Musick, Ron, Michael Bowling, Johnannes Furnkranz, and Thore Graepel. “Machine learning and games.” Machine Learning 63: 211-215. SpringerLink. Web. 25 June 2014.

Graepel, Thore, Joaquin Quiñonero Candela, and Ralf Herbrich. “Machine Learning in Games: The Magic of Research in Microsoft Products.” . Microsoft Research Cambridge, 1 Jan. 2008. Web. 20 June 2014. <http://research.microsoft.com/en-us/events/2011summerschool/jqcandela2011.pdf>.

Herbrich, Ralf, Tom Minka, and Thore Graepel. “Trueskill™: A Bayesian skill rating system.” Advances in Neural Information Processing Systems. 2006.

2.0 – Player Behaviour Capture

Another use of machine learning in video games is for player modelling. Creating a model that represents one or more aspects of the player (playstyle, preferences, skill level, etc.) allows the game to adapt to the player, predict the players choices, represent the player in one or more ways among many others.

2.1 Drivatar™ Example

Forza Motorsport uses machine learning to model and reproduce player behaviour. This allows the computer to represent the player and their racing style in online games without the user being present (“Drivatar™ – Microsoft Research.”). The game AI uses a ‘racing line model‘ which is a smooth driving path through each segment of track (Graepel, Candela, and Herbrich, 2008). The player modelling process then uses information about how you navigate the turns in a track to train your Drivatar™. The variables used are related to: how consistently you drive; how smoothly you drive through corners; how you brake before a turn and consequently how you enter the turn; how quickly and accurately you navigate the apex of a corner; and how you exit the corner. The algorithm is trained from 5 races which represent a specific population sample of cars and tracks (“Drivatar™ in Forza Motorsport.”).

This is a good example of supervised learning in a video game.

2.2 Storytelling Example

Thue, Bultiko, Spetch, and Wasylishen did a very interesting study on the use of player modelling to create dynamic story lines based on individual preferences. They use the player types defined by of Robin D. Laws in his book Robin’s Laws of Good Game Mastering (2001) to evaluate their players. Whenever the player is faced with a decision, each outcome has defined player type association(s) which are used to update a genome which represents the current player’s preferences. The interactive story system then uses this genome to decide which events / plot points should come up next (Thue, David, Vadim Bultiko, Macia Spetch, and Eric Wasylishen, 2014).

This is another example of supervised learning. This implementation does not require training ahead of time, but collecting information about the player is required before accurate decisions can be made.

References

“Drivatar™ – Microsoft Research.” Drivatar™ – Microsoft Research. Microsoft Research, n.d. Web. 23 June 2014. <http://research.microsoft.com/en-us/projects/drivatar/>.

“Drivatar™ in Forza Motorsport.” Drivatar™ in Forza Motorsport. Microsoft Research, n.d. Web. 23 June 2014. <http://research.microsoft.com/en-us/projects/drivatar/forza.aspx>.

Graepel, Thore, Joaquin Quiñonero Candela, and Ralf Herbrich. “Machine Learning in Games: The Magic of Research in Microsoft Products.” . Microsoft Research Cambridge, 1 Jan. 2008. Web. 20 June 2014. <http://research.microsoft.com/en-us/events/2011summerschool/jqcandela2011.pdf>.

Thue, David, Vadim Bultiko, Macia Spetch, and Eric Wasylishen. “Interactive Storytelling: A Player Modelling Approach.” : n. pag. Association for the Advancement of Artificial Intelligence. Web. 23 June 2014.

The next step in my research process is to look more specifically ad games. My goal in this post will be to discover and discuss several situations where machine learning could be useful in a game. I will be looking, if available, at published studies as well as my own opinions.

1.0 – Adaptive Artificial Intelligence

An important area of focus in many newer computer games is in their artificial intelligence (AI) systems. AI systems are used to control non-player characters (NPCs) or other game entities in order to create challenge for the player. As mentioned before, players are very unique, and providing them with just enough challenge relative to their play style and skill level will make the experience more enjoyable to them (Hagelback and Johansson, 51)

1.1 Some Theory

In general, an AI requires architecture and algorithms, knowledge, and an interface to the environment (Laird and van Lent, 2005). When we start looking at Adaptive, learning AI there are other factors that come into play. Nick Palmer outlines his methods for creating what he calls ‘Learning Agents’ in his online essay Machine Learning in Games Development. His setup involves the following components:

Learning Element – which is responsible for actually changing the behavior of the AI based on its past level of success or failure

Performance Element – which decides which action the AI will take based on it’s current knowledge of the environment

Performance Analyzer – which judges the actions of the performance element. Palmer clarifies that the judging must be made on the same information that used by the performance element to make decisions. The analyses made by this element will help decide how or if the learning element alters the behaviour of the AI.

Curiosity Element – which understands the goals of the AI and will challenge the performance element to try new behaviour possibilities which may improve the state of the AI with respect to it’s overall goals. This element helps keep the AI from getting satisfied by moderately successful behaviour (like hiding in cover the whole game so as not to die).

In general, developers who use adaptive AI in game development, will train the AI and allow it to improve during development, but simply capture the best results and build them statically into the final game (Palmer).

1.2 Supervised Learning and AI

Palmer mentions that his proposed system utilizes the ideas of reinforcement learning, and I found that this if often the case with game AI. I wanted to look into why this may be the case. Thore Graepel explored both methods for two different games in his talk “Learning to Play: Machine Learning in Games”. Supervised learning involves a  lot of training, and is targeted more at predicting outcomes than generating real-time behaviour (Browlee, 2013). This type of learning is used to create game playing AI’s for games such as chess and GO because these games have past move sets and results that can be used for training. They also are not real-time games, and the AI can have time to think about the best solution (Graepel)

1.4 Behaviour-Based Example

In their journal “Dynamic Game Difficulty Scaling Using Adaptive Behavior-Based AI”, Tan, Tan and Tay explore one of the ways to implement an adaptive AI system using a behaviour-based controller. In essence, they have created a system which gives the AI 7 different behaviours. These behaviours can then be activated or deactivated to change the skill level of the AI. A digital chromosome is used to store 7 real numbers from 0 to 1 which represent the probability of each behavior being activated. These values are then updated at run-time to keep the AI competitive but not too difficult. In Javascript, we could setup a chromosome quite simply with an object, this way you can even assign nice names to each value:

The idea here is that upon any win or lose state, the values within the chromosome are increased or decreased depending on if they were activated or deactivated during the round. Overtime, this process would allow the chromosome to adjust in favor of the behaviors that cause it to win. Because each behavior may be activated or deactivated for each round, a properly tuned algorithm will vary in skill around the threshold of the players ability (Tan, Tan and Tay, 290-293).

References

Laird, John; van Lent, Michael. “Machine Learning for Computer Games.” Game Developers Conference. Moscone Center West, San Francisco, CA. 10 Mar. 2005. Lecture.

Palmer, Nick. “Machine Learning in Games Development.” Machine Learning in Games Development. N.p., n.d. Web. 20 June 2014. <http://ai-depot.com/GameAI/Learning.html>.

Graepel, Thore. “Learning to Play: Machine Learning in Games.” . Microsoft Research Cambridge, n.d. Web. 20 June 2014. <http://www.admin.cam.ac.uk/offices/research/documents/local/events/downloads/tm/06_ThoreGraepel.pdf>.

Brownlee, Jason. “A Tour of Machine Learning Algorithms.” Machine Learning Mastery. N.p., 25 Nov. 2013. Web. 2 June 2014. <http://machinelearningmastery.com/a-tour-of-machine-learning-algorithms/>.

Hagelback, J.; Johansson, S.J., “Measuring player experience on runtime dynamic difficulty scaling in an RTS game,” Computational Intelligence and Games, 2009. CIG 2009. IEEE Symposium on , vol., no., pp.46,52, 7-10 Sept. 2009

Chin Hiong Tan; Kay Chen Tan; Tay, A., “Dynamic Game Difficulty Scaling Using Adaptive Behavior-Based AI,” Computational Intelligence and AI in Games, IEEE Transactions on , vol.3, no.4, pp.289,301, Dec. 2011

Tang, H.; Tan, C.H.; Tan, K.C.; Tay, A., “Neural network versus behavior based approach in simulated car racing game,” Evolving and Self-Developing Intelligent Systems, 2009. ESDIS ’09. IEEE Workshop on , vol., no., pp.58,65, March 30 2009-April 2 2009

In this post I will cover some basic machine learning definitions to help me understand things moving forward.

Problem Types

Classification

Here, the goal of the algorithm is to use information about a given item or data instance, and assign it a result or category (Laird, van Lent, 2005).

Clustering

Similar to classification, but the resulting categories are not pre-defined, and multiple data instances are used to define groups (Laird, van Lent, 2005).

Optimization

Modifying function input variables to find the highest or most optimal output result.

Algorithm Lingo

Decision Tree

A decision tree represents a process of classification through a mufti-step decision-making tree (SAS Institute).

Rules

With respect to machine learning, a rule is something that an system may define based on observations that defines how it should react to a given input.

Neural Network

Generally requires specific hardware. Neural networks learn by example rather than programming, by simulating a highly interconnected network similar to the human brain (Siganos , D and Stergiou, C).

Model

A model is a data set generated by the computer which is used to represent something. For example, a player model could be a set of variables that are set in order to represent the behaviours of a player.

References

Laird, John; van Lent, Michael. “Machine Learning for Computer Games.” Game Developers Conference. Moscone Center West, San Francisco, CA. 10 Mar. 2005. Lecture.

“Decision Trees— What Are They?.” . Statistical Analysis System Institute. Web. <http://support.sas.com/publishing/pubcat/chaps/57587.pdf>

Siganos , Dimitrios , and Stergiou, Christos . “Neural Networks.” Neural Networks. N.p., n.d. Web. 18 June 2014. <http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cs11/report.html>.