The size of the problem

There is a way around a greedy trap: check every possible path and choose the best one.

That works in a tiny maze. It falls apart when every step creates more choices.

Suppose each step offers only two moves. After 10 steps, there are 1,024 possible paths. After 20, there are 1,048,576. Ten extra steps created more than a million paths.

Chess is far larger. Claude Shannon estimated that a complete tree of possible chess games could contain about 10^120 games. That is a 1 followed by 120 zeros.

The greedy shortcut can walk into traps. Checking every path can demand more time than any machine has.

A useful search method needs a middle path: examine some possibilities, then choose which ones deserve more attention.

The size of the problem

There is a way around a greedy trap: check every possible path and choose the best one.

That works in a tiny maze. It falls apart when every step creates more choices.

Suppose each step offers only two moves. After 10 steps, there are 1,024 possible paths. After 20, there are 1,048,576. Ten extra steps created more than a million paths.

Chess is far larger. Claude Shannon estimated that a complete tree of possible chess games could contain about 10^120 games. That is a 1 followed by 120 zeros.

The greedy shortcut can walk into traps. Checking every path can demand more time than any machine has.

A useful search method needs a middle path: examine some possibilities, then choose which ones deserve more attention.