CREATIVE SOLUTIONS TO PROBLEMS

John McCarthy Computer Science Department Stanford University jmc@cs.stanford.edu

http://www-formal.stanford.edu/jmc/ started April 1, 1999; compiled May 18, 1999

Almost all of my papers are on the web page.

APPROACHES TO ARTIFICIAL INTELLIGENCE

biological—Humans are intelligent; imitate humans observe and imitate at either the psychological or neurophysiological level

engineering—Achieve goals in the world—so study the world

1. Write programs using non-logical representations.

2. represent facts about the world in logic and decide what to do by logical inference

We aim at human level AI, and the key phenomenon is the common sense informatic situation.

THE COMMON SENSE INFORMATIC SITUATION • Contrasts with the situation in a formal scientific the-

ory and most AI theories. Science is embedded in common sense.

• No limitation on what information may be relevant. Theories must be elaboration tolerant.

• Needs non-monotonic reasoning.

• Needs approximate entities.

A LOGICAL ROAD TO HUMAN LEVEL AI • Use Drosophilas that illustrate aspects of representa-

tion and reasoning problems.

• Concepts, context, circumscription, counterfactuals, consciousness, creativity, approximation

• narrative, projection, planning

• mental situation calculus

IDENTIFYING CREATIVE SOLUTIONS TO PROBLEMS

• domain dependent control of reasoning • Making creative programs will be hard.

• Making a program that will recognize creativity is easier but still too hard for me now.

• Distinguish the idea of a solution from the solution itself.

• I can identify, thinking by hand, creative solutions.

• I can sometimes express the creative idea by a logical formula.

• The Drosophila for this research is the mutilated checkerboard problem.

• As much as possible, an idea should be one thing, and it should be promising in itself.

• I know four creative solutions to the mutilated checkerboard problem, the standard solution, Marvin Minsky’s solution, Shmuel Winograd’s solution and Dimitri Stefanuk’s 17 similar solutions.

• I tried to express each idea as concisely as was compatible with leading a person to the solution.

THE MUTILATED CHECKERBOARD

7

DOMINO MUTILATED CHECKERBOARD

THE STANDARD SOLUTION

What’s the idea of the solution that a creative person or program may come up with? This is distinct from giving the detailed argument. English first—then a formula. Color the board as in a checkerboard. A domino covers two squares of the opposite color. Some people also need that the removed squares are of the same color.

THE COMMON FACTS IN SET THEORY

Board = Z8 × Z8,  (1)

mutilated-board = Board − {(0, 0), (7, 7)},  (2)

\begin{matrix}domino-on-board(x) ≡ (x ⊂ Board) ∧ card(x) = 2 \\ ∧(∀x1 x2)(x1 ≠ x2 ∧ x1 ∈ x ∧ x2 ∈ x \\ → adjacent(x1, x2)) \end{matrix}  (3)

\begin{matrix}adjacent(x1, x2) ≡ \\ |c(x1, 1) − c(x2, 1)| = 1 ∧ c(x1, 2) = c(x2, 2) \\ ∨ \\ |c(x1, 2) − c(x2, 2)| = 1 ∧ c(x1, 1) = c(x2, 1). \end{matrix}  (4)

\begin{matrix}adjacent(x1, x2) ≡ \\ |c(x1, 1) − c(x2, 1)| + |c(x1, 2) − c(x2, 2)| = 1, \end{matrix}  (5)

\begin{matrix}partial-covering(z) \\ ≡ (∀x)(x ∈ z → domino-on-board(x)) \\ ∧(∀x y)(x ∈ z ∧ y ∈ z → x = y ∨ x ∩ y = \{\}) \end{matrix}  (6)

Theorem:

¬(∃z)(partial-covering(z) ∧ ⋃ z = mutilated-board)  (7)

Makers of automatic or interactive theorem provers often don’t like set theory because of the comprehension principle. They had better get used to it.

THE UNMATHEMATICAL REQUIRE MANY HINTS • Take into account the colors.

• What are the colors of the diagonally opposite corner squares?

• How many of each color does a domino cover?

• How many of each do n dominoes cover? huh?

• What about 7 dominoes?

• How many of each do n dominoes cover? Equal.

• Two blacks left over, but maybe a more clever person ….

MARVIN MINSKY’S IDEA

Starting with the two square diagonal next to an excluded square, successively compute how many dominoes must project from each diagonal to the next diagonal.

• Good enough hint for a horse doctor.

• Not a sentence, but a program fragment—without a termination condition.

SHMUEL WINOGRAD’S IDEA

• Note that an odd number of dominoes project from the top row to the second and continue.

• A movie showed a math teacher rejecting this idea and Socratically leading the student to the standard solution.

• Winograd showed the student was on the right track, but most people need something like

• Starting with the top row, compute the parity of the number of dominoes projecting down out of each row. Consider the parity of the sum. Repeat going horizontally. Compute the parity of the total number of dominoes compared to the sum of the two parities.

DIMITRI STEFANUK’S IDEA

The idea seems to involve two program fragments.

Label an arbitrary square 1, label its rectilinear neigbors 2, their neighbors 3, etc.

Starting with n = 1, successively compute how many dominoes must project from the set of squares labelled n to the squares labelled n + 1.

FORMULAS FOR MINSKY SOLUTION

diag(n) = {x ∈ Board|c(x, 1) + c(x, 2) = n}

covering(u) ≡ partial-covering(u) ∧ ⋃ u = Board

covering(u) ∧ 2 ≤ n ≤ 13 → dominoes-into(n, u) = {x ∈ u| x ∩ diag(n − 1) ≠ {} ∧ x ∩ diag(n) ≠ {}}

\begin{matrix}card(dominoes-into(n, u)) + card(dominoes-into(n + 1, u)) \\ = card(diag(n)) \end{matrix}

covering(u) → card(dominoes-into(2, u)) = 2 REALITY BEHIND APPEARANCE

16