|
|
|
|
|
|
|
Fig. 4.
Example of a game tree |
|
|
|
|
|
|
|
|
The object of the first player, then, is to learn enough of the strategy chosen by the second player to find an opposing strategy which maximizes payoff. When the game tree involves only a finite number of vertices, as is often the case, it is at least theoretically possible to locate the maximizing strategy by enumerating and testing all strategies against the opponent. However, if there is an average of k options proceeding from each configuration, and if the average play involves m moves, there will be in excess of kmpure strategies. The situation is quite comparable to the examples of enumeration given earlier. Even for a quite modest game with k = 10 and m = 20, and a machine which tests strategies at the exceptional rate of one every 10-9 second, it would require in excess of 1011 seconds, or about 30 centuries, to test all possibilities. Efficiency thus becomes the critical issue, and |
|
|
|
|
|
