The future of backgammon
maverick
Hi all
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?
Maverick
Phill Skelton
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 counter-hits 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.
Phill
Gary Wong
!remove!this!ph...@sun.leeds.ac.uk (Phill Skelton) writes:
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
ga...@cs.arizona.edu http://www.cs.arizona.edu/~gary/
John S Mamoun
maverick wrote:
: Hi all
: I was wondering if some time in the future backgammon will be able to
: be completely solved?
There is little question that it will, eventually, be 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 ?
Absolutely. It would take a long time, though, unless computer
power improves.
: With the progress of computing speed is this likely to be achievable
: in my lifetime?
That's not a bad guess, IMHO. It might happen in 30 years,
since computer tecnology is changing so much. Within 100
years, it will certainly be solved, given the present rate
or computer technolog growth. Computers have already solved
Connect 4 (win for first player, I think) and Nine Men's
Morris (draw, as I recall).
John S Mamoun
Gary Wong (ga...@cs.arizona.edu) wrote:
: 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 :-)
Great posting and procedural deductive analysis. But isn't there
talk nowadays about designing chips with ultra-tiny circuits,
of nanometer thickness and less? Such chips might require fewer
resources to manufacture, with a much higher speed ceiling than
today's chips.
BOSCH Holger
I have seen the posting about the "future of backgammon", and I have a
related and maybe more fundamental question: I wonder if there exists
a best strategy in Backgammon, i.e. a strategy that is better than any
other strategy.
I do not talk about roll-outs or calculations that suppose that both
players play always the "best" move, since this has to be proven
first. Is it theoretical impossible that there are for instance three
strategies A, B and C, such that A is better than B, B better than C
and C better than A (and which are better than any other strategy)?
Maybe it's trivial but I couldn't figure it out. I think, the problem
is that in contact situations, the equities of two positions can
depend on each other, so you can not just work backwards and calculate
the equities. You do not even know, if and how two positions depend on
each other, since you need to know your "best" move to do so. However,
I might be wrong and following is correct.
Gary Wong proposed the following approach (in Re: The future of
backgammon):
> 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.
I do not know the framework of simultaneous equations, but how can you
know that there is enough information in the matrix? If I understand
you correctly, the matrix elements are the transition probablities
between two states. But these probablities are also unknown (at least
for
some positions, i.e. most/several contact positions), since you need
to know the best moves to compute them.
So, is there the Holy Grail of a best strategy out there???
Holger
-------------------------------------------------------------
Holger Bosch
Dept. of Computer Science, University of Geneva
24, rue du General Dufour, 1211 Geneva 4, Switzerland
Phone: +41 (22) 705-7642, Fax: +41 (22) 705-7780
E-mail: bo...@cui.unige.ch, http://cuiwww.unige.ch/~bosch
-------------------------------------------------------------
Rodrigo Andrade
>Computers have already solved
>Connect 4 (win for first player, I think) and Nine Men's
>Morris (draw, as I recall).
And also Othello (actually humans have), and Checkers. There are computers
that beat the world champions on these games. I'll not say also chess
because there's too much speculation about whether Deep Blue (the computer
who beat the world Champion Garry Kasparov last year) cheated or not.
Rodrigo
Gary Wong
BOSCH Holger <bo...@CUI.UNIGE.CH> writes:
> I have seen the posting about the "future of backgammon", and I have a
> related and maybe more fundamental question: I wonder if there exists
> a best strategy in Backgammon, i.e. a strategy that is better than any
> other strategy.
Subject to one or two restrictions, the answer is yes. (Several strategies
that are no worse than any other strategy, at least.)
> I do not talk about roll-outs or calculations that suppose that both
> players play always the "best" move, since this has to be proven
> first. Is it theoretical impossible that there are for instance three
> strategies A, B and C, such that A is better than B, B better than C
> and C better than A (and which are better than any other strategy)?
Three strategies certainly exist such that each is better than one of the
others and worse than the third (ie. those three strategies are
non-transitive); here's one example of strategies A, B and C:
A: Form a forward anchor and make low points in home board to blitz.
B: Overly `pure' play: Slot like crazy, try to prime. Bruce Becker :-)
C: Play safe and don't leave blots.
If you adjust the overall strengths of three players using these strategies
so they end up roughly equal in "skill", then A will tend to beat B because
his forward anchor is an excellent defence against being primed. B will
beat C a little more often than not, because C's back men will easily be
trapped. And it's conceivable that there is a player C who, despite losing
to B because of his weakness against primes, can nevertheless beat A through
superior skill in other areas and the fact that C will not easily be blitzed.
So these strategies are non-transitive.
However, it is _impossible_ for any set of non-transitive strategies to be
better than every remaining strategy. The complete proof is beyond the
scope of this article (that phrase is so much more appealing than "I'm
kind of hazy on the details" ;-) but there is a theorem (the Minimax
Theorem) that states that "every finite, zero-sum, two-person game has
optimal mixed strategies" (see the definition of "Minimax theorem" in
the Encyclopaedia of Mathematics at
http://www.astro.virginia.edu/~eww6n/math/). Money backgammon is actually
_not_ a finite game because the cube can take on arbitrarily many values, but
match backgammon is finite.
A _mixed strategy_ is a general class of strategy including those where a
player makes decisions probabilistically (an example of why this may be
necessary is the game "paper, scissors, rock" where the best strategy is to
pick a move at random -- always picking "paper" is not the best strategy).
Since backgammon is a game of complete information (both players can see the
state of the board and dice) we can actually go slightly stronger than the
Minimax theorem and claim that backgammon has optimal _pure_ strategies (ie.
strategies where the same move is always made in the same position). Note
that non-transitive strategies (eg. the A, B and C above) _cannot_ be optimal;
the Minimax theorem states that any optimal strategy must lie at a "saddle
point" of the payoff matrix. A strategy belonging to a non-transitive set
cannot possibly lie at a saddle point because by definition there is another
strategy along the same row/column of the matrix with a better payoff. The
practical upshot is that if you believe the Minimax Theorem (and you can
read a proof elsewhere :-) then yes, there are optimal strategies for
backgammon. (There is more than one optimal strategy because different
actions may result in identical payoff; eg. accepting or declining a double
that would result in a dead cube when you have exactly 25% chance of winning).
If you're a glutton for punishment and want to read about why this proof
does not suffice for money backgammon (with an unlimited cube) and an
attempt to find an alternate proof/disproof that optimal strategies exist
for money backgammon, look at http://www.dejanews.com/ for a position posted
by Paul Tanenbaum entitled "Extremely theoretical" and a discussion with
David Ullrich and others "Under-doubling dice". We never quite got a
rigourous proof, but personally I suspect that there is an `optimal' strategy
for money backgammon too (depending how you define `optimal').
> Maybe it's trivial but I couldn't figure it out. I think, the problem
> is that in contact situations, the equities of two positions can
> depend on each other, so you can not just work backwards and calculate
> the equities. You do not even know, if and how two positions depend on
> each other, since you need to know your "best" move to do so. However,
> I might be wrong and following is correct.
>
> Gary Wong proposed the following approach (in Re: The future of
> backgammon):
> > 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.
>
> I do not know the framework of simultaneous equations, but how can you
> know that there is enough information in the matrix? If I understand
> you correctly, the matrix elements are the transition probablities
> between two states. But these probablities are also unknown (at least
> for
> some positions, i.e. most/several contact positions), since you need
> to know the best moves to compute them.
You are quite right, my explanation glossed over part of the problem. The
statement about the Markov process and probability matrix holds if an
optimal strategy is known, but is not a practical way to find one.
Nevertheless I claim it is possible to find such a strategy by computer
(eg. the truly ugly brute force method of enumerating all strategies and
finding a saddle point of the payoff matrix).
> So, is there the Holy Grail of a best strategy out there???
Yes -- as it is written in the Gospel according to Saint John :-) (John von
Neumann proved the Minimax Theorem in 1928).
Cheers,
Gary.
--
Gary Wong, Department of Computer Science, University of Arizona
ga...@cs.arizona.edu http://www.cs.arizona.edu/~gary/
e r g y @best.com Paul Ferguson
In article <6ngrqq$ia9$1...@news4.wt.net> Rodrigo Andrade,
candrade@_R_E_M_O_V_E_wt.net writes:
>And also Othello (actually humans have), and Checkers. There are computers
>that beat the world champions on these games. I'll not say also chess
>because there's too much speculation about whether Deep Blue (the computer
>who beat the world Champion Garry Kasparov last year) cheated or not.
>
And how, pray tell, does Deep Blue cheat at chess? Give
itself an extra pawn? Take two moves in a row? Knock the
board over just before losing?
With millions watching every move, the machine scrutinized
by scientific and chess experts around the world, I fail to
see how anyone could believe that Deep Blue somehow cheated
at chess (unless they've added dice to the game recently).
//fergy
John S Mamoun
Rodrigo Andrade (candrade@_R_E_M_O_V_E_wt.net) wrote:
: And also Othello (actually humans have), and Checkers. There are computers
: that beat the world champions on these games. I'll not say also chess
: because there's too much speculation about whether Deep Blue (the computer
: who beat the world Champion Garry Kasparov last year) cheated or not.
: Rodrigo
These three games haven't been solved, even though computer
versions can beat the strongest human players.
Rodrigo Andrade
Sorry. I assumed that "being solved" meant "can't be beaten." Please clarify
the term "being solved."
Rodrigo
John S Mamoun
: Sorry. I assumed that "being solved" meant "can't be beaten." Please clarify
: the term "being solved."
: Rodrigo
"Being solved" means that all the values of all theoretical outcomes
possible have been computed and analyzed, such that the
computer can play the game perfectly. "Can't be beaten" means it
can beat all human players, but not necessarily that it plays perfectly.
So if, say, the best human players can make perfect moves 90% of
the time, a computer would only need to make pefect moves a little
over 90% of the time to beat all humans (assuming a perfect information
game).
Gary Wong
> BOSCH Holger <bo...@CUI.UNIGE.CH> writes:
> > I have seen the posting about the "future of backgammon", and I have a
> > related and maybe more fundamental question: I wonder if there exists
> > a best strategy in Backgammon, i.e. a strategy that is better than any
> > other strategy.
>
>
> 1. Some positions are known not to have a finite equity; i.e., with
> "best play" on both sides, the expected value of the position is a sum
> of a divergent sequence. This problem can be avoided if a cap is placed
> on the cube value, or in match play, or in cubeless play, or if some
> settlement value is simply imposed on such positions. No one knows how
> many such positions there are, or if they will ever be reached from the
> standard starting position with "best play".
This is true. However, it's not clear that this implies that a "best
strategy" does not exist. I can demonstrate that the correct
behaviour is a double/take in Paul Tanenbaum's position for instance,
without requiring the expected equity to be defined. And note that
the _distribution_ of X (where X is the random variable representing
the points won in a game by a particular player, given particular
strategies) is well-defined, even if E( X ) is not. We can calculate
P( X ) > 0, for instance. And if S is the sum of a large sequence of
independent and identically distributed X's, then does P( S > 0 ) >=
P( S < 0 ) for every strategy your opponent can use imply your
strategy is optimal? If so, I believe it is possible to find such
strategies without requiring E( X ) to exist. I'm not entirely sure
what a good definition of optimality is. "S is a martingale or
submartingale" might work, too.
And as you note, this restriction only applies to money games with an
unlimited cube. Another way to avoid the problem is to calculate not
the money amount, but the (logarithmic) utility function of that
amount of cash -- note that E( X ) is not defined, but E( log( X ) )
_is_.
> 2. Backgammon is not guaranteed to terminate. In theory, there could be
> positions in which there is a positive probability that the game never
> terminates (because the players keep hitting each other, and the pieces
> recycle). Our experience tells us that this is not the case, but it
> remains to be proved.
I don't believe that this matters. For a game to be infinitely long, it
must have repeat the same position (since there are a finite number of
positions). I assert that from every legal position, there is a non-zero
probability of reaching a terminal position, no matter what strategies the
players apply. So, the probability of a position later repeating itself
in the same game is strictly less than one; the probability of a game
repeating through n iterations of the same position then becomes
monotonically decreasing on n and the probability of an infinitely long
game becomes arbitrarily small.
> 4. If the convergence problem is solved, there's still the problem of
> solving the equations in the first place. In general, solving a system
> of equations in N variables takes O(N^2) time. This means that
> estimates for when we might be able to solve backgammon completely,
> based on the number of positions, might vastly underestimate the work
> required. If we have to perform work proportional to the square of the
> number of positions, that's a much bigger problem.
This is true in the worst case. The lower bound on time taken to
solve the equations would be a very sparse matrix (each row has 21
elements, one for each dice roll; the remaining columns are zero)
making the original assumption that the partial ordering exists and
the "best moves" are known. For very sparse matrices, Gaussian
elimination takes linear time. The quadratic worst case applies if
the matrix is dense. In reality the complexity will be somewhere in
between.
> 5. Solving the game by computing a value for every position implies that
> we use memory proportional to the number of positions. Even if
> computers become fast enough to solve the equations, they may well not
> have that much memory.
I'm pretty sure the computation is "worse" than the memory required;
if memory density is assumed to increase at the same rate then in 48
years we expect the same 2^32 factor in storage space. If a typical
contemporary computer is assumed to have 2^40 bits of memory, then we
expect 2^72 by then; we also assume 10^18 positions which is roughly
2^60 so we still have 2^72 / 2^60 = 2^12 = 4096 bits of memory per
position.
> In summary, I'd say that all of these problems can potentially be
> overcome or addressed, but solving backgammon seems to involve a lot
> more than just waiting for computers a million times faster than what we
> have now. There's also a lot of theoretical and practical progress that
> would have to be made.
True. I'm almost certain it can be done eventually. But in the meantime,
we'll still have a lot to argue about on r.g.b. ;-)
David desJardins
> And as you note, this restriction only applies to money games with an
> unlimited cube. Another way to avoid the problem is to calculate not
> the money amount, but the (logarithmic) utility function of that
> amount of cash -- note that E( X ) is not defined, but E( log( X ) )
> _is_.
Sure, you might solve some different problem. But this won't give you
anything resembling "optimal" play (aka "best strategy"), which was the
original goal.
If you play to maximize the logarithm of your winnings, and I play to
maximize my actual winnings, you are going to lose a *lot* of money to
me, until you wise up.
> I assert that from every legal position, there is a non-zero
> probability of reaching a terminal position, no matter what strategies
> the players apply.
Great, I look forward to seeing your proof. Please post it here.
> For very sparse matrices, Gaussian elimination takes linear time. The
> quadratic worst case applies if the matrix is dense.
This is just wrong. Gaussian elimination on dense matrices takes O(N^3)
time. Solving sparse systems of linear equations (which doesn't use
Gaussian elimination, but other techniques suited to sparse matrices)
takes O(N^2) time. As I said.
David desJardins
David desJardins
> This is true. However, it's not clear that this implies that a "best
> strategy" does not exist. I can demonstrate that the correct
> behaviour is a double/take in Paul Tanenbaum's position for instance,
> without requiring the expected equity to be defined.
I frankly think you are wrong. I'd very much like to see your rigorous
definition of "correct behavior" and rigorous proof of its application
to positions with undefined equity.
If your argument starts with "let the value of the position be X", then
it's completely bogus, because the position doesn't have a value. I
don't understand how you are going to define "correct behavior" except
as "move to the position with the highest equity; this definition won't
work except for positions which have a defined equity.
David desJardins
bshe...@my-dejanews.com
David desJardins <da...@desjardins.org> wrote:
> Gary Wong <ga...@cs.arizona.edu> writes:
> > And as you note, this restriction only applies to money games with an
> > unlimited cube. Another way to avoid the problem is to calculate not
> > the money amount, but the (logarithmic) utility function of that
> > amount of cash -- note that E( X ) is not defined, but E( log( X ) )
> > _is_.
>
> anything resembling "optimal" play (aka "best strategy"), which was the
> original goal.
Well, this is not really true. The solution of the logarithmic equity
equations will result in a program that plays risk-averse backgammon,
to be sure, but it will play risk-averse backgammon very, very well.
Gary's point is that we can construct approximations to the ideal
strategy that represent practical solutions. If you don't like Gary's
suggestion because it is too risk-averse, we can change it. For example,
use linear utility until the cube hits 64, then switch to an appropriately-
scaled logarithmic utility.
My reservation about Gary's proposal is that it changes the problem
into one requiring a lot more space. The original problem required just
3 cube locations for every checker position. Gary's proposal requires
unbounded space, since the logarithmic utility function doesn't scale
linearly. (That is, you cannot compute the utility of owning a 16-cube
based upon knowing the utility of owning a 2-cube.)
The ideal approximation will involve storing just 3 cube positions per
checker position.
> If you play to maximize the logarithm of your winnings, and I play to
> maximize my actual winnings, you are going to lose a *lot* of money to
> me, until you wise up.
I agree that a practical "solution" to backgammon must approach the
ideal behavior as closely as possible.
The key is to limit approximations to the smallest degree necessary. You
will need to construct an approximation that deals with undefined equity
as tightly as possible. It is a challenging problem simply to identify
positions that have undefined equity. A second challenging problem is to
define a reasonable approximation.
Note that I don't care about theoretical soundness as much as
practical effectiveness. A theoretical proof that says "No ideal moves
exist in backgammon" is completely worthless even if it is completely true.
Every opponent has a model of the game which is an approximation to the
ideal. The appropriate goal is to create an approximation that has
practical value.
> > I assert that from every legal position, there is a non-zero
> > probability of reaching a terminal position, no matter what strategies
> > the players apply.
>
> Great, I look forward to seeing your proof. Please post it here.
It seems to me that Gary has already done so, David, at least with respect
to the requirements of this problem. Gary pointed out that when a move
sequence revisits a position we obtain closure on the equations that
define equity. Since there are a finite number of positions, every
sufficiently long move sequence must eventually revisit a position.
Also, please note that the system of equations depends only on one-move
of lookahead. If a cycle occurs in one move (that is, after our move
the opponent faces the exact same position that we had before our move),
then the equation is no more complicated than if it doesn't.
On balance, it seems to me that the possibility of arbitrarily long games
poses no theoretical difficulty.
> > For very sparse matrices, Gaussian elimination takes linear time. The
> > quadratic worst case applies if the matrix is dense.
>
> This is just wrong. Gaussian elimination on dense matrices takes O(N^3)
> time. Solving sparse systems of linear equations (which doesn't use
> Gaussian elimination, but other techniques suited to sparse matrices)
> takes O(N^2) time. As I said.
Good point.
In the context of solving the equations of a game, we also have to deal
with the minimax problem, which is the problem of finding the best move.
Specifically: the transition probabilities for a given position are not
known until we know which move we will select for each roll, but we don't
know the move until we have solved the equations.
The minimax problem has a far more greater impact on the running time of
the algorithm than the equation-solving part. Let's look at why, under
the assumption that we have somehow dealt with the "undefined equity"
problem.
When we start our solution we have no knowledge of how to make good moves,
so the program initially moves arbitrarily. The first iteration of the
solution will establish some values, but it will turn out that many of
the moves we made to establish those values were bad, so the values
themselves aare bad. We have to solve again.
On the second iteration, the situation will improve because we have
correct equities for any position in which the program played best moves
for all possible continuations. Of course, after just one iteration that
is probably a vanishingly small fraction of all positions, but the beauty
of the algorithm is that subsequent iterations will never change those values.
So we iterate and iterate until the values converge. Each iteration involves
a solution of the system of sparse equations mentioned by Gary and David.
Each iteration plays at least as well as the previous.
Convergence is assured under the assumption that ideal play exists, which
is equivalent to the assumption that every position has a well-defined
equity. But the number of iterations before convergence is anybody's guess.
Brian Sheppard
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
bshe...@my-dejanews.com
> > strategy" does not exist. I can demonstrate that the correct
> > behaviour is a double/take in Paul Tanenbaum's position for instance,
> > without requiring the expected equity to be defined.
>
> definition of "correct behavior" and rigorous proof of its application
> to positions with undefined equity.
>
> If your argument starts with "let the value of the position be X", then
> it's completely bogus, because the position doesn't have a value. I
> don't understand how you are going to define "correct behavior" except
> as "move to the position with the highest equity; this definition won't
> work except for positions which have a defined equity.
This is a good question.
Gary assumed that the hold-cube-forever strategy cannot be better than
the reserve-the-right-to-double strategy. Possibly that is invalid in
the undefined equity situation. But it is hard to see how reserving the
right to double can be worse than keeping the right to double. Anyway,
here is the outline of Gary's proof.
We will show that doubling is better for the first player by showing
that doubling works out better than no-double even if we use the
take-and-hold strategy after we are redoubled. (Details omitted; the
arithmetic is easy.)
Then we show that taking is better, using the strategy of take-and-hold if
we redouble and are then reredoubled.
I admit that Paul Tanenbaum's position put me into a state of "cognitive
dissonance." (If you didn't major in psychology: "I couldn't tell which
way is up.") I suspect that the final word hasn't been spoken on this
subject. I am very interested in hearing your viewpoint, David.
my_...@hotmail.com
back to lurking.
1. If I told you I had solved the game of *cubeless*
backgammon, that is, I had a function that returned
the exact cubeless equity for any position,
how hard would it be to solve backgammon with the cube?
2. A method for solving cubeless backgammon: Can you
start from the end and work backwards? I.e. generate
all terminating nodes in the mini-max tree (positions
in which X has 15 checkers borne off and O does not).
Then for each end position, generate all possible nodes
that can lead to that position, and building on what
you already know, define an equity for these positions,
continue looking backwards, etc. etc.
Or would that only work for non-contact positions?
Christopher D. Yep
[*] I didn't feel like calculating a more reasonable upper bound, but clearly
10,000 is a very crude upper bound on the number of 2-4 rolls necessary.
Christopher D. Yep
>BOSCH Holger <bo...@CUI.UNIGE.CH> writes:
>> I have seen the posting about the "future of backgammon", and I have a
>> related and maybe more fundamental question: I wonder if there exists
>> a best strategy in Backgammon, i.e. a strategy that is better than any
>> other strategy.
>There are several problems, some of which you have identified:
>1. [...]
>2. Backgammon is not guaranteed to terminate. In theory, there could be
>positions in which there is a positive probability that the game never
>terminates (because the players keep hitting each other, and the pieces
>recycle). Our experience tells us that this is not the case, but it
>remains to be proved.
The sequence of dice rolls in which each player rolls 2-4 10,000 [*] times in
succession will terminate almost all legal initial backgammon positions. For
those initial positions in which both players start with both men on the bar
with each player also having at least 2 men on each of his 2 and 4 pts., we
can give player 1 dice rolls which force him off one of these pts. and then
give both players 2-4 10,000 [*] times in succession. This will terminate any
backgammon position.
Thus there is a zero probability that the game never terminates. So this
solves problem #2.
I can't take credit for this (outline of a) proof. It was discovered and
written on r.g.b. in 1994(?) by C. [Curt?] McMullen (c...@maize.berkeley.edu].
Chris
Gary Wong
> Gary Wong <ga...@cs.arizona.edu> writes:
> > And as you note, this restriction only applies to money games with an
> > unlimited cube. Another way to avoid the problem is to calculate not
> > the money amount, but the (logarithmic) utility function of that
> > amount of cash -- note that E( X ) is not defined, but E( log( X ) )
> > _is_.
>
> anything resembling "optimal" play (aka "best strategy"), which was the
> original goal.
Well, I'm only proposing the maximal utility as an interesting problem we
can attempt to solve. The problem "show me a strategy that maximises E(X)" is
not interesting, the answer is "you can't, E(X) isn't defined for all possible
strategies". Several other propositions (such as match play, and money
play with a cash limit) as you mentioned in your previous article are
valid and interesting problems too.
> If you play to maximize the logarithm of your winnings, and I play to
> maximize my actual winnings, you are going to lose a *lot* of money to
> me, until you wise up.
That's not true. Maximising one's GLOBAL utility is rational behaviour (and
some kind of "utility = log( dollars )" definition is reasonable). I am
not claiming "total utility = utility in game one + utility in game two";
that is clearly not true for nonlinear dollar/utility relations.
> > I assert that from every legal position, there is a non-zero
> > probability of reaching a terminal position, no matter what strategies
> > the players apply.
>
> Great, I look forward to seeing your proof. Please post it here.
OK, here's an informal proof. Assume the contradiction is true (ie. that
there exists a position p from which the probability of finishing the game
in finite time is zero). Note that every position has at least one legal
move by at least one player to another position (the position where neither
player has a possible move, ie. both on the bar against closed boards, cannot
be reached through legal play). Since there are a finite number of
positions, and we assumed the probability of finishing the game from this
position is zero, the only way for this game to continue indefinitely is
for it to repeat this same position again at some point in the future -- with
probability one. Since we established above that there must be at least one
possible move from every legal position, that must mean that all _subsequent_
positions must lead to the current position too, again with probability one.
But this is impossible -- from any legal position, I can show you a possible
sequence that results in an irreversible change in the game state (eg.
bearing a chequer off, or dumping more than one chequer onto the ace point).
This sequence can occur with probability greater than zero. The events
"irreversible change" and "repeat the same position" are clearly distinct.
"Irreversible change" has positive probability, and so "repeat the same
position" must have probability less than or equal to one less "irreversible
change" -- ie. less than one. But we saw that the assumption that such a
position p exists implies that the "repeat the same position" probability
_IS_ one. Therefore the original assumption is wrong, and no such
position p exists.
> > For very sparse matrices, Gaussian elimination takes linear time. The
> > quadratic worst case applies if the matrix is dense.
>
> This is just wrong. Gaussian elimination on dense matrices takes O(N^3)
> time. Solving sparse systems of linear equations (which doesn't use
> Gaussian elimination, but other techniques suited to sparse matrices)
> takes O(N^2) time. As I said.
I don't think we're being precise enough about what kind of matrices
we mean. We could claim that solving Ax = b takes no time at all, if
A is the identity matrix. If A has arbitrary elements along the
leading diagonal and zeroes everywhere else (and we know this to be
the case in advance), then solving the equation requires n divisions
for O(n) time. If we add a single element to every row above the
diagonal, then we require an additional multiplication and subtraction
for each row, which still leaves us in O(n) time. The sparse matrix
I'm talking about will have up to 21 such non-zero elements and could
require 21 multiplications and subtractions before the division --
it's still only O(n) though. (We don't have to search for the 21
non-zero elements -- we already know where they are because we stored
that information when we generated the thing in the first place.) I
readily admit that it will be a problem coming up with such a matrix,
but once we have it, it can be solved in linear time. I don't mean to
claim that I can reduce any other kind of matrix in this time.
Gary Wong
> The key is to limit approximations to the smallest degree necessary. You
> will need to construct an approximation that deals with undefined equity
> as tightly as possible. It is a challenging problem simply to identify
> positions that have undefined equity. A second challenging problem is to
> define a reasonable approximation.
The main thing that concerns me is that given that positions that have
clearly undefined equities exist, any position with a non-zero probability
of reaching one of those positions must also have undefined equity. To be
slightly more precise, here's a definition:
A position p is "troublesome" for a pair of players' strategies if the
probability of reaching the same board position p with the cube
greater by a factor of c is greater than or equal to 1/c, under those
strategies.
Paul Tanenbaum's position is troublesome if and only if both players'
strategies are "double/take", because then the same position will be
reached if both players dance (probability p = 25/36 x 25/36), and the
cube will be higher by a factor of c = 4 (being turned twice).
p > 1/c, so the position is troublesome.
But how do we go about calculating equities (and strategies) in positions
that could lead to troublesome positions? That's what I'm not sure about.
If, instead of maximising E(X) we are allowed to say that a strategy that
ensures P( S > 0 ) >= 0 (see older article for definition of S) is "good"
or "optimal" or whatever, then I can do slightly better. Note that S
is the sum of two sequences: the winnings from games that included
troublesome positions S_t, and the winnings from games that don't,
S_u. We can calculate the probability of a troublesome position
being reached from the current position given a pair of strategies,
P(T). We can calculate the equity of the current position assuming
a troublesome position will not be reached, E(X|not T). We can
(almost -- see below) maximise S_u by maximising E(X|not T), and we
can maximise P( S_t > 0 ) by other means. Therefore, the total P( S > 0 )
should be maximised. I claim that this indicates something good about our
strategy, but I don't know what :-) I can't claim it's "optimal" without
a better understanding of what optimality _is_.
The main objection I have with the reasoning so far is that it assumes
the strategy is entirely "passive" towards T -- ie. we start playing
rationally, ignoring the possibility of troublesome positions until one
occurs, at which point we switch to our "maximise P( S_t > 0 )" plan.
It does _not_ allow for discrimination between positions with different
P(T)s. If the optimal (whatever that means) backgammon strategy
happens to be one where positions with high or low P(T) are deliberately
sought after, then that strategy lies outside the set of strategies
that can be evaluated in this manner.
Related questions: the player on roll in Tanenbaum's position has a
greater probability of winning. Is this an advantage? If so, is
it worth sacrificing equity for? How much? For instance, if you had
the choice of two plays: (a) has a higher probability of reaching
Tanenbaum's position with you on roll but a slightly lower equity
otherwise; (b) has a lower probability of reaching T but slightly
higher equity otherwise. Which play would you choose? If (b) can
be an "optimal" strategy, then the set of strategies above (P( S > 0 ))
do include optimal strategies. If optimal strategies always answer
(a) or "it depends", then we need a better definition.
Gary Wong
> > strategy" does not exist. I can demonstrate that the correct
> > behaviour is a double/take in Paul Tanenbaum's position for instance,
> > without requiring the expected equity to be defined.
>
> definition of "correct behavior" and rigorous proof of its application
> to positions with undefined equity.
Brian Sheppard already answered most of this (thanks Brian -- you have a
great memory, I had to go to Deja News to remember most of this stuff :-)
but for completeness, here it is. I don't claim it's rigorous, but you're
welcome to prove or disprove any of it.
Assume the first player to roll a 6 wins and there are no gammon
possibilities. (You could estimate gammons and losses if you like, the
numbers would change a bit.)
First of all, is it a take or a drop? Assume your opponent offers you a
2-cube (the results generalise to any value) -- if you drop your equity
is well-defined, it's -1. If you take, then you can guarantee yourself
at least -0.36 points simply by taking the cube and then forgetting
about it until you can cash -- you lose 59% of the games with a 2 cube
for -1.18, but win 41% at 2 for 0.82 for total equity -0.36. So you
clearly lose less by taking.
Now, is it a double? Assume the cube is centred. The cube is worthless
to you if you enter (we've assumed you win regardless of whether you
own the cube). Since the cube is centred, your opponent can already
double so you're not giving them any additional recube vig by doubling
now. Therefore, you have nothing to lose by doubling; you also have
something to gain because you are a slight favourite with cubeless
equity 0.18. So I believe it _is_ correct to double (and take) here.
Is the situation any different for a redouble? In this case you might be a
little more reluctant to give your opponent the cube because you're giving
them the chance to double they wouldn't otherwise have had. However, I don't
believe this makes any difference; the cube will still die if you don't double
now. Since it was a correct initial double, we know we'd prefer to have our
opponent holding a live doubled cube than a dead one in any position; this
makes it a correct redouble too.
Brian questions whether it could be correct to hold onto the cube and
double later. I don't believe this strategy can be correct -- the key
is that you will be faced with _exactly the same position_ every move
from now until when somebody enters (when they are assumed to become
massive favourites to win; if your opponent enters you obviously no
longer want to double, and if you enter then you've lost your market
by a long way). The only thing that can change between this turn and
your next turn (assuming nobody enters) is the value of the cube,
which makes utterly no difference to your doubling strategy in an
unlimited money game (it might make a difference in a match game of
course, or in a money game if the value of the cube starts approaching
the cash in your pocket, but that's a different story). Therefore, if
it will be correct to double next turn, it is also correct to double
this turn. Your market cannot possibly improve under these conditions
but can get worse (if somebody enters), and so if it is correct to
double at all, it's correct to double now.
Is this conjecture true? I believe it is. I would be keen to see any
proof or disproof if you have any ideas for attacking the problem in
another way. In fact I would very much _like_ to see it proven wrong,
because such a disproof (ie. that double/take is not correct behaviour)
would imply that troublesome positions cannot exist under an optimal
strategy, which simplifies our search for an optimal strategy
enormously :-) But personally I believe the double/take is correct.
If I were playing for money and the position came up, I would certainly
double/take until the cube got so high I was unwilling to risk that
amount of cash; at that point I would be willing to either offer or
accept a cash settlement for around 15% of the cube value. This
strategy may not be optimal, but it's good enough for me.
Don Woods
> > > I assert that from every legal position, there is a non-zero
> > > probability of reaching a terminal position, no matter what strategies
> > > the players apply.
> >
> > Great, I look forward to seeing your proof. Please post it here.
>
> ...
> But this is impossible -- from any legal position, I can show you a possible
> sequence that results in an irreversible change in the game state (eg.
> bearing a chequer off, or dumping more than one chequer onto the ace point).
> This sequence can occur with probability greater than zero.
This is where your proof falls apart. Certainly there are legal moves
that would result in an irreversible change of state, but these moves
might NOT occur with probability greater than zero, because the players
might choose to make other moves given those rolls.
In effect, what you are trying to prove is that "backgammon to lose", i.e.
you "win" if the OTHER player bears off his last checker, has a non-zero
chance of terminating under optimal play. I.e., can two players who are
TRYING to keep the game going forever, always do so?
I saw another posting elsewhere in this thread that claims somebody did
solve this problem (the proof involved a large number of "2-4" rolls),
but he didn't include enough details to convince me and I haven't yet
tried chasing down his reference on DejaNews.
-- Don.
-------------------------------------------------------------------------------
--
-- Don Woods (d...@clari.net) ClariNet provides on-line news.
-- http://www.clari.net/~don I provide personal opinions.
--
Gary Wong
> Gary Wong <ga...@cs.arizona.edu> writes:
> > > > I assert that from every legal position, there is a non-zero
> > > > probability of reaching a terminal position, no matter what strategies
> > > > the players apply.
> > >
> > > Great, I look forward to seeing your proof. Please post it here.
> >
> > ...
> > But this is impossible -- from any legal position, I can show you a possible
> > sequence that results in an irreversible change in the game state (eg.
> > bearing a chequer off, or dumping more than one chequer onto the ace point).
> > This sequence can occur with probability greater than zero.
>
> that would result in an irreversible change of state, but these moves
> might NOT occur with probability greater than zero, because the players
> might choose to make other moves given those rolls.
Admittedly I didn't demonstrate that this was impossible. I should have
quoted a stronger result that there are sequences of dice rolls that
_must_ result in an irreversible change of state no matter how they are
played.
> In effect, what you are trying to prove is that "backgammon to lose", i.e.
> you "win" if the OTHER player bears off his last checker, has a non-zero
> chance of terminating under optimal play. I.e., can two players who are
> TRYING to keep the game going forever, always do so?
No, not if they roll certain sequences.
> I saw another posting elsewhere in this thread that claims somebody did
> solve this problem (the proof involved a large number of "2-4" rolls),
> but he didn't include enough details to convince me and I haven't yet
> tried chasing down his reference on DejaNews.
The key is that _odd_ points for me (my 1, 3, 5... etc.) are _even_ points
for you (24, 22, 20...). If I only roll even numbers, I enter from the bar
onto odd numbered points. If you only roll even numbers, you enter from
the bar onto (my) _even_ numbered points. The only way positions can
recur is if a blot is hit (otherwise, the pip counts are monotonically
decreasing and so trivially acyclic). If blots entering from the bar
always end up on odd/even points, and only even numbers are rolled
subsequently, then you can see that none of my recirculated blots can
ever contact any of your recirculated blots. Eventually I'm going to have
to dump multiple chequers onto my ace point (which is one of the odd points
my recirculated blots will be restricted to), or bear off. Once my ace
point is made, dumping multiple chequers onto my 3 point becomes irreversible,
too, and so on. There are a finite number of pips made up of my chequers
on my even points, so I can't keep moving them forever to delay the
inevitable -- eventually they'll end up on my 2 point, or be hit and
recirculated onto an odd point. The objection about making the 2, 4 and 6
points to prevent chequers from entering was addressed in another article
(you can't hold your board forever; if _both_ players are on the bar against
made 2, 4 and 6 points then give one player odd numbers until he's entered
and then wait for his board to crunch).
bshe...@my-dejanews.com
my_...@hotmail.com wrote:
> 1. If I told you I had solved the game of *cubeless*
> backgammon, that is, I had a function that returned
> the exact cubeless equity for any position,
> how hard would it be to solve backgammon with the cube?
The ideal answer is that there are 3 times as many positions in money
games using the cube as in money games cubeless. The positions have the
same checker positions with 3 possible cube locations for each.
That answer is complicated by the observation that cube-using positions
may not have well-defined equities. (The classic example is "Tanenbaum's
Position," in which each side has a man on the bar against a 5-point
board, with an opponent's blot on the 6 point. Each side also has a
plethora of outfield blots.)
The equity of positions like Tanenbaum's depends on how much money each
player is willing to lose, which means that the exact level of the cube
is important. And this is a problem because there are an infinitude of
possible levels.
So the answer is that somewhere between 3 times and infinitely many times
as much space is required. (I'm happy to have narrowed this down for you.)
My instinct is that there are really excellent approximations to cube-using
play that use only 3 times as much space.
> 2. A method for solving cubeless backgammon: Can you
> start from the end and work backwards? I.e. generate
> all terminating nodes in the mini-max tree (positions
> in which X has 15 checkers borne off and O does not).
> Then for each end position, generate all possible nodes
> that can lead to that position, and building on what
> you already know, define an equity for these positions,
> continue looking backwards, etc. etc.
>
> Or would that only work for non-contact positions?
The method you describe depends on establishing a "partial ordering" among
backgammon positions. That is, we need to order all backgammon positions
such that all successors of any position occur before the position does.
If we have such an ordering then we can solve backgammon by computing
equities until an equity is assigned to the initial position.
Unfortunately, a partial ordering of backgammon positions does not exist,
because it is possible for a position to lead to itself a few rolls down
the road. More complicated problems occur when you have 2 positions such
that A leads to B and B leads to A.
Other posts describe how equities can be computed in spaces that do not
have a partial ordering. There are four parts to the computation. First you
guess what the best moves are for every roll. Second, you set up transition
equations for every position on the assumption that the moves you think
are best really are best. Third, you solve the equations. Finally, you
check to see if all of your selected moves really are best, and if not you
repeat the process. Termination is guaranteed eventually.
Brian Sheppard
bshe...@my-dejanews.com
Gary Wong <ga...@cs.arizona.edu> wrote:
> bshe...@my-dejanews.com writes:
> > The key is to limit approximations to the smallest degree necessary. You
> > will need to construct an approximation that deals with undefined equity
> > as tightly as possible. It is a challenging problem simply to identify
> > positions that have undefined equity. A second challenging problem is to
> > define a reasonable approximation.
>
> clearly undefined equities exist, any position with a non-zero probability
> of reaching one of those positions must also have undefined equity. To be
> slightly more precise, here's a definition:
Thank you, Gary, for your insights into how we can handle troublesome
positions.
I propose solving the cubeless game, which has the virtue of having
1/3 of the number of positions as the cube-using game. (Happily, we can
solve the cubeless game after only 46 years of technological progress,
rather than 48!) The cubeless game also has no troublesome positions.
The we can use a search engine to solve the cube-handling problem.
In 46 years, we should be able to look ahead about 6 ply, so the cube-
handling consequences of moves should be apparent. Alternatively, we
can do full-game rollouts at a rate of about 1,600,000,000 games per second.
(Assuming the rate of CPU speed improvements slows to only a doubling
every 2 years.)
Brian Sheppard
BTW: I am only partly serious about this post. After all, if we had that
much CPU power we could solve much bigger problems than backgammon!
David desJardins
> Convergence is assured under the assumption that ideal play exists, which
> is equivalent to the assumption that every position has a well-defined
> equity.
This blanket statement needs a proof to support it. It's not obvious
that this process (choose a move in each position, solve for the
equities, then if they suggest a better move use that as the new move,
and repeat) will converge to a "best move" in each position. If you
want to claim that it does for backgammon, then you have to prove that.
In any case, it's not a very practical algorithm, either, especially as
long as the solving requires time proportional to the square of the
number of positions.
David desJardins
David desJardins
> If we add a single element to every row above the diagonal, then we
> require an additional multiplication and subtraction for each row,
> which still leaves us in O(n) time.
Putting every nonzero element of the matrix on or above the diagonal
corresponds to imposing a total order on backgammon positions, and
guaranteeing that from a given position you only move to positions which
succeed it in that total order. We all know that's not possible for
backgammon, because positions can repeat.
In the backgammon transition matrix, there will be entries both above
and below the diagonal.
> The sparse matrix I'm talking about will have up to 21 such non-zero
> elements and could require 21 multiplications and subtractions before
> the division -- it's still only O(n) though. (We don't have to search
> for the 21 non-zero elements -- we already know where they are because
> we stored that information when we generated the thing in the first
> place.) I readily admit that it will be a problem coming up with such
> a matrix, but once we have it, it can be solved in linear time.
You seem to be claiming that you can solve arbitrary systems of linear
equations in N variables, with at most 21 terms in each equation, in
O(N) time. If true that would be a revolutionary breakthrough. I hope
that you will explain how to do this.
David desJardins
Gary Wong
> Gary Wong <ga...@cs.arizona.edu> writes:
> > If we add a single element to every row above the diagonal, then we
> > require an additional multiplication and subtraction for each row,
> > which still leaves us in O(n) time.
>
> corresponds to imposing a total order on backgammon positions,
Exactly. This is all derived from the "...assume a partial ordering
exists..." from several articles ago, and leads directly to the
estimated 25,000 year solution time now/3 minute solution time in 2046
result. It can be interpreted as the expected time to calculate
an approximate equity of every position; time to calculate one iteration
of the convergence; a lower bound on the time to calculate a perfect
equity of each position; etc. etc.
> > The sparse matrix I'm talking about will have up to 21 such non-zero
> > elements and could require 21 multiplications and subtractions before
> > the division -- it's still only O(n) though. (We don't have to search
> > for the 21 non-zero elements -- we already know where they are because
> > we stored that information when we generated the thing in the first
> > place.) I readily admit that it will be a problem coming up with such
> > a matrix, but once we have it, it can be solved in linear time.
>
> You seem to be claiming that you can solve arbitrary systems of linear
> equations in N variables, with at most 21 terms in each equation, in
> O(N) time. If true that would be a revolutionary breakthrough. I hope
> that you will explain how to do this.
I never said I was solving _arbitrary_ systems. I can reduce sparse
(ie. a constant limit on the number of terms per row) upper triangular
matrices in linear time (because there are n rows; each row can be
reduced in constant time because there a constant number of elements
to eliminate).
David desJardins
> I propose solving the cubeless game, which has the virtue of having
> 1/3 of the number of positions as the cube-using game. (Happily, we can
> solve the cubeless game after only 46 years of technological progress,
> rather than 48!)
Once again: no, we can't. We don't have any method that will do this.
The straightforward methods (based on solving linear equations) require
around a billion billion times more work than that.
David desJardins
Gary Wong
> > exists..." from several articles ago, and leads directly to the
> > estimated 25,000 year solution time now/3 minute solution time in 2046
> > result.
>
> > (ie. a constant limit on the number of terms per row) upper triangular
>
> Why would we "assume" a partial ordering of the positions, when we know
> that backgammon positions aren't in fact so ordered? Are you saying
> that in the past several articles you've deliberately been assuming
> something contrary to fact, and then working out what the work would be
> under that false assumption?
In some sense yes, but I wouldn't word it like that. I clearly expressed
the assumption I was making, and derived a result that directly follows
from that assumption. The result is directly applicable to the model in
use, and approximately applicable to backgammon as far as that model
approximates backgammon. You can regard it as a lower bound or an
inequality if you like.
> What good is that? I thought the thread was supposed to be about
> determining the best strategy for backgammon. We can't do that if we
> start with false assumptions.
This thread seems to be about lots of things :-) I'd feel very reluctant
to claim that we're discussing determining the best strategy for backgammon
in anything other than a very abstract and hypothetical sense. Very little
of this is at all practical. Historically (as far as I know), every
non-trivial game that has been solved by computer (Connect Four, go-moku,
etc.) has been attacked with lots of Shannon C-type strategy and a little
bit of brute force. It would be unprecedented if backgammon were ever to be
solved by brute force alone. And by my reckoning, we have easily 4 decades
to think about intelligent solutions before we should even be allowed to
think about brute force again :-)
> It sounds like you now agree with what I've been saying all along:
> solving backgammon using any of the obvious methods takes at least time
> proportional to the square of the number of positions.
I don't see how you can reject my approximation as being based on false
assumptions, and then present another approximation that's equally invalid.
I'm not sure what assumptions you based the O(n^2) result on -- that every
position could potentially lead to every other position, I guess? Well,
that's just as bad as my assumption that a partial ordering exists. Your
result is a valid upper bound, just as mine is a valid lower bound. We
can refine these bounds by using models that more closely approximate
backgammon, for example:
Although there are around 10^18 positions, the majority of those include
at least one man borne off. These positions can clearly not lead to a
subsequent position where all men are in play. We can go further than
that, and partition the set of positions into 256 subsets, one for every
combination of numbers of chequers borne off by each player. It is clear
that a partial ordering _does_ exist between these sets, because a man borne
off cannot come back into play. All cyclic dependencies between positions
must take place within one of these subsets; the subsets themselves are
partially ordered. Other partitions are possible too (eg. number of men
over one on the ace point; number of men over one on the deuce point if
the ace point is made; contact vs. non-contact; etc.)
Furthermore, of the 10^18, a _huge_ majority will be exotic positions
that are extremely unlikely to arise through the optimal play we're
evaluating (a player has a man borne off yet still has many chequers
in the outfield; both players leaving huge numbers of blots exposed;
positions in which players abandon their 6 points long before contact
is broken; etc. etc.) Many of these can be heuristically evaluated to
be trivial double/drops (if you don't mind a heuristic approximation
-- if you want to be pure, you can still arrive at an early
double/drop result by computing enough of the pure subsequent
positions that the equity will be in the double/drop range regardless
of the partial equities of the remaining possibilities).
It's exceedingly difficult to be quantitative about any of this, but I
suspect these measures (and others like them I haven't mentioned, or
haven't thought of) save you a few orders of magnitude if you stay
pure, or several orders of magnitude if you take heuristic shortcuts.
David desJardins
> This thread seems to be about lots of things :-) I'd feel very reluctant
> to claim that we're discussing determining the best strategy for backgammon
> in anything other than a very abstract and hypothetical sense.
I certainly am. I won't claim what you are discussing, if you don't
claim what I'm discussing.
Several people seem to have read your postings and gone away with the
impression that "in 40 years we'll be able to solve backgammon exactly".
So I wasn't the only one who misunderstood what you wrote.
> Very little of this is at all practical.
That's your opinion. I see lots of "practical" applications (to the
extent that playing games is practical at all). For example, we could
solve smaller variants of backgammon (with fewer points and checkers) to
get insight into the real game. We could solve restricted backgammon
positions, such as those where one player has only one man left on the
board. Before devoting any significant computing power to that, we'd
want to try to find the best methods.
> I don't see how you can reject my approximation as being based on false
> assumptions, and then present another approximation that's equally invalid.
> I'm not sure what assumptions you based the O(n^2) result on -- that every
> position could potentially lead to every other position, I guess?
O(N^2) is the time that it takes to solve general sparse systems of
linear equations using the best known techniques. If every position
could lead to every other, then it would take more time---you can't
solve dense systems of linear equations in O(N^2) time.
You're certainly right that you can do better, for example by using
"blocking" of the equations (what you call a partial ordering of the
positions). A useful contribution would be to specify a real algorithm
and then try to get real estimates of the work. I don't think that's so
impractical as you do---for example, one can learn a lot by working on
toy problems.
David desJardins
Gary Wong
> Gary Wong <ga...@cs.arizona.edu> writes:
> > This thread seems to be about lots of things :-) I'd feel very reluctant
> > to claim that we're discussing determining the best strategy for backgammon
> > in anything other than a very abstract and hypothetical sense.
>
> claim what I'm discussing.
That's certainly fair :-) I think I'm discussing determining the best
strategy for backgammon in the same sense that I might discuss the
best approach for factoring a 2048 bit integer. I would say "25,000
years (or whatever) is the best we can do with current hardware: out
of the question. We expect to wait at least 40 years for future
hardware to provide the solution with current algorithms: better, but
we're still too impatient. Therefore, we reject both of those
approaches and try to be clever _now_." To be less than abstract and
hypothetical, we either need to find an algorithm with significantly
better performance than the best currently known, or prove that none
such exist. (Incidentally, doing either would require somebody far
cleverer than me, so at that point I give up and remain being abstract
and hypothetical :-)
> Several people seem to have read your postings and gone away with the
> impression that "in 40 years we'll be able to solve backgammon exactly".
> So I wasn't the only one who misunderstood what you wrote.
I reread my original article (wtg1gmu...@brigantine.CS.Arizona.EDU)
and that isn't quite what I said. There were three questions asked
("...will backgammon [eventually] be completely solved", "is it theoretically
possible [to solve]", and "is this likely to be achievable in my lifetime").
My responses were "very likely", "yes", and "perhaps".
I think the ambiguous part that caused confusion is the sentence:
"If we make a conservative assumption that the computer already has
some kind of partial ordering [...] then a contemporary computer would
require over 25,000 years." I should have been specific that this
assumption is conservative only for computing a _lower_ bound. When
considering it from the other point of view (ie. an upper bound) it
is a very _liberal_ (unjustified) assumption. Apologies for being vague
about that.
> > Very little of this is at all practical.
>
> That's your opinion. I see lots of "practical" applications (to the
> extent that playing games is practical at all). For example, we could
> solve smaller variants of backgammon (with fewer points and checkers) to
> get insight into the real game. We could solve restricted backgammon
> positions, such as those where one player has only one man left on the
> board.
That's very true. I believe Hugh Sconyers has already found the equities
of every position of backgammon where each player plays with 3 or less
chequers. I would be interested to know what the asymptotic performance
of his algorithm is -- given that it has terminated already, I guess that
it is significantly better than the O(n^2) upper bound on the number of
positions. There are going on 10 million legal positions with 3 chequers
each, so an O(n^2) approach would require well over 10^13 characteristic
operations. I claim this is beyond current capabilities (for moderately
complex operations, on moderately priced hardware, in a moderate length of
time). It also far exceeds the 3x10^9 operations to calculate the equities
of all positions where players have up to 15 chequers in their home boards
(which he has also solved). So his algorithm seems much better than O(n^2).
Unfortunately, we need it to be better than O(n) to solve the 15-chequer
problem any time soon (which is essentially equivalent to finding a general
backgammon solution that's a member of P with respect to the number of
chequers). Either that, or build a nondeterministic computer ;-)
> Before devoting any significant computing power to that, we'd want to
> try to find the best methods.
I couldn't agree more. Which is why I think it's pointless worrying about
whether a brute force approach is O(n) or O(n^2) or somewhere in between --
to be at all practical, we need to find an algorithm _better_ than O(n)
(or prove that none exists). We obviously can't calculate and store the
equity of every position in better than O(n) time and space (since there are
n positions, and we can't store one position without O(1) time and space),
but is there a way to find an optimal strategy _without_ all the equities?
That question's too hard for me, but I'm eager to listen if anybody else
has a good idea :-)