dotsandboxes.tex

\documentclass[a4paper,twocolumn]{article}

\usepackage{palatino}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{color}
\usepackage{calc}
\usepackage{wasysym}

\DeclareMathOperator{\mex}{mex}
\newcommand{\loony}{\rightmoon}
\newcommand{\cgtgame}[2]{\{#1 \:|\: #2\}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{freecoins}[thm]{Theorem}
\newtheorem{loonyoptions}[thm]{Theorem}
\newtheorem{loonynonneg}[thm]{Theorem}
\newtheorem{halfheartedbad}[thm]{Theorem}
\newtheorem{opensmallest}[thm]{Theorem}
\newtheorem{gamelength}[thm]{Theorem}
\newtheorem{dnbgamelength}[thm]{Corollary}
\newtheorem{parityruleofthumb}[thm]{Rule}
\newtheorem{dnbparityruleofthumb}[thm]{Rule}

\begin{document}

\title{The Dots-and-Boxes Game}
\author{Andrew Medworth (\texttt{https://github.com/amdw})}
\date{\today}
\maketitle

\begin{abstract}
  An introduction to the game dots-and-boxes, and to the more general
  game strings-and-coins. Aims to explain why these games are
  interesting, and to discuss some principles of strategy. Intended
  for readers with some mathematical background: anyone unfamiliar
  with techniques such as proof by induction will probably find this
  paper difficult, and may prefer to learn the game from another
  source instead.
\end{abstract}

\tableofcontents

\section{Introduction}

\subsection{The rules of dots-and-boxes}

Dots-and-boxes is a game for two players.

\begin{enumerate}
  \item The game is played on a rectangular grid of dots, of a size
    agreed prior to the game.
  \item A move consists of drawing a line of the player's choice
    connecting a pair of horizontally or vertically adjacent dots.
  \item It is possible for a player's move to complete either one or
    two $1 \times 1$ boxes. When this happens, the player scores one
    point for each completed box (normally recorded by writing her
    initial inside each one) and \emph{must} make another move: a
    player's turn comes to an end when she makes a move which does not
    complete any boxes (or which ends the game).
  \item The game ends when all boxes have been completed; the winner
    is the player who has completed more boxes.
\end{enumerate}

An example game on a $2 \times 2$ grid is shown in Figure
\ref{sampledab}; each move played is shown in bold, with the letter
under each position showing the player making that move. (Grid
dimensions are generally quoted in the number of \emph{boxes}.)

\begin{figure*}
  \centering
  \def\svgscale{0.7}
  \input{fig_sampledab.pdf_tex}
  \caption{Sample dots-and-boxes game on a $2 \times 2$ grid, which
    player $A$ wins 3--1}
  \label{sampledab}
\end{figure*}

The rules of dots-and-boxes are very simple: the game can be learned
in moments, and it can be played purely with pencil and paper. The
size of the board can be varied to alter the complexity and length of
the game: games are normally played on grids larger than the one in
the example, at least $5 \times 5$. (An odd number of boxes is often
chosen to prevent ties.)

The strategy of the game is deep and interesting, and the aim of this
paper is to explore it in more detail.

\subsection{Strings-and-coins}

Dots-and-boxes is a special case of a more general game called
\emph{strings-and-coins}.

\begin{enumerate}
  \item This game begins with a set of \emph{coins}, and a set of
    \emph{strings} each connecting a pair of coins; some coins may
    also have one or more strings connecting them to the
    \emph{ground}. The exact starting position is agreed before the
    game.
  \item A move consists of removing a string of the player's choice.
  \item It is possible for a player's move to remove the last string
    connected to either one or two coins. When this happens, the
    player captures those coins, removing them from the game, and
    \emph{must} play another move, her turn ending when she removes a
    string which does not win any coins (or which ends the game).
  \item The game ends when all coins are captured; the winner is the
    player who has taken more coins.
\end{enumerate}

Specifically, the $m \times n$ game of dots-and-boxes is the special
case of strings-and-coins where $mn$ coins are connected in a
rectangular $m \times n$ grid, with the outer coins connected to the
ground (the four corner coins having two ground links each, and the
other edge coins having one ground link each). The equivalences
between the two games are as follows:

\begin{itemize}
\item A box in dots-and-boxes is equivalent to a coin in
  strings-and-coins (and the completion of a box is equivalent to the
  capture of a coin).
\item A place where a line can be drawn in dots-and-boxes is
  equivalent to a string in strings-and-coins (vertical lines are
  equivalent to horizontal strings and vice versa).
\item Lines at the edge of a dots-and-boxes position are equivalent to
  ground strings, and internal lines are equivalent to strings
  connecting two coins.
\end{itemize}

The strings-and-coins game parallel to the dots-and-boxes game in
Figure \ref{sampledab} is shown in Figure \ref{samplesnc}. Connections
to the ground are indicated by arrows. In each position, the moves
played are shown in bold. Underneath is the player making the move
shown, along with the score following that move.

\begin{figure*}
  \centering
  \def\svgscale{0.7}
  \input{fig_samplesnc.pdf_tex}
  \caption{Sample strings-and-coins game equivalent to Figure \ref{sampledab}}
  \label{samplesnc}
\end{figure*}

Strings-and-coins is a more general game than dots-and-boxes, because
in strings-and-coins it is possible to start with a position of any
shape and connectivity whatsoever, whereas in dots-and-boxes, the
``coins'' are fixed in a rectangular grid, and all strings have length
1 and are either vertical or horizontal. For example, in
strings-and-coins it is possible to have a loop of three coins,
whereas this is not possible in dots-and-boxes. This greater
generality means that anything we learn about strings-and-coins will
also apply to dots-and-boxes.

Strings-and-coins is also of interest because it helps to focus the
eye on the important aspects of positions, namely the coins and the
connectivity between them, and to abstract away unimportant details
which do not affect the play, such as the orientation and shape of
chains or loops of coins. In the dots-and-boxes representation, by
contrast, the eye tends to be drawn towards the lines, while the
important things (the boxes and their connectivity) are empty space.

For these reasons, we will mostly focus our attention on
strings-and-coins, occasionally making reference to dots-and-boxes
where something we learn has specific implications there.

\section{Basic definitions}

Where possible, I have tried to be consistent with the standard
terminology of graph theory, and with existing literature such as
\cite{berl}.

We will call the two players $A$ and $B$, with $A$ generally moving
first in a given position.

The \emph{valency} or \emph{degree} of a coin is the number of strings
connected to it (these terms are borrowed from graph theory). In the
starting position of dots-and-boxes, all coins have valency 4; each
move reduces the valency of either one or two coins by 1. A coin of
valency 1 can be immediately captured.

A \emph{joint} is a coin of degree 3 or more.

A \emph{loop} is a connected set of coins which all have valency 2,
and form a circuit. An \emph{$n$-loop} is a loop consisting of $n$
coins. (In dots-and-boxes, there are no loops with fewer than four
coins, and due to the symmetry, all loops have an even number of
coins.)

A \emph{(closed) chain} is a connected set of coins with valency 2
which is not a loop. A chain has two ends, which can either be
connected to the ground or to a joint. An \emph{open chain} is one
which can be immediately captured, i.e.\ a chain where one or both
ends has valency 1; in the special case where both ends have valency
1, we may refer to it as an \emph{opened loop}. A \emph{$n$-chain} is
a chain consisting of $n$ coins.

A chain is \emph{independent} if it is connected to the ground (rather
than a joint) at both ends.

The act of \emph{opening} a chain or loop is cutting it so that it
becomes an open chain, which can then be captured.

A \emph{double-cross move} (or \emph{double-crossed move}) is a move
which wins two coins at once (because the string removed connected two
coins of valency 1). These moves are of strategic importance for
reasons we will see later.

Let $V(P)$ be the net value of a position $P$ from the perspective of
the player to move, assuming optimal play from both sides, and
independent of how $P$ was reached (i.e.\ the value of the remaining
coins, ignoring any coins taken earlier in the game). Clearly $V(P)$
will be an integer, and could be either positive, zero or negative,
according to whether $P$ is favourable or unfavourable for the player
to move. $V(P)$ is also known as the \emph{minimax} value of $P$ and
$V$ is the \emph{value function} of strings-and-coins.

The value function can be computed recursively: any terminal position
has value zero, and the value of a non-terminal position is the
maximum across all legal moves of any coins captured by the move plus
the value of the resulting position (from the perspective of the
correct player).

\section{Endgame fundamentals}\label{endgamesection}

To understand the strategy of a game, it is often a good idea to begin
with positions close to the end of the game, since the understanding
of earlier positions depends on later ones.

\subsection{Control and double-dealing moves}

Let us consider a very simple endgame position $S_n$ consisting of a
single closed $n$-chain. Obviously $V(S_n)=-n$, as there is no
alternative but to open the chain for the opponent, who will take all
$n$ coins straight away.

Now consider the position $D_n$ with $2n$ coins divided into
\emph{two} closed $n$-chains. At first glance it might appear that
this position is a $n$--$n$ draw, as $A$ must open one chain for $B$,
who will take it and then be forced to open the other one for
$A$. However this is not true: when $A$ opens the first chain, $B$ can
take all but the last two boxes, and then sacrifice them with a
\emph{double-dealing move} as shown in Figure \ref{dddemo} (with
$n=5$). Because this move does not win a coin, it ends $B$'s turn, and
forces $A$ to make a move. $A$ might as well take the two sacrificed
coins, because in either case, he is also forced to open the remaining
chain for $B$, which $B$ then wins. Thus $B$ wins by $2n - 2$ points
to $2$, so $V(D_n) = 4-2n$.

\begin{figure}
  \centering
  \def\svgscale{0.7}
  \input{fig_doubledeal.pdf_tex}
  \caption{Maintaining control through double-dealing}
  \label{dddemo}
\end{figure}

Notice that this only works with $n \ge 3$: a closed chain of length 2
can be opened by removing the middle string, in which case a
double-dealing move is impossible. Only when $n \ge 3$ is there no way
to open a closed $n$-chain without allowing a double-dealing move.

A similar situation arises with loops, but with one important
difference: when a loop is opened, in order to play a double-dealing
move a player must sacrifice four boxes, rather than two, as shown in
Figure \ref{loopdoubledeal}. This is because an opened loop has no
link to the ground, so the only way to avoid taking a coin at the end
(and thus be forced to continue making moves) is to take the string
between two connected pairs of coins, sacrificing both pairs. This
means that a double-dealing move is only possible with an $n$-loop if
$n \ge 4$.

\begin{figure}
  \centering
  \def\svgscale{0.7}
  \input{fig_loopdoubledeal.pdf_tex}
  \caption{Double-dealing on a loop}
  \label{loopdoubledeal}
\end{figure}

Double-dealing moves are an absolutely central concept in
strings-and-coins strategy, because they allow a player to maintain
\emph{control} of a position, to decide whether to play first in the
rest of the position or to force the opponent to do so.

Because of this, a \emph{long chain} is defined as a chain of at least
\emph{three} coins, and a \emph{long loop} is defined as a loop of at
least \emph{four} coins. A long chain or loop is one which cannot be
opened without allowing a double-dealing move. By contrast a
\emph{short} chain or loop is one which is not long.

(I do not particularly like this terminology, because the words
``long'' and ``short'' are such common words, and giving them a
specific technical meaning like this can often be confusing. However
they are standard in the dots-and-boxes literature, so throughout this
paper I have tried to consistently use ``long'' and ``short'' in this
technical sense, preferring ``large'' and ``small'' in more informal
contexts.)

If there are more than two $n$-chains, notice that player $B$ can
maintain control all the way to the end of the game, by taking all but
two coins of each chain and then playing a double-dealing move,
forcing $A$ to open the next chain at the cost of two coins, and
repeating this for each chain except the last, which he can capture in
its entirety. This strategy will certainly win the game if $n>3$; if
$n=3$ then the situation is slightly more complex, because sacrificing
two coins from a 3-chain results in a net loss of one coin. A similar
observation holds true for loops which are sufficiently large to allow
a double-dealing move without net loss. We will explore this topic in
more detail in section \ref{smallchains}.

\subsection{Loony moves and positions}

A \emph{loony move} is defined as a move which allows the opponent to
play a double-dealing move. There are four types of loony move:

\begin{enumerate}
  \item Opening a long chain
  \item Opening a long loop
  \item Opening a 2-chain by cutting the link at one of the ends:
    this is called a \emph{half-hearted handout}, in contrast to a
    \emph{hard-hearted handout} which is opening the 2-chain by
    cutting the middle link (and is not a loony move).
  \item Handing one of these situations back to the opponent by
    playing in an unrelated area of the board when the opponent has
    made a loony move of their own.
\end{enumerate}

A \emph{loony endgame} is defined as a strings-and-coins position in
which the only possible moves are loony moves. A \emph{loony position}
is defined as one in which a double-dealing move is
possible.\footnote{In practice, loony positions come about only when a
  loony move has just been made. The only other possibility is if the
  starting position is loony, which makes little sense.}

These concepts are extremely important to the theory of
strings-and-coins. The basic reason for this is that in a loony
position, the player has a free choice between taking all the coins on
offer and then playing first in the rest of the position, or playing a
double-dealing move, forcing the opponent to play first in the rest of
the position at the cost of either two or four coins (depending
whether a chain or a loop is involved). This is a powerful option,
which will generally lead to victory if exercised correctly (we will
discuss the exceptions in section \ref{smallchains}).

We will now examine some properties of loony positions, starting with
our first theorem.

\begin{loonyoptions}\label{loonyoptions}
  Let:
  \begin{itemize}
    \item $L$ be a loony position
    \item $m$ the number of capturable coins in $L$
    \item $P$ the same position with all $m$ capturable coins removed,
      and
    \item $s$ the minimum number of coins which must be sacrificed in
      order to play a double-dealing move in $L$ ($s$ will be $2$ or
      $4$ according to whether $L$ contains an open long chain, or
      only opened long loops).
  \end{itemize}

  Then the optimal strategy from $L$ is either to take all $m$ coins
  on offer and then make the optimal move in $P$, or to take all but
  $s$ coins and play a double-dealing move, and thus
  $$V(L) = \max(m+V(P), m-2s-V(P))$$
\end{loonyoptions}

\begin{proof}
  Taking all $m$ coins and playing optimally in $P$ results in a gain
  of $m+V(P)$ coins, and taking all but $s$ coins and double-dealing
  results in a gain of $m-2s-V(P)$ coins (assuming best play from both
  sides thereafter). So we immediately have $$V(L) \ge \max(m+V(P),
  m-2s-V(P))$$ and it remains only to show equality by demonstrating
  that no other possible strategy can yield a better outcome than both
  of these options.

  Any strategies from $L$ other than these two must fall into one of
  two categories:
  \begin{itemize}
    \item Making a move in the $P$ part of the position while there
      are $n > 0$ capturable coins still available
    \item Making a double-dealing move while there are still $n > s$
      capturable coins available
  \end{itemize}

  In the first case, the gain from this strategy can be no greater
  than $m-n+V(P)$, as the opponent can take all the capturable coins
  the first player eschewed and play from there (and there may even be
  better options available). At best, the first player has achieved
  nothing over the take-all-$m$ strategy other than to give the
  opponent $n$ free coins. $m-n+V(P) < m+V(P)$ and so this strategy
  cannot be optimal.

  In the second case, the gain can be no greater than $m-2n-V(P)$, as
  the opponent can take all $n$ remaining capturable coins and play in
  $P$ (and may again have even better options). At best, the first
  player has achieved nothing over the take-all-but-$s$ strategy other
  than to give the opponent $n - s$ free coins.  $m-2n-V(P) <
  m-2s-V(P)$ so this strategy can be discarded as well.

  Therefore, the optimal strategy from $L$ must be one of the two
  given.
\end{proof}

This argument relies on the fact that $P$ plays out the same way
regardless of which player goes first in it. Whatever strategy one
player uses from $P$ can also be used by the other if the first player
makes a different decision from $L$, thus reversing their roles. This
type of reasoning is known as a \emph{strategy-stealing} argument.

The power of the choice offered by a loony position is now clear. If
$V(P)$ is positive, we can take all the capturable coins and proceed
to reap that gain; on the other hand, if $V(P)$ is negative, we can
make the double-dealing move and force that loss on our opponent.

\begin{loonynonneg}\label{loonynonneg}
  If a player has just made a loony move, her opponent can always
  score at least half of the remaining points: in other words, for any
  loony position $L$, $V(L) \ge 0$.
\end{loonynonneg}

\begin{proof}
  Let $P$, $m$ and $s$ be defined as in Theorem
  \ref{loonyoptions}. From that theorem we already know that $$V(L) =
  \max(m+V(P), m-2s-V(P))$$

  If $V(P) \ge -m$ then $m+V(P) \ge 0$ and $V(L) \ge 0$ straight away,
  so suppose $V(P) < -m$. Then $m-V(P) > 2m$, and thus as $m \ge
  s$, $$m-2s-V(P) > 2m-2s \ge 0$$ so in this case $V(L) \ge 0$ also.
\end{proof}

Notice that this is a non-constructive proof, which does not tell us
which of the two options (taking all the coins or making a
double-dealing move) is the correct one. The position $P$ might be
very complex, and it could be difficult to work out whether it is more
favourable to play first or second in it. The strategy-stealing
argument simply shows that since the first player has a free choice
between these two options, and one of them must avoid a net loss of
coins, a loony position cannot be unfavourable for the first player.

This shows that it is \emph{generally} undesirable to make a loony
move; that is not always the case, though, as sometimes the
alternatives are actually worse. We will see some examples in section
\ref{smallchains}.

However the third and fourth types of loony move can never be the sole
optimal move, and we will prove that now.

\subsection{Canonical play results}

\begin{freecoins}\label{freecoins}
  Any coins which can be captured without affecting the ability to
  play a double-dealing move later in the turn should always be
  captured immediately.
\end{freecoins}

\begin{proof}
  If the position is loony, this result is exactly the same as Theorem
  \ref{loonyoptions}, so it remains only to check the case where the
  position is not loony (i.e.\ there are capturable coins but no
  double-dealing move is possible).

  However this case is very simple, as we will be forced to play in
  the rest of the position regardless of whether we capture the
  available coins or not. If we do not, our opponent can capture the
  coins herself and continue as if we had done so, so we have achieved
  nothing except to hand some free coins to our opponent.
\end{proof}

\begin{halfheartedbad}\label{halfheartedbad}
  A half-hearted handout is never better than a hard-hearted handout.
\end{halfheartedbad}
\begin{proof}
  Let $P$ be the position without the two coins concerned.

  The value of the position after the hard-hearted handout is
  $2+V(P)$, as the two coins should always be captured by Theorem
  \ref{freecoins}.

  A half-hearted handout by $A$ gives $B$ the choice whether to take
  the two coins and play first in $P$, or to play a double-dealing
  move, which sacrifices two coins but forces $A$ to play first in
  $P$. So the value of the position after the half-hearted handout
  is $$\max(2+V(P),-2-V(P)) \ge 2+V(P)$$ by definition of $\max$.
\end{proof}

Results like this, which prove that a certain type of move can never
be worse than another type, are known as \emph{canonical play}
results. These are extremely useful, because they can significantly
simplify the calculations necessary to evaluate a position.

For example, Theorem \ref{halfheartedbad} means we never have to
consider half-hearted handouts, because we know they will never be
better than the equivalent hard-hearted handout. If the choice is
between a hard-hearted and a half-hearted handout, we can say the
former is the \emph{canonical move}.

Theorem \ref{freecoins} is even more powerful: it means that in many
situations where there are capturable coins, we do not need to
consider the possibility of not taking them. When a long chain or loop
is opened, taking all but the last few coins (two for a chain, four
for a loop) is \emph{canonical}, so we need only consider two
possibilities: taking the whole chain and the double-dealing move.

(It is important to realise that canonical play results only prove
that certain types of move cannot be the sole best move in the
position, and hence cannot affect the \emph{optimal} value of the
position. They say nothing about whether the position is winning or
losing. In some losing positions, a non-canonical move can give the
opponent more opportunities to go wrong, and so might be worth a try
in a practical game.)

Here is another useful canonical play result.

\begin{opensmallest}\label{opensmallest}
  For any two independent chains, or any two independent loops, of
  different sizes, it is never better to open the larger one than the
  smaller one.
\end{opensmallest}
\begin{proof}
  The proof uses a useful technique mentioned in \cite{berl} called
  \emph{the man in the middle}. This is a form of proof by
  contradiction.

  Suppose someone claims that, contrary to this theorem, they have
  found a position where opening the larger structure is better than
  opening the smaller one. We challenge this person to two
  simultaneous games, both starting from that position. In Game 1,
  player $A$ is required to start by opening the smaller structure; in
  Game 2, player $A$ must start by opening the larger one. We take the
  role of player $A$ in Game 1, and our imaginary antagonist does the
  same in Game 2: she gets the position she prefers to play as $A$,
  and so do we.

  In order to prove she is right, our opponent will have to get a
  better result as player $A$ in Game 2 than we can achieve as player
  $A$ in Game 1: if she cannot, then her claim fails and the theorem
  is proven.

  The ``man in the middle'' technique shows that our challenger's task
  is indeed impossible, by taking the moves she plays in one game and
  playing equivalent moves against her in the other game, according to
  an equivalence we specify. The proof works by showing that
  regardless of the strategy our opponent chooses, we can
  \emph{always} find such equivalent moves, and that they will
  \emph{always} result in us doing at least as well in Game 1 as she
  does in Game 2. Our antagonist is essentially playing against
  herself, and we are the ``man in the middle'', hence the name.

  In this case, we see how our opponent responds to our opening of the
  smaller structure in Game 1, before choosing how to respond to her
  opening of the larger one in Game 2:

  \begin{itemize}
  \item If she takes the whole structure, we take the whole larger
    structure in Game 2, leaving us ahead.
  \item If she plays a double-dealing move, we play a double-dealing
    move ourselves on the opened structure in Game 2 (which we can
    always do, because the structure opened in Game 2 is larger). This
    again leaves us ahead, because the structures are either both
    chains or both loops, so the number of coins which must be
    sacrificed to double-deal is the same, and our structure is
    larger.
  \item If she opens the larger structure, we open the smaller
    structure in Game 2.
  \item If she plays elsewhere in the position, we copy her move in
    the other game.
  \end{itemize}

  We then await our opponent's response in Game 2, and make the
  equivalent move in Game 1, according to the same scheme: any move
  our opponent makes on the smaller structure in Game 2 we replicate
  on the larger structure in Game 1, and if she moves in the rest of
  the position, we simply copy her. We repeat this strategy until the
  both games are over.

  If $P$ is the position minus the two structures concerned, we will
  always achieve exactly the same score in $P$ in Game 1 as our
  opponent achieves in $P$ in Game 2, so any difference in outcomes
  will boil down to the two structures themselves.

  We may end up winning the larger structure in Game 1 or we may not;
  if we do, then we do better in Game 1 than our opponent in Game 2,
  because we win the larger structure and lose the smaller one in Game
  1, whereas our opponent wins the smaller one and loses the larger
  one in Game 2. (If our win of the larger structure is minus some
  coins sacrificed by a double-dealing move, so will be our opponent's
  win of the smaller structure in the other game.)

  However, even if we lose the larger structure in Game 1, we will win
  the smaller structure in Game 2, meaning both players win both
  structures in their respective games (possibly minus the same number
  of sacrificed coins), leaving the final outcomes the same.

  This shows that regardless of how good a strategy our opponent
  chooses in Game 2, we can always do \emph{at least} as well in Game
  1, possibly better. For any strategy which starts with the opening
  of the larger structure, we can specify a strategy starting with the
  opening of the smaller structure which is at least as
  good. Therefore, it \emph{cannot} be better to open the larger
  structure than the smaller one.

  (This proof depends on the fact that the two structures are
  independent of $P$, so no move played on them can affect our ability
  to copy our opponent in $P$. It also depends on the fact that any
  move played on a smaller structure can be copied on the larger one
  with no net loss of coins.)
\end{proof}

\subsection{Structure sizes and control}
\label{smallchains}

From the preceding discussion, it is clear that the concept of control
is extremely important to understanding a strings-and-coins
position. However, the winner in strings-and-coins is the player who
wins most coins, not the player who makes the last move or controls
the flow of the play. We now explore the relationship between these
two concepts.

First, suppose we have a position composed of an arbitrary
sub-position $S$ and a single chain with more coins than in all of
$S$. In this case, since the big chain contains more than half the
coins, the game will be won by whichever player can win it: neither
player will open the big chain unless they have no choice, so both
players will strive \emph{not} to take the last coin in $S$. In this
case control of $S$ will determine the outcome of the game.

In general, the more a position is dominated by chains and loops with
a large number of coins, the more important it is to have control,
because this will determine who is forced to give them away.

The complication comes from the fact that when a small enough chain
and or loop is opened, keeping control requires a net sacrifice of
coins, so if the position is dominated by such structures, naively
keeping control all the way to the end can result in defeat. It is in
these contexts that giving away control with a loony move can actually
be the optimal approach.

A chain or loop which does not require a net loss of coins to make a
double-dealing move is defined as \emph{very-long}. Because making a
double-dealing move in a chain requires a sacrifice of two coins and
in a loop requires four coins, we now have the following
classification:

\begin{itemize}
  \item Chains of length 1 and 2 and loops of length 1, 2 or 3 are
    short (as they can always be opened with a non-loony move)
  \item Chains of length 3 and loops of length 4, 5, 6 or 7 are long
    but not very-long (as they can only be opened with a loony move,
    but keeping control with a double-dealing move requires a net loss
    of coins)
  \item Larger chains and loops are both long and very-long (these can
    only be opened with a loony move, after which control can be kept
    with no net loss).
\end{itemize}

(Again I register my objection to this terminology, but it is standard
and I will stick to it.)

We will now examine how smaller chains and loops affect
strings-and-coins positions.

\subsubsection{Long but not very-long chains and loops}

Here we examine the effect of small long chains and loops by
considering a family of loony endgame positions $P_{i,k}$ consisting
of $i$ 3-chains and one $k$-chain, with $k \ge 3$. For example,
$P_{4,5}$ is shown in Figure \ref{p45}.

\begin{figure}
  \centering
  \def\svgscale{0.7}
  \input{fig_p45.pdf_tex}
  \caption{Position $P_{4,5}$}
  \label{p45}
\end{figure}

In $P_{i,k}$, $A$ can choose whether to open the $k$-chain or one of
the 3-chains, and in response, $B$ can choose whether to take the
whole chain or take all but two boxes and play a double-dealing move.

By Theorem \ref{opensmallest}, $A$ never does better to open the
$k$-chain than one of the 3-chains, so to compute $V(P_{i,k})$, we
need only consider opening a 3-chain, followed by either taking or
double-dealing in reply by $B$. Since removing one of the 3-chains
from $P_{i,k}$ yields $P_{i-1,k}$, we can calculate $V(P_{i,k})$
recursively as follows.

\begin{eqnarray*}
  V(P_{0,k}) & = & -k \\
  V(P_{i+1,k}) & = & \min(-3-V(P_{i,k}), 1+V(P_{i,k}))
\end{eqnarray*}

Example calculations for $k=3$, $k=4$ and $k=10$ can be seen in tables
\ref{vpik3}, \ref{vpik4} and \ref{vpik10}.

\begin{table*}[p]
  \centering
  \begin{tabular}{c c c c c c}
    $i$ & $V$ if $B$ takes & $V$ if $B$ double-deals & $V(P_{i,3})$ & $B$ taking optimal? & $B$ double-dealing optimal? \\
    \hline
    $0$ & $-3$ & $1$ & $-3$ & Yes & No \\
    $1$ & $0$ & $-2$ & $-2$ & No & Yes \\
    $2$ & $-1$ & $-1$ & $-1$ & Yes & Yes \\
    $3$ & $-2$ & $0$ & $-2$ & Yes & No \\
    $4$ & $-1$ & $-1$ & $-1$ & Yes & Yes \\
    $5$ & $-2$ & $0$ & $-2$ & Yes & No \\
    $6$ & $-1$ & $-1$ & $-1$ & Yes & Yes
  \end{tabular}
  \caption{$k=3$}
  \label{vpik3}
\end{table*}

\begin{table*}[p]
  \centering
  \begin{tabular}{c c c c c c}
    $i$ & $V$ if $B$ takes & $V$ if $B$ double-deals & $V(P_{i,4})$ & $B$ taking optimal? & $B$ double-dealing optimal? \\
    \hline
    $0$ & $-4$ & $0$ & $-4$ & Yes & No \\
    $1$ & $1$ & $-3$ & $-3$ & No & Yes \\
    $2$ & $0$ & $-2$ & $-2$ & No & Yes \\
    $3$ & $-1$ & $-1$ & $-1$ & Yes & Yes \\
    $4$ & $-2$ & $0$ & $-2$ & Yes & No \\
    $5$ & $-1$ & $-1$ & $-1$ & Yes & Yes \\
    $6$ & $-2$ & $0$ & $-2$ & Yes & No \\
    $7$ & $-1$ & $-1$ & $-1$ & Yes & Yes \\
    $8$ & $-2$ & $0$ & $-2$ & Yes & No
  \end{tabular}
  \caption{$k=4$}
  \label{vpik4}
\end{table*}

\begin{table*}[p]
  \centering
  \begin{tabular}{c c c c c c}
    $i$ & $V$ if $B$ takes & $V$ if $B$ double-deals & $V(P_{i,10})$ & $B$ taking optimal? & $B$ double-dealing optimal? \\
    \hline
    $0$ & $-10$ & $-6$ & $-10$ & Yes & No \\
    $1$ & $7$ & $-9$ & $-9$ & No & Yes \\
    $2$ & $6$ & $-8$ & $-8$ & No & Yes \\
    $3$ & $5$ & $-7$ & $-7$ & No & Yes \\
    $4$ & $4$ & $-6$ & $-6$ & No & Yes \\
    $5$ & $3$ & $-5$ & $-5$ & No & Yes \\
    $6$ & $2$ & $-4$ & $-4$ & No & Yes \\
    $7$ & $1$ & $-3$ & $-3$ & No & Yes \\
    $8$ & $0$ & $-2$ & $-2$ & No & Yes \\
    $9$ & $-1$ & $-1$ & $-1$ & Yes & Yes \\
    $10$ & $-2$ & $0$ & $-2$ & Yes & No \\
    $11$ & $-1$ & $-1$ & $-1$ & Yes & Yes \\
    $12$ & $-2$ & $0$ & $-2$ & Yes & No
  \end{tabular}
  \caption{$k=10$}
  \label{vpik10}
\end{table*}

We know from theorem \ref{loonynonneg} that no loony endgame can have
a positive value, but all the $V(P_{i,k})$ are strictly less than
zero. This is because the 3-chains have an odd number of coins, but
the number of coins you have to sacrifice to make a double-dealing
move is even, so the two never cancel out exactly.

(It is possible to construct a loony endgame position with value 0:
for example, the position consisting of two 4-loops shown in Figure
\ref{drawnloony}. In this case, taking the first loop would mean
sacrificing the second, while double-dealing the first loop would
sacrifice four coins to gain the second loop, with a draw in either
case.)

\begin{figure}
  \centering
  \def\svgscale{0.7}
  \input{fig_drawnloony.pdf_tex}
  \caption{A drawn loony endgame position}
  \label{drawnloony}
\end{figure}

Notice that the larger the value of $k$ (i.e.\ the bigger the big
chain), the longer double-dealing remains the optimal strategy for
$B$, the player in control. This is to be expected, as the bigger the
chain is, the more points it is worth sacrificing by double-dealing
from 3-chains to capture it.

However, in all cases, once $i$ is large enough (i.e.\ there are enough
3-chains), double-dealing after the opening of the first 3-chain
ceases to become the sole optimal strategy, and if there are an even
number of 3-chains, it ceases to become the optimal strategy at all.

The position consisting of four 3-chains, $P_{3,3}$, is a simple
counter-example to the notion that loony moves are always inferior to
non-loony moves. When $A$ opens the first 3-chain in this position,
$B$ does best to take it, winning 3 coins, and open the next 3-chain
for $A$, even though the latter is a loony move and a non-loony move
could have been played instead.

The reason is that giving away control by playing a loony move in the
position with three 3-chains, $P_{2,3}$, only loses one point, which
is more than offset by the three coins won in the process of reaching
that position. If instead $B$ had played a double-dealing move, he
would have been one point behind from the first chain, and only won
one point from $P_{2,3}$, so the game would have finished drawn.

$P_{3,3}$ is also a counter-example to the idea that the winner of a
strings-and-coins game is always the player who makes the last
move. If $A$ opens the first chain, $B$ takes it and opens the next
chain as discussed above, and $A$ double-deals (which is equally bad
for him as taking), $B$ will be leading 5--1 after the first two
chains are gone. As $B$ will have to open one of the last two chains
for $A$, $A$ will double-deal and then take the last chain, thus
winning the last two chains 4--2 and making the last move, but this
will result in a final score of 7--5 in $B$'s favour. So $A$ controls
whether he will make the last move of the game, by deciding whether to
take or double-deal on the second chain, but he is not able to win.

The same holds true for $P_{i,3}$ for all odd $i \ge 3$.

A very similar analysis would apply if the 3-chains from this example
were replaced by loops of length 4, 5, 6 or 7. All these structures
require a sacrifice of coins in order to retain control, so a precise
analysis of the rest of the position is required in order to know
whether double-dealing or taking is the right strategy. If the rest of
the position is close in score, it may be better to take all the coins
on offer and play a loony move, even though there was a non-loony move
available.

\subsubsection{Short chains and loops}

Recall that the defining characteristic of a short chain or loop is
that it can be opened with a non-loony move; therefore, sacrificing it
does not necessarily entail giving up control of the position.

From Theorems \ref{halfheartedbad} and \ref{opensmallest}, we know
that if we add a single short chain or loop of size $c$ to a loony
endgame $P$ resulting in a position $P'$, the best move will be to
open that short chain or loop (with a hard-hearted handout, if
applicable), sacrificing all the coins in it, but forcing our opponent
to play first in $P$, and thus $V(P') = -c-V(P)$.

If we continue to add short chains or loops to the position, the sign
of its value will flip back and forth, as the players will alternately
open one of the short structures, until one of them is forced to play
a loony move.

To see how this works with a concrete example, consider a family of
positions $S_{i,k}$ consisting of $i$ 2-chains plus one
$k$-chain. Then:

\begin{equation*}
  V(S_{i,k}) =
  \begin{cases}
    -k & \text{if } i = 0,\\
    -2-V(S_{i-1,k}) & \text{if } i > 0
  \end{cases}
\end{equation*}

For the case $k=3$, this means the value of the position alternates
between $-3$ (for even $i$) and $+1$ (for odd $i$), as either player
$A$ loses two coins on the last 2-chain but wins the final 3-chain, or
makes an even score on the 2-chains but has to give away the 3-chain.

For larger $k$, the oscillations as $i$ is increased are even larger,
as the significance of who wins the $k$-chain becomes greater. For
example $V(S_{i,10})$ is $-10$ for even $i$ and $+8$ for odd $i$.

\subsection{Summary}

The concepts in this section are absolutely central to dots-and-boxes
strategy.

\emph{Double-dealing moves} sacrifice a small number of coins (two on
a chain, four on a loop) to force the opponent to play first in the
rest of the position.

If a double-dealing move is available, it is also possible to capture
all available coins and play first in the rest of the position
yourself. The ability to choose freely between these two options is
very powerful, allowing the player to capture at least half the
remaining coins in the position if exercised correctly.

A \emph{loony position} is one where a double-dealing move is
possible, and a \emph{loony move} is a move resulting in a loony
position. Many of the more advanced aspects of dots-and-boxes strategy
revolve around trying to avoid making a loony move, or forcing the
opponent to do so. The only way a player can win the game after making
a loony move is if he already has a large enough lead to outweigh the
coins his opponent can win from the resulting loony position.

A \emph{long} chain or loop is one which can only be opened by a loony
move. A \emph{very-long} chain or loop is one with enough coins that
when it is opened, a double-dealing move can be played without net
loss.

In a non-loony position, any available coins can always be captured
immediately, without further analysis. In a loony position, any
available coins other than the two or four required to play a
double-dealing move can similarly always be captured.

A \emph{half-hearted handout}, being a type of loony move, is never
better than the corresponding (non-loony) \emph{hard-hearted handout},
and opening a longer independent chain or loop is never better than
opening a shorter one.

Once a loony move has been made, the correct strategy is to maintain
control (by avoiding loony moves of your own) to the end of the game,
provided there is enough potential profit in very-long chains and
loops to outweigh any coins sacrificed, which is normally the case in
practice.

If there are not enough coins in very-long structures to outweigh
sacrifices for control, the analysis is more complex, sometimes
requiring loony moves.

\section{Middlegame fundamentals}

Having established some basic principles of endgame play, we now
consider how to aim towards a winning endgame while still in the
middlegame.

We have seen that provided there are enough long chains and loops in 
a position, the winner will be the player who establishes control by 
forcing his opponent to play a loony move. This suggests the following
general procedure for winning a game of strings-and-coins:

\begin{enumerate}
  \item Ensure there are enough long chains and loops in the position
  \item Force your opponent to make a loony move
  \item Win the endgame using the techniques we have already seen
\end{enumerate}

This is how most games are won in practice. In this section we will focus
on the second element: how do we ensure that our opponent will run out of
non-loony moves before we do?

\subsection{How long is a game?}

When we succeed in playing according to the above procedure, we will 
generally play the last move of the game, having forced our opponent to
open the last chain or loop for us. (The only exception will be if the
position is dominated by not-very-long structures, as we saw in section
\ref{smallchains}.)

It is therefore important to consider whether there are any general
guidelines we can use to determine which player will make the last
move in a game, as that player will generally be able to win.

In this section, we will prove some results about how many turns there
are in a game of strings-and-coins or dots-and-boxes. Obviously, if
the total number of turns in the game is odd, the player who moves
first in the game will play last, whereas if this number is even, her
opponent will.

It turns out that the number of turns is affected by the number of
double-crossed moves made during the course of the game, in a way
which is perhaps slightly surprising. The following theorem shows
exactly how\footnote{I have never seen this theorem stated in quite
  this way in the dots-and-boxes literature, but I would be surprised
  if it is a new result, as it is merely a generalization to
  strings-and-coins of a well-known result for dots-and-boxes.}.

\begin{gamelength}\label{gamelength}
  For any game of strings-and-coins starting from a position with $C$
  coins and $S$ strings, if $D$ double-crossed moves occur during
  the course of the game, then the total number of turns in the game
  is $$1 + S - C + D$$
\end{gamelength}
\begin{proof}
  Consider a game starting from a position with $C$ coins and $S$
  strings. As the game progresses, let $s$, $c$, $d$ and $t$ track,
  respectively, the number of strings removed, coins captured,
  double-crossed moves made and turns completed.

  At the beginning of the game, clearly $$s = c = d = t = 0$$

  Since a move is by definition the removal of one string, each move
  increases $s$ by $1$, and may increase $c$, $d$ and/or $t$,
  depending whether it captures coins or ends a turn.

  Any move which does not end the game must be one of the following
  types:

  \begin{itemize}
    \item A move which captures no coins. This ends a turn, so $t$
      increases by $1$ and $c$ and $d$ are unchanged.
    \item A move which captures one coin. This increases $c$ by $1$,
      but does not end a turn, so $d$ and $t$ are unchanged.
    \item A double-crossed move. This increases $c$ by $2$ and $d$ by
      $1$, but does not end a turn, so $t$ is unchanged.
  \end{itemize}

  Each of these leaves the quantity $s - c + d - t$ unchanged, and
  since this quantity is zero at the start of the game, we have $$t =
  s - c + d$$ at every move of the game, up to the last move.

  The final move of the game must either be a single-coin capture or a
  double-crossed move, capturing the last one or two coins. Such moves
  leave the quantity $s - c + d$ unchanged. The only difference
  between the final move and any other capture is that it completes a
  turn (and thus increases $t$ by $1$).

  Thus, at the end of the game, $$s - c + d - t = -1$$ and at this
  point obviously $s = S$, $c = C$, and also $d = D$, the number of
  double-crossed moves in the whole game. Hence at the end of the
  game, $$t = 1 + S - C + D$$ as required.\footnote{I am grateful to
    Konstantin Likhomanov for pointing out this proof, which is
    significantly simpler and more elegant than my previous attempt.}
\end{proof}

Applying this to dots-and-boxes gives the following elegant
corollary\footnote{This is the result given in most of the
  dots-and-boxes literature, including \cite{berl} and \cite{wways}.}.

\begin{dnbgamelength}\label{dnbgamelength}
  The number of turns in a game of dots-and-boxes in which $D$
  double-crossed moves occur is equal to the number of dots in the
  grid plus $D$.
\end{dnbgamelength}
\begin{proof}
  If a dots-and-boxes game is played on a grid of $m$ rows and $n$
  columns of boxes, the number of coins in the equivalent
  strings-and-coins position is $mn$. There are $m(n+1)$ horizontal
  strings and $n(m+1)$ vertical ones, so the total number of strings
  is $$2mn + m + n$$

  Substituting these into Theorem \ref{gamelength} and simplifying
  shows that the game will have $$(m+1)(n+1) + D$$ turns.  Since the
  board has $(m+1)(n+1)$ dots, we have our result.
\end{proof}

\subsection{Chain parity rules}

These results allow us, in many practical situations, to work out
quite a long way in advance which player is going to make the last
move of the game.

The theorems of section \ref{endgamesection} tell us that strong
players will generally avoid making loony moves when an alternative is
available, and immediately capture any free coins which do not affect
their ability to play a double-dealing move: for example, when a long
chain is opened, they will always take all but the last two coins, or
if a long loop is opened, they will always take all but the last four,
and then decide whether to take the rest or double-deal. (The
exceptions occur when the position is dominated by not-very-long
chains and loops, or when the player believes he is losing and is
trying to confuse the situation.)

In most games, there will be enough very-long chains and loops that
whoever can gain control and make the last move will win. In that
case, there will be one double-crossed move per long chain and two
double-crossed moves per long loop, except for the last turn of the
game, where there will be no double-crossed moves if it is a chain
being taken, and one if it is a loop (since a loop cannot be captured
without at least one double-cross move).

This in turn means that if the number of long chains $L$ is
\emph{odd}, the number of double-crossed moves will be \emph{even},
and vice versa.

(The number of long \emph{loops} is irrelevant, because each loop
which is not the last structure taken will have two double-crossed
moves, which is an even number. If a loop is the last structure taken,
it will have a single double-crossed move, but that will not change
the parity either: if the last structure taken had been a different
structure instead, there would be two parity changes, one on each
structure affected, so no change in the parity overall.)

Theorem \ref{gamelength} then tells us that if we started with $S$
strings and $C$ coins and $S-C+L$ is \emph{odd}, the total number of
turns in the game will be \emph{odd}, whereas if $S-C+L$ is
\emph{even}, the total number of turns will also be \emph{even}. This
gives us the following rule of thumb.

\begin{parityruleofthumb}\label{parityruleofthumb}
  If player $A$ plays the odd-numbered turns in a game starting with
  $S$ strings and $C$ coins, and player $B$ the even-numbered turns,
  both players should try to reach an endgame position with a number
  of long chains $L$ of a certain parity. Player $A$ will try to
  control $L$ so as to make $S-C+L$ \emph{odd}, whereas $B$ will try
  to make $S-C+L$ \emph{even}.
\end{parityruleofthumb}

The equivalent result for dots-and-boxes is as follows.

\begin{dnbparityruleofthumb}\label{dnbparityruleofthumb}
  In a dots-and-boxes game played on a board with $T$ dots, both
  players should try to reach an endgame position with a number of
  long chains $L$ of a certain parity. Player $A$ will try to make
  $T+L$ \emph{even}, whereas player $B$ will try to make it
  \emph{odd}.

  (Most dots-and-boxes games are played on a grid with an odd number
  of boxes, in which case $T$ is even and so player $A$ should try to
  aim for an even number of long chains, while player $B$ should try
  to aim for an odd number.)
\end{dnbparityruleofthumb}

These rules will work provided (a) there are sufficient very-long
chains that making the last move is enough to guarantee winning the
game, and (b) the pattern of double-crossed moves does not deviate
from that described above (which normally only happens in expert play
when one player realises they are losing and tries to sacrifice some
boxes to confuse their opponent).

\subsection{Examples}

We now examine a couple of examples of these rules in operation, taken
from the exercises in \cite{berl}.

In Figure \ref{ex3p1}, we see a $3 \times 3$ dots-and-boxes position
with 10 moves having been made, and no captures, so player $A$ is to
move. The position has been divided into two structures, one to the
top and left (which is clearly going to become a long chain) and one
in the bottom right, which could become either a chain or a loop. By
Rule \ref{dnbparityruleofthumb}, player $A$ is aiming for an
\emph{even} number of long chains, so the correct move is to play the
highlighted move to turn the bottom right structure into a long
chain. Any other move loses, as $B$ will respond by taking any coins
on offer and then playing one of the ground strings in the bottom
right. It is worth playing the position through a few times to confirm
this.

\begin{figure*}
  \centering
  \def\svgscale{0.7}
  \input{fig_ex3p1.pdf_tex}
  \caption{Exercise 3.1 from \cite{berl}: $A$ to move, solution highlighted}
  \label{ex3p1}
\end{figure*}

In Figure \ref{ex3p12}, we see a more complex case: a $5 \times 5$
dots-and-boxes position with 28 moves having been made, and no
captures, so again player $A$ is to move. The only part of the
position which has not been resolved into a chain or a loop is the
four coins in the top right, so we immediately suspect a need to move
in this area --- but should we make it into a chain or a loop?

\begin{figure*}
  \centering
  \def\svgscale{0.7}
  \input{fig_ex3p12.pdf_tex}
  \caption{Exercise 3.12 from \cite{berl}: $A$ to move, solution highlighted}
  \label{ex3p12}
\end{figure*}

To answer that question, we must count the chains in the rest of the
position. This is slightly trickier than the previous case, because
most of the coins are joined together into a single mass, containing
two joints: the second coin of the first row, and the second coin of
the fourth row. However, once we see the joints, it is clear that
there are three long chains: one extending down and to the left from
the first joint, one extending right and down from the second joint,
and one connecting the two joints.

Since $A$ wants an even number of long chains, the correct move is to
turn the top right into a chain as indicated; other moves lose,
because $B$ would take any coins on offer and then take one of the
ground strings in the top right, turning it into a loop.

It should be clear that the chain-parity rules discussed in this
section are enormously helpful in analysing these late-middlegame
positions. Figure \ref{ex3p12}, in particular, would be very
time-consuming to analyse by brute force. Julian West's analysis of
some expert-level dots-and-boxes games in \cite{nochance} makes
repeated reference to these rules, and understanding how to apply them
is a vital step in the development of anyone who wants to improve
their skills at this game.

\subsection{$3 \times 3$ dots-and-boxes}

In \cite{berl}, Berlekamp gives a winning strategy for player $B$ in
$3 \times 3$ dots-and-boxes. By Rule \ref{dnbparityruleofthumb}, $B$
is aiming for an odd number of long chains; the idea is to force a
single long chain passing through the centre square by making the
moves shown in the pattern in Figure \ref{3by3strategy} (or its mirror
image).

\begin{figure*}
  \centering
  \def\svgscale{0.7}
  \input{fig_3by3strategy.pdf_tex}
  \caption{Player $B$'s winning strategy in $3 \times 3$ dots-and-boxes}
  \label{3by3strategy}
\end{figure*}

This cannot be done mindlessly: care needs to be taken to maintain the
chain and not allow the opponent to turn all or part of it into a
loop. But the value of the $3 \times 3$ starting position is $-3$, in
other words with correct play by both sides, $B$ should win $6$--$3$.

A sample game played according to this strategy may be found in Figure
\ref{3by3samplegame}.

\begin{figure*}
  \centering
  \def\svgscale{0.5}
  \input{fig_3by3samplegame.pdf_tex}
  \caption{Sample $3 \times 3$ game played according to Berlekamp's
    strategy}
  \label{3by3samplegame}
\end{figure*}

The end of the game is not shown, but it is clear that $A$ has been
forced to open the long chain of six boxes at the bottom, and that $B$
will thus win 6--3.

Player $B$'s first deviation from the pattern in Figure
\ref{3by3strategy} is on the sixth move, where he plays on the right
of the centre square. This is necessary in order to prevent $A$ from
playing on the far right of the middle row, thereby forcing $B$ to
sacrifice a box to prevent a loop from forming in the bottom
right. (However, even in that case, $B$ would still win $5$--$4$.)

This move secures the long chain through the middle square. $A$ then
tries to secure another long chain across the top, but this is stopped
on the tenth move, where $B$ sacrifices two boxes in the top left. He
sacrifices a third box in the top right on the twelfth move, but this
would have had to happen shortly anyway when the chain was completed
in the bottom right. Ultimately, $B$ wins the full six-box chain at
the bottom, more than making up for his earlier sacrifices.

\section{Nimstring and Combinatorial Game Theory}

\subsection{Introduction}

Chain counting, as described in the previous section, is a powerful
technique for assessing middlegame positions. However, it is not
sufficient on its own when the position consists of multiple areas
where the number of long chains is not yet resolved.

For example, if there are two such areas, it may be undesirable to
make a move which resolves the chain count in either area, as our
opponent might then be able to resolve the count in the other area in
her favour. In other situations with multiple unresolved regions,
there may be a winning move available, but it might be quite difficult
to work out what it is.

For example, consider Figure \ref{nimstringmotivation} (taken from
\cite{berl}, p.\ 50). Here the top of the board is going to become a
single long chain; however, the two areas at the bottom are
unresolved. Fifteen moves have been made, so player $B$ is to move,
and she has a winning move here --- however, with only the techniques
we have learned so far, it is not easy to find.

\begin{figure*}
  \centering
  \def\svgscale{0.7}
  \input{fig_nimstringmotivation.pdf_tex}
  \caption{A $4 \times 5$ dots-and-boxes position with two
    unresolved regions}
  \label{nimstringmotivation}
\end{figure*}

All games of dots-and-boxes end up with the position being split into
multiple separate regions, as in Figure \ref{nimstringmotivation} ---
or at least, the players must consider the possibility of such splits
at many points during the game. What we would ideally like is a way of
analysing the separate parts of split positions independently, and
then combining those analyses together to assess the whole position
and choose the best move.

To find such a method, we will take a step back, and look at
strings-and-coins in the context of a broader mathematical theory of
games of this type. This is called Combinatorial Game Theory,
or CGT, and there is a very large and rich mathematical literature on
it.

The theory was founded in the early twentieth century, with the study
of games such as Nim (which we will meet soon). However, the key
founding text of modern CGT, which took the study of games to a
completely new level, is John Conway's book \cite{onag}, originally
published in the 1970s. \cite{wways} was also an important early
contribution. Today, the best introductory survey I am aware of is
Richard Guy's papers in \cite{nochance}; \cite{lip} is also an
excellent student-friendly textbook.

CGT focuses on games which:

\begin{enumerate}
  \item have two players, often called Left and Right, or $L$ and $R$,
    who move alternately;
  \item have (at most) two possible types of outcome: $L$ wins and $R$
    loses, or $R$ wins and $L$ loses (there are extensions to CGT
    which cover games which can be drawn or tied);
  \item are games of complete information, so both players know
    exactly what the game state is at all times;
  \item have no element of chance, so the possible moves from any
    position are always known deterministically, and there are no dice
    rolls, coin flips, or other random factors influencing the
    outcome; and
  \item are governed by the \emph{normal play convention}, where a
    player loses if, and only if, they have no legal options available
    when required to move.
\end{enumerate}

Many popular games satisfy the first four conditions (particularly if
draws are allowed), such as chess, draughts, go, and
strings-and-coins. Games which satisfy the normal play convention are
somewhat rarer: for example in chess, a player unable to move does not
necessarily lose (as stalemate is a draw).

Strings-and-coins also does not follow this convention, as the winner
is whichever player has captured most coins during the game, which is
not necessarily the player who captured the final coin.

However, CGT can often be helpful even for analysing games which do
not follow the normal play convention: for example, \cite{nochance}
shows some applications to chess and go, and \cite{wways} contains
many interesting examples also. We should not be surprised that CGT
can give useful insights about strings-and-coins, given how often the
game does in fact boil down to which player can control who makes the
last move.

\subsection{Nimstring}

In this section, we will study a new game called
\emph{Nimstring}. Nimstring is identical to strings-and-coins in every
way except one: the winner is not the player who takes more coins but
the player who forces his opponent to take the \emph{last}
coin.

In other words, Nimstring is simply strings-and-coins modified to
follow the normal-play convention (whoever takes the last coin is required
to play another move, but cannot), and thus to satisfy all the requirements
of CGT.

Nimstring and strings-and-coins are closely related. Many of the results
we have already proved about strings-and-coins also apply to Nimstring,
in a simplified form with fewer caveats and complications. For example:

\begin{itemize}
  \item The concept of loony moves in Nimstring is identical to
    strings-and-coins.
  \item The winning procedure in a loony Nimstring endgame is to keep
    control all the way to the end using double-dealing moves. There is
    no need to worry about whether there is a net loss of coins.
  \item Because of this, there is no practical difference between long
    and very-long structures in Nimstring. In fact, all long chains are
    basically the same in Nimstring, and so are all long loops, because the
    number of coins does not matter, only who can gain control.
  \item All loony Nimstring positions are a win for the first player
    (similar to Theorem \ref{loonynonneg}). In Nimstring, since there
    is no score-keeping, there are no special situations where you win
    by playing a loony move which wins more coins than it sacrifices.
    In Nimstring, a loony move is \emph{always} a losing move.
  \item The same canonical play results hold. For example, any coins
    which can be captured without affecting the ability to make a
    double-dealing move can be taken without affecting the evaluation
    of the position (similar to Theorem \ref{freecoins}), and a half-hearted
    handout is never better than a hard-hearted one (similar to Theorem
    \ref{halfheartedbad}).
  \item Theorem \ref{gamelength} regarding the number of turns in a game
    applies to Nimstring as well, so the same chain-parity guidelines hold.
    The difference is that in Nimstring, since coin counts do not matter,
    there are no caveats about ensuring there are enough long chains and loops
    around to compensate for any coins sacrificed to keep control. In
    Nimstring, whoever can resolve the long chain count in their favour
    will win the game if they play correctly.
\end{itemize}

In fact, Nimstring is a subset of strings-and-coins: any Nimstring
position $G$ can be converted to an equivalent strings-and-coins position
simply by adding a single long chain containing more coins than $G$. The
winner of this strings-and-coins game will be whichever player can win
the long chain, which will be precisely the player who can force his
opponent to capture the last coin in $G$ (in other words, win the Nimstring
game $G$).

There are a great many other strings-and-coins positions which can
also be won using Nimstring techniques. We have observed that most
strings-and-coins games boil down to ensuring there are enough long chains
and loops around and forcing your opponent to make a loony move. This
basically means treating the game like a Nimstring game, while ensuring the
resulting control yields enough profit to outweigh any earlier sacrifices.
The ability to force your opponent to take the last coin in Nimstring is
virtually identical to the concept of control in strings-and-coins which we
examined in earlier sections.

Now, we will first introduce the basic concepts and principles of CGT,
with a strong focus on laying the foundations for Nimstring. We will
then discuss that game in the context of what we have learned. Readers
interested in going into general CGT in more depth (an exercise well
worth doing) should consult the bibliography.

\subsection{Fundamentals of Combinatorial Game Theory}

In CGT, the term \emph{game} is defined in a very abstract way: it is
simply two sets of options, one defining the choices available to $L$
if it is $L$'s move, and the other defining the choices available to
$R$ if it is $R$'s move.

Formally, a game $G$ is recursively defined as an ordered pair of sets
of games: $$G = \cgtgame{\{G^{L_1}, G^{L_2}, \ldots\}}{\{G^{R_1},
  G^{R_2}, \ldots\}}$$ where $G^{L_1}$ etc are the games which $L$ can
choose to move to if it is $L$'s move, and $G^{R_1}$ etc are the games
which $R$ can choose to move to if it is $R$'s move. These two sets of
options can be empty, finite or infinite.

To keep the notation compact, the inner braces are often omitted:
$$G = \cgtgame{G^{L_1}, G^{L_2}, \ldots}{G^{R_1}, G^{R_2}, \ldots}$$
and sometimes the options are written as sets, i.e. $$G =
\cgtgame{\mathcal{G}^L}{\mathcal{G}^R}$$ where $\mathcal{G}^L =
\{G^{L_1}, G^{L_2}, \ldots\}$ and similarly for $\mathcal{G}^R$.

The game $\cgtgame{}{}$, where neither player has any legal moves, is
called the \emph{zero game} and is often just written as $0$. So for
example, the game $\cgtgame{0}{}$ is the game where $L$ has one legal
move leading to the zero game and $R$ has no legal moves;
$\cgtgame{}{0}$ is the game where $R$ has one legal move leading to
the zero game and $L$ has no legal moves, etc.

It can be shown that any game must belong to one of four \emph{outcome
  classes}, assuming best play from both players:

\begin{itemize}
  \item A win for $L$, regardless of who moves first (example:
    $\cgtgame{0}{}$)
  \item A win for $R$, regardless of who moves first (example:
    $\cgtgame{}{0}$)
  \item A win for whichever player moves first (example:
    $\cgtgame{0}{0}$)
  \item A win for whichever player moves second (example: $0$)
\end{itemize}

The true power of CGT lies in its ability to combine two games
together to make a new game. The \emph{sum} of two games is defined as
a new game with both games ``played side-by-side'', where each move
consists of choosing one of the games and making a move in
it. Formally, if $G = \cgtgame{\mathcal{G}^L}{\mathcal{G}^R}$ and $H =
\cgtgame{\mathcal{H}^L}{\mathcal{H}^R}$, then the left options of
$G+H$ are $$\{G'+H : G' \in \mathcal{G}^L\} \cup \{G+H' : H' \in
\mathcal{H}^L\}$$ and the right options are $$\{G'+H : G' \in
\mathcal{G}^R\} \cup \{G+H' : H' \in \mathcal{H}^R\}$$ In each case,
the left part of the union is the set of options where the player
plays in $G$ (leaving $H$ untouched), and the right part is the set
where the player plays in $H$ (leaving $G$ untouched).

(It may initially appear strange to define a particular position as
being ``the same game'' regardless of which side is to move. After
all, it makes an enormous difference whose turn it is in a game: for
example, in chess, changing the side to move can often have a bigger
effect than adding or removing pawns or pieces. This concept of sums
of games explains why a game is defined this way: when two games are
added together, the moves of the two players in a given sub-game may
not actually alternate any more, as one side may play consecutive
moves in one sub-game while the other side plays consecutive moves in
the other.)

Further, the \emph{negative} of a game is defined as the game where
the options of $L$ and $R$ are (recursively) reversed, so if again $G
= \cgtgame{\mathcal{G}^L}{\mathcal{G}^R}$ then $$-G = \cgtgame{\{-G' :
  G' \in \mathcal{G}^R\}}{\{-G' : G' \in \mathcal{G}^L\}}$$

Once we can add two games and negate an individual game, we can very
easily subtract games as well: $$G - H = G + (-H)$$

The next step is to define a notion of \emph{equality} for games. The
zero game is a loss for whichever player is to move, which is to say a
win for the second player; all games $G$ where the second player can
force a win are defined to be equal to the zero game (and we write $G
= 0$). Then, we say two games $G$ and $H$ are equal, or have the same
\emph{value}, and write simply $G = H$, if $G - H = 0$ in this sense.

To take a simple example, $\cgtgame{0}{} = -\cgtgame{}{0}$, since
$\cgtgame{0}{} + \cgtgame{}{0}$ is a win for the second player and
hence is equal to $0$.

It can be shown that if $G = H$, then $G$ and $H$ are always in the
same outcome class (e.g.\ if $G$ is always a win for $L$ then so is
$H$), and moreover, for all games $X$, $G+X$ and $H+X$ are also always
in the same outcome class (indeed $G+X = H+X$), so the two games have
exactly the same effect on the outcome class when added to any third
game. (Some sources \emph{define} equality in this way: it does not
matter as it is equivalent to the definition given above.)

It is important to distinguish between the CGT definition of
\emph{value} given above, and the notion of minimax coin-score value
of a strings-and-coins position (the value function $V(P)$ of a
position $P$) used in previous sections. CGT games do not have scores,
only a win-or-loss outcome, so any CGT game position has only two
possible minimax values, ``win'' or ``loss''. The set of CGT values is
much richer, and is designed to classify not only what the best-play
outcome is of one particular game, but also what effect it has when
added to other games.

It should also be noted that CGT sources have a strong tendency to
blur the distinction between games and game values. Games are called
``equal'' if they have the same value, even if they have completely
different sets of options: in the example we saw above, $\cgtgame{0}{}
+ \cgtgame{}{0}$ does not have literally the same set of options as
the zero game, but it is still equal to $0$, because it is a win for
the second player.

In effect, CGT values partition literal games into equivalence classes
(sets of equal game value), and for most purposes within CGT, games
are treated as interchangeable with others of the same value. The
justification for this is that while the specific options available
from two equal games may differ, and thus the optimal strategy will
not be the same, the final outcome of the two is the same with best
play, and the effect of each when added to any third game is also
identical.

We can already see that game values, in a certain sense, behave like
numbers:

\begin{itemize}
  \item They can be identified as equal or unequal to each other.
  \item They can be added and subtracted.
  \item There is a zero game value such that $G + 0 = 0 + G = G$ for
    all $G$.
  \item Addition obeys the same commutative and associative laws as
    numerical addition ($G+H = H+G$ and $G+(H+I)=(G+H)+I$ for all
    games).
  \item Every game value $G$ has an inverse $-G$ such that $G + (-G) =
    0$.
\end{itemize}

In the terminology of abstract algebra, game values form a structure
called a \emph{commutative group}. This group is extremely rich and
interesting: there are games which behave like the integers
($\cgtgame{0}{}$ is like $1$ and $\cgtgame{}{0}$ is like $-1$), and
there are even games which behave like arbitrary fractions! There are
also games which do not behave like numbers at all.

\subsection{Impartial games}

Thankfully, we can leave a full discussion of the group of games to
textbooks such as \cite{lip}, because we are only interested in
Nimstring, which belongs to a very special class of games, called the
\emph{impartial} games.

An impartial game $G$ is one where the same set of options is
available to both players, i.e.\ $G =
\cgtgame{\mathcal{G}^E}{\mathcal{G}^E}$ for some set $\mathcal{G}^E$
which itself contains only impartial games. (A game which is not
impartial is called a \emph{partizan} game. In a partizan game, the
options available to the two players are different; for example, chess
is a partizan game, because one player controls the White pieces, and
the other the Black.) Nimstring is an impartial game, because either
player can remove any string when it is his turn to move. (As a
reminder, dots-and-boxes and strings-and-coins are \emph{not}
impartial games, because they do not satisfy the normal play
convention.)

Any impartial game must either be a win for the first player or the
second player: unlike a partizan game, the outcome classes ``always a
win for $L$'' and ``always a win for $R$'' are impossible, because the
options for the two players are always the same, so one player can
always ``steal'' the other's winning strategy if the players' roles
are reversed (remember the proof technique from Theorem
\ref{loonyoptions}).

The game of \emph{Nim} is central to the theory of impartial games,
for a reason we will see shortly. In Nim, a position consists of a
finite number of \emph{heaps} of ``beans'' or counters; the two
players take it in turns to select one of the heaps and remove any
number of beans from it (at least one, up to and including the whole
heap). The winner (under the normal play convention) is the player who
takes the last bean.

Clearly, any one-heap game of Nim is a win for the first player,
because she can just take all the beans immediately. Similarly, a game
of two equal heaps is a win for the second player, because whatever
move the first player makes, her opponent can simply copy it in the
other heap.

Nim is ideally suited for analysis using the concepts of CGT we saw in
the previous sub-section. A game of Nim with $n$ heaps behaves exactly
like the sum of $n$ separate one-heap games. From a single heap with
$n$ beans, both players have the same set of $n$ choices: they can
take any number of beans from $1$ up to $n$. We therefore use the
shorthand $*n$ for a single Nim-heap of size $n$; formally, $*n$ is
defined inductively as follows:

\begin{eqnarray*}
  *0 & = & 0 \\
  *(n+1) & = & \cgtgame{*0, *1, \ldots, *n}{*0, *1, \ldots, *n}
\end{eqnarray*}

In CGT, these game values are referred to as \emph{nimbers}. All
non-zero nimbers are first-player wins, because the first player can
always move to the zero game. Also, all nimbers are self-inverse: $*n
+ *n = 0$ for all $n$, because a game of two equal heaps is a
second-player win as we saw above.

Nim was solved by the American mathematician Charles L.\ Bouton in
1901. Though the terminology of ``nimbers'' and other CGT concepts was
not invented until later, Bouton effectively showed that:

\begin{enumerate}
  \item The sum of any two nimbers is another nimber, so any Nim
    position behaves exactly like a single Nim-heap.
  \item For any nimbers $*m$ and $*n$, the way to find $*m + *n$ is to
    represent $m$ and $n$ as binary numbers and exclusive-or
    ($\oplus$) them together (or equivalently, add the two binary
    numbers together without performing any carrying).
  \item Any Nim position equal to $0$ is a win for the second player;
    all other Nim positions are a win for the first player.
  \item The winning strategy in any Nim position which is not equal to
    $0$ is to find and play a move to a $0$ position, which is always
    possible.
\end{enumerate}

(From our earlier discussion of CGT and the definition of nimbers, we
can see that the last two points are implied by the first two.)

Here are some examples of nimber addition:

\begin{itemize}
  \item $*1 + *2 = *3$, since $1 = 01_2$, $2 = 10_2$ and $01_2 \oplus
    10_2 = 11_2 = 3$
  \item $*1 + *3 = *2$ since $3 = 11_2$ and $01_2 \oplus 11_2 = 10_2 =
    2$
  \item $*2 + *7 = *5$ since $2 = 010_2$, $7 = 111_2$ and $010_2
    \oplus 111_2 = 101_2 = 5$.
\end{itemize}

As an example of the winning strategy for Nim, suppose we start with
three heaps, of 13, 23 and 28 beans. Now:

\begin{eqnarray*}
  13 & = & 01101_2 \\
  23 & = & 10111_2 \\
  28 & = & 11100_2 \\
  13 \oplus 23 \oplus 28 & = & 00110_2 = 6
\end{eqnarray*}

So the whole position is equal to $*6$ (in other words it has the same
CGT value as a single Nim-heap of six beans), and one winning move
would be to take $6 = 00110_2$ coins from the 23-heap, since $*13 +
*17 + *28 = 0$.

(Note that there are moves available to higher nimbers from this
position: for example we could take 16 coins from the 28-heap leaving
a position of value $*22$. The canonical definition of nimbers says
that $*6$ should have no options to move to higher nimbers, but in
fact, because no move to $*6$ itself is available, the higher-nimber
options have no effect on the game value: they are said to be
``dominated''. This is another example of a situation where games of
equal value do not necessarily have identical sets of options.)

Now why, in a paper about dots-and-boxes, did we spend time studying
Nim, which appears on the surface to be a completely different game?
The answer is that in the 1930s, the German mathematician Roland
P.\ Sprague and the English mathematician Patrick M.\ Grundy
independently discovered that, crucially, \emph{any} impartial game
played according to the normal play convention\footnote{Surprisingly,
  if we reverse the normal play convention so that the last move
  loses, which is called \emph{mis\`ere play}, the situation is much
  more complicated.} is equal to a nimber. This means that any
normal-play impartial game whatsoever is equivalent to a single Nim
heap.

Specifically, the Sprague-Grundy Theorem states that if $$G =
\cgtgame{*a, *b, *c, \ldots}{*a, *b, *c, \ldots}$$ then $G = *n$
where $$n = \mex(a, b, c, \ldots)$$ where the function $\mex$ (short
for \emph{minimal excludant}) is defined as the smallest non-negative
integer which is not a member of $\{a, b, c, \ldots\}$.

For example:

\begin{eqnarray*}
  \mex() & = & 0 \\
  \mex(0, 1, 2) & = & 3 \\
  \mex(1, 2) & = & 0 \\
  \mex(0, 2, 3) & = & 1
\end{eqnarray*}

This is a remarkable result, because it shows that, in a certain very
important sense (namely the CGT values which we have been discussing),
all impartial games are actually the same --- although there is no
guarantee that it will be easy, in any given case, to calculate the
value of a position or find a winning move (i.e.\ one which reaches a
zero position).

The Sprague-Grundy Theorem shows why the name Nimstring was chosen for
our normal-play variant of strings-and-coins: like all impartial
games, Nimstring has a profound connection with Nim. All Nimstring
positions are equal to some nimber: $0$ for positions winning for the
second player (such as loony endgames), and ``positive'' nimbers for
those winning for the first player.

\subsection{Complimenting moves and loony values}

As with any impartial game, to calculate the value of any Nimstring
position, all we need to do is to recursively calculate the value of
each option of that position, and then calculate the $\mex$ of the
results. For example, if the moves from a given Nimstring position are
to positions of value $*1$, $*2$, $*2$ and $0$, then the position has
value $*3$, since $\mex(1, 2, 2, 0) = 3$.

The problem is that the computational cost of this calculation can be very
high. If done na\"ively, it grows exponentially in the size of the
position, because we must do one recursive computation for each option.
We must therefore look for any possible opportunity to simplify the
calculation. It would help greatly if, as discussed in the introduction
to this section, we could separately calculate the values of the independent
components of a Nimstring position and cheaply combine them together
to reach the value of the position as a whole.\footnote{There are
standard computer science techniques we could apply here: for example,
dynamic programming would avoid repeatedly calculating the values of
identical sub-positions. However, we will focus on CGT-specific ideas here.}

It might initially appear that Sprague-Grundy theory gives us exactly
what we are looking for. All we now need to do, one might think, is
calculate the nimber value of each separate component, and then use
nimber addition, just as we did for Nim.

Unfortunately, however, there is a serious problem. If $G$ and $H$ are
Nimstring positions (with at least one coin), there is a very
important difference between (a) playing a single Nimstring position
with $G$ and $H$ as independent components, and (b) playing the game
$G+H$. In Nimstring, if a player captures a coin in $G$, she can
continue with a move in $H$, which would mean that moves in both $G$
and $H$ have been made \emph{as part of the same turn}. In the game
$G+H$, this would not be allowed: each move in a sum game must be
confined to one of the components of the sum. This means that the
value of a combined Nimstring position is \emph{not}, in general,
equal to the nim-sum of its independent components.

For example, suppose $G$ is a loony position; then the combined
Nimstring position is also a loony position, and therefore a
first-player win (not equal to $0$) \emph{regardless} of the value of
$H$. There is no nimber $*g$ such that $*g + *h \neq 0$ for all $*h$
(since all nimbers are self-inverse, i.e.\ $*g + *g = 0$), so nimber
addition simply does not seem to behave the way we need it to. It
appears we are stuck with the exponential calculation for the full
position, and that breaking the position down into components does not
help.

In CGT, moves which allow the same player to play again are called
\emph{complimenting moves}. In Nimstring, capturing a coin is a
complimenting move.

Fortunately, it is possible to extend Sprague-Grundy theory to support
impartial games with complimenting moves, such as Nimstring. The
method comes from Chapter 12 in Volume 2 of \cite{wways}, but the
analysis there also supports other game features which Nimstring does
not have, so we do not need to introduce the full theory here.

For Nimstring, all we need is to introduce a new special game value,
$\loony$, pronounced ``loony'', for loony positions, with the
following properties:

\begin{eqnarray*}
  \loony + *n & = & \loony \quad (\forall n)\\
  \loony + \loony & = & \loony \\
  \mex(a, b, \ldots, \loony) & = & \mex(a, b, \ldots)
\end{eqnarray*}

(The first two definitions are easily justified by our earlier
observation that a loony position is still a loony position regardless
of what other positions are added. The third comes from the fact that
in Nimstring, any loony move is a losing move, so when evaluating a
position, loony moves can be ignored: if only loony moves are
available, the first player is losing, so the value of the position is
$0 = \mex()$.\footnote{Note that $\loony$ behaves a bit like an
  ``infinite nimber'', as adding any regular nimber to it results in
  itself, and it has no effect on the $\mex$ function.})

We can then calculate the value of any Nimstring position as follows:

\begin{enumerate}
  \item The value of the empty position is $0$.
  \item The value of a position where a double-dealing move is
    possible is $\loony$.
  \item The value of a position where there are capturable coins but
    no available double-dealing moves is the same as the value of the
    position with those coins removed.
  \item The value of any other position is equal to the $\mex$ of
    its options.
\end{enumerate}

The first two of these are clear.

The third can be seen by imagining such a position $G$ added to
another position $H$ identical to $G$ except with the capturable coins
removed. This is a zero game, because the first player must end with
some move available in both $G$ and $H$ (either with or without
capturing some of the coins in $G$ beforehand). If this is a loony
move, the first player has conceded defeat immediately; if not, the
second player can respond by capturing any of the originally
capturable coins in $G$ which still remain, followed by mirroring his
opponent's final move in the other component, resulting in two
identical non-loony components, which have total value $0$ since all
nimbers are self-inverse.

The fourth follows from the Sprague-Grundy Theorem for ``ordinary''
impartial games, plus our earlier observation that loony moves can be
ignored when evaluating a position.

We can easily see that addition in our extended value system still
obeys the commutative and associative laws, and thus we have an
essentially ``well-behaved'' theory.\footnote{Since $\loony$ has no
  inverse, technically our extended set of values is no longer a group
  but a commutative monoid, but that has no real significance for our
  discussion here.}

We now have the tools we need for understanding a Nimstring position
as (quite literally) the sum of its parts.

Figure \ref{nimstringexamples} shows some examples of Nimstring
positions with their values. In particular, note that any independent
long chain or long loop has a value of $0$, because all options from
it are loony, so when calculating the value of a position, such
structures can be ignored.

\begin{figure*}
  \centering
  \def\svgscale{0.7}
  \input{fig_nimstringexamples.pdf_tex}
  \caption{Examples of simple Nimstring values}
  \label{nimstringexamples}
\end{figure*}

Let us now apply these techniques to the position which originally
motivated our excursion into CGT, namely Figure
\ref{nimstringmotivation}.

Nimber value calculations are not easy to perform mentally, or even
using pencil-and-paper, so I have developed a computer program to
assist, which may be found in the repository which accompanies this
paper\footnote{\texttt{https://www.github.com/amdw/dotsandboxes}}. Using
this program, we can analyse each of the three areas of the position.

The top area has value $*1$, as all but seven moves there are loony,
and these seven each lead to zero positions. The square in the bottom
right has value $*2$.

The most complex area is the $3 \times 2$ area in the bottom
left. This has value $*4$, so the position as a whole has value $*1 +
*2 + *4 = *7$. To win, we need to get to a position of value zero,
which means we need to make a move in the bottom left to change its
value to $*3$. There are three moves which achieve this, which are
shown in Figure \ref{nimstringmotivationsolution}, and any of these
will win.

\begin{figure}
  \centering
  \def\svgscale{0.7}
  \input{fig_nimstringmotivation_solution.pdf_tex}
  \caption{Solutions to Figure \ref{nimstringmotivation}}
  \label{nimstringmotivationsolution}
\end{figure}

\appendix

\section{A note on sources}

This paper was the product of some difficulties I experienced with
existing sources on dots-and-boxes.

\cite{berl} is the only major work I know of focusing solely on the
game. It contains many important results and useful exercises, and
this paper would have been impossible without it, but it does not give
proofs for many key assertions, or go into as much depth as I would
have liked. This paper started as an attempt to prove some of the
results in that book, and to understand its contents more deeply
through my own analysis.

\cite{wways} contains a chapter on dots-and-boxes which has a
considerable overlap with \cite{berl} (even containing some identical
illustrations and formulations). While it does contain some valuable
non-overlapping material, I find the work as a whole, while it
contains much material of great interest, has many of the same
structural and stylistic problems as that book.

\cite{nochance} contains many excellent essays on Combinatorial Game
Theory, but has only a very cursory treatment of dots-and-boxes (a
single paper analysing a couple of games played by experts).

\cite{lip} is an excellent textbook on Combinatorial Game Theory which
I became aware of only recently. It has some material on
dots-and-boxes, but its focus is on the mathematics rather than one
specific game. (It also has the virtue, alone among these sources at
the time of writing, of being available on Amazon Kindle!)

\begin{thebibliography}{99}
  \bibitem{berl} Elwyn R.\ Berlekamp, \emph{The Dots-and-Boxes Game},
    A~K~Peters 2000
  \bibitem{wways} Elwyn R.\ Berkelamp, John H.\ Conway, Richard
    K.\ Guy, \emph{Winning Ways for Your Mathematical Plays},
    A~K~Peters 2003 (dots-and-boxes is discussed in Volume 3, Chapter
    16)
  \bibitem{nochance} Richard J.\ Nowakowski ed., \emph{Games of No
    Chance}, Cambridge University Press 1998
  \bibitem{onag} John H.\ Conway, \emph{On Numbers and Games},
    A~K~Peters 2000
  \bibitem{lip} Michael H.\ Albert, Richard J.\ Nowakowski, David
    Wolfe, \emph{Lessons in Play: An Introduction to Combinatorial
      Game Theory}, A~K~Peters 2007
\end{thebibliography}

\section*{Copyright notice}

This paper is Copyright 2016--2019 Andrew Medworth, and is licensed
under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0
International
License\footnote{\texttt{http://creativecommons.org/licenses/by-nc-sa/4.0/}}.

\input{vc.tex} The original source of this paper is a Git
repository\footnote{\texttt{https://github.com/amdw/dotsandboxes}},
and this version was generated from commit \VCRevisionMod.

\end{document}