The table that changes its mind

A catalogue that builds itself let a player start with an empty table and store every component it met, and found that the table’s use order — how often an entry is consulted — reaches much further than its arrival order: the ten most-consulted entries serve 91.4 per cent of 140,123 lookups, where the first ten to arrive serve 77.5. Then it warned about its own conclusion, in a section headed the advice table is advice:

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.

That is a precise complaint and it has a precise answer. A solver that only ever held ten reaches 94.2 per cent — more than the best ten chosen with the whole run in view.

An online rule beating an oracle is the kind of result that is usually a bug, so the mechanism matters more than the number.

The extra line #

The construction is what the rung below said it would be. The player decomposes each candidate move into connected regions and looks up each region’s stops; a region it has not met is evaluated and stored. The only change is a budget: when the table exceeds it, the least-valuable entry is dropped.

Two versions of least valuable are run. Least-used counts how often each entry has been consulted and evicts the smallest count, which is what the rung below proposed. Least-recently-used evicts whichever entry has gone longest without being consulted, and is the control.

One detail of the loop is worth writing down because getting it wrong makes the whole thing vacuous. The entry just inserted must have its access recorded before anything is evicted, and must not itself be a candidate for eviction on that pass. Otherwise a least-used rule looks at a table where the new entry has nought uses and everything else has at least one, evicts the entry it has this instant created, and the table never holds anything at all. It is a one-line bug that produces a plausible-looking zero per cent hit rate rather than a crash.

At ten slots the recency rule answers 94.2 per cent of lookups and the frequency rule 90.3. At twenty, 96.9 against 95.3. The two converge as the budget rises and recency is ahead the whole way.

The rates are directly comparable to the rung below’s, and that is not an accident of arithmetic. The player’s estimate comes from the full catalogue rather than from its own table — the table records what was consulted and does not decide anything — so a budgeted run plays exactly the games an unbudgeted run plays. Every run on this page makes the same 140,123 lookups in the same order. That is asserted rather than assumed, because a budget that changed the games would make every comparison here a comparison of two different experiments.

Why an oracle can lose #

The offline best ten is chosen with the whole run in view, which sounds unbeatable and is not, because of what the run is. It is 650 games across four different board sizes — two hundred on a 4 × 5, two hundred on a 5 × 5, a hundred and fifty on a 6 × 6 and a hundred on a 7 × 7 — and the regions a small board falls into are not the regions a large one falls into.

Eighteen distinct shapes appear in some board’s best ten. Three appear in all four. The best ten for a 4 × 5 shares five entries with the best ten for a 6 × 6, and a straight row of six squares is near the top on a 6 × 6 and absent from the small boards entirely, because a 4 × 5 rarely produces a region that long.

The three shapes common to all four are the two single dominoes — a vertical pair of squares and a horizontal one — and one four-cell L. Those are the regions every Domineering endgame produces regardless of how much board it started with, and they are the only shapes a fixed table could hold with any confidence. Everything above them in the ordering is board-specific: the long straight rows that a 6 × 6 breaks into and a 4 × 5 cannot, the wider blocks that survive on a 7 × 7 and are consumed early on a small board.

So the oracle is not a better-informed version of the online rule. It is something answering four questions with one answer. A rule permitted to hold different entries at different times is not competing on foreknowledge; it is competing on a freedom the offline table does not have, and that freedom is worth about three points of hit rate.

This reframes what the rung below measured. The ten most-used entries serve 91.4 per cent is a true statement and it is not advice, because no solver has to hold one fixed ten. The right question is not which ten but what rule, and the rule turns out to be shorter than the list and to beat it.

What is being counted, and why the budget is the real question #

It is worth being precise about the quantity all of this is a rate on, because 140,123 lookups from 650 games is a large number and the reason it is large is the whole justification for having a table.

A player choosing a move considers every legal placement. For each one it takes the resulting position, splits it into connected regions, and looks up each region — so one move on a partly-filled board costs a dozen or more lookups and a whole game costs a few hundred. The alternative to looking a region up is searching it out, which is what the recursion this site cannot run prices, and the ratio between the two is why anybody builds a catalogue at all.

The budget is the question because memory is what a solver actually runs out of. A catalogue of every shape to eight cells is 1,042 entries and is affordable; the catalogue that would cover the regions a 9 × 9 falls into is not, and where to stop building is where that decision was first faced. A solver that holds a fixed number of entries and chooses them as it goes is the only version of the idea that scales, because it never has to know in advance how large the catalogue it is drawing from would have been.

That is also why the offline orderings, useful as they were for establishing which quantity matters, could never have been an implementation. Sorting a table by use requires having built the whole table, which is the thing the budget exists to avoid. The rung below measured the right quantity with the wrong object, and the right object turns out to do better rather than worse.

What a use count does when it cannot forget #

The rung below’s own proposal — evict the least-used — does worse than recency, and the reason is worth having because it is a property of the rule rather than of Domineering.

A use count that is never reset is a ratchet. While the table is still under budget nothing is evicted, so every entry met in the early games banks uses for free. By the time the table is full, those entries have counts in the hundreds and a newly-arrived entry starts at one — and it will be evicted long before it can catch up, however often it would have been consulted had it survived.

So the settled table is substantially an arrival table. At twenty slots it shares 70 per cent of its entries with the first twenty to arrive and 65 per cent with the twenty most-used; at forty, 83 per cent against 68. That is the ordering the rung below measured and dismissed as the weak one, coming back through the door as soon as a budget is imposed on the strong one.

The recency rule has no ratchet, because recency is refreshed by every hit and forgotten by every miss. It cannot bank anything. That is exactly why it survives the run’s change of board size while the frequency rule is still holding shapes that were popular on a 4 × 5 three hundred games ago.

What forgetting costs #

The rung below flagged this rung as the first on the anchor whose answer could come out worse than the prediction, because an evicted entry has to be paid for again.

It is real and it is small. At ten slots the recency rule re-evaluates 7,832 shapes across the run — about one lookup in eighteen — and by eighty slots it is 469, one in three hundred. The evaluation being repaid is a stops computation on a component of at most eight squares, which is the cheapest thing this solver does; the expensive thing is the search a catalogue exists to avoid, and none of that is repeated.

The asymmetry there is the reason a budget is cheap in this setting and would not be in every setting. What an eviction costs is one re-evaluation of a small component; what a table buys is the avoidance of a whole-position search. Those two quantities differ by orders of magnitude, and knowing who wins and knowing what it is worth is where the gap between them is measured directly. A cache whose misses cost nearly as much as its hits save is a cache with a genuine tuning problem; this one does not have one, which is why every budget from ten upward is a good budget and the choice between them barely matters.

So the worry is answered in the direction the rung below hoped it would not have to be. A budget of ten is not a compromise. It answers more lookups than the ideal fixed ten and pays a fraction of a per cent of the run’s arithmetic to do it.

The same idea, one anchor over #

A table with a budget and an eviction rule is a cache, and this site has met one before under a different name. A position reached eleven ways is one position is the transposition table — the saving that comes from noticing that a search reaches the same position by many routes — and it is measured there as a saving on a search rather than as a table with a size.

The two are worth setting side by side because the comparison is instructive and the objects are genuinely different. A transposition table holds positions of the game being searched, it is thrown away when the search ends, and every entry in it is used or not within one search. A component catalogue holds shapes, it survives across games, and its whole value is that a shape met on one board is met again on another. So the second is the one where an eviction rule has something to be right or wrong about: a transposition table under pressure can evict almost arbitrarily and lose little, because its entries have no long-run frequency distribution to exploit.

What this page shows is that the distribution the catalogue exploits is not stationary. The shapes a solver meets depend on the board it is playing, and a rule that treats the past as a guide to the future is right only for as long as the board stays the same. That is not a difficulty a transposition table ever has, and it is the entire reason the two eviction rules come apart here.

The advice, rewritten #

The rung below’s advice named shapes. This one names a rule, and it is four words long: keep what was last used. A solver with room for ten answers 94 lookups in a hundred, one with room for twenty answers 97, and one with room for forty answers 99.

The difference between the two forms of advice is not presentational. A list of ten shapes is a claim that those ten are the right ten, which this page has shown to be false — there is no right ten, and the best ten on one board is half the best ten on another. A rule is a claim about how to decide, and it transfers to a board size nobody measured.

What the solver computed, and how #

The oracle is the full catalogue of connected shapes to eight cells — 1,042 of them — each with its stops computed from the canonical form. That table is what supplies the player’s estimates and is not the table under study.

The table under study starts empty. Six hundred and fifty games are played, 200 on a 4 × 5, 200 on a 5 × 5, 150 on a 6 × 6 and 100 on a 7 × 7, from one seed. A player to move enumerates its legal placements, decomposes each resulting position into connected regions, and looks up each region; ties in the resulting estimate are broken at random. Every lookup is recorded against the table, whether it hits or misses.

On a miss the entry is added, its use is recorded, and the table is then pruned to the budget by dropping the entry with the smallest score — the use count under the frequency rule, the index of the last consultation under the recency rule — with the entry just touched excluded from consideration and ties broken toward the earlier arrival. An entry dropped and later met again is counted separately as paid twice, which is the eviction cost.

Two things are asserted rather than reported. Every budgeted run must make exactly the number of lookups the free run makes, or the rates are not comparable and the whole page is comparing different experiments. And the recency rule at ten entries must exceed the offline best ten, since that inversion is the finding. The per-board figure additionally refuses to draw if all four boards share a best ten, which is the claim the explanation rests on.

Where the model stops #

One seed and one player. Six hundred and fifty games from a single random stream, with a player whose move choice is the component-sum estimate and a random tie-break. The direction of every result here is large — three points at ten slots, eighteen distinct shapes across four best-tens — and none of the exact figures has an error bar, because nothing was re-run.

Two eviction rules of the many there are. Frequency and recency are the two the rung below’s sentence and the obvious control suggest. A rule that ages its counts rather than never forgetting them would very likely close the gap, since ageing is precisely the repair for the ratchet described above, and it has not been run. So the finding is this frequency rule loses to recency, not that counting uses is the wrong idea.

And the four board sizes are the experiment rather than a sample. The whole explanation of why the online rule wins is that the run changes board size partway through. A run on one board size throughout would be a fairer fight for the oracle and would probably be a close one — that is the control this page most wants and does not have, because the free run it is compared against was built across four boards and re-running everything on one would replace the comparison rather than extend it.

The figures also cannot show a table changing. Six tables of counts describe a process — entries arriving, being consulted, being dropped — and the object is a sequence of 140,123 moments. What could be drawn is one moment: a board with its regions marked and the ten entries a solver happened to be holding beside it, which is a still. The board falls apart draws the decomposition and which shapes are worth fighting over draws the regions.

Where the ladder goes next #

The value-cost anchor has eight 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, the catalogue that builds itself, and now the one with a budget.

The rung above is the ageing rule, and it is the one experiment that would settle what this page has only diagnosed. The frequency rule loses because its counts are a ratchet; halving every count at fixed intervals removes the ratchet while keeping the information recency throws away, and the question is whether the result beats recency or merely catches it. It is the same loop with one more line, on the same 140,123 lookups, and it has a genuine prediction attached: if the whole of frequency’s disadvantage is the ratchet, ageing should overtake recency, because a count that remembers the last few hundred lookups strictly dominates one that remembers only the last.

Two neighbours are worth the trip. The catalogue a strong player needs is where the frequency census was built, and it is the ordering that comes third here — beaten by both online rules, which is a sharper verdict on a census than the rung below’s was. And when the catalogue starts paying is where a catalogue was first priced against the search it replaces, and reading it beside this page gives the whole decision: how big a table has to be before it is worth having, and what to put in it once it is.