Three ways to know a draw

Blocking is not enough separated two questions about a board of m columns, n rows and k in a line. Whether the first player wins as played is one. Whether Maker can own a line against a Breaker who only blocks is the other. When Breaker wins moving second, the game as played is a draw automatically, and on all fifteen boards the essay tested but one, that is why a drawn board is drawn. So the practical way to establish a draw is to establish a Breaker’s win. On a small board the search does that. On anything larger than about twenty cells, somebody has to argue for it.

Two arguments are standard, and they came from different places. The first is a pairing, which goes back at least to Hales and Jewett’s paper of 1963: choose disjoint pairs of cells so that every line holds a whole pair, and answer any move in a pair with its partner. The second is a potential, from the 1973 paper of Erdős and Selfridge: give each line a weight, add them up, and show that a small enough total can never grow to what a finished line would need. An earlier essay ran that rule on Hex. Here the point is the comparison. Given a family where the truth is known on small boards and both certificates can be computed on hundreds of boards, what does each one see, and what lies in the gaps?

There are three results. The two certificates coincide on square boards for no reason either can see. There are small draws, the four-by-four board among them, which are real, which Breaker wins, and which neither certificate can certify. And the comparison between the two depends entirely on one detail in what a pairing is allowed to be. Read strictly, the sum is far stronger. Read properly, the sum certifies nothing the pairing does not.

The certificate that needs no thought #

A pairing strategy is one of the oldest ideas in this subject, and in a positional game its logic is especially clean. If every line contains a pair, and the pairs are disjoint, then Breaker answers a move in a pair by taking the other cell of that pair, and plays anywhere else in response to a move outside the pairs. Maker can then never own both cells of any pair, and so never all of any line.

The drawing shows it on 5 × 5, where the arithmetic is tight: twelve lines at two cells each is twenty-four, out of twenty-five. On a board where each line runs the full side, two lines share at most one cell, so no pair can do double duty, and the question reduces to Philip Hall’s matching theorem of 1935. Duplicate each line, and ask for a matching from the line copies into their own cells with no cell used twice. A polynomial algorithm finds that or proves there is none. On those boards a pairing is a certificate of the most satisfying kind: a small table, checkable by eye, computed cheaply and needing no further thought.

On a board longer than its line, something else becomes possible, and it is the detail on which the rest of this essay turns.

This board has six lines, three placements in each row, and ten cells. If every line needed two cells of its own, twelve would be needed, and the pairing would fail. But the placements in a row overlap. A pair covering the third and fourth cells of a row lies in both the placement starting at the second cell and the placement starting at the third. So two pairs in a row serve all three of its placements, and four pairs serve the board. The count of cells has to be replaced by a search, since which pairs to pick is now a choice with consequences for other lines. That search is cheap on the boards here and is not obviously cheap in general. What it gains is large.

The certificate that gives a rule #

The potential argument is entirely different in kind. Give each line that Breaker has not yet touched a weight of 2 raised to minus the number of its cells Maker has not yet claimed. Every empty line starts at $2^{-k}$. A line Maker has wholly claimed has weight 1. Breaker’s rule is to take the cell where the weights of the lines through it add up to the most.

Here is why the total does not grow. When Maker takes a cell, each line through it doubles, so the total goes up by exactly the weight of lines through that cell. When Breaker then takes a cell, all lines through it die, so the total falls by the weight of lines through that cell. Because Breaker chose the heaviest cell, including the one Maker would like to play next, what Maker adds at the next turn is at most what Breaker just removed. So after each pair of moves the total has not risen. Starting from $S = \text{lines} \times 2^{-k}$, Maker’s first move at most doubles it, and if the result stays below one no line can ever reach the weight of one. So Breaker wins moving second whenever S is under one half.

This is a strange kind of certificate. It takes one number, computed by multiplication, and needs no knowledge of the shape of the board. Three lines that cross and three that do not have the same potential. And it provides a rule of play as a by-product: the proof comes with an algorithm built in, and that algorithm can be tried outside its guarantee. A pairing, in contrast, says nothing at all about a board where it fails.

It is short enough to follow on a board. Take five wide and three high with four in a row. Each row has two placements, so there are six lines at a sixteenth each, and the sum is 0.375. Maker takes the middle cell of a row, which lies in both of that row’s placements, and those two lines double to an eighth each. The total is now 0.5. Breaker adds up the weight through each empty cell. The three middle cells of that row carry a quarter each, and any other cell carries at most a sixteenth more than nothing, so Breaker takes a middle cell beside Maker’s stone. Both of the row’s lines die and the total falls to 0.25. Nothing Maker can do later revives them, and it now has two untouched rows and the same argument waiting in each. That is also a pairing argument in disguise: Breaker’s two stones and Maker’s one have settled a whole row, as a pair of middle cells would have.

The comparison with the truth #

Reading across the table shows what each sees. Of the eleven boards, eight have a pairing and five have a potential under one half, and those five are all among the eight. So on the small boards, every draw the sum certifies has a pairing as well. On 4 × 2 and on 5 × 2 at three, and on 6 × 3 at four, the sum fails, at 0.5, 0.75 and 0.5625, and a pairing succeeds.

Noughts and crosses sits in the same table with a Breaker’s loss, which is a useful reminder of what the theorems are claiming. Its potential is exactly 1, above the bound, so the sum is correctly silent, and two lines there share at most a cell, so no pairing exists.

The two boards in magenta are what the certificates cannot reach. On 4 × 4 with four in a row and 5 × 4 with four in a row, Breaker wins by exhaustive search, no pairing exists on either, and the potentials are 0.625 and 1.0625. The second potential is larger than noughts and crosses’, and Breaker wins it while losing noughts and crosses. So the potential does not simply measure how dangerous a board is. It is a sound one-way test, and above the bound it says nothing, whatever its value.

The last column contains the result that was not anticipated. The potential gives a rule, and the rule can be played with no guarantee. Tested against every possible line of Maker’s play, Breaker’s largest-danger rule, with ties broken by a fixed order, holds on every drawn board in the table where Breaker can win at all: on 4 × 4, where the theorem says nothing, and on 5 × 4 at four, where the sum is more than double its bound. This is what the earlier measurement on Hex saw too, a rule working well past its proof. The proof treats the lines as if each must be defended on its own, and a single Breaker stone on these boards kills several at once.

Both arrive at five #

For square boards with a full line, the two conditions are short enough to write out, and no sharing is possible. There are 2n + 2 lines. A pairing needs $4n + 4$ cells among $n^2$, which first holds at $n = 5$, where 24 is at most 25. The potential is $(2n + 2)/2^n$, which must fall under one half, and it does first at n = 5, where it is 0.375, with 0.625 at n = 4. One of these conditions is polynomial, and the other is exponential. One counts cells, and the other weighs lines. The coincidence is a small accident of arithmetic at low n, and nothing in either method explains it.

The accident does draw attention to a clean fact. On the 3 × 3 and 4 × 4 boards neither certificate is available, and these are the two square boards that need a search. On 3 × 3 the search says Maker wins, which is why no certificate could exist. On 4 × 4 Breaker wins, and there the certificates are simply too weak. So the only two small square boards without a certificate have different truths, and a certificate’s absence is no evidence for either.

Which reaches further, and the detail that decides it #

The natural first version of this scan requires each line to own two private cells, which is what Hall’s theorem can decide in polynomial time. Under that reading the comparison comes out overwhelmingly for the sum: 150 boards are certified by the sum alone, and just three by a pairing alone. Written up on that basis, the conclusion would have been that the potential dominates and a pairing is only good for being simple.

That conclusion is wrong, because the strict reading is not what a pairing strategy needs. Allow a pair to serve every line containing it, as on the 5 × 2 board above, and the 150 disappear completely. Across all 440 boards, the sum certifies no draw for which a pairing does not exist. The 231 boards with a sum under one half all have pairings. A further 36 have a pairing and a sum at or over one half. The sum’s apparent advantage was entirely an artefact of asking for private cells on boards where lines overlap.

Why this should be so is not obvious, and nothing here proves it in general. It would be false for arbitrary families of winning sets, since the sum needs only their sizes and a pairing needs a particular arrangement. In a family of lines on a grid, a long board has many overlapping placements that one pair can cover, and the arrangement is always favourable. The boards where the sum is under one half have lines long compared to their number, and that seems to be enough to leave room. As a measured fact over these boards it holds without exception, and as a statement about all m, n, k boards it is an open question here. The range was chosen before the result was known, and it is simply where the search runs comfortably.

So the two tools do not stand in the relation they appeared to. As a certificate on this family a pairing is the stronger of the two, and also a complete written strategy. What the potential offers in exchange is cost and generality. It takes one multiplication and no search, and it applies to any family of winning sets without regard to shape. A pairing on a large board takes a search of unknown difficulty, and it gave up on 38 of these boards within the limit set. That a stronger certificate is more expensive is a familiar pattern, and the essays on what a search costs make it in other forms, including the check that a position is symmetric before searching it. It is worth saying plainly that this comparison had its result backwards until the definition was read with care.

The convention named #

The criterion is for a Breaker moving second. With Breaker moving first, the bound is S < 1 rather than 1/2, and more boards qualify. Everything in the comparison uses the second-player version, because that is the one that certifies a draw in the game as played. A Breaker’s win as first player says nothing about the game in which the other side moves first.

A pairing here means disjoint pairs with a whole pair in every line, with no requirement that a pair serve only one. Disjointness is the part that cannot be relaxed, because Breaker’s answer to a cell has to be unique. There is a more general notion than this, in which Breaker’s reply to a cell may depend on the position, and the three pairings on Hex show how that family behaves on another board. On these boards the question has not been asked, and a Breaker’s win with no fixed pairing, like 4 × 4, may well have one of those more flexible forms.

The scan does not decide who wins. Every entry in it concerns only whether a certificate exists. The 135 boards in the fourth row include real wins for Maker and may include further draws like 4 × 4.

What the certificates cannot show #

Whether the rule always holds where Breaker can win. The largest-danger rule has been checked on the listed boards, against all of Maker’s play, and it holds on all those where Breaker wins. Beyond that this is a pattern, and on Hex a pattern of the same kind eventually failed. The tie-breaking is also part of what was tested, and another tie-break might not do the same.

How close to the truth either is at larger size. The comparison with the truth stops at twenty cells, since that is where the truth stops being computed. The share of draws neither certificate reaches may rise or fall with size.

Whether the 38 undecided boards have pairings. Each of them is a board such as 7 × 7 at six, where the search ran out of its step limit. A longer run or a better search order might settle them, and if the pairing fails on all 38 this would change none of the counts above except the fourth row. It would not touch the main result, because the sum is silent on all 38.

Whether the theorem-shaped statement is true. That the sum implies a pairing on all m, n, k boards is suggested by 231 cases out of 231 in this range. It might have a short proof, and it might fail on a large thin board outside it.

Still open: how much Breaker has to spare #

A certificate says whether Breaker wins, and neither one says by how much. Noughts and crosses is a Maker’s win by the narrowest of margins, since one well-placed counter-threat holds it as played. Five by four at four is a Breaker’s win by some unknown margin, and it seems strange that a potential of 1.0625 should mean nothing about it. The sum’s own form suggests the right scale for a margin. Weight a line’s cells by the number of stones Breaker gets each turn, and ask how many stones per turn are actually needed. That turns a yes-or-no question into a number on both sides of the line, and it is the subject of the next essay, which also asks how well the sum predicts it.