Total Possible Possition
cma...@nospam.ix.netcom.com
I'm new to backgammon, and was wondering if anyone has figured out
these numbers.
I calculate only 54,264 possible positions with 15 or fewer checkers
on the last 6 rows. This is a very small number, so is there a table
showing all the expected probilities for bearing off?
Also, what is the total number of possible legal positions? My quick
guesstimate is on the order of 10^10. It seems very small compared to
chess or go, so has this game already been 'solved' by computers yet?
Thanks for any info,
Chris
Daniel Murphy
On Tue, 17 Jun 1997 09:52:57 GMT, cma...@NOSPAM.ix.netcom.com wrote:
>I'm new to backgammon, and was wondering if anyone has figured out
>these numbers.
>I calculate only 54,264 possible positions with 15 or fewer checkers
>on the last 6 rows. This is a very small number, so is there a table
>showing all the expected probilities for bearing off?
I think you miscounted. See, for example, the rec.games.backgammon FAQ
section about Hugh Sconyer's bearoff program at
http://www.cybercom.net/~damish/backgammon/bg-faq.html#sw_sconyer_cd
Or see the WWW Backgammon Page at
http://www.statslab.cam.ac.uk/~sret1/backgammon/#Programs for more
references.
>Also, what is the total number of possible legal positions? My quick
>guesstimate is on the order of 10^10. It seems very small compared to
>chess or go, so has this game already been 'solved' by computers yet?
No it hasn't. For one thing, your guesstimate is off by about
99,999,999,990,000,000,000.
See Michael Zehr's article "Why is it so hard to write a good
backgammon program" in the rec.games.backgammon FAQ at
http://www.cybercom.net/~damish/backgammon/bg-faq.html#why_hard.
Or follow the links from the WWW Backgammon Page to a discussion about
TD-Gammon and to Gerry Tesauro's article "Temporal Difference Learning
and TD-Gammon."
Or see several references to programming backgamon at Backgammon
Galore, http://www.bkgm.com/.
______________________________________________________________________
Daniel Murphy San Francisco, California rac...@cityraccoon.com
Online Backgammon:
http://www.fibs.com, telnet fibs.com 4321
In San Francisco, monthly tourneys, annotated games:
http://www.backgammon.org/bgbg/
Brian Sheppard
Daniel Murphy <rac...@cityraccoon.com> wrote in article
<33a676a3....@nntp.best.com>...
> On Tue, 17 Jun 1997 09:52:57 GMT, cma...@NOSPAM.ix.netcom.com wrote:
>
> >I calculate only 54,264 possible positions with 15 or fewer checkers
> >on the last 6 rows. This is a very small number, so is there a table
> >showing all the expected probilities for bearing off?
>
> I think you miscounted. See, for example, the rec.games.backgammon FAQ
54,264 is the correct answer. It is possible to build a table of bearoff
expectations by completely enumerating bearoff positions. However, you
have to define a "best move" that is independent of the opponent's
position. That is, the "best move" must be the move that results in the
lowest expected number of rolls for bearing off.
Hugh Sconyers has created a *complete* bearoff database for certain
classes of positions. In this database the best move is defined by
maximizing the chance of defeating the opponent given his actual
board configuration. This is a much more massive database.
> >Also, what is the total number of possible legal positions? My quick
> >guesstimate is on the order of 10^10. It seems very small compared to
> >chess or go, so has this game already been 'solved' by computers yet?
>
> No it hasn't. For one thing, your guesstimate is off by about
> 99,999,999,990,000,000,000.
I think you counted only the number of configurations for one side's
men. The conventional answer is 10^20.
Brian
Phill Skelton
cma...@NOSPAM.ix.netcom.com wrote:
>
> I'm new to backgammon, and was wondering if anyone has figured out
> these numbers.
> on the last 6 rows. This is a very small number, so is there a table
> showing all the expected probilities for bearing off?
54,264? Surely it is 6^15 = 4.7E11 possible positions, which is a hell
pf a lot (more than you seem to think exist in the entire game)
> Also, what is the total number of possible legal positions? My quick
> guesstimate is on the order of 10^10. It seems very small compared to
> chess or go, so has this game already been 'solved' by computers yet?
> Thanks for any info,
> Chris
My quick quesstimate is 1E35 or so (i.e. 10^35), and there is no
way that this has been 'solved' by any comuter yet. I may be a factor
of a million or so out here, but it is still vastly more than your
numbers. How did you come up with them?
(My estimate is based on the assumption that all 15 checkers of one
player can each be on 26 different points (as a rough approx) -
that's 26^15 permutations straight away, though with some duplication
- so make it a factor of a hundred less; 1.7E19
Then the other player typically has ~15 points on which to place
pieces (on average there will be 4 points with more than one man on, so
only 11 points are unavailable to player 2) This leaves, after allowing
for duplication, 4E15 different permutations. Hence ~10^35 total
possible board positions.)
Phill
steen ladelund
In <01bc7b30$ea9dad60$3ac032cf@polaris> "Brian Sheppard" <bri...@mstone.com> writes:
>Daniel Murphy <rac...@cityraccoon.com> wrote in article
><33a676a3....@nntp.best.com>...
>> On Tue, 17 Jun 1997 09:52:57 GMT, cma...@NOSPAM.ix.netcom.com wrote:
>>
>> >I calculate only 54,264 possible positions with 15 or fewer checkers
>> >on the last 6 rows. This is a very small number, so is there a table
>> >showing all the expected probilities for bearing off?
>>
>> I think you miscounted. See, for example, the rec.games.backgammon FAQ
>> section about Hugh Sconyer's bearoff program.
>54,264 is the correct answer. It is possible to build a table of bearoff
>expectations by completely enumerating bearoff positions. However, you
>have to define a "best move" that is independent of the opponent's
>position. That is, the "best move" must be the move that results in the
>lowest expected number of rolls for bearing off.
>Hugh Sconyers has created a *complete* bearoff database for certain
>classes of positions. In this database the best move is defined by
>maximizing the chance of defeating the opponent given his actual
>board configuration. This is a much more massive database.
Would there be any problems in basing such a database on eqitys, and so
include cube dynamics? It seems to me that it should be possible to write
an algoritme calculating this, but perhaps it would be to lenghty, or the
database to big or..................???
Would anyone know just what Hugh actually did ??
>> >Also, what is the total number of possible legal positions? My quick
>> >guesstimate is on the order of 10^10. It seems very small compared to
>> >chess or go, so has this game already been 'solved' by computers yet?
>>
Walter G Trice
In rec.games.backgammon you write:
>I'm new to backgammon, and was wondering if anyone has figured out
>these numbers.
>I calculate only 54,264 possible positions with 15 or fewer checkers
>on the last 6 rows.
Correct.
> This is a very small number, so is there a table
> showing all the expected probilities for bearing off?
Yes. Lots of people have done this, e.g. Hal Heinrich more than
10 years ago. A one-sided table with 54264 records gives you the
probabilities of bearing off in N rolls, N=1,2,3,..., subject to
some assumption about checker play (usually that you play to
minimize mean rolls to bear off.) From these numbers you can
compute the probability of winning a 2-sided position given
the checker-play assumption.
There are also 2-sided tables for subsets of the 54264 X 54264 positions
that give exact equities taking the cube into account. E. g., the
Sconyers database.
>Also, what is the total number of possible legal positions? My quick
>guesstimate is on the order of 10^10.
Actually, it's 18,528,584,051,601,162,496. This is still a rather
small number -- smaller by several orders of magnitude, for instance,
than the total number of stars in the universe. If you can get the
54264 number you can calculate this one by an extension of the
same method. In brief...
C(n,m) = n!/(m!(n-m)!) = number of ways to select m objects from
a set of n.
D(n,m) = C(n+m-1,m) = # ways to distribute m checkers of the same
color over n points.
E. g., D(15,7) = C(21,15) = 54264.
Suppose Black occupies m of the 24 regular points. There are
C(24,m) ways to select the points. This accounts for m checkers.
The other 15-m can be on any of the m selected points OR on the
bar or off, so the number of ways to distribute them is D(m+2,15-m).
The White checkers have 26-m places left to go, so they can be
distributed in D(26-m,15) ways.
So putting it all together you sum
C(24,m) X D(m+2,15-m) X D(26-m,15)
over all values of m from 0 to 15, and get
18,528,584,051,601,162,496, assuming the programming language
you use can handle big integers.
>It seems very small compared to
>chess or go, so has this game already been 'solved' by computers yet?
No, but a reduced version of backgammon with only 3 checkers for
each side was solved by a Hugh Sconyers program.
-- Walter Trice
cma...@nospam.ix.netcom.com
On Tue, 17 Jun 1997 18:01:00 GMT, w...@world.std.com (Walter G Trice)
wrote:
Thank you very much! This answer was much more than I was expecting.
I actually wrote a computer program to recursively enumerate each
possibility. The 54264 came out instantly, an the ~10^10 came an hour
later with round off error. You were right in thay I only computed it
for 1 side's men. Squaring gives Brian's answer if you allow 2 colors
on a spot, so reduction by 100 (2^8 or so, where 8 is an average # of
spots covered by white) gives close to your answer.
The real formulas are great to have!!!
I thought about the 54264^2 tables, and now agree that you need them
for perfect play. Minimizing to, say, 3.1 rolls isn't as good as
really needing to try for 3.0 in certain positions, so increasing the
P for 3.0 at the expense of a higher P at 4.0 is a better strategy
than not knowing what your oppnent is doing.
Its nice to know the Sconyers database already has done this. I will
search for it on the net if it is freely available somewhere.
Chris
Chuck Bower
In article <EBxM1...@world.std.com>, (snip)
>
>>..., what is the total number of possible legal positions? My quick
>>guesstimate is on the order of 10^10.
>
>Actually, it's 18,528,584,051,601,162,496. This is still a rather
>small number -- smaller by several orders of magnitude, for instance,
>than the total number of stars in the universe.
(snip lots of good probability stuff)
Without checking your math (I'm lazy today), I'll believe your
"possible legal positions" number--1.85e19. Your astrophysics comment,
though, may be a bit off, depending on how you define "several". A
simple BoE calculation comes up with 10e21 stars in the visible
universe (by taking the volume--within 10^15 light years--times the
density and dividing by the mass of a typical star). Of course, if you
counted all of them, I may have to rescind...
Chuck
bo...@bigbang.astro.indiana.edu
c_ray on FIBS
Chuck Bower
In article <5o71n3$fa$1...@dismay.ucs.indiana.edu>,
Chuck Bower <bo...@bigbang.astro.indiana.edu> wrote:
>simple BoE calculation comes up with 10e21 stars in the visible universe
Oops. I meant 1e21, although the error bars would probably include
this answer...
Chuck
bob koca
wg...@world.std.com (Walter G Trice)
>wrote:
...
...
>>Also, what is the total number of possible legal positions? My quick
>>>guesstimate is on the order of 10^10.
>>
>>Actually, it's 18,528,584,051,601,162,496. This is still a rather
>>small number -- smaller by several orders of magnitude, for instance,
>>than the total number of stars in the universe. If you can get the
>>54264 number you can calculate this one by an extension of the
>>same method. In brief...
>>
>> C(n,m) = n!/(m!(n-m)!) = number of ways to select m objects from
>> a set of n.
>>
>> D(n,m) = C(n+m-1,m) = # ways to distribute m checkers of the same
>> color over n points.
>>
>> E. g., D(15,7) = C(21,15) = 54264.
>>
>> Suppose Black occupies m of the 24 regular points. There are
>> C(24,m) ways to select the points. This accounts for m checkers.
>> The other 15-m can be on any of the m selected points OR on the
>> bar or off, so the number of ways to distribute them is D(m+2,15-m).
>> The White checkers have 26-m places left to go, so they can be
>> distributed in D(26-m,15) ways.
>>
>> So putting it all together you sum
>>
>> C(24,m) X D(m+2,15-m) X D(26-m,15)
>>
>> over all values of m from 0 to 15, and get
>>
>> 18,528,584,051,601,162,496, assuming the programming language
>> you use can handle big integers.
...
-- Walter Trice
If you mean by legal position, one which can be attained by legal
moves, then you have gotten the order of magnitude but haven't
gotten the exact number right. A lot of the positions you count could
not occur. I would multiply by two though, ignoring the
cube, I consider who is on turn part of the checker position.
A few examples are more than 15 total checkers on the bar, more
than 4 checkers on the bar when opponent has no checkers in inner
board, having 15 checkers on the same point when opponent has
a 6 "blot prime" before it and is on turn. There are too many cases
and it would be very tricky to cast these out. Too tricky I think for
anyone to calculate the exact number.
The interesting question to me now is "What percent of positions
generated by Trice's method need to be thrown out?"
I am going to take a wild guess and say about 1 in 100,000.
,Bob Koca
bobk on FIBS
BobKoca on GG
Walter G Trice
bo...@bigbang.astro.indiana.edu (Chuck Bower) writes:
>In article <EBxM1...@world.std.com>,
>Walter G Trice <w...@world.std.com> wrote:
[...]
> Without checking your math (I'm lazy today), I'll believe your
>"possible legal positions" number--1.85e19. Your astrophysics comment,
>though, may be a bit off, depending on how you define "several".
"more than two but fewer than many" (Merriam-Webster's Collegiate
Dictionary -- 10th ed.)
> A
>simple BoE calculation comes up with 10e21 stars in the visible
>universe (by taking the volume--within 10^15 light years--times the
>density and dividing by the mass of a typical star). Of course, if you
>counted all of them, I may have to rescind...
log(10e21/(1.85e19)) = 2.73, which seems to be more than 2. I guess
it depends on how you define "many." :)
W. Trice
bob koca
ko...@bobrae.bd.psu.edu (bob koca) wrote:
> If you mean by legal position, one which can be attained by legal
>moves, then you have gotten the order of magnitude but haven't
>gotten the exact number right. A lot of the positions you count could
>not occur. I would multiply by two though, ignoring the
>cube, I consider who is on turn part of the checker position.
Oops, I need to retract the multiply by 2 comment. Since already
identified players as black and white may as well assume black
is on roll.
,Bob Koca