Brute Force

Thinking some more about the Logic Games project, my first attempt is going to be brute force. Each of the statements in the logic game text can be converted into a series of Boolean rules (rules whose conditions either evaluate to true or false), and then I can create a rule engine to iteratively generate facts until the question has been answered.

Here's an example, taken from another LSAT question:

A piano instructor will schedule exactly one lesson for each of six students - Grace, Henry, Janet, Steve, Tom and Una - one lesson per day for six consecutive days. The schedule must conform to the following conditions:

1. Henry's lesson is later in the schedule than Janet's lesson
2. Una's lesson is later in the schedule than Steve's lesson
3. Steve's lesson is exactly three days after Grace's lesson
4. Janet's lesson is on the first day or else the third day

If Janet's lesson is scheduled for the first day, the the lesson for which of the following students must be scheduled on the sixth day - Grace, Henry, Steve, Tom or Una?

From this, we can generate a large number of Boolean rules to describe the problem. These rules will take the form of if ... then ... statements. Taking a look at the first condition - Henry's lesson is later in the schedule than Janet's lesson - we can derive the following rules:

• If Janet is in the fifth position, then Henry is in the sixth position.
• If Janet is in the fourth position, then Henry is NOT in the third position
• If Janet is in the fourth position, then Henry is NOT in the second position
• If Janet is in the fourth position, then Henry is NOT in the first position
• If Janet is in the third position, then Henry is NOT in the second position
• If Janet is in the third position, then Henry is NOT in the first position
• If Janet is in the second position, then Henry is NOT in the first position
• If Henry is in the second position, then Janet is in the first position
• If Henry is in the third position, then Janet is NOT in the fourth position
• If Henry is in the third position, then Janet is NOT in the fifth position
• If Henry is in the third position, then Janet is NOT in the sixth position
• If Henry is in the fourth position, then Janet is NOT in the fifth position
• If Henry is in the fourth position, then Janet is NOT in the sixth position
• If Henry is in the fifth position, then Janet is NOT in the sixth position

In addition, we can derive two facts from the first condition:

• Janet is NOT in the sixth position
• Henry is NOT in the first position

Then there are three types of additional rules that are implied for all combinations of person/position:

• If person A is in position X, then persons B, C, D, E, and F are NOT in position X
• If person A is in position X, the person A is not in any of the other positions
  
• If person A is NOT in positions 1, 2, 3, 4, or 5, then person A is in position 6

So, for example, we would have a set of rules for Henry like this:

• If Henry is in position 1, then Grace is NOT in position 1
  
• If Henry is in position 1, then Janet is NOT in position 1
• If Henry is in position 1, then Steve is NOT in position 1
• etc...

And

• If Henry is in position 1, then Henry is NOT in position 2
• If Henry is in position 1, then Henry is NOT in position 3
• If Henry is in position 1, then Henry is NOT in position 4
• etc...
  

And

• If Henry is NOT in position 1, and Henry is NOT in position 2, and Henry is NOT in position 3, and Henry is NOT in position 4, and Henry is NOT in position 5, then Henry is in position 6
• etc...

Once you have generated all of the rules, the way that the algorithm will work is to iterate over the rules deriving new facts. We start off with 1 fact: Janet is in position 1. So as we iterate over the rules, we can fire at least 10 additional rules that will derive new facts: Grace is NOT in position 1, Henry is NOT in position 1, Steve is NOT in position 1, Tom is NOT in position 1, Una is NOT in position 1, Janet is NOT in position 2, Janet is NOT in position 3, Janet is NOT in position 4, Janet is NOT in position 5, Janet is NOT in position 6.

After you make a pass across every rule, you start over at the top, testing each rule again given the facts that we derived from the previous pass, then continue until you have gathered enough facts to answer the question (in this case, Una is the correct answer).

Because this is a brute force approach, we get a lot of rules to test, so the algorithm will need to keep track of which rules have already been fired (i.e. which rules have a known answer), and on each iteration, only test the unfired rules.

Now, there is still a lot of hard manual work to do to solve this problem - for each condition, we have to manually break it up into a series of Boolean rules. So, in the long run, I will want to at least make some sort of DSL to allow me to put in the conditions in a more-or-less English syntax, and let the system generate all the rules for me. But let's call that phase 2 :-) For now, I want to focus on building the rule engine. I am looking through the book Constructing Intelligent Agents Using Java by Joseph and Jennifer Bigus. The fourth chapter, Reasoning Systems, outlines a rule inference engine that I am planning on using as a model for mine. Their engine does a lot of stuff that I don't need for mine, like accounting for fuzzy logic, so mine will be a lot simpler. Also, I'll be working in Ruby rather than Java, and I think that the dynamic nature of Ruby will also simplify the code quite a bit. So it isn't exactly a port of the Java code to Ruby, I'm just using it as a good starting point.

I hope to get started over the long weekend, and I'll stick my code up on Github.

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!

Welcome to Jason's Blog

Hello! Welcome to Jason's blog!