Author: Tim Foden
Date: 09:16:08 11/19/01
Go up one level in this thread
On November 19, 2001 at 11:42:42, Les Fernandez wrote: >Need to know what the minimum number of bits that are needed to store the worse >case scenario for a pv (ie Qa6xb7# or fxg1=Q+). As you can see both these >strings are 7 characters long and represent the longest possible situation. If >someone is aware of how to represent these 2 conditions with the fewest number >of bits I would appreciate it. Would you also know the current board setup? If you do, I guess you could get away with 5 bits for the from square (at most 32 pieces on the board), and then at most 5 bits for the to square (queen can move to at most 27 other positions). For the promotion, you are moving a pawn, which has at most 4 possible moves (2 bits) and 2 bits for promotion piece. The other data could be inferred from the from and to square. Of course this requires that you also have a move generator and in-check tests available. So using a fixed number of bits (for the worst case) for each piece type: ..Kings: 5 + 4 . . = 9 bits, ( 8 to squares, plus 2 castling options) .Queens: 5 + 5 . . = 10 bits, (27 to squares) ..Rooks: 5 + 4 . . = 9 bits, (14 to squares) Bishops: 5 + 4 . . = 9 bits, (13 to squares) Knights: 5 + 3 . . = 8 bits, ( 8 to squares) ..Pawns: 5 + 2 + 2 = 9 bits, ( 4 to squares, plus 4 promotion pieces) You could use fewer bits than this if you figured out the possible moves for each piece by taking into account its actual available moves in its current position. If you are just looking for a compression scheme, maybe you could talk to Lyapco George (see http://www.geocities.com/lyapko/index.html), who seems to know a lot about this kind of thing (he has written a PGN pre-compression utility). Cheers, Tim.
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.