Phill Skelton writes:
> maverick wrote:
> > I was wondering if some time in the future backgammon will be able to
> > be completely solved?
> > Is it theoretically possible to work backwards and calculate all the
> > permutations from bearing back in to the starting set up assuming all
> > the best plays are made ?
> > With the progress of computing speed is this likely to be achievable
> > in my lifetime?
>
> The same idea had occured to me a while back, but I doubt whether it
> is possible to do it for contact situations. In any situation involving
> the possiblity of hitting blots it is no doubt possible to come up
> with sequences of hits and counterhits of enormous  theoretically
> infinite  length. It is not obvious that, for any given position the
> contribution to the equity from such sequences is going to be
> calculable, though if they make a suitably small contribution to the
> total equity they can be included roughly. But then the game won't
> have been exactly 'solved'.
>
> Just my own thoughts on the subject.
Infinite sequences aren't a problem  there are a finite number of
possible board states in backgammon, and so you can treat backgammon
as a Markov process over a finite number of states. The probabilities
of a transition from one state to any other form an n x n matrix 
there IS enough information in the matrix to determine the probability
of reaching any terminal state (if you ignore the cube, there are 6
terminal states: win, gammon, and backgammon for each player); it's
analogous to a simultaneous equation with n equations and n unknowns.
The difficulty then lies not with the possibility of infinitely long
games, but the size of n  if I got it right, then there's
63,432,274,896 ways to arrange 15 chequers among 24 points, the bar,
and borne off. That's only one player's chequers  once you include
the opponent's chequers, the number of legal positions is of the order
of 10^18.
If we make a conservative assumption that the computer already has
some kind of partial ordering of the positions so that given all
preceding positions, it can calculate the equity of the current one;
and it typically takes 400 operations to calculate the equity of a
position (21 possible dice rolls by around 20 ways to play each roll),
and a computer can currently perform 500 million operations per second,
then a contemporary computer would require over 25,000 years to evaluate
the equity of every position. According to Moore's Law, this computation
time will halve approximately every 18 months; if we assume you will
live for 48 more years then computation speeds will have increased by
a factor of 2^32, and the complete backgammon analysis will take about
3 minutes. In money play there are only 4 possible cube states (centred,
owned by X, owned by O, and let's add cubeless for completeness) so a
cubeful analysis would take just over 12 minutes.
(As a side note: such a computer is not entirely out of the question.
Bremermann [I don't have a proper reference sorry... I recently moved from
New Zealand to Arizona and left most of my books behind] conjectured based
on quantum mechanical arguments that no computer, living or artificial, can
process more than 10^47 (I think) bits per gram of its mass per second. In
48 years, the computer above would still be under 10^17 bits per second and
theoretically can be built with less than a 10^30g of matter. However,
another of Moore's Laws states that the cost of semiconductor manufacturing
plants is also growing exponentially. At current growth rates, the
international revenue spent on semiconductors is projected to equal the
total global GDP by around 2020. So I guess we can expect a slowdown in
computer development sometime in the next 25 years, assuming humans will
continue to want to spend some money on trivial things like food :)
So the short answers to your three questions are: Very likely, yes, and
perhaps.
Cheers,
Gary.

Gary Wong, Department of Computer Science, University of Arizona
gary@cs.arizona.edu http://www.cs.arizona.edu/~gary/
