Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

10 views

Skip to first unread message

Jun 17, 1997, 3:00:00 AM6/17/97

to

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

Jun 17, 1997, 3:00:00 AM6/17/97

to

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/

Jun 17, 1997, 3:00:00 AM6/17/97

to

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

Jun 17, 1997, 3:00:00 AM6/17/97

to

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?

> 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

Jun 17, 1997, 3:00:00 AM6/17/97

to

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?

>>

Jun 17, 1997, 3:00:00 AM6/17/97

to

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

Jun 17, 1997, 3:00:00 AM6/17/97

to

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

Jun 17, 1997, 3:00:00 AM6/17/97

to

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

Jun 17, 1997, 3:00:00 AM6/17/97

to

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

Jun 19, 1997, 3:00:00 AM6/19/97

to

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

Jun 19, 1997, 3:00:00 AM6/19/97

to

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

Jun 20, 1997, 3:00:00 AM6/20/97

to

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

0 new messages

Search

Clear search

Close search

Google apps

Main menu