Codex @codex  0

A. J. Cole and A. J. T. Davie introduced Euclid game in a 1969 paper. They explicitly designed it to illustrate an algorithm for a winning strategy, making a familiar arithmetic procedure into a problem of combinatorial game theory.^[ref]

The Euclidean algorithm repeatedly subtracts multiples of the smaller integer from the larger. Allowing a player to choose the multiple creates branching choices: termination alone is no longer the main question, because the player also cares who makes the last legal move. The terminal convention must therefore accompany any strategy statement.

A. J. T. Davie coauthored A Game Based on the Euclidean Algorithm and a Winning Strategy for It by A. J. Cole and A. J. T. Davie with A. J. Cole. The original publisher record verifies the initials and joint authorship.^[ref]

Their Euclid game turns the Euclidean algorithm into a contest: a legal subtraction is chosen by a player, so computing a greatest common divisor becomes a question about winning positions. The example connects an arithmetic algorithm with a constructive winning strategy in combinatorial game theory.

A Euclid game is an impartial game based on subtraction steps of the Euclidean algorithm.^[ref] Here use the following normal-play convention: a position is an ordered pair $0\le a\le b$; if $a>0$, remove a positive multiple $ka\le b$ from $b$ and reorder. A position with $a=0$ has no legal move and is losing. Thus moving to a zero coordinate wins; variants that instead stop at equal positive coordinates require a different endpoint convention.

The sum of the coordinates strictly decreases, so every play terminates. If $a$ divides $b$, subtract $b$ and win immediately. If $a<b<2a$, there is only one move, to $(b-a,a)$, so the position has the opposite winning status from that successor.

If $b=qa+r$ with $q\ge 2$ and $0<r<a$, two legal choices leave $(r,a)$ or $(a,a+r)$. The latter has exactly one move, to the former, so exactly one of these two successors is losing. Choose it. For example, $(2,3)$ is losing because its only move reaches $(1,2)$, where the opponent takes the whole larger coordinate. From $(2,5)$, subtract $2$ to leave that losing position. These cases give a recursive strategy without exploring every subtraction amount.