
  
%sheshbesh.tex: 
%How to Play Backgammon (if you must)
%and how to Research it (if you have time)
%%a Plain TeX file by Doron Zeilberger (2 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
\nopagenumbers
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
How to Play Backgammon (if you must)
and how to Research it (if you have time)
}
\rm
\bigskip
\centerline{ {\it 
Shalosh B. EKHAD{${\,\,}^1$} and Doron ZEILBERGER
}\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 at math dot rutgers dot edu} , 
%\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/.}
Nov. 15, 2005.
Exclusively published in the Personal Journal of
Ekhad and  Zeilberger
\hfill\break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/pj.html} .
Supported in part by the NSF. Accompanied by Maple packages
{\eighttt Bearoff}, 
{\eighttt BearoffOneDie}, and {\eighttt Sulam} available from
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/Bearoff}
etc.
} 
}

If you think Chess is hard, try Backgammon. Of course,
{\it conceptually} both conventional Chess and conventional
Backgammon are {\it trivial} in the sense that their set of
positions (`states') is {\it finite}, and we all know that
finite=trivial (or do we?). But {\it mathematical} Chess is not
played on an $8 \times 8$ board but on an $n \times n$ board
and mathematical Backgammon is not played with $15$ checkers for
each player and a board with
$4 \times 6=24$ points with $2$ (fair) dice each with
$6$ faces, but with $n$ checkers on a board of size $4K$
with $s$ $r$-faced dice (possibly loaded according to some {\it symbolic}
probability distribution).

It would be nice to have a {\it formula} or at least an {\it algorithm}
for computing the probability of winning at any given position,
with optimal play, as well as deciding on the {\it best move}.
In particular for the initial position. 
Of course there is {\it an} algorithm
(use Zermelo backwards induction [extended to
non-determinstic bipartite graphs in the case of Backgammon]).
Aviezri Fraenkel
and David Lichtenstein ({\it J. Comb. Theory (Ser. A)}
{\bf 31} (1981), 199-214) showed that for $n \times n$
Chess we need exponential time. Hence Backgammon,
that has the extra complication of being {\it non-deterministic},
is probably at least exponential-time.

Nevertheless, we do what we can. The advantage of Backgammon
is that it is more natural to construct
{\it toy models} for it. For example, a 2-faced die with a $4$-point
board where you only roll one die and only have one checker
for each player.
Even this case is not entirely trivial because one has cycles
(due to capturing).

One aspect that is amenable to `mathematical' analysis is the
Bearoff stage, where both sides are taking out. Since essentially
these are two Solitaire games, it is natural to consider
Bearoff Solitaire with one die or two dice. The conventional
wisdom is that {\it greedy} play is optimal, i.e. if you can
take a checker out, do so! 

Typing {\tt Sipur(r,K);}  
($r$ and $K$ specific positive integers),
after downloading and reading Maple package {\tt BearoffOneDie},
would tell you about all the `exceptions to the rule'  for one 
fair $r-$faced
die and $\leq K$ checkers, where $r$ and $K$ are entered by the
user. The output of {\tt Sipur(6,15);} (the ordinary 6-faced
fair die and $\leq 15$ checkers), can be viewed in

{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/oSipur}.

Typing {\tt Sipur2(r,K);},
($r$ and $K$ specific positive integers),
after downloading and reading Maple package {\tt Bearoff},
would tell you about all the `exceptions to the rule'  for two $r-$faced
fair dice with $\leq K$ checkers, where $r$ and $K$ are entered by the
user. The output of {\tt Sipur2(6,15);}
(the ordinary 6-faced fair die and $\leq 15$ checkers), can be viewed in

{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/oSipur2}.

See also the Maple package {\tt Sulam} that treats the more general
case of Bearoff Solitaire where one can bearoff without waiting for
all the pieces to be at home.

It should be possible to guess a {\it closed form}
expression (in some sense, using an appropriate {\it ansatz})
for quantities like $f(r;m,n):=$ the expected life of a Bearoff
Solitaire with one fair $r$-faced die, where one checker is 
$m$ points and the other is $n$ points away from the end, and then
{\it a posteriori} prove the conjecture by plugging-in into
the obvious recurrence. Of course, asymptotically it is
easy: $2(m+n)/(r+1)$ (why?), but we want
the {\bf exact} answer.
The recurrence, even for $f(2;m,n)$, is not so easy
to handle since it involves {\it max} in addition to the
usual four arithmetical operations. This is not a problem for
{\it number crunching} but is a big pain for {\it symbol crunching}.
Another problem is the expected life in, say, one 2-faced die
Bearoff with $m$ and $n$ checkers located at the $1$ and $2$
points location respectively
You are more than welcome to
experiment with {\tt Bearoff} and {\tt Sulam}. We wish we 
had the time to do it ourselves,
but we really must get back to the Riemann Hypothesis and $P\neq NP$.

\end



