A win priced in stones

A game with a yes-or-no answer offers no way to say how close a result was. Noughts and crosses in the Maker–Breaker form is a win for Maker, and 4 × 4 with four in a row is a win for Breaker, and those two statements have the same form, one bit each. But it would be surprising if they were the same size. A game can only be measured if something in it is allowed to vary, and in 1978 Vašek Chvátal and Paul Erdős found the thing to vary. They kept the board and the lines and let the players take different numbers of cells per turn.

A biased game gives Maker a stones a turn and Breaker b. The fair game is 1 : 1. As b grows, Breaker’s task gets easier, and on any fixed board there is a smallest b at which Maker stops winning. That threshold is a number, and it says how much a win is worth, in a currency the game itself provides. The same applies from the other side: as a grows, Maker’s task gets easier, and the first a at which a draw turns into a Maker’s win measures how solid the Breaker’s hold was.

Those two thresholds are computed exactly here for the small boards. What they show is how narrow the fair game’s results are: the first extra stone decides nearly everything, and most of these boards flip at the very first step in one direction or the other. They also provide a real test of the biased sum, the theorem that generalises the Erdős–Selfridge potential, and it turns out to be exact on noughts and crosses and high on every larger board.

Sixteen boards, two prices #

Everything on the table is exact, an exhaustive search with the rate fixed. Maker moves first throughout. Look first at the column for stopping Maker. Where the fair game is already a Breaker’s win, the value is 1, and that accounts for ten of the sixteen. Where Maker wins the fair game, the price of stopping is almost always 2: three in a row at 3 × 3, 4 × 3, 5 × 3, 6 × 3 and 4 × 4 all fall to a Breaker placing two a turn. The one exception on the table is 5 × 4, which holds out until three. Nothing in this range gets past three.

Now look at the column for what Maker needs. Where Maker already wins the fair game the value is 1, as it has to be. Where Breaker wins, the value is usually 2 and sometimes 3. For a line to be missed at 1 : 1 and made at 2 : 1 is the common case: 4 × 4 at four, 5 × 4 at four, 5 × 3 at four, 6 × 3 at four, all of them Breaker’s wins at the fair rate, all of them Maker’s at two. On 3 × 2, 4 × 2, 5 × 2 and 6 × 2 with three in a row, which look like nothing at all, a Maker placing two stones a turn wins in two turns. Only the pure line boards hold out longer: 4 × 3 at four and 5 × 3 at five each need 3 : 1, because each has only a few lines, and a line has to be built in a run of one or two turns.

So the fair game sits within a single stone of a flip on nearly every board in the table. A win or a draw at 1 : 1 is not a robust result. It is the outcome of a game played at a rate where small changes matter most. The most striking case is the most familiar board.

Noughts and crosses at two stones a turn #

The whole of Maker’s advantage on the 3 × 3 board disappears with a single extra stone a turn. Against one stone, five of nine openings win. Against two, none does. It is easy to see why. Maker’s only winning method on this board is the double threat, two lines each one stone short at once. A double threat works because one stone cannot answer two lines. Two stones can. To beat a Breaker placing two, Maker would need a triple threat, and there is no cell on a board this size that can bring three lines to completion at the same moment before Breaker’s stones have killed most of them.

There is a connection with the earlier result about noughts and crosses that is worth saying aloud. In the game as played, the second player can draw, although Maker wins the blocking form. The explanation was that the second player’s blocks create threats, which at the critical moment cost Maker exactly one tempo. In the biased game, the second player has no threats at all but simply gets an extra stone, which is one extra tempo per turn. Each of these gives enough to reach a Breaker’s result. So the size of Maker’s margin on the board, measured by two different methods, is under one tempo in the first case, and under one stone per turn in the second. That is what a narrow win looks like in numbers.

How fast the winner finishes #

The second number that varying the rate provides is speed. At the slowest rate at which Maker wins, how many of its turns does it take to force a line?

Here the expected order is reversed. Noughts and crosses takes four turns: a double threat cannot be built in fewer stones against best resistance on such a cramped board, and the winning line is finished on the fourth stone. The boards of height three, 4 × 3 and 5 × 3, take four as well. The boards of height four take three. It might seem that a larger board gives a Breaker more room to escape, but it gives Breaker no extra stones, and all it gives Maker is more lines through each cell. A Maker on an open enough board can create a double threat with two stones and finish on the third. So height is what decides the speed here, and width adds nothing. That is the second hint this table gives that height is the thing that matters.

The boards won only at higher rates take two or three turns at those rates. A Maker placing three a turn on 4 × 3, needing a whole row of four, wins on the second turn, and the method is pretty. It puts one stone in each of the three rows. Breaker can spoil only one row. Maker’s next three stones then complete one of the other two. The rate of three is exactly the number needed for that argument, one stone on each row in the first turn and three to fill the rest in the second, which is why two a turn fails on this board.

The biased sum, and how high it runs #

Beck’s 1982 generalisation of the Erdős–Selfridge criterion says that with Maker placing a and Breaker b, Maker moving first, Breaker wins if the sum over lines of (1 + b) raised to the power of minus k/a is less than 1/(1 + b). The sum gives a computed value of b at which a Breaker’s win is guaranteed. On a small board there is the exact value to set beside it.

On noughts and crosses, the sum is exact. Eight lines with k = 3 at b = 2 give 8/27, which is under 1/3, so the sum certifies a Breaker’s win at two stones a turn; and the search says two is the true value. At one stone the sum would be one, against a bound of one half, so the sum correctly says nothing, and the search says Maker wins. The theorem is at its sharpest on the board with the fewest lines at this length.

As lines are added it goes high. On 4 × 3 the sum asks for three against a true two. On 5 × 3 it asks for four, and on 6 × 3, with 26 lines, it asks for five, where two is still enough. On 4 × 4 it asks for four against two, and on 5 × 4 five against three. The growth of the sum tracks the number of lines, slowly but steadily, while the true price has barely moved. The reason is the same as at the fair rate. The sum weighs each line alone, and on a real board the lines overlap so much that one Breaker stone kills several at once. What the sum sees as 26 separate threats is, on the board, a much smaller number of places to play. It is a sound bound, and it is sharp when the lines barely overlap. How loose it gets is a direct measure of how much the lines share.

That looseness does not always persist at larger scales, and the biased theory is known for a striking positive result. Chvátal and Erdős posed the question on another positional game altogether: Maker claiming edges of a complete graph on n points, aiming for a spanning tree, against a Breaker claiming b per turn. The fair version of that game is settled early by Lehman’s theorem. The biased threshold is a much harder question, whose answer, due to Gebauer and Szabó in 2009, is asymptotically n/ln n, which is where a random graph with Maker’s share of edges would itself become connected. So in that family the exact price matches what one would compute by supposing both players played at random. Whether anything similar happens for the line games drawn here cannot be seen at these sizes. No board here has enough room for the asymptotics to have started.

Why price does not simply follow the count of lines #

Compare the prices with the earlier table of fair results, and the price of stopping Maker is above one on exactly the boards where Maker wins at the fair rate, as it must be. What the price adds is resolution, of the kind a temperature adds to a bare statement that a move matters. Among the k = 3 boards with Maker winning, 3 × 3 has 8 lines and a price of 2. The 6 × 3 board has 26 lines and has the same price of 2. And 5 × 4, with 34 lines, is at 3. So adding 18 lines to noughts and crosses buys nothing at this rate, whereas the eight more lines from 26 to 34 buy a whole stone. The explanation is that shape matters. Two Breaker stones per turn can contain a board of height three however wide it grows, at least as far as this table goes, and it is plausible that this is a matter of height rather than of width. Testing that takes boards the search cannot yet reach.

The other column has a similar lesson. On 4 × 3 at four and 5 × 3 at five, a Maker must have three stones a turn. On 5 × 3 at four, which is the same size of board and asks for a shorter line, two will do. Four in a row on a five-wide board has room for two placements along each row, whereas five in a row has only one. So the number of placements per row decides what the Maker needs here, more than how long a line is. Where a row admits just one placement, as on those two boards, the 4 × 3 argument above applies: three rows need three stones, one in each. A row admitting two placements can be spoiled less easily by a single Breaker stone, since a stone on an end cell of a row of five leaves the other placement alive, and that is why two a turn is enough there. It is the same overlap that lets one pair serve several lines, seen from the other side of the game.

What a price is, as a quantity #

It is worth asking what kind of number has been measured here, since this subject already has several ways of attaching a number to a game. A Conway value measures an advantage in free moves, added across components. A temperature measures how urgently a position wants a move. Both are defined by a recursion on options and are exact statements about sums. The price of a line game is none of these things, and it would be a mistake to read it as one. It applies to a whole board, not a component, and it is not additive, since a line game does not break into independent parts as long as lines cross.

What it most resembles is the sense in which the threat of a ko is counted in moves available elsewhere. In that case a player has to spend a move on something outside the fight in order to come back to it. Here the rate of play changes how many moves a player may spend in a single turn, and it asks what the game looks like when one side can do two things at once. A double threat, the main weapon on these boards, is exactly a situation in which doing two things at once would be enough to respond. A rate of two turns that weapon off. So the price of stopping Maker on these boards is mostly reporting the widest threat Maker can build: two lines at once on almost every board here, and three on 5 × 4. That reading has not been proved in general, and the 5 × 4 case would have to be examined for a triple threat to confirm it. But it gives an interpretation of the number that is about the board and not about the theorem.

The convention named #

Maker moves first throughout, and that convention matters at small rates. Had Breaker moved first, some boards would shift, since Maker’s first stone is worth a great deal on a small board. Since the fair game’s table has already separated Maker-first from Maker-second results, this essay holds that fixed and varies only the rate.

A rate is taken as placing all of a turn’s stones at once with no intervening reply. So 2 : 1 is two stones, then one reply, then two more. Other conventions exist, in which the first turn has a reduced number of stones to make the rates fairer, as connect-style games with an opening rule do. Those would produce different numbers on these boards, particularly at the small end.

What the table cannot show #

Any trend. Sixteen boards are not a trend, and the largest of them has twenty cells. Whether price grows with width at fixed height, or with height alone, has been suggested here by a handful of cases and is nowhere established. The search is the limit: rates above 1 : 1 explode the number of positions, and the 5 × 5 board at three in a row exceeds what this program can store.

That the fair game is special. Almost every board here flips within a stone of the fair rate, and it would be natural to conclude that fair rate is somehow the critical one. That is partly an artefact. Boards chosen because they are small have short lines, and their thresholds are necessarily small integers. On a much larger board the thresholds could lie far from one, as they do in the spanning-tree game.

What a fractional price would be. A rate of 3 : 2 is well defined, and the true “value” of a win might lie between integer rates, with one board’s Maker surviving 3 : 2 and another’s not. The search here tries integer rates against one, so these thresholds are coarse, and a table with fractional rates would refine them without changing what they broadly say.

Still open: whether height is the thing that matters #

The table’s one exception to a stopping price of 2 is 5 × 4. The boards of height three stay at 2 up to width 6, while 4 × 4 is at 2 and 5 × 4 is at 3. That suggests a two-dimensional table in which the price rises with both sides, but in steps at different places. The next entries are 6 × 4, 5 × 5 and 7 × 3, all out of reach of a plain search with unbiased memory, but well within reach of a program that stores positions compactly and uses the board’s symmetries at every depth. Three or four more values would show whether a board’s height sets the price with width only filling in, which would be a clean statement about these games. It would be also the first place where this family started looking like something other than a list.