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

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.

-
Hint: think of the finite game tree, and try to build a strategy from the leaves, rather than the root. – yohBS Sep 17 '13 at 21:22
Some of the confusion may be with the word 'strategy' - as noted in the answer below, formally a strategy is just a function mapping positions to moves, and such a map must exist. But in common parlance, a strategy often means a plan, and this can be thought of as an algorithm for computing a good move from each position. Now, the naive algorithm here requires space potentially exponential in the size of a position (to hold the entire game tree) and without such space available, may require huge amounts of time to generate the tree. – Steven Stadnicki Sep 30 '14 at 17:29
And while a strategy in the sense of a function is guaranteed, a strategy in the sense of an efficient algorithm isn't - there are simple games with complex solutions where very little algorithmic efficiency can be gained. – Steven Stadnicki Sep 30 '14 at 17:30

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.

-

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...

-

I think you can prove it only if the game is discrete-time two-player game. Let me give some code which will be in the Haskell language; without draws the relevant data structure is:

type Player = Int
data GameState meta = Win meta Player | AtBat meta Player [GameState]

meta :: GameState m -> m
meta (Win m p) = m
meta (AtBat m p cs) = m


The player-at-bat is allowed to choose which game state they want to descend into, which is ultimately described by metadata, plus information about the player who plays next, plus a list of the moves that they can make.

data WinStatus other_metadata = Indeterminate other_metadata

is_indeterminate (Indeterminate _) = True
is_indeterminate (SureWinFor _ _) = False


and we start filling in other cells:

is_sure_win_for :: Player -> (WinStatus meta) -> Bool
is_sure_win_for p (SureWinFor p' _) = p == p'
is_sure_win_for _ (Indeterminate _) = False

who_wins_all :: [WinStatus meta] -> Maybe Player
who_wins_all (Indeterminate _ : cs) = Nothing
who_wins_all (SureWinFor p _ : cs)
| all (is_sure_win_for p) cs = Just p
| otherwise = Nothing

winning_status :: GameState meta -> GameState (WinStatus meta)
winning_status (Win m p) = Win (SureWinFor p m) p
winning_status (AtBat m p cs) =
let cs' = map (winning_status) cs
metas = map meta cs'
in if any (is_sure_win_for p) metas
then AtBat (SureWinFor p m) p cs
else case who_wins_all metas of
Just p' -> AtBat (SureWinFor p' m) metas
Nothing -> AtBat (Indeterminate m) metas


We have now solved the problem. So now comes the reasoning moment. We see that sometimes the Nothing from who_wins_all which causes an Indeterminate to exist is due to an Indeterminate in its argument. Let's call those the propagated indeterminates, and anything else the generated ones. Indeterminates are therefore only generated when simultaneously three things hold:

any (is_sure_win_for p) metas == False
who_wins_all metas == Nothing
any is_indeterminate metas == False


If it's a two-player game, then those are actually the only three options: either one of the elements is Indeterminate, one is a sure win for one player, or they're all sure wins for the other player.

-

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.

-