Darse Billings writes:
Thanks, Tom. That is exactly the number I got.
This came up in a dinner conversation with
Gerry Tesauro and Michael Buro last week, both of whom have done
some excellent work in computer backgammon (Gerry is famous for
TD_Gammon, which brought the super strong neural net programs
(like Jellyfish and Snowie) into the world).
1.4 quadrillion isn't that big a number any more -- definitely
in the feasible range sometime in the future. The Awari oracle
(an endgame database that covers every reachable position in the
game!) is a little under a trillion positions, and the 10-piece
checkers endgame database has more than 39 trillion positions.
Building the database would reveal unreachable positions, if
there are any. But it isn't clear that it would offer enough
value to be worth building, because the equity assessments for
race positions can be estimated quite accurately by others means.
Here is my solution, and a python script to do the arbitrary
precision counting:
Define On(n,r) to be the number of ways of putting exactly
n checkers on r possibly empty points. This can be done in
On(n,r) = choose(n+r-1, r-1) ways.
Define Onf(n,r) to be the number of ways of putting n or fewer
checkers on r possibly empty points. This is the sum of On(i,r)
for i = 0..n. Due to a convenient binomial identity, this is
Onf(n,r) = On(n,r+1) = choose(n+r, r). For example, the number
of ways of putting 15 or fewer pieces on 6 possibly empty points
is equal to the number of ways of putting exactly 15 pieces on
7 possibly empty points. (This makes sense if we imagine that
the other 15-i pieces are being placed on the (r+1)th point).
I will partition the space into subcases according to the maximum
point for the white checker farthest from home. Call this point
j (in the range 1..23).
Since the maximum point has at least one white checker, the total
number of white positions is the sum over i = 1..15 of putting
the remaining 15-i or fewer checkers on the lower points, which
is Onf(15-i,j-1). Owing to the same binomial identity, this turns
out to be equal to Onf(15,j) - Onf(15,j-1). (This makes sense,
since the number of ways of leaving the max point empty is equal
to the number of ways of putting 15 or fewer checkers over the
lower points).
The number of corresponding black positions is less constrained,
essentially Onf(n,r) for the non-white points, r = 24-j. We need
to subtract one from this, because we don't want to include the
position with zero black pieces (we want at least one checker of
each colour for non-terminal positions). Thus Onf(15,24-j) - 1.
The sum of these products is the number of checker positions
with white to move (just flip the position if black is to move).
A mere 1,402,609,279,900,141 (1.4 quadrillion) positions.
The following python script produces the given output (after
cleaning it up a bit). (Thanks to Roel van der Goot for the
python tips).
-=-=-
#!/bin/env python
def choose(n, r):
c = 1L
for k in range(min(r, n-r)):
c = c * (n-k) / (k+1)
return c
def on(n, r):
# n pieces on r possibly empty points
return choose(n+r-1, r-1)
def onf(n, r):
# n or fewer pieces on r possibly empty points
# equals n pieces on r+1 possibly empty points
return choose(n+r, r)
tp = 0L
for j in range(1, 24):
pw = onf(15,j) - onf(15,j-1)
pb = onf(15,24-j) - 1
pj = pw * pb
tp = tp + pj
print pj, "=", pw, "*", pb, "split at max point", j
print tp, "total no-contact checker positions in backgammon"
-=-=-
232069298385 = 15 * 15471286559 split at max point 1
1123703971080 = 120 * 9364199759 split at max point 2
3786173740120 = 680 * 5567902559 split at max point 3
9938706066540 = 3060 * 3247943159 split at max point 4
21581190310932 = 11628 * 1855967519 split at max point 5
40200256444440 = 38760 * 1037158319 split at max point 6
65782237765320 = 116280 * 565722719 split at max point 7
96103737835380 = 319770 * 300540194 split at max point 8
126760485351610 = 817190 * 155117519 split at max point 9
152112581441304 = 1961256 * 77558759 split at max point 10
166894679526600 = 4457400 * 37442159 split at max point 11
167888095064300 = 9657700 * 17383859 split at max point 12
154973615069700 = 20058300 * 7726159 split at max point 13
131131497299400 = 40116600 * 3268759 split at max point 14
101408311376280 = 77558760 * 1307503 split at max point 15
71302628047275 = 145422675 * 490313 split at max point 16
45225023361075 = 265182525 * 170543 split at max point 17
25581509962800 = 471435600 * 54263 split at max point 18
12693999027600 = 818809200 * 15503 split at max point 19
5393905605000 = 1391975640 * 3875 split at max point 20
1890766911000 = 2319959400 * 815 split at max point 21
512500122000 = 3796297200 * 135 split at max point 22
91606302000 = 6107086800 * 15 split at max point 23
1402609279900141 total no-contact checker positions in backgammon
|