Skip to main content
added 681 characters in body
Source Link

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.

Of course, the devil is in the detail. As well as en-passant and castling status, you need to allow for the board to hold extra Queens, etc, after a promotion.

Afterthought

Or perhaps:

  • 64-bit map showing squares occupied by white pieces/pawns
  • 64-bit map showing squares occupied by black pieces/pawns
  • 64-bit map showing squares occupied by pawns
  • variable-length array of 16-bit values for the major pieces - 3 bits to identify the piece (K|Q|B|R|N), 1 bit to identify the colour, 6 bits to identify the square, 6 bits spare

After writing this I've realised that I instinctively start an exercise like this by thinking about the data structures, and then build the code on top. An alternative approach is to design the interface to the State class first, and then design the data structure underneath.

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.

Of course, the devil is in the detail. As well as en-passant and castling status, you need to allow for the board to hold extra Queens, etc, after a promotion.

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.

Of course, the devil is in the detail. As well as en-passant and castling status, you need to allow for the board to hold extra Queens, etc, after a promotion.

Afterthought

Or perhaps:

  • 64-bit map showing squares occupied by white pieces/pawns
  • 64-bit map showing squares occupied by black pieces/pawns
  • 64-bit map showing squares occupied by pawns
  • variable-length array of 16-bit values for the major pieces - 3 bits to identify the piece (K|Q|B|R|N), 1 bit to identify the colour, 6 bits to identify the square, 6 bits spare

After writing this I've realised that I instinctively start an exercise like this by thinking about the data structures, and then build the code on top. An alternative approach is to design the interface to the State class first, and then design the data structure underneath.

added 163 characters in body
Source Link

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.

Of course, the devil is in the detail. As well as en-passant and castling status, you need to allow for the board to hold extra Queens, etc, after a promotion.

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.

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.

Of course, the devil is in the detail. As well as en-passant and castling status, you need to allow for the board to hold extra Queens, etc, after a promotion.

Source Link

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.