Tag cluesolver (14)
clue solver done!
Mood: proud
Posted on 2007-10-28 16:59:00
Tags: projects cluesolver
Words: 185
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
Mood: okay
Posted on 2007-10-23 10:46:00
Tags: cluesolver
Words: 211
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
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 :-)
lapping it up
Mood: content
Posted on 2007-10-17 15:01:00
Tags: mac computer cluesolver
Words: 180
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.
computer >> me
Mood: allergy-y
Posted on 2007-10-09 17:21:00
Tags: cluesolver
Words: 28
It's an encouraging sign when you write a new feature and try to test it and the test cases fail because you put the wrong expected result - twice!
cluesolver, pictures
Mood: cheerful
Posted on 2007-10-08 15:35:00
Tags: pictures cluesolver
Words: 106
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.
my problem is...
Mood: mellow
Posted on 2007-10-05 23:51:00
Tags: cluesolver
Words: 240
Just kidding! (I have multiple problems, of course)
A problem of mine is that I can have trouble living in the moment. When I'm experiencing something I enjoy my thoughts wander to making the experience permanent somehow - buying a souvenir of a trip, arranging another get-together, buying the DVD when it comes out of a movie I'm watching. Even though I know a lot of the fun is tied up in the particular experience I'm having then (and watching a movie the second and third time is rarely as good as watching it the first), I naively try to capture it. Unfortunately, no DVD can capture the people I'm with, the anticipation of the event, the people I'm with. (except maybe Blu-ray?) And letting my thoughts wander in this direction can actually take away from the experience. Letting go and just realizing that I'm enjoying myself is worth the while.
I'm declaring a hiatus on clue solver work - every time I try to sit down and work on the UI I just can't. It's as bad as writing English papers back in college. If I were just trying to get it done I'd start over and do it in Javascript, but part of the point is learning about Google Web Toolkit. (I'm learning that I like and know Javascript better than Java, but oh well) Maybe I'll sketch out some mockups and pick it up in a week or so.
nightbane down!
Mood: tired
Posted on 2007-10-01 10:56:00
Tags: worldofwarcraft cluesolver
Words: 332
The night started poorly with two people getting locked outside of Netherspite's room and people being kinda cranky in general. However, we downed him on the next attempt and killed the Prince after a few attempts. (oh, and the free loot from the Chess Event) We had grinded up our Thrallmar rep so we could run Heroic Shattered Halls and summon Nightbane for the first time.
Nightbane, despite what I read somewhere, is not about as hard as Prince - he (?) is much harder. The tricky parts for us caster DPS in the ground phase are mostly avoiding the Charred Earth (or moving out of it when it hits your spot) and trying to stay out of the AoE fear. The air phase is tough - we finally figured out to collapse on the tank, wait for the Rain of Bones, then move back to where we were standing and kill the skeletons, and stop doing anything when Nightbane lands to avoid pulling aggro (this happened a lot). Oh, and don't stand too far apart when killing the skeletons otherwise you get the Fireball barrage. The landing is definitely the trickiest part - at first we would always wipe on landing or shortly thereafter.
Anyway, on something around our 12th attempt (anyone have a more accurate count?) we finally got him. There were a few close calls before that - got him to 14% a few times before - so I had hope, but man is it tough.
I got two pieces of loot for the night (T4 helm and Jewel of Infinite Possibilities) so I'm pretty happy.
Finally got started working on the Clue Solver again and I made some progress on the GUI for once. Figuring out parts of the Google Web Toolkit - I guess it's neat to wrote JavaScript code in Java but I'm a lot more comfortable in JavaScript (and not so comfortable in Swing-like GUIs) so it's not hugely efficient. Maybe it's more of a win on bigger projects or something.
baseball, WoW, MacBook Pro?
Mood: irritable
Posted on 2007-09-18 11:22:00
Tags: worldofwarcraft cluesolver links
Words: 370
I got a link from a Houston Chronicle blog ("The Unofficial Scorer") - I'm "this little toy"! Of course this is terrible timing since my website will be going down in a few days for a weekish.
djedi sorta convinced me to get me a MacBook Pro which I've been talking about/considering for a while now. Maybe once MacOS 10.5 comes out. It would be nice to play WoW on an officially supported platform - I'm getting paranoid that a patch will come out and break me somehow and make me cry. Also, Macs are neat.
Wow recap:
Next we tried Terestian Illhoof. He is tough. The first time I AoEd the imps way too early and ran out of mana in like 30 seconds, and we couldn't DPS the Demon Chains down quickly enough so people died left and right. I managed my mana better after that, but we still couldn't DPS the Demon Chains enough and we didn't make significant progress. Not sure how we're going to handle that but eventually we just moved on. Did the Chess Event, no problem - fun and easy!
Our last boss try for the night was Netherspite - we had tried him before briefly, but we had a better idea of portal management, etc. After a few tries we really started to get the hang of it - got him down to 17% on our last try before people had to go. I started using consumables a lot, so I need to pick me up some more of those...
I'm still working half-heartedly on the clue solver, but I need to sit down, concentrate, and design a UI for the webpage. I've been too busy and way too unfocused to do so.
me 1, logic 0
Mood: chipper
Posted on 2007-09-11 09:24:00
Tags: cluesolver
Words: 58
I almost entirely finished the clue solver backend last night, my second day of working on the new approach, and it works correctly and quickly. Take that, first-order and propositional logic!
Started looking at GUI stuff but I really doubt I'll have it done before we disconnect our cable modem here. Something to do in October, I guess :-)
if music be the food of love
Mood: nervous
Posted on 2007-09-10 09:59:00
Tags: worldofwarcraft cluesolver
Words: 261
I felt fairly blah on Saturday, feeling a real lack of drive and not wanting to do anything or start anything. I expected to be plunged more into blahness yesterday since djedi was leaving, but listening to music I don't get to at work while I read a good book (Three Fortunes in One Cookie - highly recommended!) helped a lot.
In the evening I had football on while I totally rethought my approach to the clue solver. The whole specifying everything in terms of logic just wasn't working at all, and I didn't want to give up on it, so I'm rewriting things to do my own inference, etc. It actually doesn't look that hard and I can take advantage of the fact that some things are much easier for me to understand (one and only one suspect did it) than to specify it in propositional logic, which is what I was down to.
Spent the remainder of the evening installing Galleon and getting rid of my way old program for listening to music on the TiVo. (which didn't shuffle playlists at all) It took me a while to get it working correctly for who-knows-what reason, but it works now.
Kara run was pretty successful - we downed all the stuff we had earlier, plus Curator (hard fight!) and the Chess Event. (which, as Sepp said, was "free loot!") Took a shot at Netherspite for fun and he (it?) kicked our collective asses, finishing at 100% thanks to crazy portals and beams and whatnot.
djedi's interviewing at NI today - wish him luck!
two weeks to yuma...i mean austin
Mood: cheerful
Posted on 2007-09-07 09:37:00
Tags: travel cluesolver
Words: 194
We leave two weeks from today! Here's the route we're planning to take, going 6, 8, 8, 4 hours per day, stopping for the night in Ohio, Missouri, and somewhere close to the border between Oklahoma and Texas.
Things are coming together for the move. I'm going to finalize the movers today (going with Bekins), djedi's car is all set up to magically reappear down there, etc. Wish it would just hurry up and happen now. Two weeks isn't too bad though.
We raid Karazhan again tonight! I have high hopes.
The clue solver is not going well. I rewrote it using just propositional logic (no first order logic) last night, and it still gets stuck on very simple queries. I think I may have screwed up the resolution algorithm as it deduces all sorts of unhelpful things, so I guess I'll look at that next. If all else fails I could always just do the Monte Carlo-like simulation omega697 suggested, but I'm going to be disappointed if I can't actually prove things. Oh well.
For the clue GUI I'm thinking of trying out the Google Web Toolkit (GWT) to make a spiffy interface.
a big apple a day...
Mood: cheerful
Posted on 2007-08-23 10:21:00
Tags: cluesolver
Words: 207
(can't think of any other aphorisms with "apple"...I'm open to suggestions...)
NYC trip today - for some reason I wasn't really excited about it earlier this week (generally kinda blah), but I'm really looking forward to it. Train trips are fun!
As Fire Joe Morgan points out, the Orioles lost to the Rangers 30-3 (after being up 3-0)...and the Rangers pitcher earned a save.
I've been stalling on my clue solver because the first-order logic stuff isn't working out. One problem is that I chose to define equality as any old relation (adding the rules "Eq(x,x)", "Eq(x,y)=>Eq(y,x)", "(Eq(x,y)&Eq(y,z))=>Eq(x,z)" and rules for every other function that equality preserves it), but this makes the resolver build up a huge list of useless sentences.
So I've been thinking about it, and I think I am going to go the more propositional route, since there are a very small number of people and cards, and using relations like "Player(x)" and "Card(x)" leads to more complicated sentences and seems to give the resolver trouble. I'd still like a concise way to maybe specify the first-order logic rules using those relations but then expanding them out to all the possibilities, but this seems tricky at best. I'll think about it on the train trip :-)
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)
This backup was done by LJBackup.