Game Tree - Solving Game Trees

Solving Game Trees

With a complete game tree, it is possible to "solve" the game – that is to say, find a sequence of moves that either the first or second player can follow that will guarantee either a win or tie. The algorithm (which is generally called backward induction or retrograde analysis) can be described recursively as follows.

  1. Color the final ply of the game tree so that all wins for player 1 are colored one way (Blue in the diagram), all wins for player 2 are colored another way (Red in the diagram), and all ties are colored a third way (Grey in the diagram).
  2. Look at the next ply up. If there exists a node colored opposite as the current player, color this node for that player as well. If all immediately lower nodes are colored for the same player, color this node for the same player as well. Otherwise, color this node a tie.
  3. Repeat for each ply, moving upwards, until all nodes are colored. The color of the root node will determine the nature of the game.

The diagram shows a game tree for an arbitrary game, colored using the above algorithm.

It is usually possible to solve a game (in this technical sense of "solve") using only a subset of the game tree, since in many games a move need not be analyzed if there is another move that is better for the same player (for example alpha-beta pruning can be used in many deterministic games).

Any subtree that can be used to solve the game is known as a decision tree, and the sizes of decision trees of various shapes are used as measures of game complexity.

Read more about this topic:  Game Tree

Famous quotes containing the words solving, game and/or trees:

    “More than a decade after our fellow citizens began bedding down on the sidewalks, their problems continue to seem so intractable that we have begun to do psychologically what government has been incapable of doing programmatically. We bring the numbers down—not by solving the problem, but by deciding it’s their own damn fault.”
    —Anna Quindlen (b. 1952)

    “Neighboring farmers and visitors at White Sulphur drove out occasionally to watch ‘those funny Scotchmen’ with amused superiority; when one member imported clubs from Scotland, they were held for three weeks by customs officials who could not believe that any game could be played with ‘such elongated blackjacks or implements of murder.’”
    —For the State of West Virginia, U.S. public relief program (1935-1943)

    “The sugar maple is remarkable for its clean ankle. The groves of these trees looked like vast forest sheds, their branches stopping short at a uniform height, four or five feet from the ground, like eaves, as if they had been trimmed by art, so that you could look under and through the whole grove with its leafy canopy, as under a tent whose curtain is raised.”
    —Henry David Thoreau (1817–1862)