A catalogue that builds itself

The catalogue a strong player needs measured which Domineering regions a strong player’s games actually produce, found eight of the ten commonest shapes surviving strong play, and closed on the catalogue that is not built in advance at all:

The rung above is the catalogue that changes as it is used … 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.

It converges on the frequency order by use and not by arrival, and it does not stop growing.

The construction #

The player starts with an empty table. It plays the ladder’s usual way — estimate a move by summing its components’ stops, take the best — with one change: a component it has never met is evaluated and stored rather than falling through to the mobility rule.

So the table is built out of what the games ask for, in the order they ask, with nothing swept in advance. Every entry carries a count of how often it has been consulted, which costs one integer and turns out to be the whole of the finding.

Six hundred and fifty games over four boards, 140,123 lookups, and a table that ends with 232 of the catalogue’s 1,042 shapes.

It is worth being clear about what a lookup is here, because 140,123 of them is a large number for 650 games. A player choosing a move considers every legal placement, and for each one it decomposes the resulting position into connected regions and looks up each region. So a single move on a partly-filled board costs a dozen lookups, and a game costs a few hundred. That is what makes a catalogue worth having at all — what a program does instead is where the alternative, searching each component out, is priced.

It does not settle #

The first surprise is negative and it matters for what a solver should do.

The table is still growing when the run stops: 171 entries at 450 games, 189 at 500, 201 at 550, 223 at 600, 232 at 650. There is no plateau and no sign of one.

That is not obvious in advance. A strong player’s games produce a concentrated distribution of regions — the rung below’s whole finding — so a table built from them might have been expected to fill quickly and stop. It fills quickly and then keeps adding, because the tail of the distribution is long and every game reaches a little further into it.

So a solver that stores everything it meets does not converge on a table. It converges on a habit of adding, and its memory is bounded only by how long it plays. That is the awkward half of the arithmetic that said a catalogue is worth building: the crossover where a catalogue starts paying was computed against a catalogue of fixed extent, and a table with no plateau has no fixed extent to price.

The order things arrive in is nearly arbitrary #

The rung below’s frequency order is a census: which regions a strong player’s games actually produce, commonest first. The question is whether a self-built table reproduces it.

By arrival it does not. Of the first ten shapes stored, four are among the ten commonest; of the first twenty, ten; of the first forty, thirteen. A rare shape met in the first game is stored first, and being stored first says nothing about being wanted again.

By use it does. Rank the table’s entries by how often they were consulted and nine of the top ten are among the ten commonest, fourteen of the top twenty, and twenty of the top forty.

That gap is the page. What has been seen and what has been looked at often are two orders on the same entries, and only one of them is a census.

And by reach they are equal #

Content is one measure and reach is the one the rung below used: what share of the lookups a catalogue of a given size actually serves.

The ten most-consulted entries serve $91{\cdot}4$ per cent of the table’s 140,123 lookups. The ten commonest by the frequency census serve $90{\cdot}3$. The first ten to arrive serve $77{\cdot}5$.

So a self-built table pruned by use is not merely close to the census-built one — it is very slightly ahead of it, which is what it should be, since the census is a sample of a different set of games and the use count is a sample of these ones. Pruned by arrival it is thirteen points behind.

At twenty entries the gap narrows and at a hundred it nearly closes, which is the shape a concentrated distribution always gives: any reasonable ordering eventually catches up, and what an ordering is worth is what it does when the table is small.

A fifth of the catalogue, and where the rest is #

Two hundred and thirty-two entries out of 1,042 is worth dwelling on, because it says something about the catalogue as well as about the solver.

Four fifths of the catalogue’s shapes never came up at all in 650 games across four boards. Those are the regions a played game does not produce: awkward shapes with long thin arms, shapes with holes, shapes that require a very particular sequence of placements to leave behind. The rung below found the same thing from the other end — that a catalogue built by size over-serves a strong player, because the small shapes it holds are not the shapes play produces.

So the catalogue of 1,042 is not a set of regions a solver needs; it is a set of regions that exist. The difference is a factor of five on this population, and it is bigger on larger boards, since the count of shapes grows much faster than the count a game meets.

That is a general shape and it is the reason this anchor exists. The cost of a value is not a property of the value; it is a property of how often anyone asks for it.

What a solver should do #

The rung below built its catalogues to be chosen in advance, and the practical question it left is what a solver with limited memory should hold. This page’s answer is unusually concrete.

Add freely and evict by use. A solver that adds every region it evaluates and, when short of room, discards the least-consulted entries ends up holding what a census would have told it to hold — without the census. Ten entries chosen that way serve nine lookups in ten.

Do not add selectively. A solver trying to be careful about what it stores has to decide in advance, and the information it would decide on is exactly what it does not have yet. The arrival order is what careful in advance degenerates to, and it is the worst of the three.

And the counting is the cheap part. One integer per entry, incremented on every lookup, is what separates a table as good as the census from one thirteen points worse. The storage is the expensive part and the counting is free.

That is a satisfying place for this anchor to arrive, because it removes the census from the loop. Where to stop building priced a catalogue by its reach and built it by size; the rung below rebuilt it by frequency and had to measure a strong player’s games to do it; and a solver doing neither, with one counter per entry, gets to the same place.

What the entries actually are #

It is worth looking at what the two orders put at the top, because the shapes are recognisable and the difference is visible without the statistics.

By use, the top entries are the ones a Domineering board falls into constantly: the two dominoes, the short straight strips, the small L-shapes. By arrival, the top entries include those and also whatever the first game happened to leave behind — a seven-square region with an awkward notch, met once, stored for ever.

The rung below’s census puts the two dominoes and the short strips at the top too, which is why the use order matches it. The three orderings agree about what is common; they disagree about what else to keep, and what else to keep is the whole of a small catalogue.

Why arrival and use come apart #

The mechanism is worth a paragraph because it is not specific to Domineering.

A region enters the table the first time it is met and is consulted every time thereafter. So arrival order is a statistic of first occurrences and use order is a statistic of all occurrences, and the two orders agree only if the distribution is uniform enough that first occurrences are spread like the whole population.

They are not. A common region appears in nearly every game and its first appearance is early — but so is the first appearance of a rare region that happened to occur in game one, and after that the rare one is never seen again. The arrival order therefore mixes the commonest entries with the unluckiest, and it has no way to tell them apart, because at the moment of arrival every entry has been seen exactly once.

That also says when arrival would be good enough: on a population with a short tail, where nearly everything is common, first occurrences and total occurrences order the same way. This population has a long tail — 232 entries after 650 games and still climbing — which is precisely the condition under which arrival is a bad order.

The same result, in one sentence #

A learner reaches the expert’s table if it remembers how often it looks things up, and does not if it only remembers what it has looked up.

That sentence has nothing to do with Domineering, and it is worth noticing how little of the machinery it needs. The population has to have a long tail — most things rare, a few things constant — and the learner has to be storing rather than deciding. Both conditions are ordinary. What is not ordinary is having a census to check the learner against, which is what the rung below built and what makes this measurement possible rather than plausible.

So the transferable content is a warning about first-occurrence statistics. A table, a cache, a list of things worth knowing, built by adding whatever turns up, is ordered by first occurrence unless somebody counts — and on a population with a long tail first occurrence is close to noise. The counting is one integer and it is the difference between a table as good as a census and one that is not.

What this does not settle #

One seed, one run. Six hundred and fifty games from one random seed. The tie-break in the player’s move choice is random, so a different seed gives different games, and nothing here measures how much the numbers move. The direction of the result — use beats arrival — is large enough that it will survive; the exact 91.4 against 77.5 is one sample.

The player is strong and its strength comes from the oracle. A component the player has never met is evaluated correctly when it is stored, from the full catalogue’s values. So this is a solver with unlimited access and limited memory, not one learning values from scratch. A genuine learner would have to compute each new entry itself, and the interesting question of what that costs is not asked here.

Eviction is not simulated. The table is never pruned during the run; the orderings are computed afterwards from the completed table. A solver actually evicting by use would have a different table, because an entry evicted early might never be re-added at the right moment. That is a real difference and it would make the use order’s advantage smaller rather than larger.

The concentration does the work and is not measured here. Nine lookups in ten from ten entries is a fact about how concentrated a strong player’s regions are, and the rung below is where that concentration was established. This page inherits it: the use order’s reach is high because the distribution is skewed, and on a flatter distribution every ordering would look alike and none of this would matter.

Four boards, up to seven by seven. The same population the rung below used, which is what makes the comparison meaningful and what bounds it.

And the reach is measured on the run’s own lookups. The use order is scored on the lookups it was built from, which flatters it — that is why the fair comparison is with the frequency census, which was built from a different set of games and is only a point behind.

And nothing here is drawn. Six tables of counts, and the object — a board falling into regions, each looked up in a table that grows — is a process rather than a picture. What could be drawn is one position with its components marked and the table’s entries beside them, which is a still of one moment in 140,123. The board falls apart draws the decomposition and which shapes are worth fighting over draws the regions themselves, and between them a reader has the picture this page is counting.

The advice table is advice. Four rows saying what a solver with a given amount of room should do, and none of the four has been run as a solver. They are readings of the orderings measured here, and the third row in particular — ten entries by use serve nine lookups in ten — is a statement about a table built without eviction and then sorted, not about a solver that only ever held ten.

Normal play, Domineering throughout, and a region means a connected piece of at least two free squares.

What it cost to find out #

One number is worth recording because it is the sort a reader of a solver paper never sees.

The whole measurement — 650 games, 140,123 lookups, a table built from nothing and two orderings scored against a census — is twelve seconds. The census it is compared against took longer to build than the experiment that made it unnecessary.

That is not an argument against censuses; the census is what made this checkable. It is a note about where the expensive part of a question like this actually sits. Deciding what a solver should remember sounds like an engineering question needing a large experiment, and the experiment is small; what is large is the enumeration of every region there is, which is the thing the self-built table turns out not to need.

Where the ladder goes next #

The value-cost anchor has seven 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, which player it should be measured on, and now the catalogue that builds itself.

The rung above is eviction. Every number here is computed after the fact from a table that was never pruned, and the honest version of the finding — add freely and evict by use — describes a solver nobody has run. A solver with a fixed budget of entries, adding on every miss and evicting the least-used, is one loop with one extra line, and the question is whether the table it settles on is the one this page’s ordering predicts. It is also the first question on this anchor whose answer could be worse than the prediction rather than better, because an evicted entry has to be paid for again.

Two neighbours are worth the trip. The catalogue a strong player needs is where the frequency census was built, and it is the standard this page’s self-built table matches without having it. And a catalogue that knows what it will meet is the same idea one anchor over — a table built for the positions that turn up rather than for the positions there are — and reading the two together is the site’s account of what a solver should remember.