Chapter 50: Combinatorial Game Theory and Discrete Dynamics

Why does bitwise XOR determine the winner of Nim?

Three heaps contain $3,4,5$ counters. Two players alternate; a move removes a positive number of counters from exactly one heap. Whoever has no legal move loses. Should you empty the largest heap, reduce the smallest, or preserve some hidden balance? The answer depends on the binary digits of all three heaps together.

The exclusive OR, written $a\oplus b$, adds corresponding binary digits modulo two, without carrying. Thus $1\oplus1=0$, $1\oplus0=1$, and $a\oplus a=0$. The Nim-sum of a position is the XOR of its heap sizes. For our example,

$$3\oplus4\oplus5=(011)_2\oplus(100)_2\oplus(101)_2=(010)_2=2.$$

Reduce the first heap to $3\oplus2=1$. The new position $(1,4,5)$ has Nim-sum zero. The complete theorem, established in Bouton's original Nim paper, is that zero-sum positions are losing for the player about to move, and every nonzero-sum position has a move to a zero-sum position.

Proof of the mechanism. If a zero-sum position changes one heap from $a$ to a smaller $b$, the new sum is $0\oplus a\oplus b=a\oplus b\ne0$. Conversely, let the current sum be $s\ne0$, and look at its highest nonzero binary digit. Some heap $a$ has a one in that digit. Set $b=a\oplus s$. Higher digits are unchanged, that digit changes from one to zero, and lower digits cannot outweigh it. Therefore $b\lt a$, so the move is legal; its new sum is $s\oplus a\oplus b=0$.

The empty position has sum zero. Induction on the total number of counters now proves the winner classification: from a zero-sum position every move gives the opponent a nonzero-sum position; from a nonzero-sum position a zero-sum reply is available. Every move reduces the total, so play terminates. This proof, the rules, and the binary example are the chapter foundation.

Here XOR is an outcome classifier, not a conserved quantity: it changes after every legal move. Later, chip-firing will supply a quantity that truly stays constant modulo three. Recognizing this difference is useful when designing proofs for games, rewriting systems, and resource-transfer processes. Relevant foundations are combinatorial thinking, recursive reasoning, graph theory, and Ramsey theory.

50.1 Impartial games and normal-play convention

Optional extension; not required to complete the chapter foundation.

A finite impartial game can be represented by a directed acyclic graph. Vertices are positions; an arrow $P\to Q$ means that $Q$ is a legal successor of $P$. Both players have the same available moves from a given position. Information is perfect, there are no random events, and players alternate. Under normal play, a player with no move loses. Acyclicity prevents infinite play and allows induction backward from terminal positions.

A position is a P-position if the previous player wins under optimal play: the player about to move loses. An N-position is one where the next player can force a win. A terminal vertex is P. A nonterminal vertex is N if it has at least one P-successor; otherwise it is P, because every successor is N. “Winning” always means a forced win against every legal opponent response, not just success along one selected trace.

Solved example. In a one-heap subtraction game, remove one or two counters. For heap sizes zero through five, the labels are P, N, N, P, N, N. Size three can move only to sizes one and two, both N. Size four can move to three, which is P. Induction proves that the P-positions are exactly the multiples of three: each other residue can be reduced to a multiple, while neither legal subtraction preserves residue zero.

The underlying game state may need to contain more than a board picture. Repetition restrictions, resources, or the identity of the player can change future moves. A finite position set with directed cycles is not automatically a terminating game; draws or infinite plays require extra conventions. The finite model here avoids that issue.

Exercise. In the subtraction game, classify size eight and give a winning first move. Hint: inspect its residue modulo three. Solution: eight is N; remove two to leave six, a P-position. The opponent must leave residue one or two, which you can return to residue zero.

The classical value theory for this model is developed in Grundy's Mathematics and Games. Its finite-state version is proved through the recurrences in the next section; no infinite-game or misère extension is being assumed.

50.2 Nim and the Sprague–Grundy theorem

Optional extension; not required to complete the chapter foundation.

A win/loss bit is not enough to combine independent games. Two individually winning components can form a losing sum. The extra information is a Grundy value. For a finite set $A$ of nonnegative integers, $\operatorname{mex}(A)$ is the minimum nonnegative integer absent from $A$. In particular, $\operatorname{mex}(\varnothing)=0$. Define recursively

$$g(P)=\operatorname{mex}\{g(Q):P\to Q\}.$$

A terminal position has value zero. A position has value zero precisely when none of its successors does, so the earlier P/N recurrence gives P exactly when $g(P)=0$. A Nim heap of size $n$ has successors of sizes $0,\ldots,n-1$; induction gives value $n$.

The disjunctive sum $P+Q$ allows a move in exactly one component, leaving the other unchanged. Its components must be independent: a move in one cannot unlock or prohibit moves in the other. The established Sprague–Grundy theorem says

$$g(P+Q)=g(P)\oplus g(Q).$$

Here is a complete finite proof mechanism. Write $a=g(P)$, $b=g(Q)$, $s=a\oplus b$, and induct on the sum of component heights. No successor has value $s$, because changing one component cannot retain its mex value. Now take any integer $t\lt s$, and find the highest bit where $t$ differs from $s$. At that bit $s$ has one, so exactly one of $a,b$ has one. If it is $a$, let $a'=t\oplus b$. Higher bits of $a'$ agree with $a$, and this bit changes one to zero, so $a'\lt a$. The mex definition ensures a successor of $P$ with value $a'$. Its sum with $Q$ has value $t$ by induction. The other case uses a successor of $Q$. Thus all values below $s$, and no value equal to $s$, occur among successors. Their mex is $s$.

This is the classical theory associated with Sprague and Grundy. Scope: the proof covers finite acyclic impartial normal-play games and their independent disjunctive sums. It does not identify arbitrary partisan, stochastic, or last-move-loses games with Nim.

Exercise. Classify subtraction heaps $(4,4)$ together. Hint: equal values XOR to zero. Solution: each component has value one, but their sum has value zero and is P. After an opponent's move in one heap, mirroring it in the other is a legal winning response.

50.3 Partisan games and Conway's theory

Optional extension; not required to complete the chapter foundation.

In a partisan game, Left and Right have different move sets. A finite, terminating normal-play game is written $G=\{G^L\mid G^R\}$, with its Left options before the separator and its Right options after it. The empty game is $0=\{\mid\}$. Define $1=\{0\mid\}$, $-1=\{\mid0\}$, and $\ast=\{0\mid0\}$.

Four outcome classes replace a single next-player bit: L means Left wins regardless of who starts; R means Right always wins; N means the starter wins; P means the second player wins. A recursive evaluator must record both whether Left wins when Left starts and whether Left wins when Right starts. This distinction preserves the players' identities across the game tree.

Solved example. In $1$, Left can move to zero and Right has no move, so Left wins with either starting player. In $-1$, Right wins with either starting player. In $\ast$, whoever starts moves to zero and wins: it is N. Zero is P. Thus $\ast$ is not an ordinary positive or negative number. These examples already explain why an unconditional “advantage to Left” differs from “advantage to whoever starts.”

Read the SVG downward. Each arrow is a legal move, labeled by its player. The two arrows from star are distinct choices by different players to the same terminal game. There are exactly four arrows: one from $1$, one from $-1$, and two from $\ast$.

Conway's theory also defines addition by moving in one summand, and negation by swapping player roles and negating options. Equality of game values is stronger than matching outcome classes: two values are equal when they can replace each other in every disjunctive-sum context without changing outcomes. For example, $1+(-1)$ is a second-player win; a reply in the opposite component cancels the starter's move. Similarly $\ast+\ast$ is a second-player win, with the remaining star as the reply. The identities $1+(-1)=0$ and $\ast+\ast=0$ concern game equivalence, not equality of their game-tree shapes.

A number-form such as $\{0\mid1\}$ has value $1/2$ in Conway's construction. Its number interpretation is justified by the simplicity rule, not by averaging the option values; arbitrary forms cannot be evaluated by such an average. A form with overlapping Left and Right options need not be a number. Primary treatment: Conway's On Numbers and Games. Omitted prerequisites: the recursive order relation, simplicity theorem, domination, and reversible-option reductions. Only the finite outcome calculations above are established here directly.

Exercise. What is the outcome class of $1+\ast$? Hint: consider both possible starting players. Solution: L. If Left starts, moving in star leaves $1$ for Right, who cannot move. If Right starts, the only move is in star, leaving $1$ for Left, who wins. This does not imply that every L-position equals the number one.

50.4 Winning and losing positions

Optional extension; not required to complete the chapter foundation.

For a finite acyclic impartial position graph, solve all positions in reverse topological order. Mark sinks P; mark a vertex N if one successor is P, recording such a successor as a strategy witness. Otherwise mark it P. Each edge is inspected once, so with explicit adjacency lists the running time is $O(\lvert V\rvert+\lvert E\rvert)$ and the stored labels require $O(\lvert V\rvert)$ space. Storing the graph itself costs more. A game described compactly may have exponentially many positions; a linear-time graph algorithm does not make every succinctly represented game easy.

Solved example. In the remove-one-or-two game, sizes zero through eight have labels P, N, N, P, N, N, P, N, N. For every N-size, record a legal move to the preceding multiple of three. For every positive P-size, its two outgoing edges lead to N. This provides two complementary certificates: an explicit good move at winning vertices, and verification of all possible moves at losing vertices.

A Grundy calculation refines the same traversal. At a vertex with $d$ successors, its mex is at most $d$. Mark successor values at most $d$ in a temporary array and scan for the first unmarked entry; larger values cannot affect the mex. Summing $O(d+1)$ work over vertices gives $O(\lvert V\rvert+\lvert E\rvert)$ work in the usual word-RAM model. This uses an explicit acyclic graph and integer indices; it is not a complexity claim for an implicit state space.

Changing the payoff convention changes the recurrence's boundary. In misère subtraction by one or two, where taking the last counter loses, size one is losing, size two is winning, and size three is winning. For positive sizes the losing residue is one modulo three. One must handle the terminal convention consistently: the empty state is a win for the player who would move next because the previous player just took the last counter. It is not the normal-play P-base case.

Exercise. Does “always remove the maximum allowed number” win from size four in normal play? Hint: compare its two successors. Solution: no. Removing two leaves size two, an N-position for the opponent. Removing one leaves size three, which is P. Greedy progress toward termination and optimal play are different objectives.

The framework is the finite game theory already developed by Grundy; the traversal and complexity argument here follow directly from the stated graph representation. Scope: cycles need a separate treatment of reachability, infinite play, and draws; the backward recursion is not applied to them.

50.5 Strategy stealing arguments

Optional extension; not required to complete the chapter foundation.

A strategy-stealing proof assumes that the second player can force a win and transforms that hypothetical strategy into a first-player win, giving a contradiction. It often establishes existence without telling us which first move is best. Its crucial step must explain why an extra move does not invalidate the stolen strategy; that condition is not true in every game.

Consider finite rectangular Chomp. Cells have coordinates $(i,j)$ with $0\le i\lt r$, $0\le j\lt c$. The cell $(0,0)$ is poisoned. Choosing a remaining nonpoisoned cell $(i,j)$ removes it and all remaining cells $(u,v)$ with $u\ge i$, $v\ge j$. We exclude choosing the poisoned cell; when it is the only cell left, the player to move loses. This is outcome-equivalent to requiring that player to eat the poison and lose. Every move removes cells, so the game terminates.

Proof for a full rectangle with at least two cells. Let $z=(r-1,c-1)$, the maximal corner. Assume the second player has a winning strategy from the full rectangle. First remove $z$, which removes only that cell. The assumed strategy has a legal nonpoisoned reply $b$; otherwise the second player would already lose. After that reply, the first player is in a losing position. But every nonpoisoned move $b$ from the original rectangle also removes $z$, since $z$ is coordinatewise above $b$. Thus making $b$ directly as the first move leaves exactly the same position as the two-move sequence $z,b$, with the opponent now to move. That is a winning first move, contradicting the assumed second-player strategy.

The proof uses a precise identity between residual boards, not a vague assertion that having more cells helps. This is the classical argument associated with Gale's A Curious Nim-Type Game. Scope: it proves a first-player win for the stated full rectangles; it does not solve every nonrectangular residual board or give a general efficient strategy algorithm.

Solved example. On a $2\times2$ board, remove $(1,1)$ first. The opponent can choose only $(1,0)$ or $(0,1)$. If they choose $(1,0)$, reply with $(0,1)$; if they choose $(0,1)$, reply with $(1,0)$. Either way only the poison remains for the opponent. Here an explicit strategy accompanies the existence proof.

Exercise. Why exclude the one-cell rectangle from the theorem? Hint: inspect the candidate opening. Solution: its maximal cell is the poison, so there is no legal opening and the first player loses. The proof's initial move would violate the rules.

50.6 Positional games and Maker–Breaker games

Optional extension; not required to complete the chapter foundation.

A positional game is specified by a finite board $X$ and a family $\mathcal F$ of winning subsets, forming a hypergraph. In the unbiased Maker–Breaker version, Maker starts and players alternate claiming one unclaimed element. Maker wins upon owning every element of some $F\in\mathcal F$. Breaker wins if this never happens before the board is exhausted. Breaker does not need to create a winning set of their own. That distinguishes this game from a strong achievement game, where both players seek the same kind of structure.

Solved example: a pairing certificate. Let $X=\{a,b,c,d\}$ and $\mathcal F=\{\{a,b\},\{c,d\}\}$. Breaker pairs $a$ with $b$ and $c$ with $d$. Whenever Maker first touches a pair, Breaker claims its other member. That member is available: Maker cannot have touched the pair earlier without Breaker already claiming the mate. Consequently Maker never owns both members of either winning pair. The argument covers every order of Maker's choices.

More generally, choose disjoint pairs so that every winning set contains a complete pair. Replying with mates blocks all winning sets. Merely requiring a winning set to intersect a pair is insufficient: Maker could own the intersecting element without owning its mate, and still complete the set.

The established Erdős–Selfridge criterion says that Breaker wins this Maker-first unbiased game when

$$\sum_{F\in\mathcal F}2^{-\lvert F\rvert}\lt\frac12.$$

For a single three-element winning set the sum is $1/8$, so the criterion applies. For our two winning pairs it is exactly $1/2$, so the strict inequality proves nothing, although the pairing strategy still wins. A sufficient condition need not be necessary. Primary source: Erdős and Selfridge, On a Combinatorial Game90005-8). Proof sketch: assign weights to winning sets not yet touched by Breaker; Maker increases weights of threatened sets, while Breaker selects an element to eliminate enough threat weight. The potential argument and its constant tracking are omitted; the pairing example is proved in full here. Biased games, where players claim different numbers of elements per turn, require different hypotheses and thresholds.

Exercise. If $X=\{a,b,c\}$ and every two-element subset is winning, who wins? Hint: count Maker's claims. Solution: Maker. After their first claim and Breaker's reply, Maker claims the remaining element and owns a winning pair. No pairing certificate can block all three pairs on a three-element board.

50.7 Ramsey games and online combinatorial games

Optional extension; not required to complete the chapter foundation.

Ramsey theory says that sufficiently large colored structures must contain specified monochromatic patterns. A game adds control, timing, and information constraints. In a Builder–Painter online Ramsey game, Builder selects an unexposed edge; Painter immediately colors it red or blue. Builder wants to force a specified monochromatic graph using as few exposed edges as possible. Painter seeks to delay it. The available vertices, target graph, permitted edges, and any degree restrictions must be specified before a numerical bound has meaning.

Solved example. Use an unlimited supply of vertices and target a monochromatic two-edge path $P_3$, whose two edges share a vertex. Builder exposes three distinct edges incident with the same center. Among three colors chosen from red and blue, two agree, giving the path. Thus three moves suffice. Two moves cannot guarantee success: if Builder's edges meet, Painter gives them opposite colors; if they are disjoint, they do not form a path regardless of colors. The exact value for this specified game is three.

For a monochromatic triangle, a simple nonadaptive upper bound exposes all fifteen edges of $K_6$. Fix a vertex; at least three of its five incident edges have the same color, say red, with neighbors $a,b,c$. If any edge among $a,b,c$ is red, it completes a red triangle with the fixed vertex. If none is red, those three edges form a blue triangle. This proves an upper bound of fifteen exposed edges for Builder; it does not prove that an adaptive Builder needs fifteen.

The matching static lower example on five vertices colors a five-cycle red and its complementary five-cycle blue. Neither color contains a triangle, establishing $R(3,3)=6$ together with the preceding proof. Static vertex thresholds and online edge budgets measure different quantities. An online strategy can adapt its next edge to colors already seen, so importing a static equality as an online equality would be unjustified.

Primary online treatment: Conlon, Fox, Grinshpun, and He, Online Ramsey Numbers and the Subgraph Query Problem. Scope: the small path value and triangle upper bound are proved here. No general sharp online bound or current open-status claim is asserted. Larger cases below are finite exploratory tasks, not advertised unsolved problems.

Exercise. What if Builder is restricted to a matching? Hint: consider degrees in every exposed graph. Solution: a two-edge path can never occur, because all degrees are at most one. A color-counting argument alone cannot replace the structural condition that the chosen edges share a center.

50.8 Chip-firing and sandpile models

Optional extension; not required to complete the chapter foundation.

Chip-firing is a discrete dynamical system: it need not have alternating opponents or a win/loss payoff. On an undirected graph, a vertex with at least its degree in chips may fire, sending one chip along each incident edge and removing that many from itself. A sink absorbs received chips and never fires. When all nonsink vertices have fewer chips than their degrees, the configuration is stable. A sink changes the termination analysis, so closed and dissipative systems must not be silently interchanged.

Use a triangle with vertices $a,b,s$, where $s$ is the sink. Write nonsink chip counts as $c=(c_a,c_b)$. Both nonsink degrees are two. The legal updates are

$$a:(c_a,c_b)\mapsto(c_a-2,c_b+1),\qquad b:(c_a,c_b)\mapsto(c_a+1,c_b-2),$$

provided the firing coordinate is at least two. Each move sends one chip to the sink. Therefore $c_a+c_b$ decreases by one per firing and is a nonnegative integer. Every legal sequence terminates after at most its initial nonsink total, regardless of the choices.

Solved example. Starting from $(3,2)$, fire in the order $a,b,a,b$:

$$(3,2)\to(1,3)\to(2,1)\to(0,2)\to(1,0).$$

Alternatively, $b,a,a,b$ gives

$$(3,2)\to(4,0)\to(2,1)\to(0,2)\to(1,0).$$

Every step is legal and both finish stable. The reduced Laplacian is

$$\Delta=\begin{pmatrix}2&-1\\ -1&2\end{pmatrix}.$$

If $u=(u_a,u_b)$ counts firings, then the final nonsink vector is $c-\Delta u$. Here $u=(2,2)$ and $\Delta u=(2,2)$, giving $(1,0)$. Linear updates commute algebraically, but this alone does not prove that arbitrary firing orders stay legal.

Order-independence proof for this model. Suppose one complete legal stabilization has firing counts $u$. Any other legal firing sequence cannot be the first to exceed $u$ at a coordinate $i$. Just before that hypothetical firing, coordinate $i$ has fired exactly $u_i$ times and the other coordinate at most its count in $u$. It therefore contains at most as many chips as in the stable endpoint $c-\Delta u$, which is below two. The proposed firing is illegal, a contradiction. Two complete legal stabilizations consequently have counts $v\le u$ and $u\le v$, hence equal counts and endpoints. Termination was already proved, so a complete stabilization exists from every nonnegative initial vector. This is a finite least-action argument.

A true modular invariant is

$$I(c)=c_a-c_b\pmod3.$$

Firing $a$ changes the difference by $-3$; firing $b$ changes it by $3$. Thus the initial and terminal invariants both equal one in our trace. This invariant does not by itself identify a unique stable configuration: $(0,0)$ and $(1,1)$ are both stable with invariant zero. Uniqueness for a fixed initial state comes from the legal-move argument, not from this residue alone.

Primary foundations are Björner, Lovász, and Shor's chip-firing paper and Dhar's sandpile paper, with its erratum. Omitted prerequisites: recurrent configurations, sandpile groups, spanning-tree enumeration, and scaling limits. The example establishes finite stabilization and an invariant; it does not establish a physical critical exponent or universal behavior.

Exercise. Stabilize $(2,0)$ and test the invariant. Hint: only $a$ can initially fire. Solution: one firing gives $(0,1)$, which is stable. The differences are two and minus one, equal modulo three.

50.9 Graph pebbling

Optional extension; not required to complete the chapter foundation.

A pebbling configuration puts a nonnegative integer $p(v)$ on each vertex. A pebbling move removes two pebbles from one vertex and places one at a neighbor; the other pebble is lost. For a specified root $r$, the goal is to place at least one pebble there. This is a cooperative reachability problem, not an alternating impartial game unless additional competitive rules are imposed.

Let $d(v,r)$ be graph distance to the root. Define a distance-weighted potential

$$W_r(p)=\sum_v p(v)2^{-d(v,r)}.$$

For a move from $u$ to adjacent $v$, its change is $-2\cdot2^{-d(u,r)}+2^{-d(v,r)}$. Adjacent distances differ by at most one, so $d(v,r)\ge d(u,r)-1$ and this change is at most zero. A move one step closer to the root preserves weight; other moves decrease it. Any configuration containing a root pebble has weight at least one, so an initial weight below one certifies impossibility. Weight at least one is only a necessary condition in general.

Solved example. On the path $v_0-v_1-v_2-v_3$, root $v_0$, put seven pebbles at $v_3$. The weight is $7/8$, so the root is unreachable. Eight pebbles suffice: four moves from $v_3$ put four at $v_2$; two moves put two at $v_1$; one final move puts one at $v_0$. This uses seven moves. Every move loses one pebble, consistent with eight initial pebbles becoming one.

The rooted pebbling number is the least $N$ such that every distribution of $N$ pebbles can reach the specified root. For this four-vertex path rooted at its endpoint it is eight. The seven-at-the-far-end obstruction gives the lower bound. To prove the upper bound, recursively gather toward the root. If initially $p(v_0)=0$, the number of pebbles that can be accumulated at $v_1$ by this greedy inward procedure is

$$p(v_1)+\left\lfloor\frac{p(v_2)+\lfloor p(v_3)/2\rfloor}{2}\right\rfloor.$$

Root failure means this quantity is at most one. Writing $p(v_1)=a$ and $q=p(v_2)+\lfloor p(v_3)/2\rfloor$, failure implies $a\le1$ and $q\le3-2a$. Since $p(v_2)+p(v_3)\le2q+1$, total initial pebbles are at most $a+2(3-2a)+1=7-3a\le7$. Thus every configuration of eight succeeds. This upper proof is stronger than checking only the concentrated configuration.

As a caution, put one pebble at each of $v_1,v_2,v_3$ of a three-leaf star rooted at its center. The weight is $3/2$, but no vertex has two pebbles, so no move is possible and the root remains empty. The potential is an obstruction certificate, not a complete reachability solver on arbitrary graphs. Primary treatment: Hurlbert's A Survey of Graph Pebbling, which also presents original probabilistic results. Scope: only the fixed path theorem and potential calculation above are proved here; no general pebbling conjecture is assumed.

Exercise. How many pebbles concentrated at distance two along a path suffice? Hint: each inward step halves the transferable quantity. Solution: four suffice, and three have weight $3/4$, proving they do not. The conclusion concerns this concentrated configuration, not every graph with a vertex at distance two.

50.10 Random and algorithmic combinatorial games

Optional extension; not required to complete the chapter foundation.

Randomness can enter through the starting position, player selection, or move choice. These produce different mathematical questions. A deterministic forced-win classification describes optimal adversarial play. A rollout estimate describes the specified randomized policy. Neither can substitute for the other without a proof linking their models.

Solved algorithmic example. For the remove-one-or-two game, compute $g(0)=0$ and then the mex of available previous values. This needs $O(N)$ operations and $O(N)$ stored values through heap size $N$, or constant working memory if only the most recent values are needed. The closed form $g(n)=n\bmod3$ follows by induction: the two preceding residues are exactly the other residues, whose mex is the current one. For independent heaps, XOR these values and select a legal move yielding total zero. Checking all legal moves is a valid finite strategy construction; the structure explains why it succeeds.

Now specify a different experiment. Starting with one heap of size $n$, both players choose uniformly among currently legal removals. Let $q_n$ be the probability that the player to move eventually wins under this policy. The terminal base is $q_0=0$. Size one has its single winning move, so $q_1=1$. For $n\ge2$,

$$q_n=1-\frac{q_{n-1}+q_{n-2}}2.$$

The subtraction inside the recurrence accounts for the change of player after each move. It gives $q_2=1/2$, $q_3=1/4$, and $q_4=5/8$. Optimal play wins from size four with certainty, yet random play wins with probability only $5/8$. The policies answer different questions.

For $M$ independent full rollouts under the specified policy, let $\widehat q$ be the fraction won by the starting player. Hoeffding's inequality gives

$$\Pr(\lvert\widehat q-q_4\rvert\ge\varepsilon)\le2e^{-2M\varepsilon^2}.$$

For error $\varepsilon=0.05$ and failure probability at most $0.05$, $M=738$ suffices since $2e^{-2\cdot738\cdot0.05^2}\lt0.05$. This is a sampling guarantee for that fixed policy and independent trials, not a proof of an optimal winning strategy. Exact rational recursion already gives the benchmark $5/8$, so this small experiment can detect implementation errors.

A different established model is random-turn play, where a coin determines which player chooses each next move. Peres, Schramm, Sheffield, and Wilson analyze Random-Turn Hex and a class of selection games. Their structural results are about specified selection-game payoffs and turn randomization. Omitted prerequisites: the general selection-game theorem and its relation to pivotal events. Random move selection in our subtraction example is not that theorem's hypothesis.

Exercise. Compute $q_5$. Hint: use $q_3=1/4$ and $q_4=5/8$. Solution: $q_5=1-(1/4+5/8)/2=9/16$. Size five is N under optimal normal play, but this particular random policy does not guarantee a win. Changing the opponent's policy changes the benchmark.

Compute game values and test an invariant in a discrete dynamical system

The investigation connects game graphs, recursively computed values, legal-move certificates, and order-independent dynamics. It also separates three claims that can look similar in a numerical trace: Nim-sum classifies outcomes, chip difference is conserved modulo three, and pebbling weight cannot increase. Each requires a different proof.

One cross-disciplinary application is verifying a distributed relaxation procedure. Several eligible sites may update in different orders; a simulator must check eligibility, a termination argument must prevent infinite updating, and an order-independence argument must justify the final result. The sinked triangle gives a small exact model of that reasoning. It does not assert that an arbitrary distributed system or physical sandpile inherits the same properties. In algorithmic game solvers, comparable discipline separates a correct state recurrence from a rollout policy that merely appears effective.