insomnia
Mood: awake
Music: Lager Rhythms - "MLK" (IMH)
Posted on 2007-10-22 01:41:00
Tags: logic cluesolver
Words: 649

So for the second time in a week I find myself unable to sleep. I would be more worried except that (as a mostly-awake djedi pointed out) we slept until 1 today, so it's not too surprising.

As long as I'm up, some thoughts on the clue solver:

In general it's coming along very nicely. The reason we slept until 1 today is that we stayed up late with quijax and wildrice13 playing Clue and watching the movie Clue, which was great fun. Point being, I got two games of data (in which I wrote down all my cards and every suggestion made) to test it on. After actually making the effort to enter an entire game (eating my own dogfood!) I found that it did technically work. Oh, except I entered one entry wrong the first time and I had no idea until I got to the end and didn't get the right result. So now there's undo and a history tab showing every piece of information that has been entered. That makes things a lot less painful.

An deduction algorithm problem: You often have information of the form "Player 1 has at least one of the cards {Professor Plum, Knife, Lounge}" (from observing someone else's suggestion). Now that I'm requiring the user to enter how many cards each player has, so you can do some nifty inferences from that. For example, if you know Player 1 has two cards and has at least one card from each of the following sets:

{Professor Plum, Knife, Hall}
{Professor Plum, Candlestick, Conservatory}
{Professor Plum, Revolver, Dining Room}

you can deduce that Player 1 must have the Professor Plum card. The way I'm currently making deductions like this is to, for each card, assume that they don't have it and see if there's any way to satisfy all of the sets given the number of cards they have. In this case, they can't, so by contradiction they must have the Professor Plum card.

This is all well and good, but this algorithm doesn't cover more tricky things you can do. For example, if Player 1 has two cards and at least one from each of the following sets:

{Professor Plum, Knife, Hall}
{Professor Plum, Knife, Conservatory}
{Professor Plum, Knife, Dining Room}

we can deduce using similar logic that Player 1 must have Professor Plum or Knife, but the algorithm above doesn't pick up on that. In this particular application we're OK because if we ever determine that Player 1 doesn't have Knife, we remove it from all the sets above and then can figure out she has Professor Plum, but it's an interesting problem in general. (it's kind of like finding a vertex covering of a generalized graph where the vertices are the cards and the "edges" are the sets)


Anyway, the other major feature that's left is doing simulations to determine the probability of players holding certain cards. (for example, if Player 1 had three cards and the first three clauses, it's pretty likely that she has Professor Plum even though it's not guaranteed) I was going to take a stab at this tonight but I'm losing steam. My idea is to iterate over all possible solutions, and do 500 trials per solution (or whatever). For each trial, somehow assign the cards to each player, making sure that we give them the ones we know they have and not to give them the ones we know they don't have (doing this without somehow biasing the results is the hard part it seems), then seeing if that distribution of cards conforms to everything we know about. (i.e. the clauses above) If so, record that, and if not, throw it out. But you can't keep trying until you get the same number for every solution, because that biases the results.

If anyone is more clearheaded about this last paragraph, let me know :-)

This backup was done by LJBackup.