Logic Games Project

Lately I've become interested in knowledge representation as it applies to computer science. I'm no expert on the subject. The opposite, really. But interest is a good place to start, I guess. So, I wanted to start a project that would give me a good excuse to really explore the topic.

I've been following Ola Bini's blog, and he's had a really interesting series of posts where he has been porting the code from Peter Norvig's book, Paradigms of Artificial Intelligence Programming, from Common Lisp to Ruby. I've been sitting on that book for a couple of years now, and every time I pick it up, my lousy Lisp skills get in the way, and I eventually drop it. But having Bini's Ruby code to compare it with has re-inspired me to pick my way through it again.

One of the things that really stands out with early AI research is how AI is defined. The Turing Test is one of the best known intelligence indicators. It goes like this: A human participates in two conversations, one is with another human, and the other is with a computer program. If the person can't tell the difference between the two, then the computer program has demonstrated intelligence.

There's a competition every year where programmers try to pass the Turing Test. No one has won yet, but people are coming close. What I really find interesting about it, though, is how people are coming close. If you look at some of the code that is producing human-like conversations, you find that a lot of it doesn't seem "intelligent" at all. At least not in the way that we intuitively think of "intelligence" - it has no understanding of the conversation. Take a look at Eliza, for example. Eliza is a very early attempt (1966) to pass the Turing Test. Eliza basically looks for patterns in the human statements and maps those patterns to responses. As a simple example, you might say to Eliza, "I want a new car" and Eliza's response might be "What would it mean to you if you got a new car?". So "I want X" gets mapped to "What would it mean to you if you got X?".

This is obviously a very simple example, Eliza is capable of a lot more complexity, but it is still pattern matching, not understanding. In addition, Eliza is 40 years old - a lot has happened in AI in the last 40 years. However, thinking about this approach to passing the Turing Test got me thinking about other measures of intelligence, and whether or not it would be possible to solve various intelligence tests programmatically without actually achieving what the average person would intuitively know as "intelligence". So here's what I landed on: I want to try to solve certain types of standardized test questions. Specifically the type of logic games you find on the LSAT and GRE.

Here's an example (pulled from an old LSAT):


Seven consecutive time slots for a broadcast, numbered in chronological order 1 through 7, will be filled by six song tapes - G, H, L, O, P, S - and exactly one news tape. Each tape is to be assigned to a different time slot, and no tape is longer than any other tape. The broadcast is subject to the following restrictions:
  • L must be played immediately before O
  • The news tape must be played at some time after L
  • There must be exactly two time slots between G and P, regardless of whether G comes before P or whether G comes after P
If G is played second, which one of the following tapes must be played third?
  • The news
  • H
  • L
  • O
  • S
The way I see it, there are two major parts in solving something like this programmatically. First, you have to parse the English language into some sort of knowledge system that your software can understand, then you need to use that knowledge to infer an answer. For the moment, I am going to concentrate on the latter. For two reasons: I need to know what type of knowledge representation I am going to end up with before I can start trying to parse the English, so this seems like the better place to start, and it's the part of the problem I find more interesting (and more attainable...)

So there you have it. That's my project.

For a while I am going to solve a bunch of logic games manually to start picking out patterns. I'll post the more interesting ones, and what I learned from them. Once I start getting some code written, I'll post that as well.

I have a bad habit of getting really interested in a project for a short while, and then dropping the ball. I'm hoping that committing to it here will keep me honest. As long as there's a chance (however unlikely) that someone is reading this, I'll be shamed into finishing the project ;-)

More to come soon!