Posts on August 21, 2007
clue solver!
Mood: nervous
Posted on 2007-08-21 13:36:00
Tags: projects cluesolver
Words: 448
When I was growing up1, 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.
----
1 - I fully expect wonderjess to correct me here since my memory is pretty horrible. (back)
it all seems more real now
Mood: bouncy
Posted on 2007-08-21 17:16:00
Words: 10
I told my coworkers I'm leaving. It went pretty well.
This backup was done by LJBackup.