Move encoding

[hgm]

In case of promotion in move_gen the to-square is coded as follows:

Code: Select all

bit-7       : on (as a token of promotion)
bit-6|5|4|3 : Q|R|B|N
bit-2|1|0   : direction (capture left, forward, capture right)

Then via a simple table look-up (using the bits) I get the offset to the to-square and the promotion type.

This is actually very similar in spirit to what I use in Spartacus, except that I generalized it there to apply to other board sizes and larger numbers of promotion pieces. They key to make it possible is to encode the move step in the off-board to-square, i.e. relative to the from-square, rather than the absolute to-square. Your setting of bit 7 makes it off-board, and bits 0-2 indicate the move step. (Only 3 possibilities, as you use the format only for promotion moves of orthodox Pawns.) Without the relative encoding I had severe problems in, f.e. Grand Chess, where the board is 10x10 with the last 3 ranks promotion zone, and you have a choice out of 6 pieces to promote to (as well as not promoting at all, if you aren't on last rank yet). So that means 6x30 = 180 different promotion moves, which together with the required 100 on-board to-square numbers exceeded the capacity of a single byte, The 30 possible promotion squares reduce to just 3 move steps, though, so that only 18 off-board to-square codes are needed to allow encoding of all possible promotions, and I could even afford the luxury of assigning different codes to white and black promotions, with plenty of codes to spare for other special moves.

If the entire to-square, whenever off-board, is used as index in a lookup table, it isn't really important anymore to assign the different aspects (such as direction and promo-choice) to different bits. Spartacus has a 24x14 mailbox board, where only the left half of the central 24x10 area can be physical board, and the rest is a guard band filled with GUARD codes. So what I have to do for decoding is just

Code: Select all

victim = board[toSquare];
if(victim == GUARD) { // off-board flags special move
  moveType = typeTable[toSquare];
  if(moveType == 0) { // common case of double-push
    if(board[fromSquare + leftTable[toSquare]] == ENEMY_PAWN ||
      board[fromSquare + rightTable[toSquare]] == ENEMY_PAWN  )
      epFlag = fromSquare + skipTable[toSquare]; // e.p. possible
  } else switch(moveType) {
    case CASTLING:
      rookFrom = rookFromTable[toSquare];
      rookFrom = rookToTable[toSquare];
      ...
      break;
    case PROMOTION:
      promoPiece = choiceTable[toSquare];
      ....
  }
  toSquare = fromSquare + stepTable[toSquare];
}

This limits the overhead on normal moves to just the victim==GUARD test and branch. The names for the decoding tables are shown as different here for didactic purposes; in practice they are just aliases for tables that define byte items used in different ways for the various move types. (E.g. the table that holds the Rook from- and to-squares for a castling holds the left and right neighbors of the to-square on a Pawn double-push, and the promotion piece type on a promotion.)

[spambanane]

Still using the 8-bit 6502 approach, 2 bytes. Don't like the use of 16-bit words because it's still penalized (extra cycle).

Nice to read the term "6502", i still own my atari 130 xe.

i too noticed performance issus with 16 bit values, but as my cpu and assembler knowledge is *very* rusty i have only some vague ideas about the reason. seems i have problems to catch up, but i try. what i have found so far are the architecture manuals by intel. can someone recommend other sources? thank you.