clue solver!
Mood: nervous
Posted on 2007-08-21 13:36:00
Tags: projects cluesolver
Words: 448

When I was growing up¹, I didn't play Clue much. There was that game where we drew three random cards for the solution and ended up with two weapons or something like that. We never played with the rule that if you suggested someone they moved into your room, or that your suggestion had to include the room you were in (I think). And I remember at least one game where everyone showed you a card instead of just one person. My strategy was always to simply mark off cards I had seen, which was not terribly successful when I started playing with friends who played with the "real" rules.

I finally figured out (or refigured out? maybe I knew this before? my memory - unreliable...) a better strategy on this last visit to Austin, which is to use the information about if other people have certain cards or not. So for every suggestion that someone makes, when someone passes I write down on each of those three cards that that person doesn't have them, and when someone shows a card I write down that they have one of those three cards, and using that information you can learn a lot. The last game I played I didn't win, but I was pretty close to knowing what the solution was.

So, I thought it would be a fun project to write a Clue solver - that is, something on which you indicate the information you see (Mary made the following suggestion and it got passed around until John showed a card) and it deduces everything it can from that.

My current approach is to specify rules in first-order logic and use some sample code from my old AI book (AIMA) to figure things out. Unfortunately, the rules don't lead to definite clauses, so I think forward chaining is out. I've been trying to use resolution, but it doesn't work right and is slow. Maybe I'll try backward-chaining instead. If I have to I'll break down and write Clue-specific code to figure things out but it would be really awesome if I can get it working just by specifying the correct rules.

If you're following along at home in your copy of AIMA, I've been reading a lot of Chapter 9. :-)

I found this class project to do something similar (here's the project description (pdf)) which has a good explanation of resolution and the rule-based approach, although they seem to be using propositional logic and not first-order logic. Which might be what it takes to make it work in a reasonable amount of time.

----
¹ - I fully expect wonderjess to correct me here since my memory is pretty horrible. (back)

7 comments

Comment from tehfanboi:
2007-08-21T14:00:01+00:00
I like clue, but am horrible at it. If you need test subjects I volunteer.

Comment from djedi:
2007-08-21T15:16:55+00:00
Ooo, I think you just volunteered for some clue games once we're back in Austin.

Comment from wildrice13:
2007-08-24T17:12:49+00:00
He did, I saw it!

And I will join in as well :)

Comment from kernelm:
2007-08-21T15:37:56+00:00
Oh god, Clue. I've only ever played it once, and it was at camp. At Bamberger Ranch, actually. (You know, I was all about to say math camp and mention something about how "yes, I did go to math camp" before I remembered who I was commenting to. :-P )

I totally hated it. I was horrible. Haven't played it since.

BTW, I've somehow become addicted to Scrabble on Facebook. *headdesk* There really needs to be a Brettspielwelt app on Facebook so I can play Carcassonne or Citadels all day. *g*

Comment from gregstoll:
2007-08-21T16:13:25+00:00
You should definitely try it again while writing down the propositional logic statements. It's fun!

Yikes, you can play Scrabble on Facebook? I've kinda been shunning it as a walled garden. Or maybe I'm just bitter I couldn't do the neato apps I wanted...

Comment from wonderjess:
2007-08-21T16:51:17+00:00
haha, I can correct nothing. I don't remember much about playing Clue -- just that we use to gesture emphatically with the tiny weapons and say "it was PROFESSOR PLUM in the LIBRARY with the REVOLVER" (or whatever) with great dramatic emphasis>

Comment from brittongregory:
2007-08-22T12:06:12+00:00
You might have come closer to winning if everyone had correctly passed/not passed. As it is, there was some faulty data. Throw *that* into your solver and smoke it!

This backup was done by LJBackup.