permute mailbox to bitboards (Chess, AVX-512, GFNI)

Board Representations

There are two main ways to represent a board position in chess: a mailbox or a set of bitboards.

For the non-engine developers in the audience:

Mailbox

• Likely the most obvious representation, if you have not encountered engine programming before.
• A std::array<Piece, 64>; an array of pieces, where each element of the array represents once square.
• There are more advanced representations (such as 16x8), but those are out-of-scope of this article.

Bitboard

• The most popular chess board representation; “the current meta”.
• A bitboard is a u64, where a 1 or 0 in a position represents the presence or absence of a piece.
• A common board representation is to have two color bitboards and six piece type bitboards (eight bitboards in total).

In a previous blog post, I mentioned in passing that the mailbox and bitboard representations are just transpositions of each other. This turns out to be a useful observation in a primarily mailbox engine so you can use bitboard techniques where this makes sense to do so.

BPC

I had not previously worked out how to actually efficiently do this transposition on a computer. Fortunately, during a recent Mastodon conversation with Harold Aptroot, he told me about his very neat tool He also has an associated blog post that explains the theory. that shows optimal code sequences for bit-permutations on AVX-512. His tool made this task trivial.

The Code

I'll spare you an explanation and just give the code.

#include <array>
#include <bit>
#include <cstdint>
#include <immintrin.h>

using Bitboard = std::uint64_t;

enum class Piece : std::uint8_t {
  None = 0,
  WPawn = 1, WKnight, WBishop, WRook, WQueen, WKing,
  BPawn = 9, BKnight, BBishop, BRook, BQueen, BKing,
};

std::array<Bitboard, 8> transpose(std::array<Piece, 64> mailbox) {
  __m512i s0 = _mm512_set_epi8(
      0, 0x41, 0x42, 0x44, 0x48, 0x50, 0x60, 0,
      0, 0x81, 0x82, 0x84, 0x88, 0x90, 0xA0, 0,
      0, 0x41, 0x42, 0x44, 0x48, 0x50, 0x60, 0,
      0, 0x81, 0x82, 0x84, 0x88, 0x90, 0xA0, 0,
      0, 0x41, 0x42, 0x44, 0x48, 0x50, 0x60, 0,
      0, 0x81, 0x82, 0x84, 0x88, 0x90, 0xA0, 0,
      0, 0x41, 0x42, 0x44, 0x48, 0x50, 0x60, 0,
      0, 0x81, 0x82, 0x84, 0x88, 0x90, 0xA0, 0);
  __m512i s1 = _mm512_set_epi8(
      8, 9, 10, 11, 12, 13, 14, 15,
      0, 1, 2, 3, 4, 5, 6, 7,
      8, 9, 10, 11, 12, 13, 14, 15,
      0, 1, 2, 3, 4, 5, 6, 7,
      8, 9, 10, 11, 12, 13, 14, 15,
      0, 1, 2, 3, 4, 5, 6, 7,
      8, 9, 10, 11, 12, 13, 14, 15,
      0, 1, 2, 3, 4, 5, 6, 7);
  __m512i m2 = _mm512_set1_epi64(0x8040201008040201);
  __m512i s3 = _mm512_set_epi8(
      56, 48, 40, 32, 24, 16, 8, 0,
      57, 49, 41, 33, 25, 17, 9, 1,
      58, 50, 42, 34, 26, 18, 10, 2,
      59, 51, 43, 35, 27, 19, 11, 3,
      60, 52, 44, 36, 28, 20, 12, 4,
      61, 53, 45, 37, 29, 21, 13, 5,
      62, 54, 46, 38, 30, 22, 14, 6,
      63, 55, 47, 39, 31, 23, 15, 7);

  __m512i x = std::bit_cast<__m512i>(mailbox);
  x = _mm512_shuffle_epi8(s0, x);
  x = _mm512_shuffle_epi8(x, s1);
  x = _mm512_gf2p8affine_epi64_epi8(m2, x, 0);
  x = _mm512_permutexvar_epi8(s3, x);
  return std::bit_cast<std::array<Bitboard, 8>>(x);
}

You can play with this on godbolt.