counting no-contact positions
Darse Billings
in backgammon (and boy, are my fingers tired:).
The calculation isn't too difficult, but I would like someone
to provide an independent verification. Specifically, we are
looking for the exact number of no-contact checker positions
with at least one checker of each colour (in other words, all
unfinished pure race positions).
If you prefer to e-mail me privately instead of posting, put
"no-contact positions" in the subject (to get past SPAM filters)
and send to darse at cs.ualberta.ca . I will post my solution
after hearing agreement.
Bonus puzzle for discussion:
Are there any no-contact positions that are unreachable?
- Darse.
[no sig 965770017383859140260927990014116788809506430054263]
Tom Keith
> I have counted the exact number of no-contact checker positions
> someone to provide an independent verification. Specifically, we
> are looking for the exact number of no-contact checker positions
> with at least one checker of each colour (in other words, all
> unfinished pure race positions).
Hi Darse.
Let me give it a try.
Lemma: n checkers of a given color can be distributed on m consecutive
points in (n+m-1)!/(n!(m-1)!) ways. To see why, think of m-1 partitions
separating the m points and count the number of ways the m-1 partitions
and n checkers can be arranged.
Suppose White's highest checker is on the n-point. Then White's remaining
14 checkers are distributed on points 0 thru n. This can happen in
(14+n)!/(14!n!) ways. And Black's 15 checkers are distributed on his
points 0 thru 24-n. This can happen in (15+24-n)!/(15!(24-n)!) ways.
For n=1 to 24, the total number of distrubutions is
Sum from n=1 to 24 of (14+n)!/(14!n!) x (15+24-n)!/(15!(24-n)!)
= 1402634420740800
There are two other situations to deal with:
(n=0) All of White's checkers are off. Then Black's checkers can be on
the bar in addition to the 25 other points. That's (15+25)!/(15!25!) ways
= 40225345056.
(n=25) White has a checker on the bar. Then all of Black's checkers must
be off. White's remaining 14 checkers are distributed on points 0 thru 25,
in (14+25)!/(14!25!) ways = 15084504396.
Adding these up gives:
1402634420740800
40225345056
15084504396
----------------
1402689730590252
This includes positions where one side or the other (or both) have all
their checkers off. But you said you don't want to include those.
If one color has all their checkers off, then the other color's checkers
can be distributed in (15+25)!/(15!25!) ways = 40225345056. Subtract this
number twice (once for each color having all his checkers off), and add 1
back on so that both colors with all checkers off is not subtracted twice.
1402689730590252
- 40225345056
- 40225345056
+ 1
----------------
1402609279900141
Is that anywhere close to the number you got?
Tom
Darse Billings
>
> 1402609279900141
>
> Is that anywhere close to the number you got?
Thanks, Tom. That is exactly the number I got. The number is
embedded inside that strange sequence of digits at the end of
my original post (surrounded by some other values relevant to
the calculation).
>> [no sig 965770017383859140260927990014116788809506430054263]
9657700 17383859 1402609279900141 167888095064300 54263
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
-=-=-
As for the interesting puzzle question:
Are any no-contact backgammon positions unreachable?
Obviously the player to move makes a difference. For example,
white has 15 checkers on his one point, black covers the next
six points, and it's black to move: what was white's last move?
So we're really asking if there are any no-contact positions
that are unreachable for *either* player to move. I haven't
thought of any so far.
- Darse.
"Tom Keith" <t...@bkgm.com> wrote in message news:
David Brotherton
>
> Are there any no-contact positions that are unreachable?
I claim no. I think it would be nearly sufficient to show that all 23
positions with two stacks of 15 checkers "back-to-back" are reachable
(X has 15 men on his 1 point while O has 15 men on his 23 point would
be the 1st one, and has X 15 men on his 23 point while O has 15 men on
his 1 point would be the 23rd one). I say "nearly" because there may
be some non-contact positions not reachable from those 23 positions,
but I think those oddball positions would be ultimately reachable by
using "stragglers" that don't land exactly on the stack when contact
is finally broken.
David Brotherton
>
> Obviously the player to move makes a difference. For example,
> white has 15 checkers on his one point, black covers the next
> six points, and it's black to move: what was white's last move?
>
> So we're really asking if there are any no-contact positions
> that are unreachable for *either* player to move. I haven't
> thought of any so far.
Good point, and one I wasn't thinking of when I posted my earlier
reply (I could say I anticipated your amended question, but alas I did
not). But, I think my earlier reply is good for the amended question.
I suppose a fast enough computer could check all of the enumerated
positions for legality and prove it by brute force before the heat
death of the universe....or maybe not, given the size of the number
you found :)
Darse Billings
>
> I suppose a fast enough computer could check all of the enumerated
> positions for legality and prove it by brute force before the heat
> death of the universe....or maybe not, given the size of the number
> you found :)
Actually, that was the point of the counting exercise -- to see
if it would be feasible to construct an endgame database with
all race positions. 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.
- Darse.
happyjuggler0
> > Bonus puzzle for discussion:
> >
> > Are there any no-contact positions that are unreachable?
If o is on roll and x has all her checkers on her 1pt and o has 2
checkers each on x's 2,3,4,5,6,7 points with the 3 spares anywhere on
the board then that is impossible because x could not have made a
legal move last turn. The same holds true for all positions where x
has all 15 checkers on 1 point with a 6-prime directly behind them
with o on roll. Also if there are 14 checkers with the 15th being 1 or
2 pips forward (e.g. 14 on the 6pt and 1 on the 5 or 4pt) and also
with 13 on a point and the other 2 on the next point (e.g. 13 on the
6pt and 2 on the 5pt). All these positions are with the priming player
on roll. I will let someone else count how many positions that is. :)
happyjuggler0
Another example 13 on the 6pt and 3 on the 5pt with a 6-prime behind
it. Again,this does not have to be the 6pt and I have no intention
whatsoever of counting all the positions. The 3 spares are by
definition in non-contact positions by the way.