Wythoff’s Game and the difference between cold and hot positions

Question

Wythoff’s Game and the difference between cold and hot positions

In: Mathematics

Answer 1

A _combinatorial game_ is one for **two alternating players** where everyone knows the rules, there is **no randomness**, and everyone always knows the entire state of the game; so **no private or hidden information**. We also usually require that **the game will end** regardless of what moves are picked, and that it then **has a winner and a loser**.

A fundamental result of combinatorial game theory is:

At any moment, **exactly one player has a _winning strategy_**.

A **winning strategy** means that regardless of what the other player does, from completely random and stupid to super-intelligent beyond human levels, there is always a response that will ultimately lead to victory. It does not mean that there aren’t bad moves for the winning player; if they take a sufficiently wrong turn, then they could forfeit their win.

By the nature of this result it also tells us how to act. Indeed, **in a winning position there is at least one option that, if taken, has the opponent now start in a losing condition**. So we chose this move.

Conversely, **in a losing position the opponent will always end up in a winning position regardless of what choices we make**. So we could do anything, it does ultimately not matter.

In some sense this might imply that the game is boring: it is theoretically already decided who will win, assuming perfect play. However, in reality many games are way too complex for us to check all possible avenues and thus we often don’t even know _who_ theoretically has a winning strategy. Sometimes we do, though, despite still not knowing _how_ to win.

Back to Wythoff’s Game: _hot positions_ are those where the current player has a winning strategy, and _cold_ ones are those where they don’t (and thus by the above the other player must have one!). Wythoff proved that the cold positions are exactly those where the two stacks are of size ⌊ϕ·n⌋ and ⌊ϕ²·n⌋, where n is a natural number, ϕ is the _golden ratio_, and ⌊⌋ is _rounding down_.