Einstein's Puzzle

From OpenCog

Jump to: navigation, search

Einstein's Puzzle is a logic puzzle that takes considerable deductive reasoning ability and deductive powers to solve. Creating the structure needed to solve it by machine is useful for illustrating the challenges facing a general problem-solving system.

Contents

Description

There are many descriptions of the puzzle on-line:

Why?

Einstein's Puzzle is a riddle which requires applying some common-sense reasoning and using logical deduction. It is a bounded problem, but is not all that small: approximately a dozen common-sense rules must be applied to fifteen facts in order to obtain a solution. The challenge is then two-fold:

  • Express the facts in as "natural" a fashion as possible, so that they are close to how they might be expressed in the English language. The point here is that it is relatively straight-forward to use a natural language parser (e.g. RelEx) and have that generate fairly uniform logical statements (e.g. RelEx2Logic)
  • Express the deductive rules in a "common-sense" fashion. Again, these should be close to a natural form: e.g. "If A is a neighbor of B, then B is a neighbor of A"

Hand-crafting the above sets of facts and rules is a challenge; its not something that can be done in an afternoon. Performing this exercise exposes a number of issues that must be dealt with in general problem solving. The exercise is worthy, as it illustrates just how hard common-sense puzzle-solving can be.

Note, however, the challenge for the computer is rather different than the challenge for the human. Given a set of deductive rules, the computer can very rapidly explore all of them, to obtain an answer. By contrast, a human thinker is quite slow in progressing from one mode of deduction to another. There's also another contrast: the human can rapidly draw on a large bank of common-sense knowledge (e.g. facts about neighbors, the fact that a house can have only one occupant, etc.) By contrast, the computer has no innate, common-sense logic, and the challenge is to provide enough deductive rules that can be applied to obtain an answer.

Constraint satisfaction

The puzzle is an example of a "constraint satisfaction problem".  What this means is that naive forward reasoning is not enough to solve the problem (where 'naive forward reasoning' is the application of deductive rules to facts; so for example, given the fact 'the green house is next to the white house' (expressed as a couple of EvaluationLinks) and a deduction rule 'if X is next-to Y then Y is next-to X' (a relatively basic BindLink), one may deduce that 'the white house is next to the green house'.) 

That is, simply applying deduction rules to existing facts, to generate yet more facts, is not enough to solve the problem, at least not in the naive way.

To solve a constraint satisfaction problem, one must generate a set of hypothesis, and discard those that fail to be consistent with all of the rules and facts. So, for example, one generates the hypothesis: 'the Brit lives in 1st house', 'lives in 2nd house', '3rd', '4th', '5th'. For each of these hypothesis, one must and then recursively apply all rules, and validate against all facts. If a contradiction is found, the hypothesis must be judged false.

For 'crisp logic' facts and rules, high-performance, efficient constraint satisfaction solvers are known. Most of these are based on the DPLL Algorithm, such as the solvers for Answer Set Programming (ASP) and Satisfiability Modulo Theories (SMT). The challange for OpenCog is to develop a set of algorithms that work reasonably efficiently for probabilistic logic, and approach the performance of the DPLL algorithm when the facts and rules are know with high probability to be true or false.

Status

Several variants are have been partially developed in opencog. One is based on the action planner; another uses simple deduction, using the pattern matcher. A tutorial on how to solve this puzzle using OpenCog is under development: see Einstein's Puzzle Tutorial. Note that this tutorial is very incomplete, and ahem, probably needs a major overhaul.

The EinsteinUTest is a unit test for the pattern matcher, and currently provides the most complete demonstration of solving the puzzle. The facts can be found in the file test/query/deduct-einstein.scm and the "common-sense" deductive rules can be found in test/query/deduct-rules.scm.