All,
Disclaimer:
This is not a Perl question though I have often found working on memory management problems like this helps improve my Perl. Additionally, I am not a chess player - I have probably played less than a dozen games in my life so I may be way off base here.
- First 8 bytes = 64 bit string representing the positions of the white pieces on the board
- Next 8 bytes = 64 bit string representing the positions of the black pieces on the board
- Next 6 bytes = Sixteen 3 bit strings representing the white pieces (pawn, rook, knight, bishop, king, queen)
- Next 1 byte = 1 bit representing black/white's turn, 4 bits representing what type of castling is still possible, 3 bits representing the column the last turn moved the pawn 2 places
That last 3 bits may be hard to understand but in en passant, if your opponent moves 2 places to avoid being attacked by a pawn you already have in position, you have the option to capture that pawn but you must immediately do so on your next turn. These bits serve to either tell you that en passant is possible and which piece is able to be attacked, or if en passant is not possible is set to an invalid column.
There are admittedly a few things that these 23 bytes do not encode:
- Previous board configurations leading to the three-fold repetition or five-fold repetition draw rules
- Number of previous moves without pawn move or capture for 50/75 move draw rules
- Time remaining for each player if time control is employed
While the 3 or 5 board position repetition is beyond the scope of this approach (you would essentially have to serialize every board from every move), you could fairly easily add a byte or two in order to address time and 50/75 move draw rules if you wanted.
An interesting aspect of the approach I have provided is that you can go with either fixed length records (every serialized board is 23 bytes) or with variable length since the number of white and black pieces can be read from the first 16 bytes.
My question to you is - can you see a way to save any more space? This was a thought experiment so I have no practical use but it did keep me up for a long time so I want to make sure I am not missing something sneaky/creative.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
| |
For: |
|
Use: |
| & | | & |
| < | | < |
| > | | > |
| [ | | [ |
| ] | | ] |
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.