clue solver redux!

After revamping gregstoll.com to support SSL, I spent some time looking at all of my projects and making sure that they still worked with SSL. Turns out most of them didn’t! (although the fixes were generally pretty quick)

That led me to revisit the Clue Solver, which seemed to have partially broken since I wrote it almost 10(!) years ago, probably because I used an ancient version of the Google Web Toolkit.

So I rewrote the UI from scratch using React, which I’m trying to get more experience in and is just generally a really nice Javascript framework. And now it’s done! Here’s the new version, and here’s the original one.

clue solver done!

So we played another game of Clue yesterday with wildrice13 and abstractseaweed and despite the fact that the clue solver declares it inconsistent, I’m going to be optimistic and assume I wrote something down. Also fixed a few bugs and added a special case for a weird situation that came up. (I knew David had Conservatory or Ms. White, and Andrew had Conservatory or Ms. White, so no one else can have either of those cards) Thinks like that would have made using first-order logic or propositional logic nicer (since it would have presumably taken care of them automatically), but oh well.

Thus, I am declaring the Clue Solver done! Put a few example games up so you can load them and see how they work. (and the pretty colors on the simulation tab!) Been working on it for a while so it’s nice to have it done. I’ll take a little while off (what with starting work and all) and see what I feel like doing next. I do feel like I got a decent handle on the Google Web Toolkit, so that’s nice.

shirts I want, internet options

Dumbledore is gay! And shirts to match.

I still want this WiFi detector shirt but I feel a little bad spending money when none’s coming in yet.

Speaking of computer stuff, we have Internet through Time Warner and it seems to go down reasonably often. But not really down – often just resetting the cable modem will restore things to normal. Hence my idea for a robot that can detect when I can’t reach the Internet (easy) and reset the cable modem (hard unless there’s some software way to do it, which I doubt).

So I looked into alternatives. Grande Communications doesn’t recognize our address, AT&T/SBC/Yahoo/whatever DSL doesn’t service our address, and Verizon DSL (I hate Verizon because of how difficult it was to cancel local phone service in MD, but whatever) finds a lot of different streets named Austin (our street is Austin Center Blvd) in various cities around here even though I put in the freaking zip code. GG verizon. So I guess we’re stuck until I build a robot or someone reminds me of some other company I forgot.

Very stuck on simulations in clue solver, going to try to let it go for a few days and come back to it. Frustrating because I’m so close to done.

insomnia

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 🙂

lapping it up

I got a laptop! It’s a 17" MacBook Pro and it’s pretty sweet. I was feeling kinda blah yesterday, partially from guilt with spending money when we haven’t started working yet, partially from the lousy overcast weather, and partially from not quite knowing what to do with myself. Obviously in two weeks when we’re working I’ll long for these days of endless free time, but it’s kinda like when you’re cold you can’t imagine what it feels like to be hot, and vice versa.

But I can’t stay grumpy for like in the face of new toys, so I’m feeling better. Been setting up stuff, got WoW and Ventrilo installed (I can push to talk now!), and I’m feeling more in the mood to work on the clue solver – right now I’m adding the ability to gain information by knowing how many cards each player has.

Hope everyone’s having a nice week. Has anyone seen any good movies lately? We’d like to see something at the Alamo Drafthouse but I’ve heard very little about what’s playing. Also, Netflix is fun.

cluesolver, pictures

Look, the subject is the same as the tags!

After my last post about putting the clue solver on hiatus, I couldn’t get to sleep Saturday night so I got up, played a little WoW, and, in a flurry of inspiration, sketched out a clue solver GUI. It’s not beautiful, but it seems relatively functional and easy to do with the GWT parts. I’ve coded up most of it and I’m on to writing the script interface functions and hooking it all together. This makes me a happy man!

I (at long last) have put up pictures from the trip down and a few random ones.