Author: Sune Fischer
Date: 14:13:29 01/18/02
Go up one level in this thread
On January 18, 2002 at 16:43:16, Dann Corbit wrote: >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 I should add a few factors to make it larger: Side to move: 2 En-passent: no idea, but less than 2 I guess Castle rights: can be ignored because the restrictions on king and rook will make this number magnitudes smaller. >>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. Hehe, this was the old: (64*(64 - 4)*62!)/((62 - 30)!*(8!*2!*2!*2*2)^2)= 1.1*10^42 capture a piece and turn a pawn into a queen: (64*(64 - 4)*62!)/((62 - 29)!*7!*8!*2!(2!*2!*2*2)^2)= 1.33*10^41 OK, so its about a factor 10 or maybe about same order of magnitude, they drop fairly quickly though. >Here is the table of numbers Uri's program dumps as it goes (which is the list >by category): I would like to know his approach ;) >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. I'm quite sure it is, unless someone can find a flaw in the product (which there could be of cause;) A number like 64 squares for the king is very optimistic, most of the squares will be attacked, you can't be in check if it isn't your turn, and you can't be in check by more than two pieces (right?) and so on, many rules that will diminish the final product. In particular the pawn movement, pawns have a rather limited number of squares they can go to, if just one pawn has half of 64 squares, then that is a factor 2 smaller yet. -S. >>>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.