Search code examples
algorithmdata-structureschess

Dealing with Chessboard symmetry


In a 8X8 chessboard, I was wondering how to implement the symmetry of the board.

A lot of positions are just mirrors or rotations of one another (with no pawns or castling capabilities left the directions are indistinguishable).

By using a combination of vertical, horizontal and diagonal mirrorings of the board it is always possible to fix the position of a piece within the a1-d1-d4 triangle.

How to implement these symmetries on chess board? Does it depends on choice of board representation chosen(Bitboards, 0x88, 8x8 array, and so on) ?

Edit 1: The goal is to implement generation of the endgame tables and their compression.


Solution

  • If you are looking to compress the boards, you can generate a canonical representation of each board. An older answer by @DocBrown expresses this well:

    To make this more efficient, you can work with a "canonical representation" of each board, defined as follows. Generate all symmetric boards of a given one, pack each one of it into a byte array, and among those arrays keep the array which, interpreted as a big number, has the minimum value. This packed representation is a unique identifier of the symmetry class of each board and can be easily put in a dictionary / hash table, which makes testing if that symmetry class already appeared very efficient.

    This question is in reference to the N-queens problem where a good deal of symmetry can be found since each queen is indistinguishable. For end-game boards, this is (rarely) the case so I'm not sure how much of a savings you'll get.