Article
files/lemmings

Alternatives to Online Learning for Actor Behaviors

Alex J. Champandard on July 19, 2007

Game behaviors that adapt to the player during the game (i.e. “online”) are a great thing. In fact, in a sense, they’re probably a requirement — otherwise your game is just a simulation. Adaptation makes the gameplay much more dynamic, and the levels more interesting for the player…

However, at the mention of the word “adaptation,” most developers think of machine learning (ML). Most games don’t use it; most games don’t need it. Yes, even the more advanced AI designs can be implemented without runtime learning.

Here are three complementary approaches, which actually work in practice…

1) Game Designers

“Most necessary adaptation in the behaviors is easily identified during development.”

The best games are very specifically designed in most aspects. Even the parts you consider emergent are identified by the designers, and improved iteratively. This is the case for gameplay, and the environment too. Designers create levels with multiple different approaches in mind for the player.

So in practice, there aren’t very many surprises;

  1. The development team knows exactly what kinds of situations occur in the game, what roles or style the player can take, etc.

  2. Designers can already create the different AI behaviors they require to support their ideas while in production.

In fact, there’s not much of a choice. It’s impossible to design the game well without building the AI supporting that gameplay. So the behaviors must be built offline.

2) Higher-Level Logic

With hard work, the designers can predict the majority of game situations and build behaviors for each of them. What’s left is putting them together at runtime…

To do this, it’s sufficient to have some simple logic that decide at runtime which static behaviors to select from. Adaptation comes from this higher-level logic; no learning is required here.

Generally speaking, learning is required if a behavior is missing, or if information is lacking. Designers can provide the first easily, but you need the game engine for the second…

3) Statistical Information

In the cases where behaviors must be personalized to the player (more so than just high-level logic), these fixed behaviors can be parameterized by data gathered about the player during the game.

Let’s call this indirect learning. The behaviors don’t change, but the raw data that supports them does change. So there’s no machine learning (ML) going on since no additional patterns are extracted from the raw data that’s available. It’s just a good use of statistics (though arguably, that defines machine learning :-).

Is Online Learning Useful?

These three tricks can help you make amazing adaptive AI with little hassle. Most games currently would benefit from machine learning during development, but there are few reasons to do it online.

Do you think online learning is a risky gimmick, or do you think it’s generally useful?

Discussion 13 Comments

togelius on July 19th, 2007

What an odd way of putting the question. The premise seems to be that on-line machine learning is bad and should be avoided. I suppose it makes sense if all you care about is meeting the next deadline, which is exactly why I prefer to be in academia rather than industry. With a slightly longer perspective, on-line machine learning is something to be embraced, as it can make completely new types of games possible.

togelius on July 19th, 2007

What an odd way of putting the question. The premise seems to be that on-line machine learning is bad and should be avoided. I suppose it makes sense if all you care about is meeting the next deadline, which is exactly why I prefer to be in academia rather than industry. With a slightly longer perspective, on-line machine learning is something to be embraced, as it can make completely new types of games possible.

gware on July 20th, 2007

From an industrial point of view, it is not that it should be avoided, it's more like in most cases we cannot afford it. Machine learning require computing power and memory. On consoles, hardware restrictions can be too strict for the game to use ML. Also, ML is not used not because of deadlines, but because of hardware restriction and, sometimes, because for testing reasons. If some behaviors, or any other aspects of the game, are emergents, then we may not be able to test the entire product and end up patching and patching and patching. I find the topic very interesting, but I totally agree with Alex when he says : "Most games currently would benefit from machine learning during development, but there are few reasons to do it online" Also, I think you are right when saying than "it can make completely new types of games possible". But everything isn't a deadline problems in this industry :)

gware on July 20th, 2007

From an industrial point of view, it is not that it should be avoided, it's more like in most cases we cannot afford it. Machine learning require computing power and memory. On consoles, hardware restrictions can be too strict for the game to use ML. Also, ML is not used not because of deadlines, but because of hardware restriction and, sometimes, because for testing reasons. If some behaviors, or any other aspects of the game, are emergents, then we may not be able to test the entire product and end up patching and patching and patching. I find the topic very interesting, but I totally agree with Alex when he says : "Most games currently would benefit from machine learning during development, but there are few reasons to do it online" Also, I think you are right when saying than "it can make completely new types of games possible". But everything isn't a deadline problems in this industry :)

alexjc on July 20th, 2007

Julian, thanks for the reply. Yes, the question was a bit sensationalist; I'm trying to get new readers to comment... :) But you detected the right undertone. I agree using ML (specifically during development) potentially allow news kinds of indy games, and better quality AAA ones when it's supervised by designers. Currently, online ML only works in very localized places only, like the statistical models used by Black and White. But there's no way better ML would fit into a games production environment; the publisher would never allow it or take the risk. Research into stronger ML is certainly worth doing, but I see it being used by small independent game studios rather than the traditional industry. Gabriel: I'm not even sure it's a computational problem either; even if you used the whole memory and 6 hardware threads on an XBox360, would there be an algorithm that does what you want it to? Alex

alexjc on July 20th, 2007

Julian, thanks for the reply. Yes, the question was a bit sensationalist; I'm trying to get new readers to comment... :) But you detected the right undertone. I agree using ML (specifically during development) potentially allow news kinds of indy games, and better quality AAA ones when it's supervised by designers. Currently, online ML only works in very localized places only, like the statistical models used by Black and White. But there's no way better ML would fit into a games production environment; the publisher would never allow it or take the risk. Research into stronger ML is certainly worth doing, but I see it being used by small independent game studios rather than the traditional industry. Gabriel: I'm not even sure it's a computational problem either; even if you used the whole memory and 6 hardware threads on an XBox360, would there be an algorithm that does what you want it to? Alex

gware on July 20th, 2007

Am not sure to understand the last question. But given the overall feeling that most game companies are struggling to get their game to fit in memory and at a decent framerate, I believe it is one of the first "cut" done. Machine learning as other requierements, not only it needs a bit of power and memory but, correct me if I am wrong, it would also need to load and store its data sets. And depending on the type of game and platform, it is a non trivial issue. I really think it's a fascinating topic, but I still do not see how it can be used by the whole industry. It's be interesting to see how this will evolve. Also, if anyone has "stories", papers, (or anything) about ML used during development (off-line) I would be interested.

gware on July 20th, 2007

Am not sure to understand the last question. But given the overall feeling that most game companies are struggling to get their game to fit in memory and at a decent framerate, I believe it is one of the first "cut" done. Machine learning as other requierements, not only it needs a bit of power and memory but, correct me if I am wrong, it would also need to load and store its data sets. And depending on the type of game and platform, it is a non trivial issue. I really think it's a fascinating topic, but I still do not see how it can be used by the whole industry. It's be interesting to see how this will evolve. Also, if anyone has "stories", papers, (or anything) about ML used during development (off-line) I would be interested.

togelius on July 23rd, 2007

I have hard time seeing the big problem with CPU cycles and memory consumption - just like any other aspect of a game (e.g. graphics) the learning algorithms have to be optimized and the trade-off between speed and power must be made so that the algorithm uses only what's available. E.g., it is perfectly possible to run an evolutionary algorithm on a Commodore 64 - it's just a matter of how you set various parameters and define the fitness function. Just as it was possible to do 3D graphics on that machine, if you didn't care that the world looked like Lego blocks. The issue of predictability is another thing. I agree that in many games we couldn't just thrown in learning algorithms, as we would risk unanticipated changes to the gameplay that destroyed the balance. But that is only because game designers design games based on the idea that they should be able to counter everything the player does - the game should never "be thrown off guard". Ultimately, we will never get truly open-ended gameplay this way. I've done some simple proof-of-concept experiments with a racing game that learns the player's driving style, and evolves new tracks that are supposed to be fun for this particular player. ( Read e.g. the paper at http://julian.togelius.com/Togelius2007Towards.pdf .) An integral feature of such a game, if a full game was ever developed, would be that the player and the game interact to come up with things the designer just could not have anticipated.

togelius on July 23rd, 2007

I have hard time seeing the big problem with CPU cycles and memory consumption - just like any other aspect of a game (e.g. graphics) the learning algorithms have to be optimized and the trade-off between speed and power must be made so that the algorithm uses only what's available. E.g., it is perfectly possible to run an evolutionary algorithm on a Commodore 64 - it's just a matter of how you set various parameters and define the fitness function. Just as it was possible to do 3D graphics on that machine, if you didn't care that the world looked like Lego blocks. The issue of predictability is another thing. I agree that in many games we couldn't just thrown in learning algorithms, as we would risk unanticipated changes to the gameplay that destroyed the balance. But that is only because game designers design games based on the idea that they should be able to counter everything the player does - the game should never "be thrown off guard". Ultimately, we will never get truly open-ended gameplay this way. I've done some simple proof-of-concept experiments with a racing game that learns the player's driving style, and evolves new tracks that are supposed to be fun for this particular player. ( Read e.g. the paper at http://julian.togelius.com/Togelius2007Towards.pdf .) An integral feature of such a game, if a full game was ever developed, would be that the player and the game interact to come up with things the designer just could not have anticipated.

alexjc on July 23rd, 2007

[B]Gabriel.[/B] My point was that we just don't have any general-purpose ML algorithms that can handle any problem, so regardless of computation power you'd have problems. As Julian mentioned, small problems are easy to solve using limited resources, but they require a lot of work by the AI programmer as a trade-off. [B]Julian,[/B] Would truly "open-ended gameplay" really be a game anymore? ;) Your research looks fascinating, I'm looking forward to reading more about it. To me, the big innovation here is that ML is used to expose a class of game styles rather than many specific instances. So the programmer anticipates the type of problem instead of the designer creating specific situations. I think this is a great use of ML, as it has very low risk and provides a definitive improvement in the gameplay. Given the right tools, I'm sure the designers could be involved too... (I'm sure they could easily predict the different styles of play and help design the ML :-) Alex

alexjc on July 23rd, 2007

[B]Gabriel.[/B] My point was that we just don't have any general-purpose ML algorithms that can handle any problem, so regardless of computation power you'd have problems. As Julian mentioned, small problems are easy to solve using limited resources, but they require a lot of work by the AI programmer as a trade-off. [B]Julian,[/B] Would truly "open-ended gameplay" really be a game anymore? ;) Your research looks fascinating, I'm looking forward to reading more about it. To me, the big innovation here is that ML is used to expose a class of game styles rather than many specific instances. So the programmer anticipates the type of problem instead of the designer creating specific situations. I think this is a great use of ML, as it has very low risk and provides a definitive improvement in the gameplay. Given the right tools, I'm sure the designers could be involved too... (I'm sure they could easily predict the different styles of play and help design the ML :-) Alex

Stardragon on April 25th, 2008

Alex, You said, 'Would truly “open-ended gameplay” really be a game anymore? ;)' I have to ask - did you ever play Elite, Frontier: Elite 2 or Frontier: First Encounters? With the slight exception of the latter, they were all about open-ended gameplay and were in my opinion among the most absorbing, challenging and addictive games of all time. The game in these cases, of course, wasn't so much about playing the computer as yourself. David Braben (I think) is on record as saying "it was all about what was going on inside your [the player's] head", or words to that effect. Which, taken alongside Julian's research, poses an interesting theoretical question: how can you outplay yourself? :)

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!