More Logic Games

The two position-based logic games (broadcast and piano_instructor) are working correctly now, with all rules and facts coming from the DSL, including the rules inferred by the combination of other rules.

It ain't pretty though... The inference of rules is very non-generic, and very spaghetti code-ish. I really just wanted to get the logic straight in my head first. I'll look at pretty-ing it up next. But it works! Better to have ugly, but working code today, right?

Logic Games: Almost There!

Made a bit more progress on the Logic Games project today. I have all of the rules for both the broadcast game and the piano instructor game set up generically, so that all of the base rules are specified in the DSL. Here's an example, taken from the broadcast game:

new_game
called "Broadcast"
described_as("Seven consecutive time slots... etc")

with_property "Position"
with_range 1, 7
for_entities "G", "H", "L", "O", "P", "S", "News"

new_question
described_as "If G is played 2nd... etc"
with_fact "G", "Position", :is, 2
determines ["News", "H", "L", "O", "S"], "Position", :is, 3

#L must be played immediately before O
new_rule "L", :before, "O", 1
#The news tape must be played at some time after L
new_rule "News", :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
new_rule "G", :separated_by, "P", 2

evaluate

That generates almost all the facts and rules for the game. There are a few rules that are implied by the combination of these rules - since "O" is immediately after "L", and "News" is sometime after "L", then "News" must be at least 2 after "L". So that's next: figure out how to imply rules from combinations of explicit rules.

The Start of a DSL

I've started refactoring my logic games into a DSL that more closely approximates the English language logic games questions. Here's what I have so far:

#Set up game description
new_game
called "Broadcast"
described_as(
"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"
  

)
with_property "Position"
with_range 1, 7
for_entities "G", "H", "L", "O", "P", "S", "News"

#Create the questions
new_question
described_as "If G is played second, which one of the following tapes must be played third?"
with_fact "G", "Position", :is, 2
determines ["News", "H", "L", "O", "S"], "Position", :is, 3

This replaces the first 70 lines of the game. It sets up the game, and adds all the standard rules, like one-place-at-a-time rules, mutual-exclusion rules, and last-available-position rules.

My goal was to make this read more or less like the English version of the game. One interesting requirement for that has been that it needs to remember context. So if I say "new_question" on one line, then "described_as ..." on the next line, the game needs to remember that "described_as" applies to the new question we just created. I'm doing this by maintaining state. So each action keeps a record of the thing it acted upon, so that the next action knows what the context is. The alternative was to string together actions, like "new_game.described_as(description).with_fact(...)" etc. I didn't like that approach because it looks less like English, which was, again, my goal.

The next step in the DSL will be a simple way to specify the rules. I want it to be close to the English version of the rule, so

"Henry's lesson is later in the schedule than Janet's"

might turn into something like

new_rule "Henry", "Position", :after, "Janet"

Which will then get broken up into the 20 or so rules that that implies behind the scenes.

Victory!

The Logic Games project now officially solves its first game! It's admittedly a pretty manual process right now. I still have to break the logic game up into all the initial rules and facts. But then it successfully runs through the rule engine and generates all the facts that can be inferred, and answers the question.

Here's the game it solves right now:

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

If you grab the code from github, and run

ruby logic_games.rb games

it will correctly tell you L is in the 3rd position.
Yay!

It was interesting to me that there were a lot of rules that I was using intuitively when I solved the problem by hand, but that I neglected to add to rule base because I never explicitly acknowledged the rule in my head. An example of this is the rules and facts generated by the combination of the fact that L must be played immediately before O, and the News must be played some time after L. What that implicitly means is that the News must be at least 2 slots after L, because the slot immediately after L is taken up by O. These types of rules will be the hardest to generalize, because they need to take external knowledge (previous statements) into account.

So the next step is to start generifying the logic for creating rules and facts. I would like to come up with some sort of DSL for specifying knowledge in a way that approximates the written game statements. So, for example, to specify that L must be played immediately before O, you might have something like

"L".before("O", 1)

which would translate into "The entity with the name of 'L', must be positionally before the entity named 'O', by 1 position." This would then generate the 20 or so rules that this implies, like "If L is in position 1, then O is in position 2", etc.

So, to accomplish this, I'm going to work on implementing several other games so I can start getting a feel for the types of generalizations I'll need to implement. Then I'll go from there.

Good times.