kiwipete perft position

[Joost Buijs]

I have a strange scheme, I use the piece values as index into the bitboard arrays.

I use the following constants:

White = 0;
Black = 1;

Empty = 0;
Pawn = 1;
Knight = 2;
Bishop = 3;
Rook = 4;
Queen = 5;
King = 6;

const white_pawn = White | Pawn << 1;
const black_pawn = Black | Pawn << 1;
etc.

PieceType = piece >> 1;
PieceColor = piece & 1;

The bitboard array:

uint64_t bitboard[14];

bitboard[White] == occupied by white
bitboard[Black] == occupied by black
bitboard[white_pawn] == white pawns
bitboard[Black_pawn] == black pawns
etc.

You can also have the pieces for both colors in one 64 bit field, but than you have to AND each time with the occupied[color] field, in practice it doesn't matter much.

[JohnWoe]

My programming style is very low-level, so I never do things like objects, and even structs are rare. Pieces are just represented by small integers, usually unsigned char. The 'properties' are then simply stored in arrays, indexed by the piece number. (I prefer that over grouping them in structs, where you would have to worry about padding because of various sizes.)

But there usually are many properties. Of course they have a location (square number) and a piece type. But to avoid an extra level of indirection I usually store the properties that are common to the piece type with each individual instance of the piece. That includes the piece value in evaluation (opening and end-game packed in one int), the piece value in SEE, a pointer to the piece-square table, a pointer to the Zobrist piece-square key, the Zobrist Pawn key, the contribution to the material key, the piece ID in FEN, the promotability flags or the piece number of the promoted instance, a pointer to the move-generator list, capture flags for 0x88-type capture tests, etc. Where 'pointer' can also be an index in an array rather than a full memory address.

The piece numbers are often chosen such that the type can be easily deduced from the number even without a memory access, e.g. reserve 8-15 for Pawns (so that you can test with nr&8 whether a given piece is a Pawn).

In Shuriken and RubyShogi I used classes and objects boards / Xboard etc. If there was classes and namespaces in C I would use them in Sapeli.

That padding is actually a big problem. I have HASHTABLE_ENTRY_T which is BB ( 8 bytes ) + int ( 4 bytes ).

Code: Select all

./sapeli -system
+-+ System +-+
INT: -2147483648 -> 2147483647
BOARD_T: 184 B
HASHTABLE_ENTRY_T: 16 B
EVALS: 262144 KB ( count: 16777216 / key: 16777215 )
GOOD_MOVES: 131072 KB ( count: 8388608 / key: 8388607 )
= Total memory: 393216 KB

Here it says 16 bytes. So 25% space is wasted. I can't see where this additional 4 bytes is coming from.

[hgm]

The 8-byte field in the struct must be aligned on an 8-byte boundary.

[bob]

I will add more here. You have three choices:

(1) do nothing and tolerate the wasted 4 bytes per entry;

(2) expand each entry to 16 bytes and figure out something to use the new 4 byte field for;

(3) arrange your hash entries so that you have a BB, 4 byte val, 4 byte val, BB in ONE struct. IE two hash entries in the struct. Asymmetric, but now you meet all alignment requirements. If you do something simple like always store in one table, depth-preferred in the other. Combine both tables into one, and use one of these entries for each. Gain a bit of efficiency. Ideal would be to have something that is 64 bytes long, starting on an address divisible by 64, to take advantage of cache pre-fetching. But that is another topic.

[abulmo2]

(3)Ideal would be to have something that is 64 bytes long, starting on an address divisible by 64, to take advantage of cache pre-fetching. But that is another topic.

Is it really worth in practice? I just tested Crafty 25.3 with/without aligned allocation, and the aligned allocation gain is near 0.5%, so barely measurable. On my program amoeba, I failed to see any improvement.

[JohnWoe]

I will add more here. You have three choices:

(1) do nothing and tolerate the wasted 4 bytes per entry;

(2) expand each entry to 16 bytes and figure out something to use the new 4 byte field for;

(3) arrange your hash entries so that you have a BB, 4 byte val, 4 byte val, BB in ONE struct. IE two hash entries in the struct. Asymmetric, but now you meet all alignment requirements. If you do something simple like always store in one table, depth-preferred in the other. Combine both tables into one, and use one of these entries for each. Gain a bit of efficiency. Ideal would be to have something that is 64 bytes long, starting on an address divisible by 64, to take advantage of cache pre-fetching. But that is another topic.

Thanks!
I used to think about this problem some time and ended up with 1.

For sorting I used 7 bytes for hash and 1 byte for ordering as moves are always generated in the same order. As number of possible moves on every position is less than byte( 256 ). I don't store move( int / 4 bytes ) I only store index ( char / 1 byte ).

But for simplicity I ended up using the same hashtable scheme for everything.