Robotics Reference
In-Depth Information
The trees shown above are very small, but the sizes of the trees ex-
amined by the Chess programs of today are huge. There are 20 legal
moves in the starting position and this number normally rises to an av-
erage of around 37 during the middle phase of the game, so after just
one half-move by White and a reply move by Black there are typically
approximately 1,000 different positions to consider. Two half-moves by
each side means approximately one million positions. This number be-
comes enormous when the depth of the tree reaches double figures, and
some of today's leading Chess programs typically search many parts of
the tree to a depth of 20 half-moves or more along the most important
branches. To put the size of the problem into perspective, consider the
fact that the number of possible different games of Chess, which has been
estimated at 10
120
, is greater than the number of atoms in our universe.
This means that even if every atom in the universe were to be replaced
by a computer, it would take the combined power of all these computers
ahugeamountoftimetocalculatethefirstmoveinaperfectlyplayed
game of Chess. Fortunately there are clever techniques for performing
deep tree searches, up to 20 ply or more.
7
In 1951 Shannon built a computer for playing Chess endgames (see
Figure 21
)
but he published nothing about its design or how it worked.
Shannon's original paper described three different search strategies for
programming Chess. The simplest of these was to consider all moves by
both sides up to a certain depth, as in the example above for a tree of
depth two. A much improved strategy, which Shannon called “type B”,
is more selective and is the one employed in virtually all Chess programs
since Shannon's day:
1. Examine forceful variations out as far as possible and evaluate
only at reasonable positions, where some quasi-stability has been
established.
2. Select the variations to be explored by some process so that the
machine does not waste its time in totally pointless variations.
7
The most powerful of these is called the alpha-beta algorithm, the workings of which are beyond
the scope of this topic.
