Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Work in Progress / [DBP] Supervised Machine Learning Functions: Naive Bayes Classifier (Easy-to-use!)

Author
Message
Sixty Squares
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Somewhere in the world
Posted: 16th Aug 2013 07:39 Edited at: 16th Aug 2013 08:42
NOTE: The code for the functions is at the bottom of this post. Examples are in the next post.

Hi all,

Long time no see!

I know this looks long and tedious, but trust me, it's not so bad. If you want to skip the theory just read the bits in bold and then look at the simple example in my next post. You should be ready to brainstorm ideas for your game in no time. In fact, here's a super quick sample demonstrating how little needs to be done/understood:


Before I begin, I'd like to say that everything in this post is based on my own understanding of the topics at hand. If anyone spots a flaw, please do point it out .

I've been reading a bit about machine learning lately and decided to implement a Naive Bayes Classifier in DBP. This algorithm is a Supervised Learning Algorithm, meaning you need to provide it with some data to use as a base to learn from. Later I may implement an Unsupervised Learning Algorithm (Genetic Algorithm), whereby the computer learns via trial and error, which would probably be more useful and fun for gaming because even the game's creator wouldn't know what the computer would do next . But for now, here's a simple and popular supervised algorithm.




What is a Naive Bayes Classifier?


In simplest terms, a Naive Bayes Classifier is something which, when given some features, will produce what it expects another feature to be based on data it has already seen. It does this by seeing how likely each option for the feature in question is given the known features, and then picking the most likely case. This process is entirely based on Bayes' Theorem, a formula describing the probability of some event A given an event B has occurred. We could also calculate it for A given B, C, D, etc, which is what the code in this post does. Anyway, it's Naive because it assumes that B, C, D, etc. do not depend on each other in any way. That is, B happening has nothing to do with C or D happening. This could be false (ex. if B is "lightning strikes a power line" and C is "power goes out", then these two events are clearly related). But we're naive and assume everything is independent because it makes the math nicer. This assumption can cause some problems (ex. if everything in your dataset depends completely on everything else), but usually it works out well. You "train" the Classifier on some data, it "learns" from the data and then interprets any new data you give it based on what the old data said.

But enough technical stuff. Here's a concrete example:

Suppose we want to know what spell the player will use next in a turn-based RPG game. We know that some spells are commonly used together, but we don't know which, and we don't want to sit there and think of all the possible combos the player might have come up with. What to do? Well, here are a few creatively named spell sequences that the player has used on us in the past.

Freeze Feet ---> Hover Boulder Over Head ---> Make Boulder Fall
Hover Boulder Over Head ---> Make Boulder Fall ---> Heal Self
Freeze Feet ---> Shatter Ice ---> Reassemble Ice
Freeze Feet ---> Hover Boulder Over Head ---> Heal Self
Freeze Feet ---> Hover Boulder Over Head ---> Make Boulder Fall
Freeze Feet ---> Shatter Ice --> Freeze Feet
Freeze Feet ---> Hover Boulder Over Head ---> Make Boulder Fall
Freeze Feet ---> Hover Boulder Over Head ---> Shatter Ice
Freeze Feet ---> Hover Boulder Over Head ---> Make Boulder Fall
Make Boulder Fall ---> Heal Self ---> Heal Self

Hmmm. Our player really likes freezing things.

Pretend our player just used Freeze Feet followed by Hover Boulder Over Head. What will he do next? Well, in the past when he froze our feet and hovered a boulder over our head, he made it fall on us. But he also used Heal Self or Shatter Ice. So which will he do this time? Well, in the 6 cases that he's used Freeze Feet followed by Hover Boulder Over Head, 4/6 of those times he used Make Boulder Fall afterwards. The other two times he used either Heal Self or Shatter Ice. But most of the time he just makes the boulder fall. So the AI assumes that's what he's doing this time and prepares for it by using Deflect Boulder.

Bam.

The boulder goes flying back at the player, he loses health and curses the AI for figuring out his favorite combo.

But what if the player used Heal Self followed by Hover Boulder Over Head? Well now we're in trouble. We've never seen that combo before. But here's where the probability element comes in. In the past when the second move was Hover Boulder Over Head, the player usually used Make Boulder Fall afterwards. Because of this, the Naive Bayes Classifier will still conclude that the player is using Make Boulder Fall next.

The problem arises in a case where the player uses, say, Freeze Feet ---> Heal Self. What will he do next? We haven't seen that before either. Since Freeze Feet was used first, the AI will still think the player is doing the boulder combo. This goes back to our assumption of independence. The AI doesn't know that using Make Boulder Fall depends on whether or not Hover Boulder Over Head was used, so it doesn't realize that its guess can't be accurate.

To get around this you might do a second classification. Given the player used Freeze Feet --> ???? --> Make Boulder Fall, what is ??? most likely to be? It'll probably say Hover Boulder Over Head. Since he didn't do that and used Heal Self instead, you know the combo is not exactly what the computer thinks it is. This is not a tried and true solution though-- I just thought of it ...

There is also a function for retrieving the actual probability obtained from the calculation that might come in handy.




What can I use this for?

Examples in gaming that I can think of:
Given the player's party is comprised of a Mage and 3 Clerics, what team composition should the AI use against it?
The player has selected a Warrior, added lots of Agility and equipped a sword. Based on things that I did while testing the game, what abilities will the player most likely select?
The player uses a Rocket Launcher as his main weapon, likes to spin around in circles and spends more than half of his time jumping in the air. Should the AI use landmines?
The AI has access to the same spells as the player and wants to use his combos against him. What spell does the player usually start with? What's his favorite combo from there?
How is the player going to defend against the AI's next attack? What does he think the AI is about to do?
The tic-tac-toe board looks just so. What should the AI do next? (I believe you could train an AI to play tic-tac-toe without even knowing the rules this way if you wanted to. I may try this later).


Examples outside of gaming that I can think of:
Spam filter. Given an email contains the phrases "FREE!", "BUY NOW!", "check out my page" and a tinyurl link, is it spam?
Determining the gender of a name based on endings.
Determining whether or not a picture contains a fruit.
Determining the type of bird based on its wingspan, flight speed, and rest period duration.
Basically anything that requires the classification of something based on the features it has. That's why it's called a Classifier.

The power here lies in your ability to pick good features! Be more creative than I am!

Actual Code Stuff


TODO
Better documentation
More examples
Clean up the code/comment it better
Fix any issues you guys discover
More error handling? Maybe?

How fast is it for a realtime game?: Not sure. Only one way to find out

Commands (I would go through the heavily commented simple example in my next post for a good overview of what's going on)


Code as of August 15, 2013 (Alpha) (Requires IanM's Matrix1 Utils) (Examples in next post). Just include the code with your project to use the functions.


Anyway, I hope this code is helpful somehow, and if it isn't, I hope the post was at least informative . Thanks for reading!

Hmm. It's been a while .
Sixty Squares
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Somewhere in the world
Posted: 16th Aug 2013 07:40 Edited at: 16th Aug 2013 08:39
The Simple Example

Simple, Heavily Commented Example (Look at this to learn how the functions work).


Concise version:


Hmm. It's been a while .
Ashingda 27
14
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 16th Aug 2013 08:12
Very interesting concepts, could lead to making a video game hard to beat because you cant just spam the same moves until the closing credits. Hmm I might want to try something like this in my game.

Ortu
DBPro Master
15
Years of Service
User Offline
Joined: 21st Nov 2007
Location: Austin, TX
Posted: 16th Aug 2013 09:02
Really nice write up with some good clear examples. Nice man, thanks!

I'm gonna be king of the moon dots!
Sixty Squares
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Somewhere in the world
Posted: 17th Aug 2013 01:44
@Ashingda: My thoughts exactly. Let me know if you end up using it in Land Conquest; I'd be interested in seeing how you choose to use it/how well it works in that context.

@Ortu: Thank man, I'm glad you enjoyed it

Hmm. It's been a while .
Clonkex
Forum Vice President
12
Years of Service
User Offline
Joined: 20th May 2010
Location: Northern Tablelands, NSW, Australia
Posted: 4th Sep 2013 15:52
Quote: "Long time no see!"


Good to see you're still alive, Sixty! I have a question for you: could you possibly recompile RND Sprint and post it please? I want to play it and fight over high scores with my brother once again, but it won't run on Windows 7 ("Parameter Incorrect") because it was compiled with a version of DBPro that had a bug (which has since be rectified). I've played it before (and it was fun!) but it was on my Windows XP computer last time.

AH I just saw your Bob thread....I can't believe a thread about a neverending (already sounds bad) text adventure (no! this sounds horrible) involving someone called Bob (ARG...choking... on... boring!) actually managed to survive FOUR PAGES!! (*dies with liquid boredom spilling out of every orifice*) I read through the whole thing and it was very funny

Quote: "Very interesting concepts, could lead to making a video game hard to beat because you cant just spam the same moves until the closing credits."


I agree, could be turn out very useful. I have several ideas for what I could use this for already

Sixty Squares
16
Years of Service
User Offline
Joined: 7th Jun 2006
Location: Somewhere in the world
Posted: 14th Sep 2013 03:14 Edited at: 14th Sep 2013 03:16
Quote: " could you possibly recompile RND Sprint and post it please? I want to play it and fight over high scores with my brother once again, but it won't run on Windows 7 ("Parameter Incorrect") because it was compiled with a version of DBPro that had a bug (which has since be rectified). I've played it before (and it was fun!) but it was on my Windows XP computer last time."


I'm glad you guys enjoyed it! I'm actually on a Windows 7 computer right now. I had recompiled it with the updated DBPro, but for some reason the game crashes (unexpected error) when you try to move at maximum speed (on my computer at least). It might have something to do with some outdated plugin or something, but I have no idea. It'd be interesting to try it on another computer though. I have to find the flash drive with the game on it but once I do I'll try and re-upload it!

Quote: "AH I just saw your Bob thread....I can't believe a thread about a neverending (already sounds bad) text adventure (no! this sounds horrible) involving someone called Bob (ARG...choking... on... boring!) actually managed to survive FOUR PAGES!! (*dies with liquid boredom spilling out of every orifice*) I read through the whole thing and it was very funny"

Hahahahahaha I had forgotten about that. I have no idea how it survived for 4 pages either, that's hilarious in retrospect!

Quote: "I have several ideas for what I could use this for already "

I look forward to seeing what you come up with

Hmm. It's been a while .

Login to post a reply

Server time is: 2022-12-06 03:06:43
Your offset time is: 2022-12-06 03:06:43