Does a finite game that cannot be drawn imply a winning strategy exists?

Solution 1:

Imagine all possible positions of the game arranged in a tree structure, with the initial position at the root, and the children of position $P$ being the positions that are reachable in one move from $P$ by the player whose turn it is to go next. The leaves of the tree are the ending positions in which one of the other player has won, since there are no draws. Let us call the player who moves in the initial position White, and the player who moves second Black.

We will eventually color each node white if White has a guaranteed win from that position, and black if Black has a guaranteed win. We want to color every node, and we can certainly start by coloring every leaf node either black or white, since there are no draws.

There are now some uncolored nodes whose children have all been colored. (Just go down the tree until you find one.) We can color each node $N$ as follows. Suppose that at node $N$ it is player $P$'s turn to move. If there is a move from $N$ to some position $N'$ colored with $P$'s color, then they can force a win in position $N$, by moving to $N'$, and so we can color $N$ with their color also. Otherwise every possible move $P$ can make is to a position from which their opponent can force a win, so we color $N$ with the color of $P$'s opponent.

As long as there is a node that has not yet been colored. there must be one whose children have all been colored. We can color these nodes the same way: for each one, either one of its children is a "good move" from which the player to move can force a win, and we color the uncolored node in that player's color, or there is no "good move", all moves are losers, so we color the uncolored node in the other player's color.

We can continue this process until the unique root node $R$ is colored. $R$ must be either white or black. If it is white, then the White player has a winning strategy; if it is black, then the Black player has a winning strategy.

The strategy is simple: always move to a node of your color. This is always possible. Say the root node is white. It is colored white only because it has at least one white child node $R'$, and so the White player has at least one good move to $R'$. Black has no good moves from $R'$; it was colored white because all its children are white, and so whatever Black does, the White player will again start her turn at a white-colored position. Play will descend the tree from white node to white node until it terminates at a white leaf and the White player wins.

Conversely, suppose we colored the root node $R$ black. We did this because all of White's moves from $R$ are to black-colored positions. Whatever position $R'$ White moves to, it must be black, and $R'$ is only black because there is at least one good move for Black to another black-colored position $R''$. If Black plays correctly, the game will proceed down a chain of black nodes until the position is a black leaf and Black has won.

Now consider the case where games may be drawn. Color the leaf nodes gray if they are draws. Then color the rest of the nodes as before, coloring each node with the best outcome that can be obtained by the player who has the move at that node: if a node represents a position where Black has the next move, color it black if it has a black child, gray if it has a gray child and no black children, or white if it has all white children. Do the opposite for nodes where White has the move. Now the root node is colored either white, if White can force a win; black, if Black can force a win, or gray, if neither player can force a win. The strategy is as before. Say you're White. If the current node is white, your strategy is to move to another white node, and you can guarantee that all positions will be white until you reach the end of the game and win. Otherwise, if the current node is gray, you should move to another gray node, and similarly all positions will be gray to the end of the game. And if the current position is black, you have no good strategy because all your moves are to black nodes, and the Black player can keep the position on a black node until the end of a game when she wins.

Solution 2:

Winner-indeterminacy requires one of five things

A discrete-steps game where we cannot determine some player who can win with perfect play requires at least one of the following five conditions to obtain:

1. simultaneous actions by two or more players;
2. imperfect information -- either some information about the players' actions is hidden or random;
3. an infinite tree of possible game states;
4. drawn end-states; or
5. kingmaker states: the player "at bat" cannot win but they can determine which of two other players is the winner.

Taking (1) for granted, a two-player game with perfect information cannot have kingmakers and therefore all of its indeterminacy must come from drawn end-states or an infinite game graph.

Proof that those five are sufficient to provide indeterminacy

For an example of (1),

Alice and Bob simultaneously choose integers; Alice wins if the sum is even, or Bob wins if the sum is odd. (the "xor" game)

For an example of (2), just implement the xor game with hidden information (Alice decides first but hides her result from Bob, who must decide second).

For an example of (3), implement the following variant of the xor game as follows:

An integer $p$ starts at 1, with Alice to play first. Players follow turn order and can choose either of two actions: (a) set $p$ to a given integer, or (b) end the game. When the game ends, Alice wins if $p$ is even and Bob wins if $p$ is odd.

With perfect play the game continues until someone gets sick of playing it.

Examples of (4) are trivial, and the simplest example of (5) is just,

Alice must choose whether Bob or Carol wins. (the "kingmaker" game for Alice)

You might object that not all three players are able to affect the game here, and a player who cannot affect the game winning is effectively the same as a "drawn" outcome since they're not interactive. But it's not hard to build on this to address those, for example:

Alice must choose to play either the kingmaker game for Bob or the kingmaker game for Carol. (the "kingmaker-maker" game for Alice)

Then if one is still upset that not all players are assured a turn, it's not hard to add that condition either.

Proof of necessity

Previous drafts of this answer worked out the analysis code in Haskell first; here is the upshot:

Because of (1) [more precisely, because of the rejection of (1)], a game has a definite turn order: at each stage of the game there is one player who is choosing from a list of 2 or more options for the next stage of the game: it's a digraph whose nodes are decorated with a player who is "at bat", who decides which of the child nodes of that node the game will descend into,

data GameState = Draw [Player]
               | Win Player
               | AtBat Player [GameState]

In practice you'd probably annotate this thing with other metadata, for example for Tic-Tac-Toe you may want to track a 3x3 "game board" or so which would help Haskell build this data structure and help you display the options to folks actually playing the game. But it is not essential. Also all lists mentioned here will contain at least two elements, which is a constraint that Haskell would not enforce by itself.

Because of (3), this data structure is finite and noncircular and can be traversed by recursive algorithms. [This is another thing Haskell would not enforce without strictness annotations above.]

The recursive algorithm to determine a win-state,

data WinState = SureWinFor Player
              | Indeterminate

proceeds as follows: at the leaf nodes all draws are regarded as Indeterminate and all Win p are regarded as a SureWinFor p. The AtBat p children nodes require determining first the win state for all of the child nodes:

1. If any of the children is a sure win for p, then this node is a sure win for p. Here we are implicitly using (2) -- imperfect information would mean that the player might not be able to tell one option from another.
2. Otherwise, if all of the child nodes are a sure win for another player p', then this node is a SureWinFor p'.
3. Otherwise, this node's winner is Indeterminate.

Now here's the proof that an indeterminate game which rejects (1), (2), and (3) must either reject (4) or (5) and thus have either ties or kingmakers.

Suppose any internal state of the game is judged Indeterminate. If it has any child nodes which are Indeterminate, choose one and descend into it; repeat until you have an Indeterminate node which does not have any Indeterminate child nodes. Then either:

1. It has no child nodes; since it is indeterminate it is not a Win but a Draw, or,
2. It has child nodes, none of which are Indeterminate, none of which are a SureWinFor that player, and not all of which are a SureWinFor the same other player -- but that's exactly our definition of a "kingmaker" state.

This completes the proof.

Solution 3:

I think this can be proved directly from the definition.

If the player who goes first(say it is A, the other player is B) has a winning strategy, this means: There exists a first move such that no matter what move does B do next, A can find a move such that no matter what move does B do next, A can find a move such that...A can find a move and win. So if A does not have a winning strategy, it means: For any first move, B can find a move such that for any move A does next, B can find a move such that for any move A does next,..., B can find a move such that for any move A does next, B wins. which means B has a winning strategy. And suppose B has a winning strategy we can similarly do this.

So there exists a winning strategy.

I think this can be written in a more concise recursive form, but don't know how to...

Solution 4:

The OP asks about a particular game: Chomp. Regarding that game, we can argue further.

Suppose that the second player has a winning strategy. Then they have at least one winning response to an opening 1x1 chomp by the first player. But in the position resulting from any such chomp, the total chomped area is a rectangle, so this position is one which the first player could produce on their first turn. So the first player could do that instead, and steal the second player's strategy. This would give the first player a winning strategy. This is absurd -- the players can't both force a win.

Other commenters have shown that one or other player has a winning strategy. The second player doesn't. Therefore the first player does.