Win-Loss Analysis

From Algorithmist
Jump to navigation Jump to search

A combinatorial game is one in which

  1. There are two players who play alternately
  2. There are several, but finitely many, states that the game can be in, we will call positions
  3. There is complete information (both players know all options from each position)
  4. Play is deterministic (there are no chance moves)
  5. The game must terminate after a finite number of moves

For example, tic-tac-toe, connect four and chess are impartial (if, in chess, you introduce a rule to eliminate infinite games) whereas poker is not.

There is an optimal strategy for any combinatorial game. In principle, win-loss analysis allows you to find such a strategy for any combinatorial game, but it may require a lot of time (e.g., chess has far too many positions to complete such an analysis).

Here are the rules for analysis:

  1. A game-winning move goes to a W position.
  2. A game-losing move goes to an L position.
  3. If a position has any options marked W, mark it L
  4. If a position has only options marked L, mark it W.

After completely labeling all states according to these rules, if the initial position is marked W then the first player can guarantee a win: the second player has to move to an L-marked state, and then the first player can bring the game back to a W-marked state. Likewise, if the initial position is marked L then the second player wins (if they play optimally).

By adding a couple more rules you can extend this to also work for games that have draws.

Impartial Games, Tweedledee and Tweedledum[edit]

A game is impartial if, from any position, both players always have the same set of options.

The Tweedledum-Tweedledee Strategy for Impartial Last-Move-Wins Games Assume that you are playing a last-move-wins game. Suppose that you make some move after which the game has two identical and independent "halves." Then you can win! — mirror your opponent's moves, in the opposite half to where they move. [This also works for some non-impartial games.]

As an example of this strategy, consider the following impartial combinatorial game.

Kayles
Setup: There is a line of N coins, one at each location 1, 2, 3, …, N.
Rules: On your turn, remove any 1 coin, or 2 coins at locations X, X+1 (i.e., adjacent coins).
Winning: The person to take the last coin wins.

Here is a winning strategy for the first player, based on the tweedledee-tweedledum principle: remove the middle coin (or middle 2 coins if N is even) on their first term. The remaining coins form 2 equally-sized halves. In the rest of the game, whenever the second player makes a move in one half, the first player should make the same move, but in the other half. Both halves remain the same after each of the first player's moves until the game terminates, and then they win.