A catalogue that knows what it will meet

Where to stop building priced a catalogue of Domineering regions by its reach — hold every shape of at most so many squares — and found the coverage saturating: 860 shapes buy twenty points of coverage, and the answer to where to build to is six or seven squares. It closed on the alternative:

The rung above is the selective catalogue. Regions are not equally common — the play-outs here produce some shapes hundreds of times and others once — so a catalogue built by frequency rather than by size would answer the same share for a fraction of the shapes.

A fraction, and at a reach of eight it is an eighth.

How unequal the shapes are #

Fifteen thousand three hundred and sixty components arise in play across four boards, and they carry 3,554 distinct shapes between them. The distribution is as lopsided as a distribution gets: the single commonest shape — a domino-shaped hole of two squares — accounts for 17.8 per cent of every component, the second for 15.9, and the ten commonest for 53.6.

At the other end, 2,749 of the 3,554 shapes appear exactly once in the whole sweep. Three quarters of the distinct shapes are singletons, which is the signature of a long tail and is exactly the condition under which ordering by frequency pays.

Two entries answer a third of every component a played board produces. Eight answer half. Then the curve flattens hard, because after the head there is nothing but the tail.

The same coverage, an eighth of the shapes #

Set the two orders against each other at equal coverage and the frequency order wins at every reach, by a margin that grows:

• a catalogue of every shape up to four squares is 15 shapes and answers 54.5 per cent; by frequency that costs 12;
• up to six squares is 104 shapes for 63.5 per cent; by frequency, 51;
• up to eight squares is 1,042 shapes for 69.1 per cent; by frequency, 119.

One and a third times at the smallest reach, 8.8 times at the largest. And the direction of that growth is the point: a size-ordered catalogue’s later entries are worth less and less, because the shapes it is adding are ones the game does not make.

That is where the whole saving comes from, and it is worth being blunt about it. The frequency order is not cleverer. It simply declines to hold what nothing produces: at a reach of eight, 759 of the catalogue’s 1,042 shapes never appear in 15,360 components of play, and a catalogue holding only the 283 that do would have identical coverage at a quarter of the size.

The share wasted climbs steeply with the reach — 1 shape of 15 at four squares, 22 of 104 at six, 759 of 1,042 at eight — because the number of polyominoes grows much faster than the number a game actually reaches.

What a round coverage costs #

Turning the question round — fix the coverage, ask the price — makes the difference starker. Half the components are answered by eight shapes by frequency and fifteen by size. And above about seven tenths no size-ordered catalogue in the table reaches the target at any size, because a reach of eight tops out at 69.1 per cent and the next reach is another threefold in shapes.

The frequency order gets there, and the price is the tail: 310 entries for three quarters, 2,018 for nine tenths, 3,401 for ninety-nine per cent. So the two orders do not merely differ in efficiency — they have different shapes. The size order buys coverage in expensive lumps and stops; the frequency order buys it smoothly and keeps going, at a price that rises steeply once the head is spent.

That is the practically useful reading. A catalogue is a head, not a range. The right object is the first hundred or so shapes by frequency, which answers seven components in ten; anything beyond that is buying the tail, and the tail is where the shapes appear once.

What the better order costs to have #

There is a reason nobody builds catalogues this way, and it is not that the arithmetic is hard.

A catalogue by size is defined by a number. Say eight squares and the catalogue is determined; anybody can build the same one; it is right for every game played on any board of any size, because it makes no assumption about what will turn up.

A catalogue by frequency is defined by a sweep. It has to be measured before it can be built, it is specific to the game and to the boards it was measured on, and it is only as good as that sweep resembles the play it will meet. Two players who like different openings will leave different shapes.

And the sweep here is random play, which is the weakest version of that objection and a real one. A strong Domineering player does not leave the shapes a random one leaves — when a real board falls apart measures the decomposition a played board produces and finds it quite unlike the catalogue’s population, and good play would narrow the distribution further. So 8.8 times is a measurement of what the order is worth against this sweep, and it should be read as the shape of the answer rather than as the number.

Why the head is so short #

Two shapes account for a third of everything, and it is worth asking why rather than only recording it.

Both are two squares. A component of two squares is a hole a single domino fits into, and there are exactly two of them up to translation — the horizontal pair and the vertical one. They are the last thing a region becomes before it disappears, so every region that is played out passes through one; and a board with many regions late in the game is mostly made of them.

That is a fact about the arithmetic of play rather than about Domineering. A game that removes two squares a move ends with regions of two or three squares, and those regions are few in number and enormously common in occurrence. Any decomposable game played to the end has the same head, and the shape of the head is set by how much a move removes.

It also explains the second observation, which is that the frequency order’s advantage grows with the reach. The head is small and cheap in both orders — a size-ordered catalogue of two-square shapes holds exactly the two, and so does a frequency-ordered one. The divergence is entirely in the middle and the tail, where a size-ordered catalogue is enumerating six- and seven- and eight-square polyominoes and a game is producing a handful of them.

So the two orders agree on the part of the catalogue that carries most of the coverage and diverge on the part that carries the rest, which is why the ratio is 1.3 at a reach of four and 8.8 at eight.

The two questions a catalogue answers #

Setting the two orders side by side gives the anchor a cleaner statement of what a catalogue is for, which is worth having after five rungs of pricing them.

A catalogue by size answers a question about the game. What can a region of eight squares be worth? — and it is the right object for that, because it is complete. When the catalogue starts paying is a question of exactly that shape: at what size does holding every shape become cheaper than searching?

A catalogue by frequency answers a question about a player. what is a player going to meet? — and it is the right object for that, because a player meets what play produces and not what enumeration produces. Its completeness is irrelevant; its coverage is everything.

Those are different objects and the rung below was pricing the first while wanting the second. The measurement here says how much the confusion costs at each reach, and the answer at the reach the rung below recommended — six or seven squares — is two to four times.

What a hundred entries buys #

It is worth putting the numbers into the form a person building a solver would want, because that is what five rungs of this anchor have been working towards.

Two entries answer a third of the components a played board produces, and they are the two two-square holes. That is not a catalogue; it is a special case worth writing into the code.

Eight entries answer half. All eight are four squares or fewer, so this is also what a size-ordered catalogue of reach four gives — the two orders have not diverged yet.

A hundred and nineteen entries answer seven components in ten, which is what a complete catalogue of every shape up to eight squares gives at 1,042 entries. This is the point of the page, and 119 is a table a person could hold in a file and a program could hold in memory without thinking about it.

Two thousand entries answer nine in ten, and are almost all shapes that appear once or twice. That is the tail, and paying for it is a decision rather than an obvious step.

The recommendation the rung below reached — build to six or seven squares — becomes, on this ordering, build the first hundred shapes a sweep produces. It is a smaller object, it answers more, and it has to be measured first.

What this does not say #

Coverage is not the same as usefulness. A component the catalogue answers is one a solver need not search, and the components it answers are the small ones — which are also the cheapest to search. So a catalogue covering seven components in ten is not saving seven tenths of the work, and the rung below’s measurement of what a catalogue saves is the one to read for that.

Random play, four boards. Every frequency here comes from random games on a 4 × 5, a 5 × 5, a 6 × 6 and a 7 × 7. A different set of boards would change the head of the distribution, and better play would change it more.

Coverage is of components, not of positions. A catalogue answers a position only if it answers every component of it, so a catalogue covering seven components in ten covers far fewer whole positions. The rung below measures both and this page measures the first, because it is the quantity an entry buys.

No catalogue here holds any values. Everything is counted in shapes: how many entries a catalogue has and what share of the components it would answer. What the entries cost to compute is the price of a value, and what looking one up saves against searching is the rung below’s subject; neither is changed by re-ordering the entries.

And the coverage of a shape is the coverage of its value. A catalogue entry answers a component by supplying its value, and two components of the same shape have the same value — so counting shapes and counting values would give the same table, with fewer distinct entries. The values of every small board is where the collapse from shapes to values is measured, and a catalogue keyed on values would be smaller again by that factor.

And the tail may be irreducible. Two thousand entries for nine tenths is a lot, and there is no reason to expect a better order to do much better — the shapes appearing once are not any order’s friends. What the frequency order buys is the head, and the head is most of what there is.

Ordering by size is ordering by the wrong thing #

A catalogue built to a reach and one built to a frequency answer the same question at wildly different prices, and the reason is worth stating, because build everything up to size n is the default and the default is nearly always wrong.

Size is a property of the shape and frequency is a property of the game. Building to a reach means paying for every shape that exists at that size, and the shapes grow like the combinatorics — a factor of three and a half a square for polyominoes. Building to a frequency means paying for the shapes that turn up, and those grow like the game’s own repertoire, which is far smaller and far flatter.

The two orderings disagree because play is repetitive. A board reaches a small structured set of regions and reaches some of them constantly, so the frequency distribution has a short head and a long thin tail — and a size-ordered catalogue spends nearly all of itself on the tail, in shape order, without ever asking whether a shape occurs.

Three quarters of a size-ordered catalogue never turns up at all, which is the measurement of that mismatch, and it is why eight shapes reach a coverage that fifteen size-ordered ones need.

The instruction generalises past catalogues. Precompute in the order the work will be requested, not in the order the objects can be enumerated — and if the request order is unknown, measuring it is usually cheaper than building the enumeration, because a play-out is short and an enumeration is exponential.

The same lesson, on a different anchor #

The shape of this finding has turned up before on this site and it is worth naming, because it is a habit rather than a coincidence.

A complete object — every shape of a size, every value of a day, every code of a length — is defined by a number, cheap to specify, and mostly full of things nothing produces. A measured object — the shapes a game makes, the values a ruleset reaches — is defined by a sweep, expensive to specify, and dense.

The values nobody’s game produces is the same contrast one level up: the theory hands down 1,474 values born by day three and the games reach under a tenth of them. This page is that observation applied to a catalogue rather than to a census, and the moral is the same — the difference between what a subject allows and what it produces is where most of the cost of an exhaustive object sits.

What is new here is a number for it in the currency a builder cares about: at a reach of eight, 73 per cent of the entries are for shapes no game in the sweep ever made.

The convention, named #

Normal play throughout: Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses.

A component is a connected piece of free squares on a board in play, four-connected, counted only when it holds two squares or more — a single square is a component nobody can move in. A shape is a component up to translation, so two components in different places on the board with the same outline are one shape.

Coverage is the share of component occurrences a catalogue answers, so a shape appearing 2,727 times counts 2,727 times. That is the quantity a catalogue entry actually buys, and it is not the share of distinct shapes, which would be a very different number.

A catalogue’s reach is the largest shape it holds; a catalogue by size holds every shape up to its reach, and a catalogue by frequency holds the commonest shapes in a measured sweep, in order.

The play-outs are random: each move is drawn uniformly from the legal ones, and every component of every position along the way is recorded. That is the rung below’s population, extended to record which shape rather than only how large.

Where the ladder goes next #

The value-cost anchor has five rungs: the two currencies separated and priced, the third question between them, what a program does instead of any of them, how much of a game a catalogue can answer, and now which shapes it should hold.

The rung above is the catalogue a strong player would need. Every frequency here is from random play, and the objection that random play is not play is the one thing that could overturn the ordering. A sweep driven by a solver playing well — which the site’s own evaluator can do on the boards in this table — would give a second distribution, and the two together would say whether the head is a property of Domineering or of randomness. If the head is the same shapes, a hundred-entry catalogue is genuinely all a player needs.

Two neighbours are worth the trip. When the catalogue starts paying is where a catalogue is priced against a search rather than against another catalogue, and it is the question the size order is the right instrument for. And the board falls apart is where the decomposition that makes any of this possible is priced, and it is the reason a catalogue of components is an object at all.