Combinatorial Game Theory
who wins, and by how much
Concept

Convention — where it appears

A rule outside the moves that decides who has won once the moves run out — normal play gives the loss to whoever cannot move, misère gives it the win. Everything computed here depends on which one is in force, and a position can change hands when it changes.

Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.

The money played out, and it never mattered. The bidding rule played move by move with a countable pool of chips, at every way of splitting it. The verdict is constant across the splits and opposite under the two ways of resolving equal bids, so what settles these positions is the tie-break rather than the money.

The auction never gets to the money

The critical fraction is computed and never played. Played out with a countable pool of chips — twelve positions, four pool sizes, every split of the chips, every bid answered — the verdict does not move with the money on a single one of the forty-eight sweeps, and the rule for equal bids settles all forty-eight. The reason is one line long: declining every auction wins, and bidding nothing declines.

limits · Bidding The same number, from a rule that needs no tie-break. The number computed twice: once as the critical share of a pot under the auction, and once as the probability that Left wins when a fair coin decides who moves at each turn. They agree on every position, and only the second derivation survives being played out.

A coin needs no tie-break

The same recursion has a second derivation: a fair coin decides who moves at each turn, a player whose turn it is with no move has lost, and both play to win. Written from those rules it comes out identical on every position — and it needs no rule for equal bids, because there are no bids. The number is a probability, it belongs to Left rather than Right, and the empty position is the one where the coin decides everything.

limits · Bidding The cost falls as the cool part warms. Cost of hottest-first play against the temperature t of the coolest part, on one three-part board with Right to move. For a plain switch the cost is 1 − 2t and vanishes at a half; for a cool part with a follow-up it is 1 − t. Twice the coolest temperature, drawn dashed, lies below both curves for small t.

The cheapest fight is not the yardstick

Hottest-first play was found to cost at most twice the coolest temperature on the board, on pools whose coolest parts sat at a quarter or a half. Put a fight worth an eighth on the board and the rule costs seven times it. On one board the cost falls as the cool part warms, which is the opposite of a bound in the coolest. The number that holds on all 14,946 lines of seven pools is the second-largest temperature.

complexity · Approximation What each assumption buys back. Forty-five positions of up to two heaps of up to eight, sorted into classes that no test position of up to three heaps can tell apart, under four rules. Two-player Nim has sixteen classes, both three-player conventions have forty-five, and one player against a coalition of two has six.

What survives a coalition

Three-player Nim has no winner without a convention and no sum theory at all. Fix one player against the other two and both come back: every position has a winner, the winner is read off the number of heaps of one modulo three and the number of larger heaps, and forty-five positions fall into six interchangeable classes — fewer than Nim's sixteen. Fix a scoring rule instead and the winner comes back, identical to one of the conventions, and nothing else does: no two positions are interchangeable.

limits · Multiplayer The second temperature, with the threat on top. Hottest-first play against the best reply on four pools whose hottest component is a threat of the form {10 | {8 | 0}}, with a switch just below it and a smaller threat below that. Over 2,254 lines the cost never exceeds the second-largest temperature on the board and meets it exactly on 97.

The price of a tie

The second-largest temperature bounded hottest-first play on 14,946 lines, and the pool that should have broken it puts a threat on top. It does not break: over 2,254 more lines the cost never passes the second temperature and meets it on 97. What the pool finds instead is where the rule goes wrong — one move into the game about as often as at its start — and why. Almost every line that meets the bound is a tie: two parts equally hot and the rule taking the first on the board. Break ties well and the lines meeting it fall from 636 to 51 on the earlier pools, and to none on any board with the threat on top.

complexity · Approximation Six rulesets, and the heaps that stop mattering. Single heaps of six impartial rulesets classified under three-player play with one player against a coalition of two. Nim's heaps fall into three classes; subtraction {1, 2} keeps five, Kayles six, subtraction {1, 3} ten, subtraction {2, 3} twelve and Dawson's Kayles ten before every larger heap is interchangeable, and three rulesets have a smaller heap that joins the large class early.

A coalition counts to three

Three-player Nim with one player against two collapses to six classes, because every heap of two or more is a store of tempo either side can draw on. Put the same coalition on games whose heaps are not all stores and it does not collapse: subtraction {1, 2} keeps five kinds of heap, Kayles six, subtraction {1, 3} ten and {2, 3} twelve, each count settling as the range grows. Past a threshold the large heaps are interchangeable again — and in every one of the five, unlike Nim, a single large heap hands the game to the coalition. The classes neither refine the two-player values nor coarsen them: {1, 3} has two Grundy values and ten coalition classes.

limits · Multiplayer Answering locally wins back half. Six cheap tie-breaks for hottest-first play and the searched one, scored over 17,200 lines of eleven pools by the share of board order's excess cost over the search each recovers: first on the board 0%, prefer to deny the opponent one -28%, prefer a follow-up of one's own 21%, answer where the opponent just played 50%, answer locally, else deny 32%, answer locally, else a follow-up 71%, locally, a follow-up, then an urgent denial 52%, the best, by search 100%.

Answer where the opponent played

Most of what hottest-first play costs is the choice between parts equally hot, and a search could make that choice well. Six choices a player could make without searching were scored on all 17,200 lines of eleven pools. Answering where the opponent has just played wins back half of what board order loses, and 95 per cent of it on the pools with a threat on top; preferring a part with a follow-up of one's own wins back a fifth; the two together, 71 per cent. Preferring to deny the opponent a follow-up is worse than taking the first part on the board, and denying only an urgent one takes the combination back down to 52. What is left is mostly at the opening move, where there is nothing yet to answer.

complexity · Approximation

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchDisjunctive sumCounterexampleApproximationFollow-upHeuristicHotstratSenteTemperatureAlternationBoundDecision

All concepts