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

Question

The author of this page, about a simple game (Chomp) http://plus.maths.org/content/mathematical-mysteries-chomp makes the following statement: "One of the players is sure to have a winning strategy. This is easy to see, because the game must finish in finitely many moves, and can't be drawn."

Is that "easy to see"? It doesn't seem obvious to me that a finite game that cannot be drawn must have a winning strategy for one player or the other.

I dare say it's not the first time in my life I've failed to see the obvious, but I'd be interested to see a proof of this assertion.

Answer 1

Suppose that the second person does not have a winning strategy, then the first person must have a move which does not lose. After two moves we cannot have a winning position for the second player. We are therefore back in a position where the second player does not have a winning strategy.

Since the game is finite and determinate, and we never reach a position which is a win for the second player, the first player must win.

Answer 2

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.