Stacking Piece Sets

[leothetechguy]

So I've been recently exploring board representation for developing my own chess engine. I originally started using a quad-bitboard structure, but was annoyed by probably having to rely on SIMD Registers for fast operations. That's when I discovered the page for piece sets on the chess programming wiki:

https://www.chessprogramming.org/Piece-Sets

So my Idea is to stack 6 Pieces sets on top of each other, each 32 bits wide. The position in the word determines piece type and color.
And combined with the 6 other piece sets it forms a vertical 6 bit value specifying the position 1-64. Then, whenever a piece is captured, I'd set that position to one of the positions of the kings. Knowing that either king always has to be on the board, I could then infer that those pieces have been captured and ignore them.

I've also explored where to store other information (Castling Rights, en passant, side to move), The bishops for example would technically need only 5 bits to store the position, as they only move along diagonals, giving me an additional 4 bits to store other information. Any Thoughts?

[smatovic]

Reminds of the table driven move generator:

https://www.chessprogramming.org/Table- ... Generation

Vincent Diepeveen (32-bit apologist) claimed fastest speed back then when 32 vs 64 bit was topic.

--
Srdja

[hgm]

I used the system of moving captured pieces to the King location in my EGT generator. But what do you do when the King moves?

Otherwise I don't understand anything of what you are saying. What is 'stacking''?

In the 'mailbox trials' I used an attack map for storing the captures, which can be seen as a 2-dimensional piece set (attackers x victims). It was stored by victim row, for easy extraction of the captures in MVV/LVA order, and updated incrementally.

[leothetechguy]

I just made a Proof of Concept:

Code: Select all

#include <stdio.h>

int main() {
    char pieces[] = "rnbkqbnrppppppppPPPPPPPPRNBKQBNR";

    int vertical[] = {
        0b01010101010101010101010101010101,
        0b00110011001100110011001100110011,
        0b00001111000011110000111100001111,
        0b00000000111111110000000011111111,
        0b00000000000000001111111111111111,
        0b00000000000000001111111111111111
    };

    char board[8][8] = {
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'},
        {'.', '.', '.', '.', '.', '.', '.', '.'}
    };

    for (int i = 0; i < 32; i++) {
        int position = 0;
        for (int bit = 0; bit < 6; bit++) {
            if (vertical[bit] & (1 << i)) {
                position |= (1 << bit);
            }
        }

        int row = 7 - (position / 8);
        int col = position % 8;

        board[row][col] = pieces[i];
    }

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Does this make it any clearer? I know I would still need to store more information about the board state (Castling Rights, en-passant, side to move, repetition). But I think the approach could work.

If the king moves, I'd just check which pieces share the same position as the king before the move, and update them all to the kings new position when moving.

[hgm]

OK, I understand now.

But this is all horrendously slow, for no purpose. You scatter bits that only ever have meaning when used together over various words, so that you need a loop to collect them before you can do anyting useful with those.

Speedwise it is also a bad idea to use a two-dimensional array for the board; access to it is slower than to a 1-dimensional array. So most engines 'linearize' the board to a 1d array, and use 'square numbers' to access it. Your code first has to take the square number apart, and then let the compiler recombine the parts to make a memory address from it to access the array.

[leothetechguy]

I agree that using a 2d board for the engine would be horrible, I just quickly threw this together to verify that I could store and retrieve the board this way. In an Engine I'd probably directly start generating moves after retrieving the position of the piece, then updating the position on my piece sets after making the move.

Disclaimer: I'm a complete noob when it comes to these things and have never written a chess engine before.


Here is an Improved Version of the Proof of Concept for what it's worth:

Code: Select all

#include <stdio.h>

int main() {
    char pieces[] = "RNBKQBNRPPPPPPPPpppppppprnbkqbnr";

    int vertical[] = {
        0b01010101010101010101010101010101,
        0b00110011001100110011001100110011,
        0b00001111000011110000111100001111,
        0b00000000111111110000000011111111,
        0b00000000000000001111111111111111,
        0b00000000000000001111111111111111
    };

    char board[64] = {'.','.','.','.','.','.','.','.',
                      '.','.','.','.','.','.','.','.',
                      '.','.','.','.','.','.','.','.',
                      '.','.','.','.','.','.','.','.',
                      '.','.','.','.','.','.','.','.',
                      '.','.','.','.','.','.','.','.',
                      '.','.','.','.','.','.','.','.',
                      '.','.','.','.','.','.','.','.'};

    for (int i = 0; i < 32; i++) {
        int position = 0;
        for (int bit = 0; bit < 6; bit++) {
            position |= ((vertical[bit] >> i) & 1) << bit;
        }

        board[position] = pieces[i];
    }

    for (int i = 0; i < 64; i++) {
        printf("%c ", board[i]);
        if ((i%8)==7) {
            printf("\n");
        }
    }

    return 0;
}

[hgm]

That is a bit better. But it still stores the location of the pieces in a way that is completely useless without significant further processing.

Storing the game state is not a goal in itself. The algorithm that evaluates positions, as well as updating the game state as result of a move requires you to find which piece is on a given square ('board'), or what square a given piece is on ('piece list'). And since speed is an issue, you want that information to be available fast, with a minimum amount of work. Of course you could find out where your King is by looping through the board, examining every square to see what's on it, until you encounter the King. But that is slow, as you might have up to 64 tries before you find it. But if you keep the location of each piece in an array you can get it in a single memory access, without further processing. just square = location[pieceNr]. And even though this piece list in principle is redundant information if you already store the board as an array, the extra work for updating it on a move is almost nothing. Even if location just is an array of byte-size integers, this leaves plenty of room for indicating whether a piece is captured, so that you don't have to test all pieces for coinciding with the King when you move the latter.