Ø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. _______________________________________________ Bug-gnubg mailing list [email protected] http://lists.gnu.org/mailman/listinfo/bug-gnubg
