Challenge Problem in Algorithms and Data Structures
Analyzing a Game Tree
Revised November 22, 2005.
The purpose of these problems is to provide a challenge to the top students,
meaning those who master the regular material of the course and would like
to learn more.
Do not try to work these problem to improve a poor grade ... if you are doing
badly in the course, concentrate on the regular material.
-
The simple game tic-tac-toe can be easily analyzed using a
game tree.
More generally, every finite deterministic game (such as Tic-tac-toe, Chess,
Checkers, Go, and
Mill)
has an associated
game graph, which
is usually (incorrectly) called a "game tree." (The reason it's wrong
to call it a "tree" is that it usually isn't. The game graphs of Chess
and Checkers contain cycles. The game graph of Tic-tac-toe is acyclic,
but it is also not a tree.)
-
In general, a game graph for a deterministic finite 2-person zero sum game
is a bipartite directed graph with one start node, and one
or more end nodes. Each node is a state
of the game. Each end node has a value, the amount the first (red) player
wins if the game ends at that node. A win for the second (black) player
is denoted by a negative value, a draw by zero. Every node which is not an
end node is colored either red or black.
-
It is helpful to imagine that there is a "pebble" on the node representing
the current game state. The pebble begins on the start node. If the
current node is red, the red player moves the pebble along any arc to
another node. If the current node is black, the black player moves the
pebble along any arc to another node. If the current node is an end
node, the game is over, and the red player wins an amount equal to
the value of that node from the black player.
-
There could be a cycle in the game graph (such as for Chess or Checkers).
If the pebble never reaches an end node, we will say that the
game is a draw, and the win is zero.
(Both Chess and Checkers have official rules on how to deal with this
situation.)
Given a game graph G, let value(x)
be defined as follows:
-
If x is a node,
and if red has a strategy which guarantees that,
starting from x, he will win at least V,
then value(x) is greater than or equal to V.
-
If x is a node,
and if black has a strategy which guarantees that,
starting from x, red will win at most V,
then value(x) is less than or equal to V.
Here is the assignment:
-
Give a precise definition, in graph-theoretic terms, of
a strategy for the red player starting at a node x,
and similarly,
a strategy for the black player starting at a node x.
-
Prove that
value(x) is uniquely defined for every node
x.
-
Design a reasonably fast algorithm which, given a game graph
G with n nodes as input,
outputs value(s), where s
is the start node of G, and also outputs
a strategy for the red player starting at a node
s which guarantees a win of
at least
value(s),
and a strategy for the black player starting at a node
s which guarantees that the red player wins at
at most value(s).
Ideally, your algorithm runs in
O(n) time, but that may not be possible. (I am not
reavealing the answer.)
If G is acyclic, there is a simple
O(n) time bottom-up dynamic programming algorithm
to solve G.
If there are cycles, the problem is harder.
Note that your algorithm could, theoretically, be used to find a
perfect strategy for either player for Chess. The problem with this
plan is practical: in the case of Chess, the number of nodes of
G far exceeds the number of atoms in the known universe,
multiplied by the number of nanoseconds in the (currently estimated)
lifetime of the universe; which means that if you could turn every
atom in the known universe into a gigaflop computer, you still couldn't
traverse G in the estimated lifetime of the universe.
Warning!
While showing that website to
a student during my office hours, we discovered that
the computation of value in the
Tic-tac-toe game tree made by
Yosen Lin is incorrect.
Yosen hopes to fix the page this weekend (December 2-4, 2005).