Indian Computing Olympiad

Games and strategies

Solving finite games

The bottom up computation in the Bead Necklace game corresponds to the following top down analysis, which applies for any game that has a finite number of positions.

There are two players 0 and 1. The game is described as a game graph. The vertices are the positions and each position of the game is labelled 0 or 1 depending on which player moves at that position. The edges describe how the game can evolve from one position to another.

We label some of the positions as winning for player 0 — let this set be G. If the game ever reached G, player 0 wins. Otherwise, player 1 wins. (If the game graph is a dag, all plays will end in a sink state, so we just label the sink states as winning for 0/1, as in the Pearls game.)

Let W0 denote the set of positions from which player 0 can win in at most n moves. W0 is G, since, if the game is in a position in G, player 0 has already won.

We now calculate W1.

• Consider any state s labelled 0 from which there is at least outgoing edge to t in W. Then, 0 can move into W = W0 and win, so s belongs to W1.
• Symmetrically, consider any state s labelled 1 from which all outgoing edges lead to W. Then, 1 is forced to move into W = W0 where 0 wins, so t belongs to W1.

In general, let Wi be the set of positions from where player 0 is guaranteed to win in i moves. We can calculate W{i+1}.

• Consider any state s labelled 0 from which there is at least outgoing edge to t in Wi. Then, 0 can move into Wi and win in i moves, so s belongs to W{i+1}.
• Symmetrically, consider any state s labelled 1 from which all outgoing edges lead to some Wj, for j ≤ i. Then, 1 is forced to move into Wj from where 0 wins in j moves, so t belongs to W{i+1}.

Notice that W0 is included in W1 is included in W2 ... Since the game graph has only n positions, for some i, we must have Wi = W{i+1}. In particular, we must stop when we reach W{n-1} because we cannot add more than n-1 new nodes to the original set W0.

Let W the final winning set for 0 — that is, W = Wi such that Wi = W{i+1}.

Claim:

1. If the game starts in W, player 0 always wins.
2. If the game starts outside W, player 1 always wins.

Proof:

1. If the game starts in W, player 1 cannot move the game outside W. Player 0 can not only stay in W but also "decrease the rank" — that is, move from Wi to W{i-1}. So, after some time, the game must reach W0 where player 0 wins.
2. On the other hand, if the game starts outside W, player 0 cannot move the game to within W and player 1 can always keep the game outside W. Since player 0 can never reach G, player 1 must win.

How do we compute these quantities?

Naively, this can be done in O(nm) time — we have to compute sets W1,...,X{n-1} and we scan all edges in each iteration.

However, with some care, we can do it in O(m) time.

Hint: Keep a count at each neighbour of how many good neighbours it has. Initialize this count to 0. When you add a node to W, notify all your incoming neighbours that you are good (increment their good neighbour count).

• To classify a 0 vertex as good, check if its good count is nonzero.
• To classify a 1 vertex as good, check if its good count is equal to its degree.

This can be done in linear time, like BFS.