Author: Dann Corbit
Date: 13:43:16 01/18/02
Go up one level in this thread
On January 18, 2002 at 16:26:06, Sune Fischer wrote: >On January 18, 2002 at 15:12:07, Dann Corbit wrote: > >>Here is the numeric output of Uri's program: >>3.70106301211527e+046 >> >>Which would indicate (if I interpret it correctly) that there are _at most_ >>3.7e46 distinct positions in chess. > >That number is still on the large side, >a simple calculation can bring it under 10^43. > >32 pieces on the board: >(64*(64 - 4)*62!)/((62 - 30)!*(8!*2!*2!*2*2)^2)= 1.1*10^42 > >The factors are: >white king 64 squares >black king 64-4 squares (if white king in corner) >rest of the pieces: 62!/(62-30)! >white pawns can cycle: 8! >white knights can cycle: 2! >white rooks can cycle: 2! >white's white squared bishop half the board 2 >white's black squared bishop half the board 2 >square the last few factors since those are identical for black > >Now realize that the white pawns can only move from rank 2 to 6, this is >another huge factor that is not included in the above. > >Okay, now we shoud add the number of positions with 31 pieces and 30 and ... >down to the two kings. > >Each of those elements in the sum will be orders of magnitudes smaller than the >number above (right?), so they can be ignored. Smells like hand-waving. Remove one pawn. Orders of magnitude less? Maybe there are more, because of less possible illegal positions. And we must add 30 different categories on the way down to the two kings. Here is the table of numbers Uri's program dumps as it goes (which is the list by category): 4.032e3 2.374848e6 6.880214400000000000000000000000009e8 1.306895232e11 1.83055960128e13 2.016206442390528e15 1.818417385635256319999999999999996e17 1.380893388400877568000000000000001e19 9.010540386998363135999999999999998e20 5.130518388786255754079999999999999e22 2.580103899370081990144800000000002e24 1.157146570234186206637247999999991e26 4.665050555573374751447039519999997e27 1.701738256733824547675202479999978e29 5.647729008729626602595924112000034e30 1.713015152007927543806181498547170e32 4.765529886571048034261032746780865e33 1.219106133901038524050885920934012e35 2.871962662751699192209092270548780e36 6.231919751816264191522547640628490e37 1.244357903407170974320709795570276e39 2.281594693720326791719171567974781e40 3.829493388939728412381328835763312e41 5.858865030663834175346187587061709e42 8.123597887144719502376972389300728e43 1.008649695012244517310238532693819e45 9.453290062302758229325484949877637e45 2.181641888408481450289923085842070e46 4.580381943379412354171981385400221e45 6.436622548181210761121999267842181e43 2.139208232215563729772586138722192e40 With the grand total: 3.701063012120722292782714774208595e46 >I'm sure it could be proven to be less than 10^35 if one did more of those >considerations;) I'm sure that this number is *WAY* too optimistic. If it is less than 10^40 I will be utterly astonished. >>This indicates that a chess position could be encoded in at most 155 bits (if we >>were clever enough). >> >>Even at that, it's quite a pile of board positions. > >and then think of the number of possible games! ;) 5900 legal moves possible, approximately. Don't forget about all of those half-move clocks. I have the source for Uri's program. Maybe he would like to publish it and have it critiqued. I certainly would not reveal it without his permission, though. I ran this particular computation with Keith Briggs' doubledouble number class.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.