
%cg.tex: ``Combinatorial Games''
%
%a Plain TeX file by Doron Zeilberger (3 pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
%end macros
 
\bf
\centerline
{
Combinatorial Games (Handout for Math428)
}
\rm
\bigskip
\centerline{ {\it 
Dr. Z.
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg@math.rutgers.edu} \hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/   .}
Nov. 24, 2003. 
} 
}
 
An  {\it impartial} combinatorial game is given by a set
of {\bf positions}, $V$, and a function $f:V \rightarrow 2^{V}$
where for every $v \in V$, $f(v)$ is the {\it set of positions
reachable from $v$ by {\bf one} legal move}.

Any combinatorial game can be described by a {\bf digraph}
whose vertices are $V$ and the arcs are
$\{vw \vert w \in f(v)\}$, i.e. there is an arc from position
$v$ to $w$ iff $w$ can be reached from $v$ in one legal move.
Conversely, given a digraph, we can define a game in which
a penny is placed on the {\bf initial position}, and in 
each turn, the player slides the penny along one of the
arcs that come out of the {\bf current position}.
A player who can't move (i.e. is at a sink) lost the game.
If the digraph is {\bf acyclic} then there can never be any ties,
and every position (vertex) can be labelled $P$ or $N$ according
to whether the {\bf Previous} or {\bf Next} players won respectively.

{\bf Labelling algorithm} 

1. Label all the sinks by $P$. 

Alternate steps $2$ and $3$ until all the vertices are labelled.

2. Label $N$ all vertices that have (at least one) arc going to
a vertex previously labelled $P$ (because this means that
the player whose turn it is to move (the Next player) has a good
move, i.e. a move that is bad for the Previous player.

3. Label $P$ all vertices that have {\bf all} their outgoing arc
going to vertices labelled $N$ (this means that whatever the Next
player can do, will lead to a win to the Previous player).

{\bf Sprague-Grundy function}

For any set of non-negative integers $A$ let
$mex(A)$ be the {\it smallest non-negative integer not in $A$}.
For example, $mex(\{0,1,2,4\})=3$ and $mex(\{1,4\})=0$.
In particular $mex(\emptyset)=0$.

The {\bf Sprague-Grundy function} of a Combinatorial game is
defined recursively by
$$
f(v)=mex \left ( \{f(w) \vert vw \in E \} \right ) \quad .
$$


If the graph is acyclic then $f(v)$ can always be defined.
For all the sinks $s$, $f(s)=0$. Removing the sinks
leaves another acyclic graph whose sinks get the value $1$.
Removing these vertices, yields yet another graph whose
sinks either get the value $2$ (if they have arcs that go both
to vertices whose values are $0$ and $1$) or the value 
$0$ (if all the arcs go to vertices labelled $1$), etc.



The {\bf Nim Sum} $\oplus$ of a set of numbers is obtained by converting
them to binary and adding them up without carry.

For example: 
$$
5 \oplus 7 \oplus 9=
$$
$$
(0101)_2 \oplus (0111)_2 \oplus (1001)_2=(1011)_2=2^3+2^1+2^0=11_{10}
$$

If $G_1, G_2, \dots, G_r$ are games, then
their {\bf Cartesian product} $G_1 \times G_2 \times \dots G_r$ is
the game in which you have $r$ boards, the $i$-th being the
digraph $G_i$, and each of them has a penny at the
{\bf initial position}, and at each turn the player
can decide which board to play on (just one board!), and on
that board slide the penny along one of the arcs.

{\bf Theorem:} The Grundy function of
the position $[v_1, \dots, v_r]$ in the compound game
$G_1 \times \dots \times G_r$ is given by
$$
f([v_1, \dots, v_r])=f(v_1) \oplus \dots \oplus f(v_r) \quad.
$$
In particular, you can tell whether a position is winning 
(Grundy function is not $0$) or losing (it is $0$).
In the former case, you should also be able to figure out the winning move,
by picking the board with the largest Grundy function and making
a move that would made the Nim sum of the Grundy functions $0$.


{\bf Exercises}

1. Prove that a position $v$ is $P$ iff
$f(v)=0$.

2. Consider the game $G_1$ that starts with $10$ counters, and a player
may take-away $1$ or $2$ counters.
(a) Draw the digraph of the game.
(b) Find the winning/losing positions.
(c) Find the Grundy function of all the positions.

3. Do the same as 1, for the game $G_2$ that starts with $12$ counters
and you can take-away $1$ or $3$ counters.

4. Consider the game $G_1 \times G_1 \times G_2$. If
the first pile has $8$ counters, the second has $6$ counters
and the third has $5$ counters, is this a $P$ or $N$ position?
If it is an $N$ position, what is a winning move?

5. Consider the game $G$ that starts with $n$ counters, and a
player can move any number $i$ of counters, $1 \leq i \leq n$,
if the pile is empty then the player whose turn is to move lost.
What is the Grundy function $f(i)$? What is the winning move?

6. The game of $r$-pile Nim is $G \times G \times \dots \times G$ ($r$ times).
In $4$ pile Nim, the current position is
$(4,5,6,8)$ (i.e. the first pile has 4 counters, the second
$5$, the third $6$, and the fourth $8$). Is that
an $N$ or $P$ position? If it is an $N$ position, find the
winning move.

\bye



