Quote: Original post by willh
I had no idea that this was a such a deep polarizing issue within the game AI community.

Interestingly, it is actually more of a deep polarizing issue within the academic community that is trying to "help" the game AI community. Things can get a little prickly at AIIDE.

Quote: One thing I think Kevin forgot to mention was CPU time. Usually a lot of things need to happen at once in order to make a great game look and feel even greater. Some ML stuff can eat precious cycles that may be better used elsewhere. Nobody would want a super complicated polynomial regression running behind Call of Duty slowing the game down, even if it did make the dogs way more difficult to kill.. (assuming an online ML model).

Funny that he didn't mention that. That's usually one of the first obstacles that is listed. However, thanks to Moore, that roadblock becomes less and less of an issue. One approach that people have taken is to simulate more things rather than simulating fewer things better. From a psychology standpoint, people will be more impressed by a city teeming with (simple) people rather than a mostly empty city with a sprinkling of compelling characters -- who you may or may not interact with.

The article remind me of my own final year project in CS where I tried tackling Reinforcement Learning. It was excited about all the possibilities. In the end the results were rather lack lustre. The problem I encountered was that the action domain space in the game was too small and rule set lacked enough depth to produce meaningful or interesting results.

I’ve since moved to using entity webs, rule sets, goal oriented action planning, and recently looking into sampling historic action data to generated future content.

ML just doesn’t seem to be a good fit as a core AI system. As too many of the tasks that AI needs to do can be done simpler, easier, and more effectively with other techniques. I think ML might come back again in future, but as an optimizing component of games to make them personalized to the player’s skill level and interests. Adjusting the weights so enemies remaining a consistently challenging, or adjusted item drops, and quests so that players get more of the content they want and less of what they don’t.

Quote: Original post by willh
This is more likely due to poor design than a failure of a particular ML approach. Using the driving example; why use one ML monolith to solve for all at once like the article suggests? It would be more effective (and realistic) to build one for gas, one for break, and one for steering, and one to alter the input used for the gas/break and steering-- I'm generalizing, but this is often how these sorts of things are applied in non-game environments.

Driving games are actually one excellent counterexample where machine learning works well (and has been used in commercial games). I think the reason for that has a lot to do with the fact that they don't have a lot of the problems I mention. Machine learning is known to work well (it's been used on real world robot cars with significant success, and that's a *much* harder problem), the features and outputs are fairly constrained and well understood (again, lots of research on this from the real world), it's not too hard to gather data, and at the end of the day the task is really pretty simple. I suspect that a FPS AI is marginally doable, but harder, an RTS AI is epically hard, and a compelling RPG character is far enough beyond the abilities of current technology to be essentially impossible.

With that said, I think that even the FPS AI is probably easier and safer to do by hand (you'll get better results with less effort). So far, nobody has proven me wrong (and a lot of smart people have tried). :)

Quote: Original post by willh
I agree that data volume is a real issue IF you need lots and lots of samples. This has a been a problem facing every discipline. Due to the growth of the Internet many problems are just now getting the attention they deserve. 15 years ago it would have been very hard (labour intensive) to collect a good database of car images. These days there is an abudance of data (or at least the capacity to collect it) and I think this is one area where the game AI of the future might start to sow its seeds.

The problem is, you can't just go on the internet and get data. You can't get data from a different game, or even the prequel to this game. For most learning problems, the data needs to be from the actual game in its final form. Otherwise, garbage in, garbage out. If you learn on a different game, you will learn the wrong set of behaviors.

Even driving games probably follow this. To some extent because they're learning the particular phsyics engine and the idiosynchracies of that implementation of the cars, and to some extent because they're learning the tracks.

Quote: Original post by willh
For example, Kevin mentions defining 'fun'. I agree that it's a pretty tough thing to define. But what if we wanted to determine a players frustration level to automatically adjust game difficulty (I may not know what fun is, but I do know what it isn't). Maybe EA could start analyzing (anonymously of course) play from online matches, annotating said matches, and then build a model of 'angry' player. I don't really know because I've never really given it much thought, but I do know that similar problems outside of games have been solved (to varying degrees of success).

Dynamic difficulty adjustment is getting a lot of attention from academia (and has been for at least a decade now). So far, nobody has cracked it. With that said, I'm not convinced that this is really the win that we think it will be. Wing Commander 2 had something like this, where the difficulty of the next mission depended on how banged up you were during the previous one. To a first order, (a) you don't want the player to feel like you are condescending to them by making it easier because they "can't handle it," and (b) you don't want them to have to game the learning system in order to succeed. For instance, in Wing Commander, if a mission was too hard, I would go back and re-fly the previous one, intentionally taking as much damage as possible. Not a win.

Again, there is a simple difficulty mechanism that already exists. Players can choose what setting to play a game on. It seems to me that simply giving them the choice is the best way to adjust difficulty.

Quote: Original post by willh
As far as not being any easier; Well, if your point is to save effort and cut costs then I recommend not starting at anything at all. (I'm being sarcastic). If your goal is to make more interesting games then applying ML to new problems might be worth investigating. Going one step further we should all agree that building 3D games is a lot more labour intensive than 2D tile based side scrollers... The production value of games these days is simply amazing! The QA alone is staggering when compared to what happened in the 80s. :) Definately not any easier though. So I can't say I agree with Kevins conclusion..

I think you're missing the point here. The point isn't that it's too hard, and so we should all cry to mommy. :) The point is that if machine learning takes more effort and produces worse results, then there's no point in using it. The whole argument for ML is that it saves effort. If it doesn't do that, why bother?

Quote: Original post by willh
Lots of not-done-before's have happened in front of our very eyes. For me that's not a very convincing argument against something. :) I like to be optimistic though.

The real point here is that a lot of smart people have worked on this, and failed to crack it. Unless you have some unique insight that isn't just "try this obvious and straightforward technique," or you specifically want to take this challenge on because you think it's an interesting hard problem (and not because you want to make games for a living), you're probably better off sticking with traditional methods.

The CPU time point is a really good one. Nice catch. :) I was mostly thinking of offline learning as I wrote it, but even there it can be an issue - and for online learning, obviously even more so.

Quote: Original post by TechnoGoth
The article remind me of my own final year project in CS where I tried tackling Reinforcement Learning. It was excited about all the possibilities. In the end the results were rather lack lustre.

Your story isn't at all uncommon and I think part of my reason for sticking with this stuff is that I got really lucky the first time. :)

Back in the 90's I was working on a video surveillance project for a small software company. For kicks I decided to try using Evolutionary Programming to build a classifier that would determine if a change between frames was caused by a human or not. I spent a few weeks pouring over archived video (in the 90s!!!!!) and building a data set of human and non-human signals. I built a simple enviornment to generate a classifier, let it run for a few days, and as if by magic the darn thing was correctly classifying close to 80% of non-human events correctly. It meant that human operators got 80% fewer false alarms because of things like car headlights and trees blowing in the wind (which had all sorts of positive implications).

A good friend of mine had also been experimenting with this sort of thing in an academic environment. He was a very sharp guy (and knew it), so when the results of his experiments were less than stellar he put ML/AI in to 'wishful thinking' category. Who could blame him?

When I tried to demonstrate the 'power' of these techniques for my friend, using a toy problem, I failed miserably. Needless to say he wasn't all that impressed. I knew that something had to have worked from my past success so I kept at it-- otherwise I problably would have abandoned it too.

Quote: Original post by TechnoGoth
The article remind me of my own final year project in CS where I tried tackling Reinforcement Learning. It was excited about all the possibilities. In the end the results were rather lack lustre. The problem I encountered was that the action domain space in the game was too small and rule set lacked enough depth to produce meaningful or interesting results.

I’ve since moved to using entity webs, rule sets, goal oriented action planning, and recently looking into sampling historic action data to generated future content.

ML just doesn’t seem to be a good fit as a core AI system. As too many of the tasks that AI needs to do can be done simpler, easier, and more effectively with other techniques. I think ML might come back again in future, but as an optimizing component of games to make them personalized to the player’s skill level and interests. Adjusting the weights so enemies remaining a consistently challenging, or adjusted item drops, and quests so that players get more of the content they want and less of what they don’t.

Wasn't some version of a learning algorithm used in Virtua Fighter 3 for the PS2?

I don't know if you'd call it ML, but fighting games often use pattern matching where they look at your last several actions, and predict your next action on that basis. It turns out that simply doing that on your blocks and strikes can generate a nearly unbeatable AI, so the next step is to make it intentionally screw up.

Thanks for the response Kevin. I agree with almost everything you're saying, so this post might be kind of boring to someone looking for a good debate. :) I'll try to add something towards the end to spurr some discussion, but feel free to pass if it's old covered ground for you.

DISCLAIMER TO READERS: The following is meant to reflect a difference of opinion only. If you are easily offended by a difference of opinion please stop reading this post.

Quote: Original post by Kevin Dill
With that said, I think that even the FPS AI is probably easier and safer to do by hand (you'll get better results with less effort). So far, nobody has proven me wrong (and a lot of smart people have tried). :)

I couldn't agree more. Like you say, it's an interesting ML problem for someone doing research, but probably not worth the time (or complexity) to put in to practice commercially.

For an RTS though (or a command-and-control thing) it might make more sense.. which kind of ties in to the next point.

Quote: Original post by Kevin Dill
The problem is, you can't just go on the internet and get data. You can't get data from a different game, or even the prequel to this game.

I hope my previous post didn't imply that I thought data collection to be easy. I was trying to make the point that data availability is something everyone has struggled with, and that it is problem #1 for any ML project.

I do have to wonder if some of the RTS games, with all of their online matches, might not be able to make use of that data to build an uber-AI. I've watched a few videos where players have totally smashed the hardest AI in StarCraft on their first attempt. Maybe I'm nostalgic for the days when 'beating the machine' was a serious accomplishment, but I can't help but think that it would be really cool to have a machine opponent that could earn someone serious 'street-cred' if they beat it.

As far as reusability goes, once you have a framework for a type of problem, not everything needs to be rebuilt from scratch. I've built a tool which works on different types of data for different classification tasks. Each time I use it I have to invest a few days in to collecting and 'normalizing' data so that its in a format the program can use. Once that part is done though, it's often business as usual-- if not the changes are usually minor.

I also keep what I call 'generic not' data. The 'generic not' gets reused for many of the projects I undertake with this program. I also keep annoted data sets. These are data sets that have been marked, by hand, to identify various things. Some of this can be reused.

Quote: Original post by Kevin Dill
The whole argument for ML is that it saves effort. If it doesn't do that, why bother?

We disagree on the reason for ML. I use ML techniques to solve problems that I am unable to solve using my own facilities of reason. Take face detection: what lines of code are required to tell that something is a face? The answer (for me and the entire digitial camera industry) was to let a machine figure it out.

Modeling player behavior in MMORPGs so they can 'persist' even when offline, Dynamic difficulty adjustment, or just more interesting NPCs would all be great and I think an ML approach could contribute to those goals. But I'm not the one whose under a deadline, with a fixed budget, who needs to make _something_ happen in the context of a broader production.

I'm sensitive to the fact that game development is a business enterprise. From what you've seen so far, do you think it's possible that some of the 'pro-ML' arguments might not be keeping the cost/effort factor in mind?

The following is my attempt at spurring debate

If I wanted to make a strong case for ML versus the traditional (in the interest of debate), I think it would hing on ML being the inevitable future. I wouldn't say state tables will ever go away, but I can see them becoming a way of tweaking the broader ML agent for various situations.

Look at Microsofts project Natal for example. Many years of research have gone in to pose estimation, 3D reconstruction, speech recognition, face detection, etc.. None of these things happened over night and nobody would have dared bet the bank on them 10 years ago. All of these things are based on ML techniques, or are at least heavily dependant on statistics and linear algerbra.

Sooner or later someone will make an RTS AI framework based on ML. WalMarts problem of knowing when and how to move stock between stores isn't that much different than managing units in an RTS. There are too many similar areas of research going on in the real world for there not to be a crossover eventually.

I would be really interested to hear from someone who has legitimate and grounded reasons for disagreeing with you in the present sense though.

Quote: Original post by willhFor kicks I decided to try using Evolutionary Programming to build a classifier that would determine if a change between frames was caused by a human or not.

I have to wonder what application this would have in games, however.

Quote: Original post by willh

Quote: Original post by Kevin DillThe problem is, you can't just go on the internet and get data. You can't get data from a different game, or even the prequel to this game.

I hope my previous post didn't imply that I thought data collection to be easy. I was trying to make the point that data availability is something everyone has struggled with, and that it is problem #1 for any ML project.

The problem is not one of data availability, it is one of matching the data you can collect to the world model that your game uses. As AI developers, we are inherently tied to whatever data model that underlies our game. Knowledge representation is the next layer on top of that and is necessary simply an abstraction of what that data model is.

Even lifting behavior from one game to another is a difficult proposition unless the games are almost identical -- not in the way the game is played, but in the way it is represented. For example, SC2 and Company of Heroes are essentially the same type of game (RTS). You collect things so you can build things so you can train things so you can group things so you can attack things. However, the underlying structure between how Relic did things and how Blizzard does is (likely) wildly dissimilar.

Chris Jurney has given a number of lectures at GDC and AIIDE about the difficulty that Relic encountered in going from CoH to Dawn of War 2. For example, Company of Heroes didn't include melee combat (guns) whereas DoW2 did. That single change alone caused them to have to retool a bunch of their AI. There were whole new data structures that had to be put into place and new reasoners designed to use them based solely on that one change.

That being said, the advantage in the above example is still there in that you are going from code to code. With trying to mine information off the internet, live video, etc., you still have the problem of capturing only the relevant behavior in such a way that it matches how you are representing it in data.

Quote: Original post by willhI do have to wonder if some of the RTS games, with all of their online matches, might not be able to make use of that data to build an uber-AI. I've watched a few videos where players have totally smashed the hardest AI in StarCraft on their first attempt.

One of the advantages that a person has in that battle is adaptability. ML techniques, by their very nature, are good at finding "a solution set". Once that happens, the human can read and adapt to it. Additionally, if you were to feed in a bunch of data from online matches (assuming that we don't have the data issue stated above), what will tend to happen is that an uber-hybrid strategy will fall out. That is, it will be an average of all the inputs.

Much of the success in RTS games is through use of context-dependent strictly dominant strategies. While a mixed strategy will work in a general sense, it is vulnerable to being overwhelmed by the edge case strategies. For example, if you were to go 1/3 anti-A, 1/3 anti-B, and 1/3 anti-C, you are seemingly protecting yourself from A, B, and C. However, if the other player goes 100% A, they will overwhelm you. It is this "read and react" flexibility that needs to be built into a system. This necessitates a decision engine that is more rule-based expert system. The moment you start hand-authoring these rules, though, you have stepped away from a ML approach.

Quote: As far as reusability goes, once you have a framework for a type of problem, not everything needs to be rebuilt from scratch. I've built a tool which works on different types of data for different classification tasks. Each time I use it I have to invest a few days in to collecting and 'normalizing' data so that its in a format the program can use. Once that part is done though, it's often business as usual-- if not the changes are usually minor.

This is on the right track and is almost straight out of the co-lecture that Kevin and I did at last year's GDC AI Summit. In fact, I believe we are going to have a session on modular code reuse again this year. However, this can be done with non-ML techniques as well (which is what Kevin and I were discussing).

Quote: Original post by willh
We disagree on the reason for ML. I use ML techniques to solve problems that I am unable to solve using my own facilities of reason. Take face detection: what lines of code are required to tell that something is a face? The answer (for me and the entire digitial camera industry) was to let a machine figure it out.

Nifty, I admit, but not really relevant to game AI, however.

Quote: Modeling player behavior in MMORPGs so they can 'persist' even when offline

But you can do much of this simply by tweaking knobs in reinforcement learning a la the Creature in Black & White. If you keep it out of the black box, you can also allow the player to do this by hand or by selecting preset combinations of data.

Quote: Original post by willhLook at Microsofts project Natal for example. Many years of research have gone in to pose estimation, 3D reconstruction, speech recognition, face detection, etc..

But not really applicable to constructing artificial behavior.

Quote: Sooner or later someone will make an RTS AI framework based on ML. WalMarts problem of knowing when and how to move stock between stores isn't that much different than managing units in an RTS. There are too many similar areas of research going on in the real world for there not to be a crossover eventually.

This actually speaks to my point earlier. the WalMart problem is an NP-Hard optimization problem that has a "right answer". RTS games played against humans don't really have a "right answer".

Is ML in a broad sense worth looking into to assist in construction and manipulation of other AI techniques? Sure. Is it ever going to replace those techniques? Who knows? Will it happen anytime soon? Not likely.

Quote: Original post by InnocuousFox
I have to wonder what application this would have in games, however.

I'll take that as a legitimate question... and the legitimate answer is 'that it's not always straightforward the first time'.

Was topical, given the original comment about the chaps CS class and reinforcement learning (not exactly game specific).

Quote: Original post by InnocuousFox
The problem is not one of data availability, it is one of matching the data you can collect to the world model that your game uses. As AI developers, we are inherently tied to whatever data model that underlies our game.

It sounds like you're describing a data portability issue. If I'm reading that right then I can only say that everyone has it, be you a web browser company or Lexus-Nexxus. I'm not sure how that is restricted to Game development. Doesn't seem insurmountable. Effort, yes. Cost, yes. Worth it? I don't know-- I'm not the person putting up the cash. :)

Many game companies already have a _similar_ problem with their QA processes. How do you go from controller & screen to describing a bug in a reproduceable way for a developer?

Quote: Original post by InnocuousFox
With trying to mine information off the internet, live video, etc., you still have the problem of capturing only the relevant behavior in such a way that it matches how you are representing it in data.

It's a lot of work to be sure. Once you have the data, then annotated the data, making it portable isn't usually the labor intensive part.

I wouldn't consider this an insurmountable issue for a company that is willing to spend money/time/resources doing motion capture or other forms of data collection.

Quote: Original post by InnocuousFox
Additionally, if you were to feed in a bunch of data from online matches (assuming that we don't have the data issue stated above), what will tend to happen is that an uber-hybrid strategy will fall out. That is, it will be an average of all the inputs.

What leads you to believe that you'll get an 'average'? I can think of plenty of ML techniques that do not result in an 'average of all inputs'.

Quote: Original post by InnocuousFox
However, this can be done with non-ML techniques as well (which is what Kevin and I were discussing).

Good programming and design skills are often transferable. I don't consider this a negative.

Quote: Original post by InnocuousFox

Quote: Original post by willh
We disagree on the reason for ML. I use ML techniques to solve problems that I am unable to solve using my own facilities of reason.

Nifty, I admit, but not really relevant to game AI, however.

Dave, if you're not going to contribute something constructive then please refrain from commenting. Thank you.

Quote: Original post by InnocuousFox

Quote: Modeling player behavior in MMORPGs so they can 'persist' even when offline

But you can do much of this simply by tweaking knobs in reinforcement learning a la the Creature in Black & White. If you keep it out of the black box, you can also allow the player to do this by hand or by selecting preset combinations of data.

Perhaps, but what I've seen so far is something that is a poor and unbelievable approximation at best. I don't see how one would call that 'problem solved' by any measure. The last time I played an MMORPG I did not have the option of 'persisting' in a realistic way. EDIT: And my boxer in Fight Night for the PS3 does NOT play anything like me when the computer controls it, despite the few controls I have to tweak.

Quote: Original post by InnocuousFox

Quote: Original post by willh
WalMarts problem of knowing when and how to move stock between stores isn't that much different than managing units in an RTS.

This actually speaks to my point earlier. the WalMart problem is an NP-Hard optimization problem that has a "right answer". RTS games played against humans don't really have a "right answer".

I don't understand the reasoning behind your argument.

Are you suggesting that the real world, with its weather, traffic, currency exchange rates, variable fuel rates, and shifting regional/national purchasing trends is somehow more predictable/easier than an RTS? If you've got that solved then you're wasting your time on games and should be dealing with commodity trading. There might even be a nice job opening for you on Wall Street (or within WalMart!). ;)