A count that forgets

The table that changes its mind gives a Domineering player a table of component values with room for only a few entries, and runs the same 650 games under two ways of deciding what to throw out. Evicting whatever was used least recently answers 94.2 per cent of 140,123 lookups with ten entries. Evicting whatever was used least often answers 90.3. The rule that counts uses loses, and loses to a rule that remembers nothing but the order of the last few uses.

It named the reason and did not test it. A use count that is never reset is a ratchet: entries that arrived while the table had room bank uses for free, and a newcomer starts at one and is evicted before it can catch up. So the counted table ossifies into the early games. And it made a prediction with teeth: halve every count at fixed intervals, and the ratchet is gone while the frequency information recency throws away is kept — so if the ratchet is the whole of frequency’s disadvantage, the aged count should overtake recency, not merely catch it.

This is that experiment. The prediction holds. It holds by a small margin, at a particular interval, and the interval is the more interesting finding.

The same loop, with one more line #

Nothing about the games changes. The player considers each legal placement, splits the resulting board into connected regions, and looks up each region’s stops. The estimate comes from the full catalogue of 1,042 shapes, so the table under study never influences a move; every run makes the same 140,123 lookups in the same order, which is checked rather than assumed.

The one change is in the counting. Every so many lookups — the half-life — every count in the table is halved. An entry used heavily a thousand lookups ago and not since loses half its standing each interval, and a newcomer used steadily now overtakes it within a few intervals. Six half-lives are tried, from 25 lookups to 5,000; a game of this run averages about 216 lookups, so they range from a tenth of a game to more than twenty.

At every table size, a count that forgets at the right rate beats recency. At ten entries a half-life of 50 lookups answers 94.66 per cent against recency’s 94.25. At twenty, a half-life of 200 answers 97.08 against 96.88. At forty, a half-life of 1,000 answers 98.63 against 98.56. And the count that never forgets sits well below all of them — 90.30, 95.26, 96.98.

So the diagnosis was right. The frequency rule’s deficit against recency was not a deficit of frequency information; it was the ratchet, and a count that forgets keeps the information and loses the ratchet. At ten entries, halving the counts every fifty lookups moves the counting rule from four points behind recency to four tenths of a point ahead.

The margin is small, and that is also a finding #

Four tenths of a point is not much, and it is worth being honest about what it does and does not say.

The prediction was that ageing would overtake recency because a count remembering the last few hundred lookups strictly dominates one remembering only the last. It overtakes. It does not dominate by much, because recency already captures almost everything the recent past has to offer in this run: the shapes a Domineering board breaks into change slowly within a game and sharply between board sizes, and a rule that tracks the last few uses follows both.

What the counts add is a little stability. A shape used constantly for the last hundred lookups and skipped for the last three is evicted by recency and kept by an aged count, and the aged count is right to keep it more often than not. At ten entries that is four tenths of a point of 140,123 lookups — a few hundred more hits over the whole run — which is the size of the effect of remembering a little more than the last thing.

And the margin shrinks as the table grows: 0.41 points at ten entries, 0.21 at twenty, 0.07 at forty. A table with room for forty shapes rarely evicts anything that matters under any sensible rule, so the choice of rule stops mattering, which is what the table that changes its mind found for recency against frequency as well.

The right memory grows with the table #

The best half-life is not a constant of the game. At ten entries it is 50 lookups, about a quarter of a game. At twenty it is 200, a game. At forty it is 1,000, nearly five games.

That scaling has a plain reading. A table with room for ten shapes can hold only what the current stretch of the current game is producing, so its counts should forget quickly — anything learned more than a quarter of a game ago is about positions no longer on the board. A table with room for forty can hold the shapes that recur across games, so its counts should remember across games; forgetting quickly would evict shapes that will be back in the next game.

Put another way, the half-life is measuring how far back the table can afford to look, and the answer grows with its size — faster than the size, as the next section but one shows. That is not a property of Domineering in particular; it is the ordinary behaviour of a cache whose contents drift, and the four board sizes of this run are what make the contents drift.

And the longest half-lives fall back. At ten entries, halving every 5,000 lookups answers 93.11 per cent — below recency — because a count that takes twenty games to halve is very nearly the count that never forgets, ratchet and all.

Choosing a half-life without seeing the run #

A solver does not get to try six half-lives and keep the best. It has to pick one before the games start, and the table of best half-lives says what a sensible rule for picking would look like.

The best half-life divided by the table size is five lookups per entry at ten entries, ten at twenty, and twenty-five at forty. The right memory grows faster than the table. A rule that set the half-life proportional to the table size would be right at one size and too forgetful at the larger ones, and the counts would drift back toward recency there.

That is consistent with the explanation in the previous section and adds something to it. A small table is full of shapes the current stretch of play is producing, and those change within a game. A large table has room for shapes that recur between games, and the time between recurrences of the rarer ones is longer than a game, so the counts that keep them must last longer than a game. The larger the table, the rarer the shapes at its bottom, and the longer their counts have to last.

How much a wrong choice costs also depends on the size, and in the opposite direction. At ten entries the half-lives from 25 to 100 all land within 0.13 points of one another, but stretching the half-life twenty-fold, from 50 to 1,000, gives up more than a point — enough to fall behind recency. At forty entries the whole range from 25 to 200 sits within three hundredths of a point, and even the longest half-life tried loses less than half a point from the best. A small table needs its memory tuned; a large table barely notices. That is the same fact as the shrinking margin seen from the other side: when a table rarely evicts anything that matters, no rule for choosing what to evict can matter much either.

A practical solver would not stop at a fixed rule. It could measure its own eviction regret — how often it re-evaluates something it recently threw out — and lengthen the half-life when regret is high, which is the same signal the re-evaluation counts below provide after the fact. Nothing of the kind is run here. What the run supplies is the evidence that such tuning has a target, and that the target moves with the table.

A cache by another name #

A table of component values with an eviction rule is a cache, and computing has studied caches under pressure for as long as it has had memory to run short of. A position reached eleven ways is one position is the transposition table, the cache a search keeps of positions it has already valued; what it costs to notice a repetition prices the bookkeeping that identifies them. Neither has had to choose what to forget, because the searches measured there are small enough to keep everything.

The component catalogue is different in the way that makes the eviction question interesting. Its entries outlive the game they were created in, and their value depends on what the next games will need. Where to stop building faced that for a catalogue built in advance and priced each extra point of coverage; this page faces it for a catalogue built on the fly, where the question is not how much to hold but how long to remember why each entry is held.

Why the board sizes matter to all of it #

The run is 200 games on 4 × 5, 200 on 5 × 5, 150 on 6 × 6 and 100 on 7 × 7, in that order, and the change of board is the reason recency beat the fixed tables in the first place.

Eighteen shapes appear in some board’s best ten, and three in all four. Every change of board size replaces most of what a small table should hold, and a counted table has to un-learn the old board before it can learn the new one. The ratchet makes that impossible; ageing makes it take a few half-lives. So the best half-life at a given size is also a statement about how quickly the distribution moves relative to how much the table can hold — and a run that never changed board would put the balance somewhere else entirely. That run is the obvious control, and it is a separate experiment with a separate answer.

What forgetting costs #

Hit rate is one measure of a table. The other is what its mistakes cost, and in this setting a mistake is an eviction that has to be paid for again: a shape thrown out and met later is evaluated a second time.

The best half-life pays fewer re-evaluations than recency at every size — 7,253 against 7,832 at ten entries, 3,854 against 4,144 at twenty, 1,685 against 1,790 at forty. The count that never forgets pays 13,365 at ten entries, nearly twice what recency pays, which is the ratchet’s cost in a currency other than hits: an ossified table keeps evicting the newcomers the games actually want and paying for them again.

The two measures agreeing is worth a sentence. A rule could in principle answer more lookups by thrashing — evicting and re-evaluating cheaply — and the hit rate alone would hide it. Here the better hit rate comes with fewer re-evaluations, so the aged count is not winning by churning; it is winning by keeping the right shapes.

The evaluations being repaid are stops computations on components of at most eight squares, the cheapest thing this solver does. Knowing who wins and knowing what it is worth prices the search a table exists to avoid, and it is orders of magnitude dearer. So none of these re-evaluation counts threatens the table’s worth; they rank the rules.

The ratchet, seen from inside #

The earlier essay measured what the never-forgetting table holds and found it closer to an arrival table than to the use order it was meant to approximate — at forty entries, 83 per cent of its contents are among the first forty shapes to arrive. That is the defect ageing repairs, and the repair can be stated as a property of the counts rather than of the hit rates: under a half-life, an entry’s count is a weighted sum of its uses with weights falling by half every interval, so an entry’s standing is dominated by its last few half-lives of use and by nothing earlier.

That is also why the aged count and recency end up close. Recency is the limiting case of ageing with an infinitely short half-life — only the last use counts — and the count that never forgets is the limiting case with an infinitely long one. The six half-lives sit between the two extremes, and the curve of hit rate against half-life rises from recency’s level, peaks, and falls toward frequency’s. The peak is where the table’s size and the distribution’s drift balance.

What the run cannot say #

One seed, one sequence of boards, one player. Every number here comes from the same 650 games; none has an error bar, and margins of a tenth of a point are well within what a different seed could move. The direction of the result — some half-life beats recency at every size, and the best half-life grows with the table — is the claim, and the exact half-lives are measurements of this run.

Six half-lives is a coarse grid. The best at each size is the best of the six, not the best there is; a half-life of 80 might beat 50 at ten entries, and nothing here says. The grid is spaced so that neighbouring half-lives differ by a factor of two to five, which is fine enough to locate the peak at each size and too coarse to claim its exact height.

Halving is one way of forgetting. Exponential decay at every lookup, sliding windows and counts capped at a ceiling are others, and each has its own tuning. What the run establishes is that the ratchet is the defect, not that halving is the best repair.

And the board sequence is the experiment. The whole effect depends on the distribution of shapes changing during the run, and the run changes it by switching board size. The catalogue a strong player needs shows that a stronger player’s games concentrate their shapes differently, and a catalogue that builds itself that the table’s use order tracks a census of what is met; neither says what a single board size, played over and over, does to the balance between counting and recency.

The convention the values depend on #

Normal play. The table holds each component’s stops — the two numbers a cooling calculation reads off a value — and those come from canonical forms, which exist because every normal-play position has one. A misère component has no canonical form of that kind and no stops to cache, so there would be nothing in the table to evict; and the player’s decomposition into independently valued regions is itself a normal-play licence, as the board falls apart sets out.

Still open: one board, played over and over #

Every result on this page and the one before it depends on the board changing. Recency beat the fixed tables because a fixed table is wrong for three board sizes out of four; ageing beat recency by forgetting at a rate tuned to how fast those boards replace one another.

Hold the board fixed — play all 650 games on one size — and the reason recency won disappears. A counting rule should then do at least as well as recency and may do better, and the best fixed table, chosen with the whole run in view, should stop being beaten at all. Whether that happens, and whether it happens on every board size or only on some, is the control this experiment most needs.