Re: [Bug-gnubg] (OT) Position ID documentation

[Massimiliano Maini]

I've some python that computes the number of positions where both
players occupy no more than X
regular points (board points, 1..24).

The computation is a sophistication of W.Trice's one: you assume that
black occupies m regular points
(m being of course between 0 and you limit X) and you compute number
of positions for black checkers
in the same way as Walter. Then for white it's more complicate: you
can't use just D(26-m,15) as you
want to limit the number of occupied points, so you just do the same
reasoning you've just done for
black with the additional note that if black occupies m points, white
can't occupy more than the min
between X (your imposed limit), 15 (max # of checkers) and  24-m
(vacant points).

It turns out (if my computations are OK) that limiting black and white
to be holding no more than 11
regular points each, then the number of points is already less than 2^64.

Python output here below, code further below. I'm ashamed about the
naive implementation of Cnm,
but hey, it works and takes no time, screw efficiency  :)

MaX.


=========================================

C:\Documents and Settings\mmaini\Desktop\BG
posID>d:\python26\python.exe bgposid.py
TOT1: 18528584051601162496,1.852858e+19
TOT2: 18528584051601162496,1.852858e+19
0,0.000000e+00
False False
Lim,#Pos,in64
0,256,1
1,8041216,1
2,20822945536,1
3,9822623914496,1
4,1194790350513152,1
5,45681766196850176,1
6,629989668141016576,1
7,3551999654903397376,1
8,9550656424722482176,1
9,15092292700890794496,1
10,17700293897831133696,1
11,18404277853614314496,1
12,18517676380201988096,0
13,18528090608482589696,0
14,18528575503767612416,0
15,18528584051601162496,0

=========================================

import math;

def Cnm(n,m):
        return 
(math.factorial(long(n))/(math.factorial(long(m))*math.factorial(long(n-m))))

def Dnm(n,m):
        return Cnm(long(n+m-1),long(m))


def BlackOnM(m):
        # Black occupies m regular points (board points, 0..24).
        T1 = Cnm(24,m)
        # The remaining 15-m black checkers are distributed over
        # the occupied m points + the bar and the off (m+2 points).     
        T2 = Dnm(m+2,15-m)
        # The 15 whie checkers are distributed over the 24-m
        # available regular points, plus the bar and the off (26-m).
        T3 = Dnm(26-m,15)
        return long(T1*T2*T3)
        
def BlackOnM_WithLim(m,lim):
        # Black occupies m regular points (board points, 0..24).
        T1 = Cnm(24,m)
        # The remaining 15-m black checkers are distributed over
        # the occupied m points + the bar and the off (m+2 points).     
        T2 = Dnm(m+2,15-m)
        # White can occupy a number of points that is the minimum
        # between 15 (number of checkers), 24-m (points left vacant
        # by black) and lim (self-imposed limit).
        T3 = 0
        for p in range(0,min(lim,15,24-m)+1):
                # White occupies p regular points out of the available 24-m.
                T31 = Cnm(24-m,p)
                # The remaining 15-p white checkers are distributed over
                # the occupied p points + the bar and the off (m+2 points).
                T32 = Dnm(p+2,15-p)
                T3 += T31*T32
        return long(T1*T2*T3)


def TotPos():
        Tot = 0
        for M in range(0,16):
                Bm = BlackOnM(M)
                Tot += Bm
        return Tot

def TotPos_WithLim(lim):
        Tot = 0
        for M in range(0,lim+1):
                BmL = BlackOnM_WithLim(M,lim)
                Tot += BmL
        return Tot


# Sanity check :)
TOT1 = TotPos()
TOT2 = TotPos_WithLim(15)
print 'TOT1: %d,%e' % (TOT1,TOT1)
print 'TOT2: %d,%e' % (TOT2,TOT2)
print '%d,%e' % (TOT1-TOT2,TOT1-TOT2)
print TOT1<(pow(2,64)), TOT2<(pow(2,64))

# Iterate on Lim.
print 'Lim,#Pos,in64'
for lim in range(0,16):
        NP = TotPos_WithLim(lim)
        print '%d,%d,%d' % (lim,NP,NP<pow(2,64))


=========================================