TAOCP 2.2.3 Exercise 28

Section 2.2.3: Linked Allocation

Exercise 28. [40] The following construction shows how to "solve" a fairly general type of two-person game, including chess, nim, and many simpler games: Consider a finite set of nodes, each of which represents a possible position in the game. For each position there are zero or more moves that transform that position into some other position. We say that position $x$ is a predecessor of position $y$ (and $y$ is a successor of $x$) if there is a move from $x$ to $y$. Certain positions that have no successors are classified as won or

Verified: no
Solve time: 7m58s

Let $G=(V,E)$ be the finite directed graph of game positions. If $(x,y)\in E$, then $y$ is a successor of $x$ and $x$ is a predecessor of $y$.

Terminal positions are already classified as either won or lost. We wish to deduce all further positions that are forced wins or forced losses.

The recursive definitions are:

A position is won if it has at least one lost successor.
A position is lost if all of its successors are won.

The crucial point is that in a graph with cycles, not every position need be classifiable as won or lost. Positions that cannot be forced into either category remain unclassified. The algorithm must therefore propagate information backward from positions already known.

Data maintained

For each position $x$:

$\mathrm{state}(x)\in{\text{unknown},\text{won},\text{lost}}$.
$c(x)$, initially equal to the number of successors of $x$.

Also store, for every node $y$, the list of predecessors of $y$.

Maintain a list (or queue) $Q$ of positions whose status has just been determined and whose predecessors still need processing.

Algorithm

Initialization

For every node $x$, set

$$ c(x)=#{\text{successors of }x}. $$

For every terminal position already designated won, set

$$ \mathrm{state}(x)=\text{won}, $$

and place $x$ in $Q$.

For every terminal position already designated lost, set

$$ \mathrm{state}(x)=\text{lost}, $$

and place $x$ in $Q$.

All other positions start with

$$ \mathrm{state}(x)=\text{unknown}. $$

Propagation

While $Q\neq\Lambda$, remove a position $y$ from $Q$.

Case 1: $y$ is lost

Every predecessor $x$ of $y$ is immediately won, provided it has not already been classified.

Indeed, $x$ has a lost successor, namely $y$.

Therefore, for each predecessor $x$:

if $\mathrm{state}(x)=\text{unknown}$, set

$$ \mathrm{state}(x)=\text{won}, $$

and place $x$ in $Q$.

Case 2: $y$ is won

For each predecessor $x$ of $y$ that is still unknown, decrease $c(x)$ by $1$.

The interpretation is that one more successor of $x$ has now been shown to be won.

If after the decrement

$$ c(x)=0, $$

then every successor of $x$ is known to be won. Hence $x$ is lost.

Set

$$ \mathrm{state}(x)=\text{lost}, $$

and place $x$ in $Q$.

When the queue becomes empty, stop.

Correctness

We prove that every label assigned by the algorithm is correct.

Lemma 1

Whenever the algorithm labels a position $x$ as won, $x$ is genuinely won.

Proof

A position is labeled won only in Case 1.

Then there exists a successor $y$ of $x$ already labeled lost.

By the defining rule of the game,

$$ (\exists\ \text{lost successor}) \implies \text{won}. $$

Hence $x$ is won. ∎

Lemma 2

Whenever the algorithm labels a position $x$ as lost, $x$ is genuinely lost.

Proof

A position is labeled lost only when $c(x)$ reaches $0$.

Initially $c(x)$ equals the number of successors of $x$.

The counter is decreased exactly once for each successor that becomes known won.

Therefore $c(x)=0$ means that every successor of $x$ has been established won.

By the defining rule,

$$ (\text{all successors won}) \implies \text{lost}. $$

Hence $x$ is lost. ∎

Lemma 3

Every position that is logically forced to be won or lost is eventually labeled.

Proof

Consider the smallest set $S$ containing the initially labeled terminal positions and closed under the two inference rules

$$ \text{lost successor} \Rightarrow \text{won}, $$

$$ \text{all successors won} \Rightarrow \text{lost}. $$

These are exactly the positions whose status is deducible from the terminal labels.

Whenever a position enters $S$ because it has a lost successor, the algorithm labels it won the moment that lost successor is processed.

Whenever a position enters $S$ because all its successors are won, each such successor eventually causes one decrement of its counter, and after the last decrement the algorithm labels it lost.

Thus every member of $S$ is eventually discovered. ∎

Lemma 4

The algorithm terminates.

Proof

Each position can change state at most once:

$$ \text{unknown} \rightarrow \text{won} $$

$$ \text{unknown} \rightarrow \text{lost}. $$

Once classified, it is never reinserted as unknown.

Since the graph has finitely many positions, only finitely many insertions into $Q$ are possible.

Therefore the queue-processing loop must terminate. ∎

What remains unlabeled?

The algorithm does not assume that every node becomes won or lost.

If a directed cycle never receives information forcing one of its nodes to be won or lost, none of its vertices is labeled. Such positions are neither provably won nor provably lost by the recursive rules.

Hence the final result is:

Every node labeled won is truly won.
Every node labeled lost is truly lost.
Every node left unknown is not derivable as won or lost from the rules.

This correctly handles cycles and avoids the false claim that all positions must receive a label.

Relation to the linked-list representation

The queue $Q$ and the predecessor lists can be stored using the linked-allocation methods of Section 2.2.3.

The essential game-solving mechanism is the backward propagation through predecessor lists:

a newly discovered lost node immediately makes its predecessors won;
a newly discovered won node decreases the remaining-successor count of each predecessor, possibly making that predecessor lost.

This is the intended finite-game solution and runs in time proportional to the size of the graph, since each edge is processed only when its endpoint is classified. ∎