Information Technology Reference
In-Depth Information
Chess Playing: The game of chess offers another example of how
scaling up can change a computer's rate of success. A variety of ap
proaches are used to instruct a computer how to play chess, but the
most common and successful methods all use the same basic approach:
At each point in the game, the computer generates all possi
ble moves, determines which approach is best, and selects the
bestlooking move.
To determine which of these moves is best, the computer
looks at all responses that could be made to each move, as
suming the opponent makes the best possible response.
As a practical matter, it can be difficult to determine which
moves are best without looking at all possible future moves for both
sides. In the jargon of gameplaying programs, a ply is the term used
to describe a move made by either player. Thus, two plies occur if
you move and then your opponent makes a move. With three plies,
you move, then your opponent moves, and then you move again.
With this terminology, the basic idea of most chess programs is to
look ahead in the game through as many plies as possible to deter
mine the possible consequences of each move. Once these conse
quences are known, the best current move can be selected.
Unfortunately, however, the game of chess is complex, and it
has been estimated that, on the average for any given ply, a player
will have to choose among about 20 possible moves. This number
gives rise to the following rough analysis:
In one ply, you will have about 20 possible moves.
For a second ply, an opponent will have about 20 possible re
sponses for each move you might make. Thus, there are about
20 20 or 400 possibilities at the end of two plies.
For each of these 400 possibilities, you will have a choice of
roughly 20 responses. This gives 20 20
20 or 20 3
8,000 possibilities at the end of three plies.
At the end of i plies, there are roughly 20 i
possible move
sequences.
Search WWH ::




Custom Search