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)  [GammOnLine forum]
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)  [Recommended reading]
Solvability of backgammon  (Gary Wong, June 1998) 
Undefined equity  (Paul Tanenbaum+, Aug 1997)  [Recommended reading]
Under-doubling dice  (Bill Taylor, Dec 1997)  [Recommended reading]
Variance reduction  (Oliver Riordan, July 2003)  [Long message]

[GammOnLine forum]  From GammOnLine       [Long message]  Long message       [Recommended reading]  Recommended reading       [Recent addition]  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