One board, and recency still wins

The table that changes its mind found a small table of Domineering component values doing better under recency than under a use count, and better under recency than the best fixed table chosen with the whole run in view. The explanation it gave, and a count that forgets sharpened, was that the run changes board: 200 games on 4 × 5, then 5 × 5, then 6 × 6, then 7 × 7, with the shapes a table should hold replaced at every change. A fixed table has to answer four questions with one answer, and a rule allowed to change its contents does not.

Both essays named the control and did not run it. Play all 650 games on one board size and the change of board disappears. The prediction is clear: the shape distribution stops moving, the ratchet that hurt counting stops mattering, and the fixed table chosen after the fact — which now has one question to answer — should stop being beaten.

It is beaten anyway, on three boards of four.

The board held fixed #

The loop is the one used before, unchanged: a player considers every legal placement, splits each resulting board into connected regions and looks up each region; ties are broken from one seed; the estimate comes from the full catalogue, so the table under study never changes a move. The only change is the sequence of boards — one size, 650 times.

On 4 × 5 the prediction holds. With ten entries a use count answers 87.12 per cent of lookups against recency’s 81.85, and the best fixed ten answers 87.27, better than either. A small board, played over and over, has a stable set of commonest shapes, and a table that holds them does best.

On every larger board it fails. On 5 × 5 recency answers 89.78 per cent, the use count 85.51, the fixed ten 87.82. On 6 × 6 recency answers 94.83 against 93.85 and 93.29. On 7 × 7, 96.83 against 95.08 and 92.84. Recency beats the best fixed table by two points on 5 × 5, one and a half on 6 × 6, four on 7 × 7 — the largest margin on the largest board, with no change of board anywhere in the run.

So the change of board was not the whole of what recency was exploiting. On three of the four boards, something inside the games themselves rewards a table that follows the last few lookups over a table that holds the commonest shapes.

What the mixed run’s explanation predicted #

It is worth restating the evidence the explanation rested on, because it was real evidence and this result does not remove it.

Each board’s own best ten shares only a handful of shapes with the others — three shapes are in all four lists — so a single fixed table serving the four-board run is badly placed on at least three boards at any moment. That handicap is real, and it is part of why the fixed table lost by three points in the mixed run. What the explanation implicitly predicted is that removing the handicap would reverse the result, since each board’s own best ten is, by construction, the best any fixed table can do on that board.

The one-board runs give that fixed table exactly the advantage the explanation said it lacked, and on 5 × 5, 6 × 6 and 7 × 7 it still loses to recency. So the handicap was sufficient to explain part of the gap and not necessary for it. There was a second cause all along, and the mixed run could not show it because the first cause was pointing the same way.

Every size, every rule #

The grid fills in what the ten-entry row suggests. On 4 × 5 the fixed table is best at every table size — 87.27, 93.63 and 98.99 per cent — and recency is worst at every size. On the larger boards the fixed table is never best, and the winner among the online rules depends on the size: a half-life of 50 lookups at ten entries on every larger board, and longer half-lives as the table grows — though on 5 × 5 the short one still wins at twenty.

At forty entries the rules converge on every board, as they did in the four-board run, because a table with room for forty shapes rarely has to evict anything that matters. The disagreement between the rules is a small-table phenomenon wherever it appears, and so is the effect this page is about.

Not the opening against the endgame #

The obvious candidate for drift within a game is the game’s own progress. A Domineering board in its opening breaks into one or two large regions, and in its endgame into many small ones, so the shapes a table should hold early might differ from the ones it should hold late. A rule that follows recent lookups would track that change and a fixed table could not.

The measurement rules it out. Split each game’s lookups into its first, middle and last thirds and take the ten shapes each third consults most. On 6 × 6 the first and middle thirds share all ten; on every board every pair of thirds shares at least seven. Across all three thirds of a board, only twelve to fourteen distinct shapes ever reach a top ten. The mean region looked up does shrink toward the end — from 2.69 squares to 2.52 on 6 × 6 — but the ten commonest shapes are the same ten from the first move to the last.

That is worth recording as a negative result in its own right, because it was the explanation that seemed most likely. A game’s opening and its endgame look very different on the board, and they consult almost exactly the same component shapes, because the shapes that recur are the small ones — a domino, a straight three, a small L — and those appear at every stage.

Inside a single move #

What remains is the smallest time scale there is.

A player choosing a move looks up the regions of every legal placement, one after another, before choosing. Two placements on the same board differ by one domino, so they break the board into nearly the same regions, and the lookups for one move are dominated by the same few shapes over and over.

A move on 7 × 7 makes 29.35 lookups of 4.03 different shapes, so 86 per cent of its lookups repeat a shape it has already asked for. On 6 × 6 it is 18.81 lookups of 3.53 shapes, 81 per cent repeats. On 5 × 5, 7.72 of 3.00, 61 per cent. On 4 × 5, 6.83 of 3.20, 53 per cent.

That is the locality recency is paid for. A table under recency holds the three or four shapes the current move is asking about, because it has just been asked about them, and it answers the next twenty-five lookups of that move from them. A fixed table holds the ten commonest shapes over the whole run, and it answers those lookups only when the move’s few shapes happen to be among the ten. The larger the board, the more lookups a move makes of the same few shapes, and the more a table that follows the move is paid for following it.

On 4 × 5 a move makes seven lookups and only about half repeat. There is little within-move locality to exploit, the whole game uses a small stable set of shapes, and the table that holds that set wins. The crossover between 4 × 5 and 5 × 5 is sharp — counting five points ahead on one board, recency four points ahead on the next — and the repetition share moves only from 53 to 61 per cent between them, so the per-move count explains the direction of the result better than its size. Nothing here identifies the exact threshold.

What this does to the earlier explanations #

Two earlier explanations need adjusting, and it is better to say how than to leave them standing beside a result that contradicts part of them.

The change of board was real, and it was not the only cause. The table that changes its mind showed that each board’s best ten differ, and that is still true; a fixed table over four boards is handicapped by it. But the one-board runs show recency beating fixed tables with no change of board at all, so some of the four-board result was the within-move locality this page measures. The two causes act together in the mixed run, and the mixed run cannot separate them.

The ratchet explanation survives intact. A count that forgets halved use counts at intervals and overtook recency, and the one-board grid agrees: where the fixed table does well, never-forgetting counts do nearly as well; where recency wins, short half-lives win with it. The best half-life at ten entries on the larger boards is 50 lookups — two moves’ worth on 7 × 7, which is exactly the time scale of the locality measured above.

Two time scales, read off the two measurements #

The half-life table and the per-move table can be set side by side, and they say the same thing in different units.

The one-board runs tried half-lives of 50, 200 and 1,000 lookups, and at ten entries the shortest won on every board larger than 4 × 5. The four-board run tried 25 and 100 as well and found everything from 25 to 100 within 0.13 points, so 50 marks a band rather than a sharp optimum. Converted into moves with the per-move counts, that band means very different things on different boards.

A move on 7 × 7 makes about 29 lookups, so a count halved every 50 lookups has lost more than half of a shape’s standing within two moves — in effect a table remembering the last move or two, out of a game of about twenty-one moves. On 6 × 6 the same half-life is under three moves of a sixteen-move game. On 5 × 5, where a move makes under eight lookups, it is six and a half moves of an eleven-move game. And on 4 × 5, where the fixed table wins, the best half-life is 1,000 lookups: about 146 moves, or seventeen games — a count that, on the time scale of one game, never forgets.

So the right memory for a small table is short where moves are long. On the two largest boards it is a couple of moves, which is exactly the scale of the repetition: a move’s twenty-nine lookups of four shapes are served by a table that holds those four shapes for the length of the move and lets them go soon after. The 5 × 5 reading is the untidy one, since half a game is a long memory for a burst of eight lookups, and it is also the board where the half-life’s lead over recency is largest — 0.32 points, against 0.29 on 6 × 6 and 0.15 on 7 × 7, which is the direction a longer useful memory would push. A grid that stopped at 50 cannot say whether a still shorter half-life would do better there.

The measurement also says what a use count that never forgets is doing wrong on these boards, in terms simpler than a ratchet. A count accumulated over hundreds of moves says which shapes are common across the run. The lookup that is about to arrive is not drawn from the run’s distribution; it is drawn from the current move’s, which is four shapes and changes with every move. A count that remembers the run is answering the wrong question well.

A cache that follows the question being asked #

The general shape of the finding is familiar from caches everywhere, and it is worth stating in those terms.

A cache is paid for locality of reference: the next request is likely to resemble recent ones. There are two kinds. Temporal locality is the same item asked for again soon — which is what a move’s repeated lookups are. Distributional skew is some items being asked for far more than others over the long run — which is what a fixed table of the commonest shapes exploits. Recency is built for the first and a fixed table for the second, and a use count sits between them.

Domineering play produces both, in proportions that depend on the board. On small boards the long-run skew dominates, because moves are short and the shape set is small. On large boards the temporal locality dominates, because a move is a burst of dozens of lookups of a handful of shapes. The catalogue a strong player needs measured the skew, and when the catalogue starts paying priced a catalogue against search; neither could see the bursts, because both counted lookups over whole runs.

The same distinction separates the component table from a transposition table. A position reached eleven ways is one position prices the saving from noticing a position already evaluated inside one search, which is temporal locality of the purest kind — the same position reached again within the same move’s search. A catalogue that knows what it will meet orders shapes by how often play meets them, which is the long-run skew. The measurements on this page say a Domineering player’s component lookups have both at once, with the balance set by the board, and that no single rule serves both as well as each could be served separately.

And the saving at stake is the one knowing who wins and knowing what it is worth prices: a miss costs a stops computation on a small component, which is cheap, but the whole point of the table is to avoid the search that computing an entire position’s value would need. The difference between 96.8 and 92.8 per cent on 7 × 7 is four lookups in a hundred, at a cost that is small each time and is paid tens of thousands of times over a run.

A solver designed with this in mind would keep two tables: a tiny one holding whatever the current move has asked for, discarded when the move is chosen, and a larger fixed one holding the commonest shapes across games. Nothing of the kind is run here. The per-move counts say the first table would need about four entries.

What the runs cannot say #

One seed, one player, one sequence per board. The direction of each result is large on the larger boards — recency ahead of the fixed table by one and a half to four points — and small effects between rules at forty entries are within what a different seed could move.

A random tie-break inflates repetition. The player evaluates every placement before choosing, and the estimate for most placements is built from the same few regions. A player that pruned its candidates, or searched deeper on a few, would make fewer lookups a move and repeat fewer shapes, and the balance between recency and a fixed table would shift toward the fixed table. The locality measured here is a property of this player as much as of the game.

And the boards are small. 7 × 7 is the largest played. A board of 10 × 10 would make still more lookups a move and, if the trend holds, reward recency more; that is an extrapolation and is not measured.

The convention the values depend on #

Normal play, as in every essay on caching component values. The table caches the stops of each component, and stops come from canonical forms; the decomposition of a board into independently valued regions is a normal-play licence. The eviction question only arises because those values are worth keeping — under a convention with no decomposition, there would be no components to cache.

Still open: two tables #

The per-move measurement suggests a design this page does not test: a table that lives for one move, holding the handful of shapes that move keeps asking for, beside a table that lives across games, holding the commonest shapes. The first is paid for temporal locality and the second for skew, and each would be sized for its own job — four entries or so for the first, on the evidence above, and as many as memory allows for the second. Whether the pair beats a single table under the best half-life, and by how much on each board, is the experiment this leaves.