In this section we consider a more interesting provably intractable problem: playing games with full information, two players and zero sum. We will see that even for some simple games there cannot be a much more efficient algorithm, than exhaustive search through all possible configurations.
The rules of an n-player game G are set by
families f,v of information and value
functions and a transition rule r. Each player 
at each step participates in
transforming a configuration (game position) x in C into
the new configuration 
by
choosing a move 
based only on
his knowledge 
of x.
The game proceeds until a terminal configuration t in
T is reached. Then vi(t) is the loss or gain
of the i-th player.
Our games will have zero sum: SUMivi
(t) =0 and full information: fi(x)=x,
r(x,m)=r'(x,ma(x)) , where 
points to the active player.
We identify C and M with the set of integers and consider
binary two-players games, taking I={+1,-1}, a(x)= sign(x)
, and vi(t)=a(t)i. We assume the board preserves
its size, |r(x,m)|=|x|, and includes a time counter decremented
each step to prevent endless games.
An example of such games is chess. Examples of games without full
information are card games, where only part 
(player's own hand) of the position x is known.
Each player may have a strategy providing a move for each
position. A strategy S is winning if it guarantees
victory whatever the opponent does, even if he knows S.
We can extend v
Evaluating or solving a game, means computing V. This ability is close to the ability to find a good move in a modified game. Indeed, modify a game G into G' by adding a preliminary stage to it. At this stage the player A offers a starting position for G and the opponent B chooses which side to play. Then A may either start playing G or decrement the counter of unused positions and offer another one. Obviously, B wins if he can determine the winning side of every position. If he cannot while A can, she wins. Also, any game can be modified into one with at most 2=|M| moves. Evaluating such games is obviously sufficient for choosing the right move. A position of the new game consists of a position x of the old one and, possibly, a segment y of a move extended with "?"s to the move size. The active side replaces the first "?" with the next bit of y. When "?"s are gone, the next position is generated by r.
Theorem. Each position of any full information game has a winning strategy for one side.
(This theorem [Neumann, Morgenstern 44] fails for games with
partial information: each player may lose if his strategy is known
to the adversary. E.g.: 1. Blackjack (21); 2. Each player picks a bit;
their equality determines the winner.) The game can be solved by playing
all strategies against each other. There are 
positions of length n, 
strategies and 
pairs of them. For a 5-bit game that is 
. The proof of this Theorem gives a
much faster (but still exponential time!) strategy.
Proof: Make the graph of all |x|-bit positions and moves; set V=0; reset V=v on T; Repeat until idle: If V(x)=0, set V(x)=a(x)maxm{a(x)V(r(x,m))}. The procedure stops with V-1(0) empty since our games have time limits.
Games may be categorized by the difficulty to compute r. We
will consider only r computable in linear space O(|x|).
Then, the 22|x| possible moves can be computed in
exponential time, say 23|x|. The algorithm tries each
move in each step. Thus, its total running time is 
: extremely slow (
for a 13-byte game) but still much
faster than the previous (double exponential) algorithm.
Problem: the Match Game. Consider 3 boxes with 3 matches each:
