The catalogue a strong player needs

A catalogue that knows what it will meet priced a catalogue of Domineering regions by how often play produces each shape, and found the frequency order beating the size order by nearly nine times. It closed by naming the objection:

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 … If the head is the same shapes, a hundred-entry catalogue is genuinely all a player needs.

The head is the same shapes, a hundred entries is more than enough, and the catalogue built from random play turns out to be the safe one.

The player, and whether it is strong #

The player is a heuristic and not a solver, and it is worth saying exactly what it is.

At each turn it decomposes the board into regions, looks up every region small enough to be in the catalogue, and sums their stops — what each player gets moving first. If every region is in the catalogue the estimate is exact; if one is too large it falls back on the count of available placements, which is this site’s own rule of thumb. It plays the move with the best estimate, breaking ties at random. That is the same estimate when the catalogue starts paying priced against a search, used here to move rather than to evaluate.

That is what a player with the catalogue in front of them would do, which is the right player to ask this question of. And it earns the word: against a player choosing uniformly at random it wins 232 of 240 games, with the sides swapped on every board.

The random tie-break is not a detail. A deterministic player produces one game per board, so a sweep of six hundred and fifty games would be measuring four lines of play; breaking ties at random gives a distribution.

What each style produces #

The same six hundred and fifty games, on the same four boards, played two ways.

Random play produces 15,360 components carrying 3,554 distinct shapes. The board-reading player produces 24,439 components — more, because its games last longer — carrying 1,477.

So playing well more than halves the number of distinct shapes a game visits, while producing more components. The two facts together are the interesting shape: a strong player plays longer games and sees less variety in them, which is what a player who knows where they are going looks like from the outside.

The board falls apart counts how often a Domineering board decomposes at all, and this is the same question asked about the pieces: not how many there are, but how many different ones. That is not what the rung below could see, and it is the first sign that the catalogue’s answer changes with the player.

The head is the same #

Eight of the ten commonest shapes are the same under both. The order among them differs and the shares differ — the commonest shape is 17.8 per cent of random play’s components and 35.3 per cent of the strong player’s — but the shapes themselves are the game’s, not the sampler’s.

That is exactly the condition the rung below named. It could not be assumed: a random player wanders into shapes a real one would never make, and if the head had been made of those, the whole frequency ordering would have been an artefact.

The shares moving in the same direction is the second half of the answer. A strong player does not merely visit the same shapes; it visits them more concentratedly, because it is steering the board into positions it can evaluate.

A hundred entries, and fewer #

The counts are not close.

Seven entries answer three quarters of what a board-reading player meets. A hundred and fourteen answer nine tenths.

The rung below priced a 119-entry catalogue and reported it as answering 69 per cent of the components random play produces. The same catalogue answers 84 per cent of what the strong player produces, and a catalogue built for the strong player answers nine tenths at the same size.

So the hoped-for conclusion holds and is understated: a hundred entries is not merely enough for a player, it is enough for a player and most of the way for a random one.

Which catalogue is safe #

The cross-coverage is where the practical answer is, and it is asymmetric.

A catalogue of 119 entries built from random play answers 69 per cent of random play’s components and 84 per cent of the strong player’s. It does better on the population it was not measured on.

A catalogue of 119 entries built from strong play answers 90 per cent of strong play’s components and 54 per cent of random play’s. It does far worse on the population it was not measured on.

The reason is that random play’s distribution is wider. A catalogue built from a wide distribution covers a narrow one that shares its head; a catalogue built from a narrow one has spent its entries on a head the wide distribution shares and nothing else.

That gives a rule for building any such catalogue, and it is the opposite of the obvious one. Measure the frequencies on the weaker player, not the stronger: the resulting catalogue costs the same and is robust to the opponent turning out to play differently from the sweep. A catalogue tuned to one style of play is a catalogue that fails against another.

Why playing well narrows the board #

The concentration is worth an explanation, because a stronger player visits fewer shapes is not obvious and is not a general fact about games.

A Domineering move does two things: it takes a placement, and it changes the shape of what is left. A random player is indifferent to the second, so it cuts regions apart wherever the dice fall and produces a long tail of ragged shapes. A player reading the board is not indifferent: it is evaluating the position after the move, so it prefers moves leaving regions it can evaluate — which on this player means regions inside the catalogue.

So the strong player is steering toward the catalogue, and the concentration is partly a self-fulfilling property of the player rather than a property of good Domineering. That is the circularity named further down and it is why the numbers here cannot stand alone.

What is not circular is the head. The two commonest shapes under both styles are the same two, and they account for 33.7 per cent of random play’s components and 62.7 per cent of the strong player’s. A shape that commonly arises when nobody is trying is a shape the game’s geometry produces, and the strong player finding it too is evidence about Domineering rather than about the catalogue.

Which is the reason the rung below’s objection was worth taking seriously and is now answered rather than dismissed. Had the two heads disagreed, the frequency order would have been a fact about a dice-throwing program, and the 119-entry catalogue would have been a catalogue of shapes no player ever meets. They agree, so it is not, and the ordering survives the one thing that could have overturned it.

The board falls apart is where the decomposition is priced, and the reading here is one level up from it: a board does not merely fall apart, it falls apart into a small number of shapes, and how small depends on who is playing.

The player who slips #

Real players are neither. So the sweep is run a third time with the strong player making a random move one time in seven, which is what a good opponent who has not solved the game looks like.

It sits between: 2,098 distinct shapes, and 12 entries for three quarters against the pure strong player’s 7 and the random player’s 310.

The concentration therefore degrades smoothly with the quality of play rather than collapsing, and it degrades from the tail rather than from the head — which is a second reason a catalogue built on the wide distribution is the right one to hold. Every degree of imperfection in an opponent moves the population toward the sweep the catalogue was measured on.

The three styles also bracket the answer in a useful way. Whatever a real opponent is, the number of entries they need lies between 7 and 310 at three quarters’ coverage, and between 114 and 2,018 at nine tenths — and the catalogue the rung below priced sits comfortably inside the first bracket and at the bottom of the second. A specification that is right for the whole range of opponents is worth more than one fitted to a point in it.

What a builder should take from this #

The anchor exists to price the machinery a Domineering program would carry, so it is worth collecting the answer as a specification.

Hold about a hundred regions. At 119 entries a frequency-ordered catalogue answers 84 per cent of the components a strong player meets and 69 per cent of a random one’s. Past that the curve is flat: 300 entries buy two more points against the strong player.

Measure the frequencies on weak play. The catalogue built from random play is the robust one, and it costs nothing extra to build — the play-outs are cheaper, since no evaluation is needed to make a move.

Expect the tenth that is not covered to be the expensive part. A component outside the catalogue is a search, and searches are what the catalogue exists to avoid; when the catalogue starts paying prices exactly that trade and is the page a builder should read next.

And do not tune it to an opponent. The asymmetry in the cross-coverage is the whole practical finding: a catalogue fitted to one style of play loses half its coverage against another, and a catalogue fitted to no style in particular loses nothing.

That last is a general point about measured objects and this site keeps arriving at it from different directions. A catalogue that knows what it will meet established that a measured object beats a complete one; this page adds the qualification, which is that a measured object inherits whatever the measurement was made against, and a wide measurement is the one that inherits least.

Why the direction of the error is the finding #

The two numbers — 114 entries against 2,018 — are the headline and the asymmetry underneath them is worth more, because it decides whether every measurement on this anchor was wasted.

A catalogue built on one distribution and used against another can fail in two directions. Over-serving means it holds entries that never turn up: wasted memory, wasted build time, and nothing worse. Under-serving means it lacks entries that do turn up: a lookup misses, the search runs, and the whole saving the catalogue was built for is not there.

The measurement here says which way round it goes. A catalogue built on random play over-serves a strong player — it holds everything the strong player meets and a great deal besides — and one built on strong play under-serves a random one.

So every figure on this anchor is conservative in the safe direction. The coverage numbers measured against random play are floors for what a strong player would experience, the catalogue sizes are ceilings, and a builder who follows the random-play measurements ends up with more than they need rather than less.

That is the property that makes the earlier rungs usable rather than obsolete, and it is not automatic — it holds because the head of the two distributions is the same eight shapes and strong play differs by concentrating the tail rather than by moving it. A player whose commonest shapes were different, rather than merely fewer, would have broken every number on this ladder, and checking that they are not is the only reason this rung had to be run at all.

What this does not say #

The player is not a solver. It reads stops from a catalogue of regions of at most eight squares and falls back on a count when a region is bigger, which on a 7 × 7 board is most of the early game. Where to stop building is the page that fixed eight squares as the catalogue’s reach, and the fallback is the mobility rule three rungs down a different anchor. So the sweep measures a player with this catalogue, and a catalogue measured on such a player is measured on something that already depends on it. That circularity is real and is why the random sweep stays the primary measurement.

Four boards, and the largest is 7 × 7. These are the rung below’s boards, kept so the two pages compare, and 49 squares is small for Domineering.

Shapes, not positions. A component is recorded by its shape up to translation, so two components in different places on the board with the same outline are one entry — which is what a catalogue holds and is not what a player sees. A catalogue that knows what it will meet is where that convention is set out and where the frequency order was first priced.

And nine tenths is not everything. The remaining tenth of a strong player’s components are shapes the catalogue does not hold, and a player meeting one has to search. When the catalogue starts paying is where a catalogue is priced against a search rather than against another catalogue, and it is the page that says what that tenth costs. Where to stop building says how much bigger the catalogue would have to be to cover it, which is a great deal.

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 shape is a component up to translation. Coverage is the share of component occurrences a catalogue answers, so a shape appearing a thousand times counts a thousand times.

The random player chooses uniformly among its legal placements. The board-reading player computes, for each placement, the sum of its components’ stops when every component is in the catalogue and the difference in available placements otherwise, and takes the best — breaking ties uniformly at random. The player who slips is the same with a random move one time in seven.

A catalogue’s entries are ordered by frequency in the sweep that measured it, and using it against another population means taking its first $n$ entries and asking what share of that population’s components they answer.

The sweep is 650 games across four boards, played identically under each style.

Where the ladder goes next #

The value-cost anchor has six rungs: the two costs separated, the third question between them, what a program does instead, how much of a game a catalogue answers, which shapes it should hold, and now which player it should be measured on.

The rung above is the catalogue that changes as it is used. Everything here is a catalogue built once from a sweep and then held fixed; a solver that added each region it had to evaluate would build its own catalogue as it played, and the question is whether it converges on the frequency order or on something else. The measurement is the same play-outs with a growing table and a record of what it holds at each point, and it would say whether the frequency order is a target a learner reaches or a thing that has to be measured in advance.

Two neighbours are worth the trip. Where to stop building is where a catalogue was first priced by its reach, and it is the size-ordered baseline every number here is against. And the board falls apart is the decomposition that makes a catalogue of components an object at all, and it is worth reading beside a finding about how a strong player steers the decomposition.