Where to stop building

A program that plays Domineering well does not evaluate boards. It evaluates the regions a board has fallen into, looks each of them up, and adds the values — which is why a board that falls apart is easier, and which needs a catalogue of small regions to look things up in.

When the catalogue starts paying priced that catalogue against the search it replaces: it pays after 5 to 206 boards depending on how far it reaches, and the crossover falls as the board grows. It closed on the question a program author actually has to answer:

This page says where the catalogue stops paying and not where it stops being useful, and the two are different questions: a catalogue that reaches eight squares answers a share of the positions a board falls into, and what that share is — measured against the reach, on a real board — is what decides where to build to.

The share saturates, and it saturates early.

What is being measured #

The measurement is a play-out and a lookup. Six hundred and fifty games are played at random on boards of 4 × 5, 5 × 5, 6 × 6 and 7 × 7; every position they pass through is broken into its connected regions; and each region is asked whether it is small enough for a catalogue of a given reach.

Two shares come out of that, and they are different questions:

• component coverage — the share of regions the catalogue can answer, which is what a program’s lookup rate would be;
• position coverage — the share of whole board positions every one of whose regions is inside the catalogue, which is what a program’s complete answer rate would be.

The second is much the smaller and it is the one that matters, because a board with one region outside the catalogue has to be searched anyway.

The price of a point #

The marginal table is the whole decision:

Build to six or seven squares. Past that the catalogue costs more than a hundred shapes for every point of coverage it adds, and past nine it costs more than a thousand. The last three squares together buy less coverage than the first one did, and cost six hundred times as much.

The shape of the table is two exponentials running against each other. The number of polyomino shapes grows by a factor of about three and a half per square, and the share of regions of a given size falls at least as fast, so their product — the coverage bought per shape stored — collapses.

The catalogue’s own cost, for scale #

The shapes are not the only currency. Building a catalogue means evaluating every shape in it, and the evaluation of a nine-square region is not the evaluation of a three-square one.

At reach ten the catalogue is 12,871 shapes and takes about six seconds to build in this site’s evaluator; at reach six it is 104 shapes and takes a tenth of a second. So the two costs — shapes stored and seconds spent — rise together, and neither is the reason to stop. The reason to stop is that neither buys anything.

That is worth separating clearly. A cost that rises steeply is a reason to build carefully; a benefit that stops rising is a reason to stop building. This table has both, and the second is the one that settles the question.

Why the coverage saturates #

The reason is not about catalogues at all. It is about what a board looks like early in a game.

A board before it breaks up is one region, and one region of forty-nine squares is outside every catalogue anybody will build. So each board carries a floor of positions no reach can touch: 38 per cent of the positions on a 4 × 5 board, 46 on a 5 × 5, 54 on a 6 × 6 and 60 per cent on a 7 × 7.

That floor is what the saturation is made of. The coverage a catalogue can ever reach is one minus the floor, and the floor grows with the board — so a catalogue is worth less on a larger board, exactly where the search it replaces is dearest.

This is the same phenomenon one fight makes a board a fight ran into from the other side, where half the positions in a play-out could not be given a temperature because a region was too large. Two censuses, two purposes, one obstacle: the early game is where the exact machinery does not reach.

What that means for a program #

Three consequences, and they are not the ones the crossover suggested.

The catalogue is an endgame instrument. It answers most of what it will ever answer by six squares, and what it answers is the late board. A program relying on it is a program that plays the endgame by lookup and the opening by search, which is the opposite of the usual arrangement in game programming.

A larger board makes it worse, not better. The crossover falls with board size — the catalogue pays sooner on a big board, because a big board’s search is dearer — and the coverage falls too. So the catalogue becomes cheaper to justify and less able to help at the same time, which is a trap worth naming.

And the missing part is not a tail. Forty to sixty per cent of positions have a region beyond ten squares. That is not a residue to be mopped up with a slightly bigger catalogue; it is the majority of the game, and it needs an approximation — a bracket, a bound, a heuristic — rather than a table.

What a program would do with the rest #

If half the positions are outside the catalogue, the question is what to do with them, and this site has measured three of the available answers.

Search them. That is the honest answer and it is what the crossover is a price for. A region of a dozen squares is expensive but not impossible, and the tree and the graph is where the memoisation that makes it affordable is priced.

Bound them. Two errors that cancel is the reading built for exactly this: a band from a count of dominoes, which needs no evaluation, adds across a board and holds the value about seven times in ten. It is the natural companion to a catalogue, because it covers the case the catalogue misses.

Or decompose them further. A twelve-square region is not a catalogue entry and it is often nearly two — a narrow waist, a single square joining two halves — and a program that spotted those would convert an uncovered region into two covered ones. Nothing here measures how often that would work, and it is the obvious thing to measure next.

What the rung below’s number becomes #

The crossover — how many boards a catalogue has to serve before it pays for itself — reads differently with the coverage beside it.

A catalogue that reaches eight squares pays for itself after about twenty boards on a 5 × 5, which sounds like a bargain. But it only answers half the positions those boards pass through, so the search it was meant to replace is still being run on the other half, and the effective saving is half of what the crossover suggests.

Multiplying the crossover by the coverage is the honest figure, and doing that moves the sweet spot down rather than up: a six-square catalogue costs a twentieth as much to build as a ten-square one and answers 85 per cent as many regions. Nothing in the pricing rewards the extra reach.

That is the answer the rung below asked for, and it is worth stating as an instruction rather than as a finding: build the catalogue to six or seven squares, spend the rest on the approximation for everything else.

The two shares, and which one a program feels #

It is worth being careful about which number a program actually experiences, because the two shares differ by twenty points and lead to different designs.

Component coverage is what the lookup table sees. Around 70 per cent of the regions a game produces are inside an eight-square catalogue, so seven lookups in ten succeed. That is a respectable hit rate and it is the number a cache designer would quote.

Position coverage is what the evaluation sees. Around half the positions have every region inside the catalogue, so half the evaluations complete without a search. That is the number the program’s speed depends on, and it is much the smaller because a position is only answered when all of its regions are.

The gap between them is the arithmetic of and: a position with three regions needs three lookups to succeed, and 0.7 cubed is 0.34. So the more a board has broken up — which is the situation the catalogue was built for — the more likely it is that one of the pieces is the one that missed.

That is the awkward heart of it. A catalogue helps most on a decomposed board and a decomposed board gives it the most chances to fail. The two effects nearly cancel, and what is left is the modest position-coverage figures above.

The arithmetic also says how to read one share off the other, which is worth having because only one of them is cheap to measure. If a position has $k$ regions and each is inside the catalogue with probability $c$, the position is answered with probability about $c^k$ — so position coverage is component coverage raised to the average number of regions, and the exponent is a property of the board rather than of the catalogue. That is why the twenty-point gap between the two shares widens with board size: a larger board breaks into more pieces, the exponent rises, and the same lookup rate delivers less. The independence the estimate assumes is not exactly true — a board that has split into many regions has split them all small — but it is true enough to explain the shape, and it means a program author who improves the lookup rate by a point gains rather less than a point where it counts.

What this does not say #

Four limits.

Random play. The positions are those random games pass through, and a game between strong players would break the board up differently — probably later, since a good player avoids splitting a board they are winning on. That would lower the coverage further.

Domineering only. The saturation is driven by how fast the number of shapes grows against how fast the regions shrink, and both are properties of this game. In Amazons an arrow cuts the board permanently, so regions shrink much faster and a catalogue would cover far more.

Coverage is not saving. A region answered by lookup saves whatever its search would have cost, and small regions are cheap to search. So the coverage figures overstate the benefit: the regions the catalogue answers are the ones the search would have found easiest, and the ones it misses are the expensive ones. That is the reverse of the trade a cache normally offers.

And the reach is measured in squares, not in shapes. A catalogue could be built selectively — the common shapes to ten squares, the rare ones to six — and nothing here prices that. It is the obvious engineering answer and it needs a frequency count the play-outs could supply.

Who builds catalogues #

Endgame databases are the standard instrument of computer game-playing and their economics are usually discussed the other way round: chess tablebases grow with the number of pieces, are consulted for exact play near the end, and everybody accepts that the count of positions is astronomical. The unusual thing about a combinatorial game is that the database’s entries are values rather than outcomes, so an entry stays valid inside every position that contains the region — which is the argument for building one at all.

Berlekamp’s Go endgame work is the fullest example: a library of small local positions with their values, combined by the theory rather than searched. The reach question there is answered by the game — a Go endgame is made of small local positions by nature — and Domineering is the case where it has to be answered by measurement, because its regions shrink slowly.

What this page adds to that literature is a number rather than an idea: the coverage curve is flat past seven squares, so the received practice of building as far as the memory allows is buying almost nothing.

The convention, named #

Normal play, Domineering, Left placing vertically.

A region is a connected component of free squares with at least two squares in it; single squares are ignored, since neither player can use one. A catalogue’s reach is the largest region it holds, and it holds every shape up to that size, counted up to the eight symmetries of the square.

Component coverage is the share of regions inside the reach; position coverage is the share of board positions all of whose regions are. The two are reported separately throughout because a program’s lookup rate and its complete-answer rate are different numbers and the second is smaller.

The shape counts are the catalogue’s own: 15, 36, 104, 312, 1,042, 3,584 and 12,871 at reaches four to ten.

One line is worth carrying away. A catalogue’s reach buys coverage that saturates and costs shapes that do not, so the question is never how far a table can be built but where the two curves cross — and here they cross at six or seven squares.

Where the ladder goes next #

The value-cost anchor has four rungs to here: the two currencies separated and priced, the third question that sits between them, what a program does instead of any of them, and now how much of a game a catalogue can answer at all.

The rung above builds the selective catalogue this page’s last section asks for, and the numbers are much better than “the same share for a fraction of the shapes” suggested. A catalogue that knows what it will meet orders the shapes by how often play actually produces them, and eight shapes answer half the components a played board produces — a catalogue by size needs fifteen for the same half, and 1,042 for what 119 chosen by frequency reach. The advice above becomes sharper as well as cheaper: three quarters of a size-ordered catalogue never turns up in play at all, so most of what the tenth square buys is not merely poor value but dead weight.

The rung after that answers the objection this whole measurement rests on. Every figure here comes from random play, and random play is not play. The catalogue a strong player needs re-runs it against a player that reads the board, and the head of the distribution survives — eight of the ten commonest shapes are the same — while the tail collapses: 114 entries answer nine tenths of what a strong player meets, against 2,018 for the random one. Strong play concentrates the distribution rather than moving it.

And it settles the direction of the error, which matters more than the counts. A catalogue built on random play over-serves a strong player, and one built on strong play does not serve a random one. So the measurement on this page is conservative in the safe direction: every share reported here is a floor for the play a program will actually meet, and the saturation it finds arrives even earlier than six squares once frequency is taken into account.

Two neighbours are worth the trip. How often a board falls apart is where the decomposition rate is measured, and it is the other half of what decides a catalogue’s worth — a board that never splits gives a catalogue nothing to do. And two errors that cancel is the approximation this page’s uncovered majority has to be handed to, and it is the reading that survives being added across a board.