Blocking is not enough

Noughts and crosses is the game everybody has solved by the age of ten. Two competent players always draw, and when a child discovers this, the game is over for them. Ask why it is a draw and nearly everybody gives the same answer: there are only eight lines, and whenever one player gets two in a line the other blocks it. The first player has an extra move and nothing to do with it, because every threat can be answered as soon as it appears.

Part of that answer is right. The rest is exactly wrong, and the board is small enough to prove it. Take the second player’s stones and strip them of any power except blocking: they stop the first player completing a line, and they can never complete one of their own. This is what the subject calls a Maker–Breaker game. Noughts and crosses in that form is not a draw. It is a win for the first player, from the centre or from any corner, against all possible blocks.

So the thing that holds the draw is not the blocking. It is that the second player’s blocks are also threats. At the critical moment the first player has a winning move available, and cannot play it, because the opponent would complete a line first. A draw that looks like pure defence depends entirely on the defender’s ability to attack.

The second player never wins #

Before separating the two games, it is worth recalling what strategy stealing gives in this setting, since the whole family inherits it.

An m, n, k game is played on a board of m columns and n rows, with two players placing stones alternately and the first to complete k in a line (row, column or diagonal) winning. Noughts and crosses is 3, 3, 3. Gomoku in its free form is 15, 15, 5. Hales and Jewett’s paper of 1963 set out the theory for games of this kind, and the argument that names no move applies to all of it. Suppose the second player had a winning strategy. The first player could make an arbitrary move, forget about it, and then play the second player’s strategy as though moving second. An extra stone never hurts in these games, since it only occupies a cell and can only help complete lines. If the strategy ever calls for the cell already occupied, make another arbitrary move. So the first player would win as well, and both cannot. Therefore the second player has no winning strategy, on any board.

The search confirms it on every board it can finish: nowhere does the first player lose. It also has the practical effect of simplifying everything after it. Since a loss is ruled out, the question for any board is a yes-or-no one, whether the first player wins, and a program need not distinguish a draw from a loss for the first player while searching. That shortcut is what makes boards larger than about sixteen cells reachable at all on a desktop machine.

The argument’s limits are what earlier essays emphasised, and they apply directly: it says nothing about which of a win or a draw is the truth, and it names no move. Those are what the search supplies. Nor does the argument distinguish between a game that is drawn by a good defence and one drawn in some other way. It takes the separate question of Maker and Breaker to do that.

Two games on one board #

The Maker–Breaker game keeps the board, the lines and the turn order, and changes the win condition. Only Maker can complete a line. Breaker wins by placing a stone in every line, which is the same as Maker failing to own any. A draw is impossible, because a full board either has a line of Maker’s or a stone of Breaker’s in every line.

The relation between that game and the game as played is simple in one direction. If Breaker wins moving second, then in the game as played the second player can adopt that strategy, and the first player will never complete a line. So the game as played is at least a draw for the second player. And since strategy stealing rules out a win for the second player, it is exactly a draw. So if blocking suffices, the game is a draw. The converse is what fails. If Maker wins, it does not follow that the first player wins as played, because Maker’s strategy may give the opponent time to complete a line of its own, which in the Maker–Breaker game would simply not count.

The figure shows the first moves of each. As played, every first move draws, which tells a player very little. As a Maker–Breaker game, five of the nine openings win and four do not. The edge is the only opening from which blocking really is sufficient. So the common-sense view that the edge opening is the worst is correct, and it can be said why in a way that the game as played cannot: an edge opening is the only opening that gives up the Maker’s win. Against a player who only blocks, the centre and corners win, and against the same player the edge does not. The draw as played conceals that difference between the openings entirely, and it needs another game to reveal it.

A corner is not a better block #

The second move shows the same thing more sharply.

It is well known that after a centre opening the second player must take a corner, and that an edge reply loses. In the left-hand board that is what the search finds. The usual explanation is that a corner is “better”, without saying at what. The right-hand board says at what, by eliminating one possibility. In the blocking game all eight replies lose, so the corner is not a better block in any sense that blocking could measure.

The difference is a count of a different kind. After a centre opening, four of the eight lines are dead for the second player, since they run through the centre. An edge cell lies on two lines, one of which goes through the centre, so an edge reply has exactly one line left to make anything of. A corner lies on three lines, one through the centre, leaving it two. So a corner reply has twice as many live lines as an edge reply, and that is the whole gap between a lost game and a drawn one. None of those lines is any use in stopping the first player from completing anything. What they do is give the second player the chance to make a threat at the moment it matters.

The block that is a threat #

The moment is easy to find, and it is the centre of the whole argument.

The game opens with a cross in the centre and a nought in a corner. The cross takes the corner on the same row as the nought, which threatens the diagonal through the centre. The nought must block in the opposite corner of that diagonal, and that block sits in the same column as the first nought, with the cell between them empty.

Consider what the cross would like to do now, at the third panel. A cross in the middle of the right-hand column would make two lines at once: the middle row through the centre, and the right-hand column through the corner just taken. Nobody can block two lines with one stone. In the blocking game this move ends the game. The search agrees: at that point the move wins by force, and two other moves there also keep the win for Maker.

In the game as played, every one of those moves loses on the spot. The noughts need one more stone to complete the left-hand column, and the cross has just failed to stop them. So the cross is compelled to block instead, in the middle of the left-hand column, the only move on the board that does not lose. Having spent its move there, it has given up the win. The search reports that too: the block draws, and it no longer wins the blocking game either. The nought’s block has cost the cross one tempo, at the one moment the tempo decided the game.

That is the sense in which noughts and crosses is drawn because of the threats. No amount of counting lines against stones could find this: the count of lines is what makes Maker win, and the draw comes from a stone that does two jobs at the same time. It should also be said what the usual explanation gets right, namely that the draw can be held by answering threats as they come. But the answers work only because each answer changes what the other side is allowed to do next.

The one board where the two come apart #

So much for noughts and crosses. The natural question is how general this is. It might be the normal way a game of this family comes to be a draw, with blocking usually inadequate and counter-threats usually doing the work. It is not.

On all fifteen boards in the table, the Maker-first result and the game-as-played result agree, with one exception, and it is 3, 3, 3. Everywhere else, when the game as played is a draw, Breaker wins moving second, and the draw is a draw because blocking is sufficient. When the first player wins as played, Maker wins as well, as anyone would expect. A game can in principle be a Maker’s win and a draw as played, and in this range that combination occurs exactly once, on the most famous board in the family.

There is a reason to expect it to be rare at small sizes. Maker needs many lines to win at all, and a board that has enough lines for Maker to win usually gives the first player enough spare tempi to answer the opponent’s counter-threats as well. On 4 × 3, the next board along, one extra column gives Maker six more lines of three, and the first player then wins as played as well as in the blocking game. For the counter-threat to be decisive, the board must be just barely large enough for Maker to win at all, with no spare tempo for the first player. Noughts and crosses is that board: four turns to win, against a Breaker who needs only one well-timed threat. This is a plausible story and no more. A larger table might show further exceptions, and the search here stops at twenty cells.

The published results for larger boards leave plenty of room for this. The 5, 5, 4 game is a draw and the 6, 5, 4 game is a first-player win, according to the literature on the family, and both are beyond what the search here reaches. Whether 5, 5, 4 is a draw because Breaker wins, or a draw in the manner of noughts and crosses, is a question this table does not settle.

An easier kind of draw, for contrast #

It helps to see what a draw looks like when blocking really is sufficient, because it looks nothing like noughts and crosses. The simplest way for Breaker to win is by a pairing: choose disjoint pairs of cells so that every line holds a whole pair, and answer each move in one of those cells by taking its partner. Then Maker can never own both cells of a pair, and so can never own a whole line.

On this board a line must span the whole width, so only the three rows count, and each can keep a pair to itself. The answering rule is a complete strategy, and it never looks at anything. There is no threat in it, and no timing, and the second player’s stones have no attacking value. That is what a draw by blocking is at its simplest. Nothing like this can exist on the three-by-three board. Two of its lines share at most one cell, so no pair can serve two of them, and eight lines would need sixteen cells out of nine. The next essay sets out the different ways of certifying a Breaker’s win and asks how much of the table each reaches.

What the extra stone in the theorem is, and is not #

The proof of strategy stealing leans on one sentence, that an extra stone never hurts, and the separation of the two games throws that sentence into a new light. In the Maker–Breaker game it is plainly true, and its consequences are simple. More stones can only help Maker, so moving first cannot be worse than moving second, and on the table Maker moving first wins everything that Maker moving second wins.

In the game as played, the sentence is also true, and the reason needs a moment’s care. A stone cannot complete a line for the opponent and cannot unmake the owner’s lines. But a stone does use up a turn, and in a game where the opponent’s threats must be answered, a turn is what is in short supply. So the statement is exactly about extra stones in addition to turns, as the proof uses them, and not about spending a turn to place one. That distinction is what tempo means in this family. The cross’s position after the nought’s block is full of useful stones, and it is the absence of one free move that costs the win.

This also explains why the table’s three columns are in the order they are. Maker second is the weakest position, with neither threats nor tempo. Maker first has the tempo and no threats to fear. The first player as played has the tempo too, and has threats to fear. Reading across a row, the three answers can only change in a limited way: Maker first wins whenever Maker second does, and the first player as played can win only where Maker first does, because a first player’s win is a Maker’s win with fewer resources. The gap at noughts and crosses is the single board where the middle column says yes and the left-hand column says no.

Why the proof of a draw and the proof of a win look so different #

Even at this size a strategy for each side has a quite different character. Maker’s win at noughts and crosses is short and tactical, with the double threat as its one idea. Breaker’s win on a drawn board, in the simplest case, is the pairing drawn above, with no tactics at all. The game as played, on the only board where it differs, is decided by a single interaction between one player’s threat and the other’s block.

That difference matters to how anyone could hope to extend these results. A Maker’s win can be proved by exhibiting a short tree of threats, and this is how the large board results on the family have been obtained, using what Allis called threat-space search: consider only the moves that make threats, so that the opponent’s replies are forced, and the tree stays small. A draw has no such shortcut, because a draw has to answer everything. It needs a certificate of a very different kind, either a pairing or a sum or something else. And the game as played is harder than either, because the threats of both sides have to be considered at once, which is the reason the Maker–Breaker form has become the main object of study in this area.

The convention named #

Strict alternation, first to complete wins, and a full board with no line is a draw. The Maker–Breaker game changes only the final clause, in a way the two terms are meant to name. Some treatments of the family let an overline count or not count (six in a row, on a board asking for five) and that changes a small number of cases on larger boards, as tournament rules for gomoku show. Every board here is small enough that the question barely arises, and the search counts any line of length k or longer as complete by the natural rule that it contains a line of exactly k.

The table reports what was computed exhaustively for each board, with a three-valued search on boards up to fifteen cells and with a yes-or-no one above that. The two agree where both ran. Boards with a larger first dimension are listed first by convention, and a board is the same under exchange of rows and columns.

What the table cannot show #

Whether noughts and crosses is unique at any size. Fifteen boards is a very short list, and the family is enormous. A game with a Maker’s win and a draw as played might appear again at larger sizes or in three dimensions, and there are published results on some such boards that this table cannot compute and does not rely on.

What a human opponent sees. A child who learns to draw at noughts and crosses learns the replies, not the theory. Nothing here says the explanation given in this essay is the way anyone experiences the game, only that the common explanation is false as a matter of computation.

Anything about why a player should prefer a win in the blocking game. The Maker–Breaker result says something definite about the openings: the edge is the one that gives up the win. It does not say that an edge opening is easier to draw against, or that a real opponent is more likely to go wrong after a corner. Those are questions about players, and they are outside this calculation.

Still open: how a Breaker’s win can be known without searching for it #

The table above comes from an exhaustive search, and that stops at about twenty cells. For a board too large to search, the only way to know that a draw is a draw is by a certificate, and two are available from the theory: a pairing, of the kind just drawn, and the sum over lines that Erdős and Selfridge used, which says that Breaker wins if the lines are few enough relative to their length. Both are sufficient. Neither has been proved necessary, and how much of the true picture they capture can only be judged by comparing them against a table like this one, on boards where the truth is known. That comparison turns up draws that both miss.