Author: Bruce Moreland
Date: 09:16:54 04/23/00
Go up one level in this thread
Did you guys ever determine an upper bound for this? I can't remember what happened last time we went through this. But I know that if you can count the legal positions, you are done. You just take log2(total) and you are done, you can't do any better than that if you are talking about the minimum number of bits necessary to store *any* position. If you put a white pawn on the board, there are 48 places it can go. The next white pawn has 47 places, and so on through the white pawns and black pawns. The first white knight has 48 places, since 16 squares are occupied by pawns, and there are 48 left. The second white knight has 47, and so on. If you continue doing this you get 2.23*10^51, which is 171 bits. This does not include cases where pieces have been captured, or where pawns have been promoted. And it also doesn't cover cases with different castling flags (this should be minor), or cases with different en-passant values (possibly a little more major). Of course it doesn't take into account illegal positions, but even if 90% of positions are illegal (which has got to be way too much), you only subtract three or four bits. But something significant that it doesn't take into account is game history, which is pertinent for 3x repetition and 50-move rule. That would be completely massive, you'd have to account for every unique position in every unique game, back to the point of the last capture or pawn move. This wouldn't be necessary if you are just trying to compress board positions. bruce
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.