Skip to main content
1 of 3

Do you just want elegant code, or do you want efficiency?

I'm inclined to think that the memory allocated to a State needs to be a lot less than an array of 64 integers. It's fairly easy to get it down to 32 (max number of pieces) × 6 bits which is a factor of 10 smaller.

But looking at how the data is used also matters. Do you want to store the piece at each position, or the position of each piece? Perhaps you could do a bit of both: a 64-bit map indicating the squares occupied by white, another 64-bit map indicating the squares occupied by black, 16 bytes to hold the (x,y) position of each white piece, 16 bytes to hold the position of each black piece; total 48 bytes compared with your 256. It not only saves space, but copying the board involves moving less data, and of course smaller data structures lead to better CPU cache hits. And you still get pretty efficient access for the major operations: your 8×8 search to find all the white pieces is replaced by a scan of a 16-byte array, and the test of whether a square is occupied becomes a simple shift/mask test on a 64-bit integer.