87flowers ~ $

rapidly indexing arbitrary king and knight moves

chess

  1. 0x88 math
  2. the subset
  3. the code

A recent development in NNUE architecture is "Threat Inputs" (TI). In addition to normal piece location information, threat inputs also provide additional feature inputs into the neural network. These additional features tell the network how pieces are being attacked or defended on the chess board in the current position.

I am unhappy with the current state of the art in TI feature indexing, which requires several look-up tables. I have been contemplating this issue for about a month, trying to come up with a computational way to compute feature indexes.. A recent realization allowed me to come up with a scheme to compute relative indexes for knight and king moves without large LUTs.

This was somewhat inspired (but not directly) by a previous article of mine.

0x88 math

We consider the bit patterns in 0x88 for the relative vector for each possible king and knight move:

HexBinaryMove
0x1000010000King N
0x1100010001King NE
0x0100000001King E
0xF111110001King SE
0xF011110000King S
0xEF11101111King SW
0xFF11111111King W
0x0F00001111King NW
0x1F00011111Knight move
0x2100100001Knight move
0x1200010010Knight move
0xF211110010Knight move
0xE111100001Knight move
0xDF11011111Knight move
0xEE11101110Knight move
0x0E00001110Knight move

Our goal is to be able to assign a unique index from 0-7 for each possible king and knight move. I came to the realization last night that if we can select a discriminatory subset of the bits, we can compute indexes for the king and knight threats using that.

the subset

The initial obvious subset is bits 0, 1, 4 and 5. Unfortunately this results in bad collisions within the knight moves.

The subset I settled on was bits 0, 1, 4 and 6. This does have overlap between the king and knight moves, but that doesn't matter for our use case.

HexBinaryMoveBitsBits (decimal)Output index
0x1000010000King N 0100 40
0x1100010001King NE0101 51
0x0100000001King E 0001 12
0xF111110001King SE1101133
0xF011110000King S 1100124
0xEF11101111King SW1011115
0xFF11111111King W 1111156
0x0F00001111King NW0011 37
0x1F00011111Knight move0111 71
0x2100100001Knight move0001 12
0x1200010010Knight move0110 63
0xF211110010Knight move1110144
0xE111100001Knight move1001 95
0xDF11011111Knight move1111156
0xEE11101110Knight move1010107
0x0E00001110Knight move0010 20

Notice that 0x21 collides with King E and 0xDF collides with King W, but also that this does not matter for our use case.

the code

u8x16 coords_to_indexes(u8x16 coords, Square sq) {
  // 00rrrfff → 0rrr0fff
  const u8x16 expandedCoords {_mm_gf2p8affine_epi64_epi8(coords.raw, u64x2::splat(0x0102040008102000).raw, 0)};
  const u8x16 expandedSq = u8x16::splat(expandSq(sq));

  // 0x88 difference
  const u8x16 diff = expandedCoords - expandedSq;

  // extract subset of bits
  // xdxcxxba → 0000dcba
  const u8x16 bits {_mm_gf2p8affine_epi64_epi8(diff.raw, u64x2::splat(0x0102104000000000).raw, 0)};

  // lookup table
  const u8x16 perm {{0xFF, 2, 0, 7, 0, 1, 3, 1, 0xFF, 5, 7, 5, 4, 3, 4, 6}};
  const u8x16 indexes = bits.swizzle(perm);

  return indexes;
}
coords:         d5 e5 e4 e3 d3 c3 c4 c5 e6 f5 f3 e2 c2 b3 b5 c6
expandedCoords: 43 44 34 24 23 22 32 42 54 45 25 14 12 21 41 52
expandedSq:     33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33
diff:           10 11 01 f1 f0 ef ff 0f 21 12 f2 e1 df ee 0e 1f
bits:           04 05 01 0d 0c 0b 0f 03 01 06 0e 09 0f 0a 02 07
indexes:        00 01 02 03 04 05 06 07 02 03 04 05 06 07 00 01
© 2024. All rights reserved. 87flowers