Jump to content

  • Log In with Google      Sign In   
  • Create Account

Machine Learning with Multiplayer games


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
25 replies to this topic

#1 Schwartz86   Members   -  Reputation: 102

Like
0Likes
Like

Posted 09 March 2011 - 11:49 AM

Hello GDNet Community,

I am software engineer and I have become quite interested in learning more about artificial intelligence and machine learning. My interest was initially in the domain of robotics, however, I am currently interested in how machine learning might be applied to multiplayer/online games. Is anyone aware of any research that uses machine learning techniques to create 'smarter' enemies. For example, take 3D FPS like Halo. It seems that games could benefit by 'watching' players when they compete online. If it is possible to identify patterns over several iterations that lead to a winning strategy (i.e. 60% of the time the winner of the match is invisible and has a rocket launcher for 70% of the match duration) perhaps the 'game' could take note of this and attempt to derive new strategies when a player competes against the computer rather than a human.

This could offer several advantages:
- Gameplay could change overtime. The more you play, the smarter the opponent gets
- Computer AI could possibly begin to mimic that of human players and thus even when you aren't playing 'real' opponents, the gameplay will feel the same.
- If this strategy could be successfully implemented, it could allow for a completely new gaming scenario. I am imagining players conducting 'bot' wars where each player would pit there 'trained' bot against another's. Theoretically, the player with the most experience would have the 'better trained' bot.

There would clearly be some disadvantages as well...
- Takes control away from game designers. Who knows what the AI would do!
- Player could get frustrated by 'dumb' opponent while the game attempts to learn and possibly deploy ridiculous strategies based incorrectly using recognized patterns through previous game play

I realize this may only be a pipe dream and I know there are a large number of issues with what I proposed above (also with machine learning in general). However, I am only looking for more information about what machine learning techniques have been used in games (if any) and trying to figure out to what depth this topic has been explored.

Thanks!
Chris

Sponsor:

#2 IADaveMark   Moderators   -  Reputation: 2474

Like
0Likes
Like

Posted 09 March 2011 - 07:56 PM

Is anyone aware of any research that uses machine learning techniques to create 'smarter' enemies.

There are literally dozens on academic and independent AI researchers working on this. There are likely hundreds of papers that have been written on it over the past 10 years. So, yes. We are aware of research.

The bottom line is that it is not all its cracked up to be. You can do far better with hand-crafted rules with tunable parameters.



Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#3 xEricx   Members   -  Reputation: 564

Like
0Likes
Like

Posted 10 March 2011 - 10:49 AM

You can do far better with hand-crafted rules with tunable parameters.


Exactly... and most Game Designers, as you stated, want to keep control over the NPCs so for most "professional" games, it's not an option.

As for your point about "dumb opponents", keep in mind that most studios would let QA play with the game for a while, and package with the game whatever data came from this learning phase, so they would probably start off as quite good opponents.

It's just too risky to rely on learning for a production that costs millions...

#4 ApochPiQ   Moderators   -  Reputation: 15736

Like
2Likes
Like

Posted 10 March 2011 - 11:02 PM

Strategic-level AI in a game like Halo is trivial: get the biggest gun, sit in the hottest kill spots, troll the spawn points.

Every high-level human player will act like this, and every decent bot will follow roughly the same pattern. Maybe dependent on game rules there might be some variations, but that's not the hard part at all.


Coming up with an intelligent way to play the game is pretty easy. What gets messy is when you need to actually act on the high-level strategy and come up with good behaviour for your agents. Suppose you play a 4v4 Halo game of Capture the Flag. Pick a basic strategy (a common one I see online is the 4-man rush, another is the divide-and-conquer) and go for it.

Now... deal with the situation where the enemy gets the rocket launcher before you do.

Deal with the situation where one of your allies lags out and you have to pick up the slack.

Deal with the fact that some players will react realistically to cover fire (i.e. hide) and others will react in true Rambo fashion (i.e. pop out guns blazing).

Deal with the fact that most players, especially under pressure, are far from rational, and may do highly irrational things (especially risky things) to gain a win.

Deal with the emotional pressure of being close to losing and bringing the game back from the edge of defeat.

Deal with the psychology of demeaning and dominating your enemy to make your victory all the more certain.



These are all things that good human players can cope with more or less instinctively; how do you codify them for a bot? Until we have "intelligence" on that level, no bot will ever pass the Halo Turing Test.


Good bot AI is not about coming up with strategies or even tactics. Well-known battlefield tactics are killer in an FPS, as any good team players can tell you; get 4 guys who know how to roam as a pack and assault fixed positions correctly, and they'll tear up Halo all day long. Code that into a bot and you end up with a virtually unbeatable opponent.

Bots don't have to compensate for perception delays.

Bots don't have to compensate for shaky trigger fingers.

Bots don't have to deal with feeling angry or depressed when they're losing.

Bots don't have to sacrifice vital time to make crucial decisions; they can do it almost instantaneously.


A good bot can slaughter human players all day. And they aren't that hard to write - I watched a friend of mine write a virtually unkillable bot AI for one of his school projects a couple of years ago, and he's far from an AI expert. He just put in place some basic rules (aim for the head, pace shots to mitigate recoil, etc.) based on his own experience in shooters. Those damn bots could mop the floor with us time and again, even though their pathfinding was crap and they tended to bunch up a lot (rocket fodder syndrome).


I'll steal a phrase from another AI colleague here (B. Schwab, respect if you're in the audience) - good AI isn't about winning. It's about losing with style.

Make a bot that can beat a human? No sweat.

Make a bot that can challenge a human, without causing excess frustration, and still provide a good, balanced experience to a very wide variety of players and skill levels?



Sweat.


Sweat very hard.

#5 Schwartz86   Members   -  Reputation: 102

Like
0Likes
Like

Posted 11 March 2011 - 01:27 PM

Strategic-level AI in a game like Halo is trivial: get the biggest gun, sit in the hottest kill spots, troll the spawn points.


Yea, although I used that example in my original post, I was thinking more of strategy games where AI becomes more difficult and harder to create 'unique' player experiences. In most strategy games, after I figure out how to beat the automated opponent once, I can do it every time and the game quickly gets less exciting. It seems a lot of games, rather than create 'smarter' opponents as the difficulty is increased, simply allow the automated opponent to cheat or give them higher statistical advantages. For me, this is irritating and once I realize that the game is just 'cheating' to make it more challenging, I quickly lose interest.

I realize there are a lot of problems with machine learning and that in most cases, especially in games-- where the state of the world is entirely known in advance-- its easier/better to just program the agent. I was just interested in seeing if there had been any successful attempts in using this technique.

#6 IADaveMark   Moderators   -  Reputation: 2474

Like
0Likes
Like

Posted 11 March 2011 - 04:50 PM

The only reason that you can beat opponents on replays is because they let you. They specifically make stuff non-dynamic as a design decision. It is easy to make a widely varied, adaptive AI with the techniques already mentioned. In fact, your "learned AI" would actually tend to stagnate towards a vanilla solution rather than a creative one.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#7 ApochPiQ   Moderators   -  Reputation: 15736

Like
2Likes
Like

Posted 11 March 2011 - 06:20 PM

To elaborate on the above, machine learning systems are good at finding local optima of a solution space, but not necessarily optima of the interesting solutions.

In other words, a learning system will quickly figure out how to mop the floor with you, and then just do that. Over and over. A machine will always have better reactions, better micro-management, better timing; even with the exact same resources and units in a strategy game (say, Starcraft II) the AI can always win, because it does not have human limitations and fallibilities.

So the AI will learn how to kill you, and then never do anything else. If it's designed to win - if that is the fitness criteria for how it is taught - then it will win, period. It won't play an interesting, creative game; it'll find that local optimum and just hammer on it until you give up in disgust.


To reiterate what I posted earlier, the challenge of game AI is not about winning - it's about losing in a way that feels like the AI was trying to win but was bested by the player. That's a much thornier problem overall. And since "interesting gameplay" is not quantifiable, we can't (yet) teach a machine to do it using standard machine learning algorithms, because we have no way to tell the machine how good it is doing at being interesting.

Therefore, human-designed and tuned behaviours remain the best tool we have available for that particular job.

#8 EJH   Members   -  Reputation: 314

Like
0Likes
Like

Posted 14 March 2011 - 08:32 AM

- If this strategy could be successfully implemented, it could allow for a completely new gaming scenario. I am imagining players conducting 'bot' wars where each player would pit there 'trained' bot against another's. Theoretically, the player with the most experience would have the 'better trained' bot.


There's a game like that called NERO: http://nerogame.org/

There's should be links to the papers about it with references on that site.

#9 EJH   Members   -  Reputation: 314

Like
0Likes
Like

Posted 14 March 2011 - 08:47 AM

I'll steal a phrase from another AI colleague here (B. Schwab, respect if you're in the audience) - good AI isn't about winning. It's about losing with style.

Make a bot that can beat a human? No sweat.


I'd add multiple caveats to that - "depending on game genre" and "easy to make a bot that can beat humans that are unskilled to average at the game".

Look how much it took for a bot to beat the best Chess players in the world. You are saying that was "easy"? Now consider Starcraft 2 or any other RTS. They are much more complex than Chess.

Blizzard cannot make a non-cheating AI that can give any Diamond league+ player a challenge. Same goes for every other company that makes RTS or turn-based strategy (GalCiv for example). So clearly, coding a bot (that doesn't cheat) for a deep strategy game that can beat expert level humans is far from easy.

#10 IADaveMark   Moderators   -  Reputation: 2474

Like
0Likes
Like

Posted 14 March 2011 - 11:07 AM

The idea of "cheating AI" vs. "non-cheating AI" is silly. Until we are modeling computer vision to look at screens and robotic hands to move mouse and keyboard, we are making a "cheating AI".
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#11 ApochPiQ   Moderators   -  Reputation: 15736

Like
2Likes
Like

Posted 14 March 2011 - 08:05 PM

Look how much it took for a bot to beat the best Chess players in the world. You are saying that was "easy"?


Yes.

Algorithmically, solving chess is fairly simple. It's just a matter of throwing enough horsepower at it. Deep Blue was not impressive in its chess prowess nearly as much as it was impressive in its computing power. The same can be said of Watson on Jeopardy.

The real strides in chess AI have not come from solving the game (which isn't hard, just requires tremendous resources) but rather in heuristics which make solving the game fast much more practical.


I would argue that it's pretty easy to make an AI that can out-micro a human all day long, and as any good RTS player can tell you, you can throw two groups of otherwise-equivalent units together and the player with the better micro will win. Throw in strategy-level optimizations (things like being able to "click" infinitely fast to produce multiple units in a single frame vs. the human limitations of moving the mouse, etc.) and the AI can outplay a human easily.

The trick is, as you say, in not blatantly exploiting the inherent superiority of the computer in such matters. The trick, as I said, is to strike the balance between making use of computer power and making use of limited-scope fallibilities that can permit the AI to lose gracefully and in a way which is stimulating to the player.


I strongly challenge anyone with real, shipped game AI experience to disagree with this. Even in highly probabilistic "luck-based" games, computer analysis and resistance to "false trends" in randomness can beat out a human player with ease. It isn't that the game is hard to solve perfectly, it's that it's hard to solve imperfectly.



I'll leave you with an example from my own work - from earlier today, in fact.

I have a group of AI bots designed to perform dogfights in a 6DOF environment. Against the player, they are decently competent; odds of more than 2 or 3 to 1 player are almost always fatal. Against each other, they produce very visually interesting fights, but actually take forever (sometimes literally several hours) to score kills on each other. Why? They're too damn smart. The AI can evade almost any incoming attack and do so with such efficiency that the attackers have a very hard time landing hits on the defenders. Writing the AI to be that smart was easy, and, contrary to what you might expect, involves zero cheating - there is no prediction of what other agents will do, no sharing of information, nothing. What the AI agents do is entirely self-contained and could easily represent the thought process of a skilled human.

My challenge in this project has nothing to do with making an AI that's better than me. That's already done.

My challenge is in making an AI that can lose and still look like it put up a good fight.

#12 willh   Members   -  Reputation: 160

Like
1Likes
Like

Posted 15 March 2011 - 08:31 AM

Algorithmically, solving chess is fairly simple. It's just a matter of throwing enough horsepower at it. Deep Blue was not impressive in its chess prowess nearly as much as it was impressive in its computing power. The same can be said of Watson on Jeopardy.


I do not agree. Watson (Deep QA) is a very different beast and is not just a game tree. Watson is more 'AI' than Deep Blue.


There are, as far as a I know, no equivilants to WATSON available on the desktop running at a much slower speed.

#13 EJH   Members   -  Reputation: 314

Like
0Likes
Like

Posted 16 March 2011 - 12:08 PM


Look how much it took for a bot to beat the best Chess players in the world. You are saying that was "easy"?

Algorithmically, solving chess is fairly simple. It's just a matter of throwing enough horsepower at it. Deep Blue was not impressive in its chess prowess nearly as much as it was impressive in its computing power. The same can be said of Watson on Jeopardy.

I'll leave you with an example from my own work - from earlier today, in fact.


Cannot tell if serious ... IBM's Watson, which parses conversational English riddles and solves them in real-time is "easy", but making your dog-fighting planes avoid bullets a little bit less often is an example of "complex" AI? Really?

Go is a pretty simple game is it not? Explain why nobody on the planet can make a Go Bot that gives even a mediocre Go player a run for their money.

#14 IADaveMark   Moderators   -  Reputation: 2474

Like
2Likes
Like

Posted 16 March 2011 - 02:00 PM

Go is a pretty simple game is it not? Explain why nobody on the planet can make a Go Bot that gives even a mediocre Go player a run for their money.

Same reason as chess. You could do a game tree search, but the branching factor is ridiculous. It is solvable, but it would take too long.

And after millions of years, all you would get is "42".



Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#15 ApochPiQ   Moderators   -  Reputation: 15736

Like
1Likes
Like

Posted 16 March 2011 - 05:22 PM

Cannot tell if serious ... IBM's Watson, which parses conversational English riddles and solves them in real-time is "easy", but making your dog-fighting planes avoid bullets a little bit less often is an example of "complex" AI? Really?

Go is a pretty simple game is it not? Explain why nobody on the planet can make a Go Bot that gives even a mediocre Go player a run for their money.


*sigh*


I said Watson is similar to Deep Blue in that the actual solving methods pale in comparison to the computing power harnessed in running those algorithms. I can play chess against a damn-near-unbeatable AI on my phone, but I cannot play Jeopardy against a damn-near-unbeatable, Watson-level AI on any hardware that I personally have access to.

Just as Deep Blue was impressive predominantly in its horsepower, and not its particular cleverness in chess algorithms, many problems (akin to the one tackled by Watson) become tractable only first by virtue of having huge resources, and second (and often peripherally) by virtue of having elegant solutions.


Nowhere did I say nor imply that solving chess intelligently is easy - just that a brute force solution is known to exist, and works pretty well even with fairly limited heuristics to help speed it up. I also did not say that Watson's job is easy. If it were, there's no need for all the computer energy that went into solving each question on the show. I just said that the impressive part is the power, not the cleverness or depth of the algorithms involved.

Throw enough horsepower at it, and NP-complete problems become (sort of) tractable too. Doesn't mean we know a good way to solve them.

#16 krokko   Members   -  Reputation: 130

Like
0Likes
Like

Posted 16 March 2011 - 06:21 PM

To elaborate on the above, machine learning systems are good at finding local optima of a solution space, but not necessarily optima of the interesting solutions.

In other words, a learning system will quickly figure out how to mop the floor with you, and then just do that. Over and over. A machine will always have better reactions, better micro-management, better timing; even with the exact same resources and units in a strategy game (say, Starcraft II) the AI can always win, because it does not have human limitations and fallibilities.

So the AI will learn how to kill you, and then never do anything else. If it's designed to win - if that is the fitness criteria for how it is taught - then it will win, period. It won't play an interesting, creative game; it'll find that local optimum and just hammer on it until you give up in disgust.

You mention StarCraft and in the case of that game I think you're wrong. RTSes are limited information games, just like poker; you have to make a lot of decisions very quickly based on little information. Mindgames are extremely important on a high level where the players can no longer distinguish themselves with better mechanics. If you made an AI that could execute a strategy perfectly, then at least in SC:BW that wouldn't be enough to beat a pro player, because unit control only matters when the players are otherwise equal. If you let a human do the decision making and an AI the actual playing, then that pair would win, but a human could outplay an AI simply with decision making.

Here's an article on some AI research in SC:BW:
http://arstechnica.com/gaming/news/2011/01/skynet-meets-the-swarm-how-the-berkeley-overmind-won-the-2010-starcraft-ai-competition.ars

#17 ApochPiQ   Moderators   -  Reputation: 15736

Like
0Likes
Like

Posted 16 March 2011 - 08:11 PM

I'm prepared to be wrong, but I'm not yet convinced. Give me a scenario where a human decision can outplay a perfectly operated AI.

#18 ImmoralAtheist   Members   -  Reputation: 118

Like
0Likes
Like

Posted 17 March 2011 - 07:26 AM

Using machine learning to learn strategies can be quite advanced.
However strategy games typically have several ai types (aggressive, rusher, economist, turtler etc.). We assume that these types, function in a rock paper scissor way, and that the player's strategy can be classified as either of these. The AI will gather information about you, and use a point based system to make a prediction on what playstyle you use. The more points in a strategy, the more likely the ai is to pick a counter to that. Over several matches the game could save statistics, and determine wether it's counters are working or not.
With many losses it will be more likely to experiment, and maybe another strategy proves more effective, which it will then use instead.

You make adaptive AI, which could be switching between other premade strategy types, but depending on implementation, it might be better to make a separate ai.

#19 frioux   Members   -  Reputation: 100

Like
0Likes
Like

Posted 18 March 2011 - 06:51 AM

Hi,

I have been toying with that lately using reinforcement learning for a tactical rpg. Im still not sure what I will be able to do in practice with that.

I used an old work I had on reinforcement learning.

I have the following algorithm:
(Simple for test)
Follower
Follower_wait
Random
Random_follower
(Learning)
MDP
Adaptive MDP
Multiplicative weight (not sure what it is right now)

Heres some problems:

The number of possible actions can be big. (in fact everything is big).

I need to get a prior with self-play but in a real game, the number of units you have is variable, the field is variable, the number of opponents is variable, the stat of all unit is variable. So I need to use fake stats, fake field and possibly calculate multiple prior depending on differents fights configurations.

The natural reward function would in function of the number of dommage inflicted or healed, status recovery and the like plus a bonus for killing an enemy. But its not enough, the reward fonction need to return a value for each situation even if theres no unit around. So you need another motivator, that additional motivator will be related to the distance of your agent to the enemy, that part of the reward function will be according to the kind of behavior you want your agent to have (aggresive, coward, etc.).

Speed of convergence, after the prior have been done, what garanty we have that the algorithm will have time to adapt?

All those techniques are heavy on the cpu and memory, in a multiplayer envoronment, it can quickly become a problem.

So, im still far from having something working in production, it work, but will it be really efficient and is the server will be able to handle it?

Conclusion: Making that kind of AI work in a real game is whole project in itself.

Oh yeah, theres anothers problems. How to represent the strategy (policy) if its the ensemble of all the transition posible for all combinaison of actions/states.

I have another idea in mind where you would use a genetic algo. A gene could represent an action to execute in a situation. Or the ADN could return the action with field state variable as possible value of the ADN (genetic programming). The environnent could include some player "squads" as predator for robustness and you could possibly run the algo for each possible field/enemy units possibility because the solution representation is simple. More thinking to do.

#20 Daerax   Members   -  Reputation: 1207

Like
0Likes
Like

Posted 18 March 2011 - 12:28 PM

I'm prepared to be wrong, but I'm not yet convinced. Give me a scenario where a human decision can outplay a perfectly operated AI.


The scenario where the human is perfect. This is every bit as realistic as the perfectly operated AI concept.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS