Author: KarinsDad
Date: 13:45:37 05/17/99
The ideas here are based on a derivative of the first schema that I proposed as following: 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits move by repetition 7 bits 50 move rule 12 bits kings (6 per, including castling information) 32 bits blanks (1 per) 48 bits pawns (3 per) 20 bits knights (5 per) 20 bits bishops (5 per) 20 bits rooks (5 per) 10 bits queens (5 per) Since there are a maximum of 12 promoted pieces on a board (without taking pieces in order to promote) and at least 4 pawns must be taken off of the board to promote pawns into those 12 pieces, there could be a requirement of 12 more bits. 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits move by repetition 7 bits 50 move rule 12 bits kings (6 per) 32 bits blanks (1 per) 48 bits pawns (3 per) 20 bits knights (5 per) 20 bits bishops (5 per) 20 bits rooks (5 per) 10 bits queens (5 per) 12 extra promotion bits 185 bits (24 bytes) is the smallest size required to accommodate all legal positions with this state information using this schema. The last pawn does not need a color bit if there are 16 pawns on the board. 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits move by repetition 7 bits 50 move rule 12 bits kings (6 per) 32 bits blanks (1 per) 47 bits pawns (3 per minus last pawn color bit) 20 bits knights (5 per) 20 bits bishops (5 per) 20 bits rooks (5 per) 10 bits queens (5 per) 12 extra promotion bits 184 bits (23 bytes) is the smallest size required to accommodate all legal positions with this state information using this schema. Since the structure decreases in size due to pieces being removed and people do not play games where only 4 pawns are taken and all of the resulting pawns (although not passed) are pushed and promoted, the following structure can represent all REAL positions. 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits move by repetition 7 bits 50 move rule 12 bits kings (6 per) 32 bits blanks (1 per) 47 bits pawns (3 per minus last pawn color bit) 20 bits knights (5 per) 20 bits bishops (5 per) 20 bits rooks (5 per) 10 bits queens (5 per) 4 extra promotion bits 176 bits (22 bytes) can be used to accommodate all legal positions from REAL games with this schema. The reason that a 22 byte structure is sufficient is effectively the same reason that chess sets do not come with enough pieces for promotions, it is not required. To increase the probability (from 99.9999999999999999999% to 100%) that real positions can be represented in 21 bytes, the following compression is added: All pieces on rank 1 and 8 are reduced in size by 1 bit to 4 bits since pawns cannot be located on rank 1 and 8. 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits move by repetition 7 bits 50 move rule 12 bits kings (6 per) 32 bits blanks (1 per) 47 bits pawns (3 per minus last pawn color bit) 20 bits knights (4 or 5 per) 20 bits bishops (4 or 5 per) 20 bits rooks (4 or 5 per) 10 bits queens (4 or 5 per) 4+ extra promotion bits (more bits are acquired once pieces are removed and when pieces are on rank 1 or 8) Also, you could often gain an additional bit (using the king on the edge algorithm I mentioned earlier), but it is not REALLY necessary since even the extra promotion bits are not REALLY necessary. One issue though: The move by repetition only indicates how many times the current position has shown up in a game. It does not indicate how many times other positions have shown up in a game and hence it is not sufficient for complete move by repetition state information. To do that, this position would have to include many other positions (possibly a large number). Hence, move by TRUE repetition state information cannot be saved. With the realization that move by repetition is not helpful (i.e. it is not sufficient state information), it becomes apparent that all state information is based on a given point in a given game that the position exists. If the move by repetition information cannot be supplied, then you have an insufficient specific game state. Hence, all state info can be dropped (i.e. side to move, 50 move rule, en-passant and castling information is not needed) since the state is not sufficient anyway. 12 bits kings (6 per, no castling info needed) 32 bits blanks (1 per) 47 bits pawns (3 per minus last pawn color bit) 20 bits knights (5 per) 20 bits bishops (5 per) 20 bits rooks (5 per) 10 bits queens (5 per) 7+ extra promotion bits Hence, 21 bytes is the smallest size (so far) that will represent real positions with no state information. Now, I am sure that people will say "Side to move, En-passant and Castling state information is required.". I say, "Why?". Effectively, what this structure represents is a position, not what state the position is in (in order to determine what can be done next). The reason I went down this path is to prove that there is NO minimum sized binary board position structure. The reason for this is that you cannot save all of the other positions required for move by repetition needed by this position WITHIN this position to determine the next action that can be done. The best you can do is to save the state information that can easily be supplied, is most often needed, and can be used. To do this, the smallest structure (so far) that is usable in a program for real positions would be: 1 bit side to move 1 bit ep not available (eps are smaller) 2 bits move by repetition 7 bits 50 move rule 12 bits kings (6 per) 32 bits blanks (1 per) 47 bits pawns (3 per minus last pawn color bit) 20 bits knights (4 or 5 per) 20 bits bishops (4 or 5 per) 20 bits rooks (4 or 5 per) 10 bits queens (4 or 5 per) 4+ extra promotion bits or 22 bytes. And for all intents and purposes, move by repetition and the 50 move rule state information is not REALLY needed and can default to 0, hence: 1 bit side to move 1 bit ep not available (eps are smaller) 12 bits kings (6 per) 32 bits blanks (1 per) 47 bits pawns (3 per minus last pawn color bit) 20 bits bishops (4 or 5 per) 20 bits knights (4 or 5 per) 20 bits rooks (4 or 5 per) 10 bits queens (4 or 5 per) 5+ extra promotion bits or 21 bytes. If you do not have 100% state information, but just that which is GENERALLY needed, you can also get away with dropping the fantasy legal positions (which are needed even less) as well and this allows one to get down to 21 bytes. KarinsDad :)
This page took 0.02 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.