Author: KarinsDad
Date: 11:11:26 10/31/99
Go up one level in this thread
On October 31, 1999 at 11:07:26, KarinsDad wrote: [snip] > >No, this is incorrect. The reason is simple enough. Since the 2 kings take up 2 >squares, that leaves approximately 62 squares for the a1 rook, 61 squares for >the h1 rook, 60 squares for the a8 rook, and 59 squares for the h8 rook. >Dropping illegal positions for the moment, that results in 13388280 or just >under 24 bits for the rooks or 6 bits per rook. > >Let's do the real math: > >Method 1: >12 bits for kings and castling >4.33 bits for rooks * 4 rooks (this includes color and position) >= 29.33 bits > >Method 2: >12 bits for kings and castling >5 bits for rooks * 4 rooks (this includes color and position when we cannot get >away with a minor piece compression, i.e. many pawns) >= 32 bits > >Note: Method 1 and 2 are the methods I use, depending on which one compresses >more (with a lot of pawns, the second method actually compresses better). > >Method 3 (your method, note: white here will be side to move, so I will do >reductions for illegal white rooks): > >240 (black king in corner 4 * 60, no castling) * 62 black rook * 61 black rook * >58 (reduced from 60 since the white rook cannot be right next to the black king >since it is white to move) white rook * 57 white rook = 3000790080 > >1392 (black king on edge 24 * 58, no castling) * 62 black rook * 61 black rook * >57 (reduced from 60 since the white rook cannot be right next to the black king >since it is white to move) white rook * 56 white rook = 16804424448 > >1980 (black king in interior 36 * 55, no castling) * 62 black rook * 61 black >rook * 56 (reduced from 60 since the white rook cannot be right next to the >black king since it is white to move) white rook * 55 white rook = 23064148800 > >56 (white king on e1, queenside castling, black king cannot be next to white >rook) * 61 black rook * 60 black rook * 59 (not going to do a reduction here >since this value does not greatly impact the final result and this entire >portion of the equation would have to be broken down to the 3 possibilities of >black king in corner, on edge, and in interior) white rook = 12092640 > >56 (white king on e1, kingside castling) * 61 * 60 * 59 = 12092640 > >54 (white king on e1, both side castling) * 60 * 59 = 191160 > >56 (black king on e8, queenside castling) * 61 * 60 * 59 = 12092640 > >56 (black king on e8, kingside castling) * 61 * 60 * 59 = 12092640 > >54 (black king on e8, both side castling) * 60 * 59 = 191160 > >(both kings on start squares, both sides can castle to at least one side) = >approximately 12101 > >3000790080 + 16804424448 + 23064148800 + 12092640 + 12092640 + 191160 + 12092640 >+ 12092640 + 191160 + 12101 = 4.29e10 or just under 36 bits. This is similar to >the approximate result I indicated above with 12 bits for the kings and 24 bits >for the rooks. At most, the illegal position reductions could drop 1 bit (from >36 bits down to 35 bits), but as was shown, they did not even do that (it >dropped about a half bit). > >As can be seen, the other two methods save considerably (4 to 6+ bits) over >including rook positions in with the king positions. The main reason for this is >that it takes fewer bits to store a position as a "location bitmap and a type of >piece per location" (5+ bits per piece) than it does the nearly 6 bits per piece >in a "store each piece via location" method. > Although the idea behind what I wrote here is correct, the numbers are incorrect. I forgot that the rooks are duplicate pieces, hence, you would have approximately half as many positions. This would drop the entire thing from 36 bits to 35 bits. It's still greater than the 29.33 or the 32 bits of the other two methods. And, it's also considerably more difficult to enumerate. KarinsDad :)
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.