Backgammon Theory

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?