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

[bgnj]

Øystein Johansen wrote:
> 
> Let's first try to get the number of legal positions below 2^64. The
> difference is "only" 8.190836056001331E+16 positions. I could divide this
> differently into contact and non-contact positions.
> 

This is an interesting problem.  I counted all the non-contact positions in
order to see if that would get the number of positions down to 64 bits but
unfortunately it did not.  Here was my methodology:

1) Assume no pieces are on the bar for a non-contact position.

2) Let player 1 occupy M points on the board (not including the bearoff
tray).  Therefore player 1 has one checker on point M, and 14 other checkers
spread across M+1 places (including the bearoff tray).  Note that if M=0,
this means that all of player 1's checkers are in the bearoff tray.  The
number of combinations for player 1's checkers is: M+14 C 14

3) Player 2 therefore has 15 checkers spread across 25-M places (including
the bearoff tray).  The number of combinations for player 2 is: 39-M C 15

4) The number of total combinations for a given M is: (M+14 C 14) *  (39-M C
15)

5) Compute the total sum for M=0..24

The final result was 1.4E+15, which is far short of the 8.2E+16 positions
that would be needed.  I've included the complete program output below for
those who are interested.


Massimiliano Maini-3 wrote:
> 
> According to rough calculations (excel not having big integers),
> all the positions where black occupies 10 or less (regular)  points are
> already less than 2^64.
> 

I wrote a little program to compute the number of positions up to each m.  I
discovered that Massimiliano was exactly correct.  When m=10, the number of
positions is less than 2^64 (1.811E+16 vs 1.845E+16).  But when m=11, the
number of positions is too large (1.847E+16).  Again, complete program
output is below.

- BGNJ

----------------------------

Calculation of non-contact positions:

M=0, P1=1, P2=25140840660, P1*P2=25140840660, total=25140840660
M=1, P1=15, P2=15471286560, P1*P2=232069298400, total=257210139060
M=2, P1=120, P2=9364199760, P1*P2=1123703971200, total=1380914110260
M=3, P1=680, P2=5567902560, P1*P2=3786173740800, total=5167087851060
M=4, P1=3060, P2=3247943160, P1*P2=9938706069600, total=15105793920660
M=5, P1=11628, P2=1855967520, P1*P2=21581190322560, total=36686984243220
M=6, P1=38760, P2=1037158320, P1*P2=40200256483200, total=76887240726420
M=7, P1=116280, P2=565722720, P1*P2=65782237881600, total=142669478608020
M=8, P1=319770, P2=300540195, P1*P2=96103738155150, total=238773216763170
M=9, P1=817190, P2=155117520, P1*P2=126760486168800, total=365533702931970
M=10, P1=1961256, P2=77558760, P1*P2=152112583402560, total=517646286334530
M=11, P1=4457400, P2=37442160, P1*P2=166894683984000, total=684540970318530
M=12, P1=9657700, P2=17383860, P1*P2=167888104722000, total=852429075040530
M=13, P1=20058300, P2=7726160, P1*P2=154973635128000, total=1007402710168530
M=14, P1=40116600, P2=3268760, P1*P2=131131537416000, total=1138534247584530
M=15, P1=77558760, P2=1307504, P1*P2=101408388935040, total=1239942636519570
M=16, P1=145422675, P2=490314, P1*P2=71302773469950, total=1311245409989520
M=17, P1=265182525, P2=170544, P1*P2=45225288543600, total=1356470698533120
M=18, P1=471435600, P2=54264, P1*P2=25581981398400, total=1382052679931520
M=19, P1=818809200, P2=15504, P1*P2=12694817836800, total=1394747497768320
M=20, P1=1391975640, P2=3876, P1*P2=5395297580640, total=1400142795348960
M=21, P1=2319959400, P2=816, P1*P2=1893086870400, total=1402035882219360
M=22, P1=3796297200, P2=136, P1*P2=516296419200, total=1402552178638560
M=23, P1=6107086800, P2=16, P1*P2=97713388800, total=1402649892027360
M=24, P1=9669554100, P2=1, P1*P2=9669554100, total=1402659561581460

------------------------------

Calculation of positions for each m:

C = C(24,m)
D1 = D(m+2,15-m)
D2 = D(26-m,15)
pos = C * D1 * D2

m=0: C=1, D1=16, D2=40225345056, pos=643605520896, total=643605520896
m=1: C=24, D1=120, D2=25140840660, pos=72405621100800, total=73049226621696
m=2: C=276, D1=560, D2=15471286560, pos=2391242050713600,
total=2464291277335296
m=3: C=2024, D1=1820, D2=9364199760, pos=34494715371916800,
total=36959006649252096
m=4: C=10626, D1=4368, D2=5567902560, pos=258430678407982080,
total=295389685057234176
m=5: C=42504, D1=8008, D2=3247943160, pos=1105509013189701120,
total=1400898698246935296
m=6: C=134596, D1=11440, D2=1855967520, pos=2857778401442764800,
total=4258677099689700096
m=7: C=346104, D1=12870, D2=1037158320, pos=4619874957794553600,
total=8878552057484253696
m=8: C=735471, D1=11440, D2=565722720, pos=4759871168636812800,
total=13638423226121066496
m=9: C=1307504, D1=8008, D2=300540195, pos=3146803717043226240,
total=16785226943164292736
m=10: C=1961256, D1=4368, D2=155117520, pos=1328855528604764160,
total=18114082471769056896
m=11: C=2496144, D1=1820, D2=77558760, pos=352348056827020800,
total=18466430528596077696
m=12: C=2704156, D1=560, D2=37442160, pos=56699687305497600,
total=18523130215901575296
m=13: C=2496144, D1=120, D2=17383860, pos=5207114140300800,
total=1852833733041876096
m=14: C=1961256, D1=16, D2=7726160, pos=242447642511360,
total=18528579777684387456
m=15: C=1307504, D1=1, D2=3268760, pos=4273916775040,
total=18528584051601162496




-- 
View this message in context: 
http://old.nabble.com/Re%3A-%28OT%29-Position-ID-documentation-tp28666843p28719539.html
Sent from the Gnu - Backgammon mailing list archive at Nabble.com.