Gödel, Escher, Bach An Eternal Golden Braid by Douglas R. Hofstadter

the infiniteness of the goal stack, Achilles got his wish. Problem reduction

wins the day!

Despite my mockery, problem reduction is a powerful technique for

converting global problems into local problems. It shines in certain situa-

tions, such as in the endgame of chess, where the look-ahead technique

often performs miserably, even when it is carried to ridiculous lengths,

such as fifteen or more plies. This is because the look-ahead technique is

not based on planning; it simply has no goals and explores a huge number

of pointless alternatives. Having a goal enables you to develop a strategy for

the achievement of that goal, and this is a completely different philosophy

from looking ahead mechanically. Of course, in the look-ahead technique,

desirability or its absence is measured by the evaluation function for posi-

tions, and that incorporates indirectly a number of goals, principally that of

not getting checkmated. But that is too indirect. Good chess players who

play against look-ahead chess programs usually come away with the im-

pression that their opponents are very weak in formulating plans or

strategies.

Shandy and the Bone

There is no guarantee that the method of problem reduction will work.

There are many situations where it flops. Consider this simple problem, for

instance. You are a dog, and a human friend has just thrown your favorite

bone over a wire fence into another yard. You can see your bone through

the fence, just lying there in the grass-how luscious! There is an open gate

in the fence about fifty feet away from the bone. What do you do? Some

dogs will just run up to the fence, stand next to it, and bark; others will dash

up to the open gate and double back to the lovely bone. Both dogs can be

said to be exercising the problem reduction technique; however, they

represent the problem in their minds in different ways, and this makes all

the difference. The barking dog sees the subproblems as (1) running to the

fence, (2) getting through it, and (3) running to the bone-but that second

subproblem is a "toughie", whence the barking. The other dog sees the

subproblems as (1) getting to the gate; (2) going through the gate; (3)

running to the bone. Notice how everything depends on the way you

represent the "problem space"-that is, on what you perceive as reducing

the problem (forward motion towards the overall goal) and what you

perceive as magnifying the problem (backward motion away from the goal).

Changing the Problem Space

Some dogs first try running directly towards the bone, and when they
encounter the fence, something clicks inside their brain; soon they change
course, and run over to the gate. These dogs realize that what on first

Artificial Intelligence: Retrospects^611