Three rules and a tie-break

What a strategy has to remember counted the bookkeeping a winning player carries over the catalogue of Domineering regions. Four thousand two hundred and sixty-nine positions carry 128 values between them, so a player who wants to predict needs 128 numbers — and 3,308 of the turns available in those positions are decisions, moments where some placements are best and others are not, so a player who wants to win needs an answer for each.

That page closed on what a table of 3,308 is an upper bound for:

The rung above is the compression. Three thousand three hundred lines is what an exhaustive table costs; what a player costs is smaller, because the decisions are not independent — a great many of them will be instances of two or three patterns … Measuring it means grouping the decisions by something like which placement keeps the region connected, and asking how few rules answer all 3,308.

Three rules answer 94.5 per cent of them, and no number of rules answers all.

What a rule is allowed to be #

The word rule has to be pinned down before any of this counts, because there are two things it could mean and only one of them is a strategy.

A rule here is a filter on placements, not a chooser. It scores every candidate and keeps the ones scoring highest, so a rule that cannot tell two placements apart passes both of them on rather than picking. A list of rules is applied in order — each narrows what the one before it left — and a decision is answered by the list when everything surviving the whole list is a best move.

That is the only definition under which a short list is a compression. A collection of rules of which some one is right, with nothing to say which, is not something a player can carry: it needs an oracle to select the rule, and the oracle is the table the list was supposed to replace. Applied in a fixed order they need no oracle, and the price of that is a rule near the bottom of the list may be handed candidates the rule above it has already spoiled.

Seven rules are on offer. Four are about the board — keep the region whole, break it up, play at a cell with few neighbours, play at a cell with many. Two are about moves — leave the opponent fewest replies, which is the rule the dominance ladder has spent three rungs sharpening, and keep the most further moves for oneself, which is the reading which option the reduction keeps scored and rejected. And one is a control: take whichever placement comes first in scan order, which has no content at all.

One rule does most of it #

Leaving the opponent fewest replies answers 2,528 of the 3,308 decisions, which is 76.4 per cent, and it is far and away the best of the seven. Splitting the region answers 55.1 per cent, playing in the middle 32.4, keeping the most room 29.4, and the two rules that pull the other way — keep the region whole, play at the edge — answer a tenth each.

The control is the number that makes the rest readable. Taking whichever placement comes first answers 1,849 decisions, 55.9 per cent, which is more than five of the six content-bearing rules. That is not a mystery and it is not an argument that scan order is wise: most decisions in this population offer exactly two candidates and exactly one is best, so a rule with no content is right about half the time by construction. Mobility’s 76.4 per cent is to be read against 55.9, not against nought, and the two rules scoring under a fifth are worse than doing nothing thoughtfully.

The right way to read a rule scoring 10 per cent, incidentally, is not that it is a bad rule but that it is nearly the reverse of a good one. Keep the region whole answers a tenth of the decisions; break it up answers more than half. Which is a finding about Domineering and not about heuristics: a player who splits a region hands the opponent two independent small fights instead of one large one, and the sum is the object — two small cold pieces are worth less to move in than one big hot one.

And three rules do nearly all of it #

The greedy list starts with mobility at 76.4 per cent. The rule that adds the most on top of it is keep the region whole, which alone was the second worst of the seven and which takes the list to 91.7 per cent — because it is being asked a different question. Applied alone it is asked to pick from every placement; applied second it is asked only to separate placements that the mobility count has already declared equal, and among those the connected one is usually better.

That is the whole reason a list is worth more than its parts, and it is worth saying plainly: a rule’s value depends on what it is handed. The third rule on the list is the control, which takes the list from 91.7 to 94.5 per cent, and it earns that by breaking ties rather than by knowing anything — a decision where the first two rules leave two candidates and one is best is answered by an arbitrary choice half the time, and the list is scored on whether the placement it names is best.

Then it stops. The fourth rule adds nothing, the fifth adds nothing, and it is not that the greedy search has taken a wrong turn — after the tie-break there is exactly one candidate left, so nothing downstream of it can change any answer. The list is complete at three and it is wrong 181 times.

Why the second rule is worth more than it looks #

The jump from 76.4 to 91.7 per cent is the most interesting number on the page, and it is worth working out rather than reporting.

Applied alone, keep the region whole answers 332 decisions out of 3,308. Applied after the mobility count it answers 506 more than mobility manages by itself. The rule has not changed; the question has. Alone, it is asked to choose among every placement the position offers, and it happily names a placement that keeps the region whole and leaves the opponent five replies over one that keeps it whole and leaves two. Second, it is handed only the placements the count has already declared level, and among a set of equally restrictive moves the connected one is usually the better.

There is a general shape here that the whole ladder keeps meeting. A heuristic’s score is not a property of the heuristic — it is a property of the heuristic and the population it is scored on, and a filter changes the population for everything downstream of it. That is why the seven single scores in the table two figures up cannot be used to predict what a list of them will do, and why the list has to be built by measurement rather than by ranking.

It is also why the residue is what it is. Everything the three rules cannot reach is a decision on which the first two are both silent, and silence compounds: a position where the count cannot separate two placements is a position where the two placements leave the same number of replies, which on a small region usually means they are geometrically similar, which is exactly when the connectivity rule has nothing to say either.

What no rule reaches #

The residue is not scattered. Four of the 181 are on six-square regions and 177 on the seven- and eight-square ones, where roughly one decision in nine survives everything. That is the wrong end of the population to be failing on, because it is the end a real board is made of: when a real board falls apart measures what a played Domineering game actually produces, and the pieces that matter are the ones large enough to still have a fight in them.

The mechanism is uniform. In every one of the 181, the mobility count scores the candidates identically and the connectivity rule scores them identically too, so the list falls through to the arbitrary tie-break and takes the wrong placement. The rules are not being misled — they are being silent, and the silence is broken by a coin.

Whether the residue compresses #

A hundred and eighty-one exceptions is not obviously a table worth writing, so the natural next question is whether they compress in turn.

They do, in one sense and not the useful one. The 181 unanswered decisions carry forty-seven distinct values, so as a set of positions the residue is far from 181 unrelated accidents — twenty of them are on positions worth $\ast$, ten on $\{\ast \mid -1\ast\}$, ten on $-1/2\ast$. There is real structure there, and most of it is infinitesimal: a position worth a nimber or a number-plus-star has no fight left in it, and what remains is the tempo question this anchor is named for.

But a value does not name a move. That is the founding fact of the tempo anchor — what a value leaves out is where it is established, and it is the reason a strategy needs 3,308 lines where a prediction needs 128. So an exception table indexed by value would tell a player which positions are exceptional and not what to do in them, which is a warning light rather than a strategy. The residue compresses as a description and not as an answer.

What a player costs #

So the answer to the rung below’s question is 184 against 3,308: three rules, and a hundred and eighty-one positions in which to ignore them. That is an eighteen-fold compression of the thing a player has to carry, and it puts the two questions this anchor separates into their proper proportion — 128 numbers to predict the outcome, 184 entries to achieve it, 3,308 to achieve it without thinking.

It is worth noticing what the compression is made of. Almost all of it comes from one rule that a player of any board game already knows, and the rule is not exact and never was: the margin a count needs found it settles the direction of a comparison only once the gap in replies reaches three, and here it is being asked to settle every gap including one. It answers three quarters of the decisions anyway, which is the difference between a rule of thumb judged as a theorem and the same rule judged as a heuristic with a residue attached.

Why the order of the rules is doing so much #

Three rules applied in order is not the same object as three rules, and the ordering is carrying more of the 94.5 per cent than the rules are. It is worth separating.

Applied as a set, the three rules would have to be combined — scored, weighted, voted — and every combination is a fourth decision with its own parameters. Applied in order, each rule is a filter: it narrows the candidates and hands the survivors to the next one, and a rule that is silent simply passes everything through.

That structure is what lets a weak rule contribute. Keep the region whole is a poor rule on its own, because most placements do not split anything and it says nothing about them; as a second filter it only ever sees candidates the first rule has tied, which is exactly the population it discriminates on.

It also explains why the fourth and fifth rules add nothing. By the time two filters have run, the surviving candidates agree on both criteria, and a third geometric rule is being asked about positions specifically selected for having no geometric difference left. A filter chain exhausts its subject faster than a scoring rule does, because each stage removes the cases the next stage could have decided.

The practical reading is that the ordering should be treated as part of the rule and reported with it. Three rules in a different order are a different strategy and would score differently — and nothing on this page measures the other five orderings, which is the cheapest remaining experiment on this anchor.

What this does not say #

Seven rules are not the space of rules. The greedy list saturates over the seven offered, and a rule nobody wrote down would change the number. What the saturation shows is that the seven are not independent — after two of them the third distinguishing rule available adds nothing — and not that no eighth exists. A rule built from the values of the options would answer everything, and would be the table again.

Greedy is not optimal. The list is built by adding whichever rule answers the most given the ones already chosen, which is not guaranteed to find the best list of three. It is guaranteed to find a list of three that answers 94.5 per cent, which is what the claim needs.

The population is regions of at most eight squares, and the residue’s concentration at seven and eight squares is a warning that the rate would rise on larger ones. What proportion of a twelve-square region’s decisions the three rules answer is not known here and the trend does not encourage optimism.

And best is stops, not values. A best move is the one maximising what its player keeps — the right stop of what is left for Left, the left stop for Right — which is the rung below’s definition, used here so the two censuses are the same census. It is not the same as the move that wins: on a position that is already lost every move is worst, and this measurement counts the placements a player would choose given the position rather than the ones that change the outcome.

The convention, named #

Normal play throughout: a player who cannot move loses.

A position is a set of free squares, and the population is every position reachable by play inside the catalogue of regions of at most eight squares, counted once however many regions it arises in — including the disconnected leftovers, since a played region becomes several.

A decision is a position and a player for whom at least two placements are available and at least one is not best. Positions with no move, one move, or nothing but best moves are not decisions, because a player cannot go wrong in them.

A rule scores placements and keeps the highest-scoring; a list applies rules in order to what the previous ones left; and a list answers a decision when everything surviving is a best move. A list that leaves two candidates, one best and one not, has not answered it.

Best is measured by stops, as above. Connected counts four-connected pieces, edges and not corners, which is the connectivity Domineering actually decomposes along.

Where the ladder goes next #

The tempo anchor has four rungs to here, and this one has compressed an exhaustive table into three sentences plus a residue.

The rung above takes the residue apart and finds it is not one thing. Seventy-two of them were not silence reports that seventy-two of the 181 unanswered decisions are the rules speaking and being wrong — not falling silent, which is what this page describes them as, but scoring the candidates and preferring the worse one.

That is a materially worse failure and it changes what a solver should do with the rules. A rule that declines can be backed up by a search: run the rules, and where they say nothing, evaluate. A rule that answers confidently and wrongly cannot be backed up at all, because there is no signal to trigger the fallback.

On the 109 that really are silence, a rule chosen per value answers more than half — so the residue is not one hard case but several small ones, each with its own answer. And the star class this page singles out is settled outright by a rule nobody would have proposed: leave the younger position.

Which explains why three rules stall at 94.5 per cent and a fourth and fifth add nothing. The last 5.5 per cent is not a missing idea of the same kind; it is a mixture of two different failures and several unrelated situations, and adding another geometric rule addresses none of them.