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:
- simultaneous actions by two or more players;
- imperfect information -- either some information about the players' actions is hidden or random;
- an infinite tree of possible game states;
- drawn end-states; or
- 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
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:
- 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.
- Otherwise, if all of the child nodes are a sure win for another player
p', then this node is a
- Otherwise, this node's winner is
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:
- It has no child nodes; since it is indeterminate it is not a
Win but a
- 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.