Author: Dieter Buerssner
Date: 05:32:47 03/03/05
Go up one level in this thread
I can beat it by almost 3 bits rather easily. Using your idea of encoding the castling rights in the K square, and reasoning given in other messages of this thread. First the positions without ep: 2*15^8*23^2*22^2*50*51*42!/(32!*2^4) = 1,116,831,790,908,041,696,550,562,500,000,000 = ~1.12e33 And now the positions with ep. We define 14 ep states. For example for white to move state 1 could mean. wPa5, bPb5, state 2 wPb5, bPa5, state 3 wPb5, bPc5, etc. So 2 pawns are already set, by one of the 14 states. The two other pawns on these 2 files have 2*6 possibilities. So the pawn part of the above formula becomes 14*2*6*15^6. Now the 16 pawns occupy practically 18 squares (because one pawn must have just done a double step, making 2 additional squares unavailable for the other men). This now gives 2*15^6*14*2*6*22^2*21^2*48*49*40!/(30!*2^4) 369,379,773,635,426,085,230,899,200,000,000 = ~3.7e32 Adding both numbers together we get 1.49e33 = ~2^110.195 One can of course still reduce this number. For example, the scheme will count positions with both Ks on neighboring squares. With some effort, this could be avoided at least for parts of the positions. Perhaps also something like Eugene Nalimov's idea for getting rid of unblockable checks could be used in a more complicated enumeration scheme. Getting down to 100 bits looks difficult, however. One could try some sort of Monte Carlo integration, to estimate the number of legal positions. However this might not be easy. Practically, one could only look at every 1e20th position or so. Regards, Dieter PS. I think, I was too fast, to call my first idea for encoding the ep-square wrong.
This page took 0 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.