Theory

Forum Archive : Theory

 Number of distinct positions

 From: Walter Trice Address: wgt@world.std.com Date: 17 June 1997 Subject: Re: Total Possible Possition Forum: rec.games.backgammon Google: EBxM1o.Hu6@world.std.com

```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(7,15) = 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
```

 Did you find the information in this article useful?           Do you have any comments you'd like to add?

### Theory

Derivation of drop points  (Michael J. Zehr, Apr 1998)
Double/take/drop rates  (Gary Wong, June 1999)
Drop rate on initial doubles  (Gary Wong, July 1998)
Error rate--Why count forced moves?  (Ian Shaw+, Apr 2009)
Error rates--Repeated ND errors  (Joe Russell+, July 2009)
Inconsistencies in how EMG equity is calculated  (Jeremy Bagai, Nov 2007)
Janowski's formulas  (Joern Thyssen+, Aug 2000)
Janowski's formulas  (Stig Eide, Sept 1999)
Jump Model for money game cube decisions  (Mark Higgins+, Mar 2012)
Number of distinct positions  (Walter Trice, June 1997)
Number of no-contact positions  (Darse Billings+, Mar 2004)
Optimal strategy?  (Gary Wong, July 1998)
Proof that backgammon terminates  (Robert Koca+, May 1994)
Solvability of backgammon  (Gary Wong, June 1998)
Undefined equity  (Paul Tanenbaum+, Aug 1997)
Under-doubling dice  (Bill Taylor, Dec 1997)
Variance reduction  (Oliver Riordan, July 2003)

 From GammOnLine         Long message         Recommended reading         Recent addition

 Book Suggestions Books Cheating Chouettes Computer Dice Cube Handling Cube Handling in Races Equipment Etiquette Extreme Gammon Fun and frustration GNU Backgammon History Jellyfish Learning Luck versus Skill Magazines & E-zines Match Archives Match Equities Match Play Match Play at 2-away/2-away Miscellaneous Opening Rolls Pip Counting Play Sites Probability and Statistics Programming Propositions Puzzles Ratings Rollouts Rules Rulings Snowie Software Source Code Strategy--Backgames Strategy--Bearing Off Strategy--Checker play Terminology Theory Tournaments Uncategorized Variations

Return to:  Backgammon Galore : Forum Archive Main Page