Information Technology Reference
In-Depth Information
A player will not need to find a list of moves from an initial to a final state. The
player must find the
best next move
, wait for the opponent to make a move, then
find the best next move again, and so on, until the game is over.
The best next move for a player must take into account the
responses
available to
the opponent. The responses from the opponent will also take into account the
possible counterresponses from the player, which should take into account the
possible counter-counterresponses, and so on.
The best next move for a player should not rely on the opponent's making a
mistake
. If an opponent plays poorly, so much the better. Ideally, however, a player
will find a move that is a first step toward winning even when the opponent is
playing at her very best.
10.2.1 Game trees
To see how players can take into account all the possible responses, the counterre-
sponses and so on, it is useful to look at a structure called a
game tree
, whose nodes
correspond to states of the game:
The root node of the tree (usually at the top) is the initial state of the game.
Each leaf node of the tree (usually at the bottom) is a final state of the game,
where according to the rules, one of the players has won or there is a tie.
Each non-leaf node has as children (below it) all the game states that can be
reached by making legal moves according to the rules.
Figure 10.3 shows a game tree for an anonymous game between two players, Max
and Min. In this game, in the initial state (level 0), Max has two moves available to
him (move 1 and move 2). In the two states to which these moves lead at level 1,
Min has three legal moves available to her, leading to six states at level 2. From there,
Max has either two or three moves available to him, which either lead to the game's
being over at level 3, or Min's moving one final time from level 3 to level 4. The tree
depicts all possible unfoldings of this game, ending with final states where either Max
wins (labeled
W
) or Min wins (labeled
L
). The tree does not display what the states or
the moves of the game are. Nonetheless, the rules of the game determine the entire
structure of this game tree, from the start to the end.
The main observation is that just by looking at how the game unfolds according to
the tree, one can determine whether Max should choose move 1 or move 2 as his first
move. To figure this out, every node on the tree is
labeled
as either a winning position
for Max (
W
) or a winning position for Min (
L
).
