Author: KarinsDad
Date: 15:34:00 10/28/99
Go up one level in this thread
On October 27, 1999 at 18:15:45, Daniel Karlsson wrote: >On October 27, 1999 at 11:34:22, KarinsDad wrote: > >> >>Next problem. How do you differentiate between a knight 010 and a queen 0101? >>How do you know whether the pattern 0101 is a white knight followed by a black >>piece or a white queen? >> > >Perhaps this is not needed. Just out of curiosity i tried this: > >_: 0 >P: 1 >N: 00 >B: 01 >R: 10 >Q: 11 >K: 000 > >The back rank in the opening, RNBQKBNR, is encoded to 10000111000010010. Now, >knowing there are 8 squares on each rank, a simple back-tracking algorithm comes >up with the following possibilities: >1 PKBQKBNR >2 RNBQKBNR >3 RKPQKBNR >4 RKQPKBNR >5 RKQRNBNR >6 RKQRKPNR >7 RKQRKR_R >8 RKQRKRB_ > >We then add which one of the above combinations is the correct one to the code. >I.e. "is it 1? no!", "is it 2? yes!" > >The encoded row would then become 10000111000010010:01. Of course some >additional bits are needed to indicate end-of-row, color, etc. And some bits >could be saved by a better algorithm (no pawns on 1st and 8th, never two >adjacent kings, etc). > >Is it worth investigating further? Maybe. I haven't tried it. The first question that must be answered is: How many bits will this take up on a starting board? Your example took up 17 bits for data, several bits for a data delimeter (the : ), and 3 bits (not 2) to determine which of the 8 possibilities was the real one. So, about 22 or 23 bits (or so). The white pawn line would take up about 13 or 14 bits. Ditto for each blank row. So, (22 + 13 + 13 + 13) * 2 + 31 color bits (the last piece is known, but other color information may be difficult to determine) + 1 side to move bit + maybe 4 more bits for castling state = 158 or so bits, best case. Now, remove 4 pawns and add 3 promoted pieces and you have just added 2 more bits. Do this 3 more times for all possible promoted pawns and you are at 166 bits. You will also add bits here for the number of possibilities for each promoted piece. Also, this is being extremely conservation with the delimeter size, the number of possibilities size, etc. I doubt this works within 160 bits, but work with it and see what you come up with. One thing that gets ingrained within you when you work with this type of stuff. There is only so many pounds of crap that you can place in a 5 pound bag (i.e. most tricks don't work, it's just another way to stuff the bag and probably not as efficiently). Good luck! 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.