I've been reading about combinatorial games, on an article by Brilliant: https://brilliant.org/wiki/combinatorial-games-winning-positions/#chomp-and-strategy-stealing.
The article makes 4 statements about combinatorial games, which I am confused about:
-
Due to the deterministic nature of the game, one can show via backward induction that every position can be uniquely characterized as a winning or a losing position.
-
The empty game (the game where there are no moves to be made) is a losing position.
-
A position is a winning position if at least one of the positions that can be obtained from this position by a single move is a losing position.
-
A position is a losing position if every position that can be obtained from this position by a single move is a winning position.
What I am confused about is the following:
-
I don't understand why every position can be uniquely characterized as a winning or a losing position. Can't there be positions that don't bring a player close to winning, but don't cause them to lose either?
-
I still don't fully understand what an empty game is. Is it a game where you can't make any moves (like when you are checkmated in chess)? But then why is an empty game an automatic loss? In a misere game, it would be a win, because your opponent is the last to move!
-
I don't understand why the fact that "one of the positions that can be obtained from this position by a single move is a losing position" is sufficient to show something is a winning position. Because that means the position will only cause the opponent to lose if he or she chooses to move to the worst possible position – otherwise you're opponent won't be any closer to losing then before! So how can that be considered a winning position?
Best Answer
Let's address points 2 and 3 first.
2: The empty game is the game where neither player has any legal move. The authors of that article are (implicitly, although they don't say it, it applies to all of their examples) only considering games under the normal (as opposed to misere) play convention, where the last player to move wins.
3: Let's make sure you have correct definitions of winning and losing positions. A winning position is a position where the side to move can win, and a losing position is a position where the side to move loses no matter what they do. To show a position is winning, I just need to exhibit a single winning move. It must lead to a position where the opponent loses no matter how they respond, i.e., the new position is a losing position for the opponent who is now on move.
Now 1 follows by an inductive argument from 2 and 3, assuming that (1) the game has finitely many positions; (2) it is impossible to repeat a position; (3) the game is impartial, i.e., the two players have the same legal moves. (These assumptions are not stated, but applies to all their examples.) If (3) did not hold, there would be four types of positions, not just two (winning and losing).
The inductive argument runs like this: By the additional assumptions above, the game can be represented as a finite tree where the starting position is at the root, and the leaves are all terminal positions where neither player can move. Argue by induction on the height of the nodes. At height 0 (the leaves), we have the empty position which we know is losing. At any higher node, the children are already classified as winning or losing (by induction). If all the children are winning, then the position is losing; otherwise, at least one child is losing, so the position is winning. Therefore, all nodes can be classified as winning or losing.