Bayes Academy: Development report 1

post by Kaj_Sotala · 2014-11-19T22:35:15.475Z · LW · GW · Legacy · 28 comments

Some of you may remember me proposing a game idea that went by the name of The Fundamental Question. Some of you may also remember me talking a lot about developing an educational game about Bayesian Networks for my MSc thesis, but not actually showing you much in the way of results.

Insert the usual excuses here. But thanks to SSRIs and mytomatoes.com and all kinds of other stuff, I'm now finally on track towards actually accomplishing something. Here's a report on a very early prototype.

This game has basically two goals: to teach its players something about Bayesian networks and probabilistic reasoning, and to be fun. (And third, to let me graduate by giving me material for my Master's thesis.)

We start with the main character stating that she is nervous. Hitting any key, the player proceeds through a number of lines of internal monologue:

I am nervous.

I’m standing at the gates of the Academy, the school where my brother Opin was studying when he disappeared. When we asked the school to investigate, they were oddly reluctant, and told us to drop the issue.

The police were more helpful at first, until they got in contact with the school. Then they actually started threatening us, and told us that we would get thrown in prison if we didn’t forget about Opin.

That was three years ago. Ever since it happened, I’ve been studying hard to make sure that I could join the Academy once I was old enough, to find out what exactly happened to Opin. The answer lies somewhere inside the Academy gates, I’m sure of it.

Now I’m finally 16, and facing the Academy entrance exams. I have to do everything I can to pass them, and I have to keep my relation to Opin a secret, too. 

???: “Hey there.”

Eep! Someone is talking to me! Is he another applicant, or a staff member? Wait, let me think… I’m guessing that applicant would look a lot younger than staff members! So, to find that out… I should look at him!

[You are trying to figure out whether the voice you heard is a staff member or another applicant. While you can't directly observe his staff-nature, you believe that he'll look young if he's an applicant, and like an adult if he's a staff member. You can look at him, and therefore reveal his staff-nature, by right-clicking on the node representing his apperance.]

Here is our very first Bayesian Network! Well, it's not really much of a network: I'm starting with the simplest possible case in order to provide an easy start for the player. We have one node that cannot be observed ("Student", its hidden nature represented by showing it in greyscale), and an observable node ("Young-looking") whose truth value is equal to that of the Student node. All nodes are binary random variables, either true or false. 

According to our current model of the world, "Student" has a 50% chance of being true, so it's half-colored in white (representing the probability of it being true) and half-colored in black (representing the probability of it being false). "Young-looking" inherits its probability directly. The player can get a bit of information about the two nodes by left-clicking on them.

The game also offers alternate color schemes for colorblind people who may have difficulties distinguishing red and green.

Now we want to examine the person who spoke to us. Let's look at him, by right-clicking on the "Young-looking" node.

Not too many options here, because we're just getting started. Let's click on "Look at him", and find out that he is indeed young, and thus a student.

This was the simplest type of minigame offered within the game. You are given a set of hidden nodes whose values you're tasked with discovering by choosing which observable nodes to observe. Here the player had no way to fail, but later on, the minigames will involve a time limit and too many observable nodes to inspect within that time limit. It then becomes crucial to understand how probability flows within a Bayesian network, and which nodes will actually let you know the values of the hidden nodes.

The story continues!

Short for an adult, face has boyish look, teenagerish clothes... yeah, he looks young!

He's a student!

...I feel like I’m overthinking things now.

...he’s looking at me.

I’m guessing he’s either waiting for me to respond, or there’s something to see behind me, and he’s actually looking past me. If there isn’t anything behind me, then I know that he must be waiting for me to respond.

Maybe there's a monster behind me, and he's paralyzed with fear! I should check that possibility before it eats me!

[You want to find out whether the boy is waiting for your reply or staring at a monster behind you. You know that he's looking at you, and your model of the world suggests that he will only look in your direction if he's waiting for you to reply, or if there's a monster behind you. So if there's no monster behind you, you know that he's waiting for you to reply!]

Slightly more complicated network, but still, there's only one option here. Oops, apparently the "Looks at you" node says it's an observable variable that you can right-click to observe, despite the fact that it's already been observed. I need to fix that.

Anyway, right-clicking on "Attacking monster" brings up a "Look behind you" option, which we'll choose.

You see nothing there. Besides trees, that is.

Boy: “Um, are you okay?”

“Yeah, sorry. I just… you were looking in my direction, and I wasn’t sure of whether you were expecting me to reply, or whether there was a monster behind me.”

He blinks.

Boy: “You thought that there was a reasonable chance for a monster to be behind you?”

I’m embarrassed to admit it, but I’m not really sure of what the probability of a monster having snuck up behind me really should have been.

My studies have entirely focused on getting into this school, and Monsterology isn’t one of the subjects on the entrance exam!

I just went with a 50-50 chance since I didn’t know any better.

'Okay, look. Monsterology is my favorite subject. Monsters avoid the Academy, since it’s surrounded by a mystical protective field. There’s no chance of them getting even near! 0 percent chance.'

'Oh. Okay.'

[Your model of the world has been updated! The prior of the variable 'Monster Near The Academy' is now 0%.]

Then stuff happens and they go stand in line for the entrance exam or something. I haven't written this part. Anyway, then things get more exciting, for a wild monster appears!

Stuff happens

AAAAAAH! A MONSTER BEHIND ME!

Huh, the monster is carrying a sword.

Well, I may not have studied Monsterology, but I sure did study fencing!

[You draw your sword. Seeing this, the monster rushes at you.]

He looks like he's going to strike. But is it really a strike, or is it a feint?

If it's a strike, I want to block and counter-attack. But if it's a feint, that leaves him vulnerable to my attack.

I have to choose wisely. If I make the wrong choice, I may be dead.

What did my master say? If the opponent has at least two of dancing legs, an accelerating midbody, and ferocious eyes, then it's an attack!

Otherwise it's a feint! Quick, I need to read his body language before it's too late!

Now get to the second type of minigame! Here, you again need to discover the values of some number of hidden variables within a time limit, but here it is in order to find out the consequences of your decision. In this one, the consequence is simple - either you live or you die. I'll let the screenshot and tutorial text speak for themselves:

[Now for some actual decision-making! The node in the middle represents the monster's intention to attack (or to feint, if it's false). Again, you cannot directly observe his intention, but on the top row, there are things about his body language that signal his intention. If at least two of them are true, then he intends to attack.]

[Your possible actions are on the bottom row. If he intends to attack, then you want to block, and if he intends to feint, you want to attack. You need to inspect his body language and then choose an action based on his intentions. But hurry up! Your third decision must be an action, or he'll slice you in two!]

In reality, the top three variables are not really independent of each other. We want to make sure that the player can always win this battle despite only having three actions. That's two actions for inspecting variables, and one action for actually making a decision. So this battle is rigged: either the top three variables are all true, or they're all false.

...actually, now that I think of it, the order of the variables is wrong. Logically, the body language should be caused by the intention to attack, and not vice versa, so the arrows should point from the intention to body language. I'll need to change that. I got these mixed up because the prototypical exemplar of a decision minigame is one where you need to predict someone's reaction from their personality traits, and there the personality traits do cause the reaction. Anyway, I want to get this post written before I go to bed, so I won't change that now.

Right-clicking "Dancing legs", we now see two options besides "Never mind"!

We can find out the dancingness of the enemy's legs by thinking about our own legs - we are well-trained, so our legs are instinctively mirroring our opponent's actions to prevent them from getting an advantage over us - or by just instinctively feeling where they are, without the need to think about them! Feeling them would allow us to observe this node without spending an action.

Unfortunately, feeling them has "Fencing 2" as a prerequisite skill, and we don't have that. Neither could we have them, in this point of the game. The option is just there to let the player know that there are skills to be gained in this game, and make them look forward to the moment when they can actually gain that skill. As well as giving them an idea of how the skill can be used.

Anyway, we take a moment to think of our legs, and even though our opponent gets closer to us in that time, we realize that our legs our dancing! So his legs must be dancing as well!

With our insider knowledge, we now know that he's attacking, and we could pick "Block" right away. But let's play this through. The network has automatically recalculated the probabilities to reflect our increased knowledge, and is now predicting a 75% chance for our enemy to be attacking, and for "Blocking" to thus be the right decision to make.

Next we decide to find out what his eyes say, by matching our gaze with his. Again, there would be a special option that cost us no time - this time around, one enabled by Empathy 1 - but we again don't have that option.

Except that his gaze is so ferocious that we are forced to look away! While we are momentarily distracted, he closes the distance, ready to make his move. But now we know what to do... block!

Success!

Now the only thing that remains to do is to ask our new-found friend for an explanation.

"You told me there was a 0% chance of a monster near the academy!"

Boy: “Ehh… yeah. I guess I misremembered. I only read like half of our course book anyway, it was really boring.”

“Didn’t you say that Monsterology was your favorite subject?”

Boy: “Hey, that only means that all the other subjects were even more boring!”

“. . .”

I guess I shouldn’t put too much faith on what he says.

[Your model of the world has been updated! The prior of the variable 'Monster Near The Academy' is now 50%.]

[Your model of the world has been updated! You have a new conditional probability variable: 'True Given That The Boy Says It's True', 25%]

And that's all for now. Now that the basic building blocks are in place, future progress ought to be much faster.

Notes:

As you might have noticed, my "graphics" suck. A few of my friends have promised to draw art, but besides that, the whole generic Java look could go. This is where I was originally planning to put in the sentence "and if you're a Java graphics whiz and want to help fix that, the current source code is conveniently available at GitHub", but then getting things to his point took longer than I expected and I didn't have the time to actually figure out how the whole Eclipse-GitHub integration works. I'll get to that soon. Github link here!

I also want to make the nodes more informative - right now they only show their marginal probability. Ideally, clicking on them would expand them to a representation where you could visually see what components their probability composed of. I've got some scribbled sketches of what this should look like for various node types, but none of that is implemented yet.

I expect some of you to also note that the actual Bayes theorem hasn't shown up yet, at least in no form resembling the classic mammography problem. (It is used implicitly in the network belief updates, though.) That's intentional - there will be a third minigame involving that form of the theorem, but somehow it felt more natural to start this way, to give the player a rough feeling of how probability flows through Bayesian networks. Admittedly I'm not sure of how well that's happening so far, but hopefully more minigames should help the player figure it out better.

What's next? Once the main character (who needs a name) manages to get into the Academy, there will be a lot of social scheming, and many mysteries to solve in order for her to find out just what did happen to her brother... also, I don't mind people suggesting things, such as what could happen next, and what kinds of network configurations the character might face in different minigames.

(Also, everything that you've seen might get thrown out and rewritten if I decide it's no good. Let me know what you think of the stuff so far!)

28 comments

Comments sorted by top scores.

comment by jslocum · 2014-11-20T15:41:15.991Z · LW(p) · GW(p)

I really like the idea overall.

Serious ideas:

  • games that help explain ideas like 'screening' variables, rules for propagating information up and down different branches of the network, etc.

  • more advanced topics like estimating the normalization constant for a very large hypothesis space?

  • more advanced gameplay mode where you have a scenario and a list of hidden and observable variables, and have to figure out what shape the network should take - you then play out the scenario with the network you made - success requires having constructed the network well!

Bad jokes:

  • A character named Gibbs who runs an energy drink stand and gives out free samples.

  • The Count of Monte Carlo should make an appearance.

  • A face-off against agents of the evil Frequentist, hell bent on destroying all that is (probably) good and (likely to be) held dear.

comment by IlyaShpitser · 2014-11-20T01:20:08.883Z · LW(p) · GW(p)

Neat! Two suggestions:

(a) A trial (with evidence and a verdict) is a good way to show how to update beliefs as new evidence comes to light, if there is room in the game for that. It's such a natural thing to use Bayes nets in this context that lawyers invented an early version called 'Wigmore charts'.

(b) It would be neat to demonstrate confounding bias somehow (e.g. a common cause cancelling out an existing relationship, or explaining it away entirely).

Replies from: Kaj_Sotala
comment by Kaj_Sotala · 2014-11-20T10:35:22.097Z · LW(p) · GW(p)

Thanks, I have to look up Wigmore charts!

I was intending on having something like confounding bias appear in the form of the protagonist's model of the world being gradually updated to contain larger and more detailed networks, so e.g. two variables that appeared to have a causal relationship in an early network would turn out to have a common cause in a later, more accurate one. (The player can acquire more accurate networks either by allocating time to studies and learning from the work of others, or by experimenting themselves. Not sure of the exact mechanics for these yet.)

Replies from: IlyaShpitser
comment by John_Maxwell (John_Maxwell_IV) · 2014-11-20T02:41:06.763Z · LW(p) · GW(p)

Nice work!

Did you consider using one of those fancy new JavaScript game frameworks so your game can trivially be distributed through the internet and played on all platforms? (An acquaintance who runs a game site reports that web-based games on his site get more plays than downloadable ones.)

I found this on Google, not sure if the code will be useful: http://pl4n3.blogspot.com/2013/07/bayesjs-bayesian-networks-javascript.html

Replies from: Kaj_Sotala, KenChen
comment by Kaj_Sotala · 2014-11-20T10:37:12.099Z · LW(p) · GW(p)

At a later stage, possibly. Right now I'm just focused on getting a playable and fun version out in a language/framework I happen to be familiar with already, and think about optimizing the platform for maximal reach later on. Getting an in-browser version would be good, though.

Replies from: KenChen, kpreid
comment by KenChen · 2014-11-20T16:18:16.314Z · LW(p) · GW(p)

Strongly agree that you would have a much, much higher impact by making this game available on the web. Straight-up Java is pretty much dead now. Consider even making a Facebook app, which would allow players to share the game with their friends for stronger distribution.

comment by kpreid · 2014-11-26T05:26:42.813Z · LW(p) · GW(p)

Loudly agreeing with other comments:

Java being dead as a way to run apps is true outside of special cases.

In today's world, you should write anything as a web app/page unless you know of a specific reason not to. For a thing like this, it's especially important as it means the potential user doesn't have to install anything, and doesn't have to trust you. This removes barriers: they can click a link someone gave them and be playing.

Having to use JavaScript can be obnoxious because it gives you more ways to make mistakes and get cryptic failures, but on the upside it can be a lot more concise sometimes — requiring less detailed work before you have something that does what you want. (Fun fact: JavaScript has "Java" in the name for marketing reasons and no other.)

comment by KenChen · 2014-11-20T16:17:41.647Z · LW(p) · GW(p)

Strongly agree that you would have a much, much higher impact by making this game available on the web. Straight-up Java is pretty much dead now. Consider even making a Facebook app, which would allow players to share the game with their friends for stronger distribution.

comment by V_V · 2014-11-20T13:35:59.375Z · LW(p) · GW(p)

Your model of the world has been updated! The prior of the variable 'Monster Near The Academy' is now 0%.

Priors don't get updated, posteriors do. Moreover, if the posterior probability becomes 0, then you will be unable to recognize monsters afterwards, and you will not be able to further update your model for this variable. It looks like you are overupdating.

Replies from: Kaj_Sotala
comment by Kaj_Sotala · 2014-11-20T15:12:44.938Z · LW(p) · GW(p)

Thanks for the comments!

Priors don't get updated, posteriors do.

That's technically true, though it felt to me like such a common abuse of terminology that it could be allowed to slide. That said, if I just said "the probability of the variable", that would avoid the problem. (That probability may still be listed as a "prior variable" the next time it's used in a calculation... but then it's a prior for that calculation, so that's probably okay.)

Moreover, if the posterior probability becomes 0, then you will be unable to recognize monsters afterwards, and you will not be able to further update your model for this variable.

That's true, too. I was thinking that the belief networks aren't supposed to literally represent the protagonist's complete set of beliefs about the world, just some set of explicitly-held hypotheses, and she's still capable of realizing that something that she assigned a 0% probability actually happened. After all, the boy could have been looking in her direction because of something that was neither her response nor a monster, say a beautiful bird... which wasn't even assigned a 0% probability, it wasn't represented in the model in the first place. But it's not like she'd have been incapable of realizing that possibility, had it been pointed out to her - she just didn't think of it.

Replies from: abramdemski
comment by abramdemski · 2014-11-22T06:20:01.831Z · LW(p) · GW(p)

While I was reading it I got the impression that it was pointing at common mistakes, not just demonstrating correct behavior -- so the protagonist first sets the probability to zero based on naive trust (and because the player is not yet ready to handle an explicit model of the correctness of statements), but this gets corrected later in a realistic way.

If the game made a point of this sort of thing, it would give the (good!) impression that all examples in the game are approximations which need to be refined quite a bit to account for real-life details.

In hindsight, I see it's not doing this effectively. Perhaps when she finds out the kid was wrong she's like "Whoops! We just gave a probability of zero to something which then immediately happened!! That's just about as wrong as you can possibly get. We'd better account for that in our model." Or, something to that effect.

comment by NancyLebovitz · 2014-11-20T00:11:52.549Z · LW(p) · GW(p)

My first thought when the student said there were no monsters in the area was to wonder whether the student was trustworthy, though whether the student was correct would have been a better question.

comment by Articulator · 2014-11-20T00:16:38.541Z · LW(p) · GW(p)

This looks really interesting - do you have a timeframe on a playable demo, Kaj?

I sympathize with you on the Java - easier than most other methods, but oh god the lack of style. I think even just making those choice buttons a little less default (non-serif font, lose the blue shading) could move it a fair way toward being presentable.

My primary concern currently is that even if you have a robust engine to abstract much of the coding, this looks like it would have a very poor input to output time ratio. Do you have any plans for circumventing that, or do you have enough time to brute force it?

Replies from: Kaj_Sotala
comment by Kaj_Sotala · 2014-11-20T10:39:13.138Z · LW(p) · GW(p)

Hopefully within a few months: since this is for my thesis, I have the chance to work mostly full-time on this until next summer, though some of that time also needs to be spent on collecting data on test subjects and finding out whether they actually learn things from playing the game.

comment by CalmNearEnd · 2014-11-20T00:41:28.953Z · LW(p) · GW(p)

This idea seems amazing.

This is how envisioned the beginning should be:


???: “Hey there.”

Eep! Someone is talking to me! Is he another applicant, or a staff member? Based on my own school there were roughly 30 students in a classroom to the one teacher. So 30 to 1. Adding in other staff members such as janitors, secretaries, and the principal I'll say to 1 staff member to 24 students to makes the math nice. That makes my prior a one in twenty five chance for it to be a staff member before I turn around.

I’m guessing that applicant would look a lot younger than staff members! So, to find that out… I should look at him! I'll need to estimate how many students look old enough to be teachers and how many staff members look young enough to be students and I can update accordingly.


Or is this way too complex to start with?

Replies from: ArisKatsaris
comment by ArisKatsaris · 2014-11-20T10:22:28.646Z · LW(p) · GW(p)

Since in the immediately next part the protagonist assigns a 50% chance on a monster being behind her back (because she doesn't know for sure either way), I'm guessing that the concept of having reasonable priors is one which is supposed to get gradually introduced. This early on, the character's estimates seem to be tending to go from a false 50% to either a false 0/% or a false 100%.

So, yeah, what you suggest is probably too complex to start with.

Replies from: Kaj_Sotala
comment by Kaj_Sotala · 2014-11-20T10:25:37.863Z · LW(p) · GW(p)

You're absolutely correct.

comment by iarwain1 · 2014-11-20T16:41:08.084Z · LW(p) · GW(p)

I wonder if you could make this project open source and let other LW members contribute. This looks like a fun and possibly useful project that many in the community would be willing to contribute to.

Replies from: Kaj_Sotala
comment by Kaj_Sotala · 2014-11-20T18:08:21.103Z · LW(p) · GW(p)

https://github.com/ksotala/BayesGame

It's a mess, but feel free to poke around and laugh, and then improve it once you've finished laughing. Or to make your own competing game. :-)

comment by MockTurtle · 2014-11-20T10:33:06.144Z · LW(p) · GW(p)

This is a really brilliant idea. Somehow I feel that using the Bayesian network system on simple trivial things at first (like the student encounter and the monster fight) is great for getting the player into the spirit of using evidence to update on particular beliefs, but I can imagine that as you go further with the game, the system would be applied to more and more 'big picture' mysteries of the story itself, such as where the main character's brother is.

Whenever I play conversation based adventure games or mystery-solving games such as Phoenix Wright, I can see how the player is intended to guess certain things from clues, and ask the right questions to gain more crucial information, but having the Bayesian Network be explicitly represented in the game means the game is a lot simpler in some ways (you don't have to do all the updating in your head) but also introduces a different kind of challenge (the player can be shot down if ve tries to guess the answer to the mystery right away with too little data, and it becomes a lot more to do with which pieces of evidence that could be looked at could provide the most information). A growing vision in my mind of what a game like this would look like is making me quite excited to play it!

But I think I'm getting a little carried away. The game as an educational tool would probably quite different from a game which tries to make mystery-solving a challenge. Getting the balance right, to make it fun, might still be pretty challenging, I think.

As a side note, it'd be pretty awesome to use this system to show particular logical fallacies that people (either other characters, or the main character before applying proper probability theory) in the game could make.

comment by SilentCal · 2014-11-21T23:05:31.738Z · LW(p) · GW(p)

Hmm... so the following events need to successively introduce necessary concepts. Not sure when you want to incorporate 'do' operations; I'd guess a good bit later, once inference is well established (but I could also envision basic ones sooner). You might teach the player to navigate larger networks next, and introduce some simple decisions.

Maybe have a case where the node of interest is the majority vote of three nodes (N1, N2, N3). N1 is observable for cost 3, and is itself the majority vote of three nodes that are observable with cost 2. N2 is observable with cost 3, and is the deterministic is child of an observable node of cost 2. N3 is hidden. You have 5 actions.

ETA: Also want more complicated examples incorporating the collision-inference stuff from the expects-an-answer-or-is-looking-at-a-monster scenario.

comment by Stuart_Armstrong · 2014-11-20T15:40:29.276Z · LW(p) · GW(p)

Great!

comment by spatiality · 2014-11-20T08:21:11.765Z · LW(p) · GW(p)

That's awesome you are working on this!! I really would love to play it, with little regard to the outcome ( I pit it somewhere between quite interesting and totally super helpful) I wondered though whether you could make the player tally the probabilities himself and keep the scorings hidden yet allow taking notes ("hard mode"? and "hell" with no prior info on time limits? haha I can totally see being hit by the planning fallacy when trying to figure that one out for the first few times) I also imagine leaving the graphics away for now seems like the sane thing to do, even if you might want to think about it again after it is finished. Because of spreading the art.

Replies from: Kaj_Sotala
comment by Kaj_Sotala · 2014-11-20T15:13:53.065Z · LW(p) · GW(p)

I did think about something like the "hard mode" but left it out as infeasible right now. Maybe at some point. :)

comment by SilentCal · 2014-11-21T21:15:21.412Z · LW(p) · GW(p)

Looks brilliant!

Just read through your blog posts (indexed reasonably well on your mailing list at https://groups.google.com/forum/?fromgroups#!forum/the-fundamental-question), and I recommend the same to others, especially http://kajsotala.fi/2013/12/bayesian-academy-game-constraints/

EDIT: I've been able to answer most of my questions/concerns myself from reading those posts. Are they still accurate as to the end goal of the project?

Replies from: Kaj_Sotala
comment by Kaj_Sotala · 2014-11-27T16:12:53.211Z · LW(p) · GW(p)

Are they still accurate as to the end goal of the project?

Very generally speaking yes, but some of the more ambitious stuff (e.g. the elaborate social relationship mechanics) are likely to be left out from the version that I'm currently working on, since their direct educational value would be hard to justify to my supervisor. They might get in a later version, though.