The opponent stops choosing

Alternation is the difficulty is a claim with an experiment attached, and the experiment is to remove the alternation and see what happens. One way to remove it is to take the opponent’s choosing away: leave the rules alone, leave the board alone, and replace one of the two players by a rule that names a move without searching.

What is left has one chooser in it. It is a puzzle — is there a sequence of moves that beats this fixed reply? — and a puzzle’s answer is a line of play somebody can check. The question is what that costs in accuracy, and the answer is nothing like the same on different games.

The three rules #

Each replacement takes the options in the order the game’s own move list produced them and picks one. None of them looks at the position beyond that, and none searches.

The first move offered. A rule about the generator rather than the game, which is exactly what makes it a fair stand-in for a player with no idea what they are doing.

The move leaving the opponent fewest replies. The one rule here that is a real heuristic. It is the mobility argument in its crudest form and it is the rule most solvers order their moves by.

A fixed pseudo-random reply. Chosen from the position’s own description, so the same position always draws the same answer. A rule that replied differently on two visits would not be a rule at all, and the question here is what happens when the opponent stops being a chooser rather than what happens when they become unpredictable.

Nim loses almost everything #

The game everybody calls solved is the one that collapses.

Nim on heaps of 3, 4 and 5 has six positions the mover loses and a move available. Against a fixed opponent, five of the six become wins — under every one of the three rules. On three heaps of five it is six of seven.

That is not a small effect at the edges. It is nearly the whole of what the game had. A Nim position is lost when the heap sizes exclusive-or to nothing, and every move from such a position leaves a non-zero exclusive-or — so the opponent, if they are paying attention, simply restores it. Against a rule that is not paying attention the loser moves anywhere, the fixed reply almost never happens to restore the balance, and the position is won from there on.

So Nim’s difficulty is entirely in the opponent. Three exclusive-ors settle any position and the settlement is only worth something against somebody performing the same three exclusive-ors. This is the second time the same board has said something unexpected about that word: four of its five turns are turns at which the choice decides, and now nearly every loss it holds is recoverable the moment the other player stops choosing.

The boards lose almost nothing #

Domineering on three rows by four has 122 positions the mover loses with a move available. Against the first-move rule, six of them become wins. One in twenty.

The rule is not playing well. It throws away a winning move eighty-eight times over the same sweep, which is measured rather than assumed.

Eighty-eight misplays and six recovered positions. The fixed opponent is a bad player and being a bad player barely matters, which is the opposite of what the Nim rows say about the same experiment.

The reason is the shape of a Domineering loss. A player who is losing is losing because the board has run out of room for their dominoes, and that is a fact about the squares rather than about the play — the opponent can hand back a move or two and the count still does not come out. There is no single restoring move for the opponent to fail to find, because there is nothing to restore.

Nim’s losses are the other kind. They are held by an exact arithmetic condition that one careless move destroys, and the opponent’s whole job is to re-establish it every turn. A position whose loss is enforced by an invariant is a position that a careless opponent gives away; a position whose loss is enforced by a shortage is not. That is the distinction the table draws, and it cuts across the usual division into easy games and hard ones.

Three rules, one answer #

The three replacements are very different players and they produce almost the same table, which is worth a moment because it is not what one would expect.

Nim gives away five of six against the first move offered, five of six against the last, five of six against the widest, five of six against a random reply. Domineering gives away six, six, seven and six. The rules disagree about which move to play at nearly every turn and they agree almost exactly about what it costs.

The reason is that the quantity being measured is not the rule’s quality. It is whether the position has a reply that has to be found — and if it has, then any rule not looking for it will miss it with much the same frequency. A Nim loss has exactly one restoring move among a dozen, so a rule picking without looking finds it about one time in twelve whatever its principle. A Domineering loss has no restoring move at all, so a rule picking without looking loses nothing whatever its principle.

That is a useful thing to know about this kind of experiment in general. The spread between the games is enormous and the spread between the rules is almost nothing, so the measurement is reading the board rather than the player — which is what it was supposed to be doing, and is not what a comparison of heuristics would be doing with the same numbers.

The board where no rule can be wrong #

One row is nought against nought, and it is the row that explains what the measurement is really about.

Clobber on two rows of three recovers none of its forty-two losses, under any of the rules, and the rules never misplay on it at all. Not once in the whole sweep does the first-move rule, or the mobility rule, or the random rule throw away a win.

That is not a coincidence and it is not the rule being good. It is the board: not one of its 114 turns is a turn at which the choice changes the answer, so there is no move available anywhere on it that throws a win away. A rule cannot misplay a position in which misplaying is impossible.

So the zero in this table and the zero in that one are the same zero seen from two sides, and either alone would be misleading. A zero in the recovery column with misplays beside it says the game is unforgiving; a zero with no misplays beside it says the game never asked. The control column is what tells them apart, and without it the Clobber row and the Domineering three-by-three row look identical.

The heuristic that never errs #

One entry in the slips table is worth stopping on, because it is a stronger claim than anything else here.

The mobility rule — take the move leaving the opponent fewest replies — never throws away a win on either Domineering board. Seventeen misplays for the first-move rule on three rows by three and none for this one; eighty-eight against none on three rows by four.

A one-line rule with no search in it therefore plays Domineering perfectly on those boards, in the only sense a normal-play game has of perfect: it never converts a win into a loss. That is a much larger claim than the rule usually gets, and it is a claim about two boards rather than about the game — the same rule is the one that orders a solver’s moves, where it is presented as a heuristic that expands 1,125 positions instead of 30,202, and its being right as well as fast is not part of that argument.

It does not extend. On Nim the mobility rule misplays twenty-four times over forty-eight turns and gives away five of six losses, exactly as badly as the others. On Clobber’s three-by-three board it misplays 110 times. So it is a fact about Domineering: on a board where every move is a domino and the count of remaining placements is nearly the whole of the position, minimising the opponent’s placements is minimising the opponent’s game.

The pair of mobility rules is the sharpest comparison available here, because they differ by a sign. Minimising the opponent’s replies never throws a win away on either Domineering board; maximising the rule’s own replies throws one away 136 times on three rows by four, half again as often as picking the first move in the list. The same idea, read in the two directions, is the best of these rules and the worst of them.

That has a plain reading on a game of this shape. A Domineering board is a fixed quantity of room being divided between two players who need it in different orientations, so every square a player’s domino uses is a square the opponent might have used. Denying room is playing the game; taking room is a side effect of denying it, and pursuing the side effect directly is how a rule ends up worse than not thinking at all.

What the collapse is a collapse of #

It is worth being exact about which question has become easy, because two different things could be meant and only one of them is true here.

The question that becomes a puzzle is the whole question. With one player following a fixed rule, deciding whether the other can win is a search over one player’s moves with the replies determined, which is one chooser and one existential. It has a short answer — the line of play — and checking it means replaying it.

What does not happen is that the position changes. The verdict against a fixed opponent is a different verdict, and the table is exactly the measurement of how different. On Nim it is different on five positions in six; on the small Clobber board it is different nowhere. So the collapse is real in every case and it costs nothing in some and nearly everything in others.

The connection back is the one the reduction makes. A quantified formula whose universal quantifiers have been replaced by fixed values is an ordinary satisfiability question, and the difference between the two answers is the difference between the two classes. The measurement here is that difference on boards, and its size is a fact about each game rather than about the classes.

What the experiment is not #

Two nearby experiments would answer different questions, and neither is this one.

Replacing both players by rules is a simulation rather than a question — it produces one line of play and one winner and establishes nothing about the position. The asymmetry is the whole design: one player keeps the search, so the answer is still a claim about what can be done rather than about what happened.

Weakening the searching player is the more familiar experiment and it goes the other way. A search cut off at a fixed depth, guessing where it stops, is a verdict that changes with the depth, and what it measures is how much of the answer is near the leaves. Here the searching player is exact and the opponent is the approximation, which is why the errors can only run one way.

The pairing of the two is what makes the alternation visible. A game is hard because two things are being quantified, and each experiment removes one of them: cutting the search short removes the depth and keeps both choosers, and fixing the opponent removes a chooser and keeps the depth. The second is the one that changes what kind of question it is, and the first is the one that changes only how well it is answered.

The two kinds of loss, named #

The reading that runs through every row is worth stating once on its own, because it is the transferable part and it is not about complexity at all.

A position can be lost for two reasons. It can be lost by an invariant — a quantity the opponent restores every turn, which the mover can never touch. Or it can be lost by a shortage — the mover simply has fewer moves left than the opponent, and nothing either of them does changes that.

An invariant needs a custodian. Somebody has to notice the balance and re-establish it, and a player who is not looking will fail to, so a loss held by an invariant is a loss that evaporates against an opponent who is not looking. A shortage needs nobody: it is already true of the position, and the opponent can play as badly as they like without creating room that is not there. Numbers avoid numbers is the same observation in the value theory — a position whose value is a number is one where neither player wants to move, and the outcome follows from the sign whatever anybody does.

Nim’s losses are invariants, all of them, and the invariant is the exclusive-or. Domineering’s are shortages. That is the whole explanation of an eighty-three per cent against a five per cent, and it predicts the result for any game before the sweep is run: ask what enforces the loss, and whether it needs somebody to keep enforcing it.

Normal play, and three rules with no search in them #

Normal play throughout, and the mover is the player whose question is being asked. A fixed rule with no move available has lost, exactly as a searching player would — the replacement changes how a player chooses and not what ends the game.

Three conventions of the sweep are worth stating.

Only a loss can move, and the share is taken over the losses. Taking the opponent’s choice away cannot cost the mover a game they were winning, so a win against a chooser is a win against anything. Quoting the changes against every position in the sweep would divide by a population most of which had nowhere to go, and would report Nim at ten per cent rather than at eighty-three.

A partizan game is asked twice, once with each player searching, and the two runs are kept apart. They are different questions on a partizan board and folding them together reports changed verdicts on positions that could not change — including wins turning into losses, which cannot happen and is the signature of the two questions having been mixed.

And the fixed rules take the generator’s order as given. The first move offered is a rule about how this site lists moves rather than about the game, which is the point: it is a stand-in for a player with no idea, and a player with no idea plays whatever is in front of them.

What a fixed opponent is not #

It says nothing about how a real weak player plays. The three rules are predictable, and a person is not; a person is inconsistent, which is a different experiment with a different answer. What is measured here is the removal of the quantifier, not the weakening of the player.

It measures verdicts, not margins. Every game here is normal play, so the answer is win or lose and nothing else. On a scoring game the same experiment would have a size as well as a direction, and what taking every box costs is that measurement made on a fixed rule of exactly this kind — where the greedy player searches as deeply as the solver and is obliged to capture, so the gap is the price of one rule.

And four games is four games. The spread between eighty-three per cent and nought is the finding, and the explanation offered for it — invariants against shortages — is a reading of eight positions rather than a theorem. What would test it is a game whose losses are held by an invariant and whose moves are small, which is not among these.

Still open: how many careless moves a loss survives #

Every rule here replaces the opponent for the whole game. A more useful question is graded: how many careless moves can a winning player afford before the position is genuinely gone?

The measurement is available with the same apparatus and has not been made. Let the opponent search except at k turns chosen adversarially, and find the smallest k at which the verdict moves. On Nim that number would be one, or very nearly; the whole of the game’s loss condition is destroyed by a single misplay. On Domineering it would be larger, and on the small Clobber board it would not exist at all.

That number is what a player means by a forgiving game, and nothing here has yet measured it.