16 replies to this topic

[calculemus1988]

I am learning about Bayes Networks at Stanford's online AI class. I was wondering if there are books that talk about and implement code related to Bayes networks in context of games?

Thanks

[IADaveMark]

There's not a lot of writing about Bayes in games because there's not a lot of use for Bayes in games. That's unfortunate because it is a really powerful technique. Most of the reason that we don't need to process partial information in the game realm is because, with regard to the game engine and entities, we already have ALL the information. What we can use it for is stuff that is not inherently a part of the game -- the player, for example. There is some use of Bayes to intuit player intent. For example, given a list of criteria about a situation, if the player is holding his sniper rifle, we are undetected by the enemy, we are in cover, and the player starts to move forward, chances are the player is not planning on rushing the enemy -- he wants to pop a melon or two.

That being said, in the book, AI Game Programming Wisdom, there is a great explanation with examples of Bayesian networks by Paul Tozour.

[willh]

There's not a lot of writing about Bayes in games because there's not a lot of use for Bayes in games.

I disagree. Dave, have you ever played Monopoly for the iPhone? <shudder>

It has 3 difficulty levels. At level 1 (easy) you can offer the computer the list price for a property it owns, and it will sell it. At levels 2 and 3 I'm pretty sure that the computer cheats-- as in the dice are loaded with magical weights that allow the computer to alter its 'luck' level. lol. It doesn't look like EA made any effort to build a 'smarter' opponent and IMO the game seriously suffers because of it.

Bayes would have been perfect for Monopoly.

So, OP, there is plenty of room for improvement in games, provided you're thinking about the right sorts of games.

[IADaveMark]

Like I said, there are game for which it would be a powerful technique. Discerning the results of something stochastic (e.g. Monopoly) is one. I also seem to remember our discussion regarding the very Stratego-like game a few months back where I suggested that Bayes is the way of approaching that. However, in the face of actual perfect knowledge that the computer has, AI programmers don't need to use Bayes when we can just look up the info and fake stupidity. That's not my preferred method... I was just stating that it is often done that way.

A good example would be finding the player when he is hidden. Obviously the computer knows where the player is and can simply feign stupidity. However, that doesn't always lead to convincing error. Using Damián Isla's occupancy maps, however, is a Bayes-like treatment of influence maps. THAT leads to a very realistic approach by the NPCs because it is based on that magic combination of observation, belief, and possibility.

[calculemus1988]

I am kinda disappointed finding out more and more(I am student by the way) that the jobs available in computer science are not that interesting as I thought. The things we study in theory, the cool stuff, don't have much applications yet. It seems the real world is way way behind in relation to the theory that is developed. I am not like oh I should quit computer science, far from that, I am just saying theory is way way too far from what is actually done in real world and what you get paid for.

[willh]

I am kinda disappointed finding out more and more(I am student by the way) that the jobs available in computer science are not that interesting as I thought. The things we study in theory, the cool stuff, don't have much applications yet. It seems the real world is way way behind in relation to the theory that is developed. I am not like oh I should quit computer science, far from that, I am just saying theory is way way too far from what is actually done in real world and what you get paid for.

Calculemus, about 1% of people get the really cool jobs (like test driving Bugati Verons, reverse engineering fly brains, or designing video games). Everyone else is stuck doing things that your average teenager could care less about.

EA, in terms of a profit model, did the right thing by building a cheap AI. They wasted no money, and the 'Monopoly' brand name sold itself. The lame AI probably didn't affect sales one bit.

Dave is quite right in pointing out that most RTS or FPS games don't require an AI any more complex than a set of scripts. There really isn't much value in building complex AI for for most NPCs.

It has been my experience that if you want to do interesting cutting-edge things you have two options: Work for yourself, or work in academia. Build a game that uses a strong AI as the gimic that gets people to play it. It's never been a better time for the indy developer.

[Emergent]

While it's true that intellectual products like new algorithms don't take huge numbers of people to produce -- so you'll be facing some competition to get these jobs -- I wouldn't totally write off these technologies as useless.

- Android and iOS devices both include speech recognition engines. Witness the much-hyped Siri. As far as I know, Hidden Markov Models are at the heart of most speech recognition algorithms; it's possible that Bayes nets are in use here too. And the speech recognition engines, though impressive, still leave much room for improvement. That means room for competition.

- The government funds a great many contractors that you've never heard of, who are trying to develop both old-fashioned database systems, and fancier statistical analysis tools including semantic networking tools, for understanding intelligence data. I imagine Bayes nets either get used here, or could be used.

- Robotics is very slowly taking off, not just in defense and in a few "silly" consumer applications like the Roomba (though it has some sophisticated competitors that even do SLAM!), but also in warehousing and factory automation, and we're just beginning to see the very leading edge of agricultural robotics. The world won't need a billion roboticists, but it is one more area where these sophistical tools can actually be useful.

I also think that games have a lot to teach these other fields. Sure, they don't need to deal with uncertainty to the same extent, but one thing they do a great job of is producing usable interfaces for interacting with the real world (or simulations thereof). People are beginning to acknowledge, for instance, that Starcraft is a pretty good model for what a good "net-centric warfare" interface should look like. Indeed, it was by explicitly following a strategy of copying Starcraft's UI that Ed Olson and his students won the recent MAGIC robotics competition in Australia. The difference, of course, is that instead of loading a map file you're doing SLAM, and the "fog of war" is real! My point in bringing this up is to say that, although some of these algorithms don't get used in games themselves, they get used in other fields that involve many of the same things as game development.

[calculemus1988]

Thank you guys, I got a good idea about Bayes Nets in games.

In week 3 Machine Learning course, we learn about Neural Networks. So that I don't start a new topic, you guys wanna talk about Neural Nets in games? Are they used and to what degree?

Thanks

[IADaveMark]

Thank you guys, I got a good idea about Bayes Nets in games.

In week 3 Machine Learning course, we learn about Neural Networks. So that I don't start a new topic, you guys wanna talk about Neural Nets in games? Are they used and to what degree?

Thanks

Even the most basic search of this forum's posts will give you the answer(s) about NNs in games. Trust me... we don't want to restart that.

[Daerax]

I am learning about Bayes Networks at Stanford's online AI class. I was wondering if there are books that talk about and implement code related to Bayes networks in context of games?

Thanks

Bayes Networks would be wasted on games. They are slow, inference on them is NP - hard. Building the network structure from data is also NP-hard. So for a decent sized network you gonna be doing something like gibbs sampling to do inference on network a structure that is almost guaranteed to be wrong. For a game the AI will take a long time to get at the distribution and is not worth it. Most of machine learning is either too slow, data intensive or stationary for Game use.

If there would be one machine learning thing that I would actively look into, it would be Decision Trees. Decision trees are brittle so can add variance and do well with little data. You could then augment them as Random forest or boosted trees. I think that would be where I would start.

A close cousin to bayes nets that might be useful to some types of games (arcade shooter, anything requiring movement tracking and prediction) would be a particle filter. Finally, a bared down Reinforcement learning algo may be good for long term play in a strategy or RPG. All of these would be very hard to get right and take a lot of time when a simple markov chain based model or even Finite state machine would have done just as good or better for much less work.

[Daerax]

While it's true that intellectual products like new algorithms don't take huge numbers of people to produce -- so you'll be facing some competition to get these jobs -- I wouldn't totally write off these technologies as useless.

- Android and iOS devices both include speech recognition engines. Witness the much-hyped Siri. As far as I know, Hidden Markov Models are at the heart of most speech recognition algorithms; it's possible that Bayes nets are in use here too. And the speech recognition engines, though impressive, still leave much room for improvement. That means room for competition.

- The government funds a great many contractors that you've never heard of, who are trying to develop both old-fashioned database systems, and fancier statistical analysis tools including semantic networking tools, for understanding intelligence data. I imagine Bayes nets either get used here, or could be used.

- Robotics is very slowly taking off, not just in defense and in a few "silly" consumer applications like the Roomba (though it has some sophisticated competitors that even do SLAM!), but also in warehousing and factory automation, and we're just beginning to see the very leading edge of agricultural robotics. The world won't need a billion roboticists, but it is one more area where these sophistical tools can actually be useful.

I also think that games have a lot to teach these other fields. Sure, they don't need to deal with uncertainty to the same extent, but one thing they do a great job of is producing usable interfaces for interacting with the real world (or simulations thereof). People are beginning to acknowledge, for instance, that Starcraft is a pretty good model for what a good "net-centric warfare" interface should look like. Indeed, it was by explicitly following a strategy of copying Starcraft's UI that Ed Olson and his students won the recent MAGIC robotics competition in Australia. The difference, of course, is that instead of loading a map file you're doing SLAM, and the "fog of war" is real! My point in bringing this up is to say that, although some of these algorithms don't get used in games themselves, they get used in other fields that involve many of the same things as game development.

You are definitely right about game having a lot to teach other fields.

Robotics usually focus on reinforcement learning type stuff.

Yeah contractors, data scientist are the prime users of bayes nets. They have the resources, expertise and time to build, train and sample from networks (sometimes measured in days). The lack of black box also means that the parameters themselves may have actionable info.

HMM mostly, never heard of bayes nets though Condition random fields gaining in use.

Siri is stupid (not an insult) - I read from someone who worked on it that its mostly keyword matching.

[willh]

1320029118[/url]' post='4878783']


If there would be one machine learning thing that I would actively look into, it would be Decision Trees. Decision trees are brittle so can add variance and do well with little data. You could then augment them as Random forest or boosted trees. I think that would be where I would start.

A close cousin to bayes nets that might be useful to some types of games (arcade shooter, anything requiring movement tracking and prediction) would be a particle filter. Finally, a bared down Reinforcement learning algo may be good for long term play in a strategy or RPG. All of these would be very hard to get right and take a lot of time when a simple markov chain based model or even Finite state machine would have done just as good or better for much less work.

Trees are that little tool that nobody ever talks about. You can derive probability distributions from them, use them for clustering, regression, and classification. They can be built in near real time, and a human can understand their output (it's a decision tree!!!).
I've posted a few screen shots of regression and boosted regression trees. I've even offered to write a tutorial. They lack a cool name maybe... Or the math isnt complex enough to invoke the voodoo factor? Not even one thumbs up though... <sigh>

[ApochPiQ]

If you honestly feel they are that valuable, you should be willing to make the resources available to teach people about them without needing encouragement. Most people won't see the need or interest until after a resource is available which clearly, concisely, and comprehensively illustrates the value of that technique.

Frankly, you shouldn't need our approval or rabid anticipation to do something that you think is worthwhile.

[Daerax]

If you honestly feel they are that valuable, you should be willing to make the resources available to teach people about them without needing encouragement. Most people won't see the need or interest until after a resource is available which clearly, concisely, and comprehensively illustrates the value of that technique.

Frankly, you shouldn't need our approval or rabid anticipation to do something that you think is worthwhile.

I am short on time or I would volunteer. Someday maybe. But he is right Decision Trees are something that are not payed enough attention to. Random Forest in my use case outperformed neural nets and SVM and are speedy to train.

For games, more than neural or bayes nets or genetic search, decision trees are the one thing out of machine learning I would argue to be most applicable to games in a splash and dash manner. They represent a probability distribution over the data, are not very far from FSM many are used to and with a weighted randomized voting method are close to behaviour trees (although built in an inverse manner - decision trees you start from a list of scenarios and desired ouptuts and it returns a tree, btrees - you start with actions to input states and build the tree - at least for what I can understand of behaviour trees, the game literature terminology is not one I am fluent in)

Here is a fairly clear but basic python example of a decision Tree from Machine Learning An Algorithmic Perspective (I highly recommend the book). http://www-ist.masse...Code/6/dtree.py

[willh]

1320082315[/url]' post='4878944']
If you honestly feel they are that valuable, you should be willing to make the resources available to teach people about them without needing encouragement. Most people won't see the need or interest until after a resource is available which clearly, concisely, and comprehensively illustrates the value of that technique.

Frankly, you shouldn't need our approval or rabid anticipation to do something that you think is worthwhile.

I do think they are worthwhile, and so I use them in my work. It's also why I have suggested them.
Thinking something is a great tool in no way means that one is obliged to write a how-to guide for the uniniatied.

[ApochPiQ]

I'm not trying to suggest you're obligated to do anything; I'm just saying that if you think these are worth teaching people about, why wait for the "thumbs up" as you put it? Just go do it. Unless you're doing it purely for recognition, there should be no reason to hold off.

[Normalized]

For video games, I think decision trees make more sense than Bayesian network. Generally, the outcomes you want in a video game are well defined.

The advantages of decision trees are

1: easy to program

2: designer friendly

3: easy to debug

4: can be used as a Game tree for game theory applications

5: full deterministic because each node only has 1 parent node.
Unlike a Bayesian network where multiple variables can affect the truth-value.

The advantages of Bayesian network seem to be

1: allows independent / conditionally independent nodes

2: allow reasoning about independent nodes

3: Often will have less nodes. However, each node will have more edges. Especially true with joint probability