kiwipete perft position

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Joost Buijs
Posts: 990
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: kiwipete perft position

Post by Joost Buijs » Mon Oct 14, 2019 5:56 pm

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
Posts: 102
Joined: Sat Mar 02, 2013 10:31 pm

Re: kiwipete perft position

Post by JohnWoe » Mon Oct 14, 2019 8:43 pm

hgm wrote:
Mon Oct 14, 2019 8:39 am
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. :lol:

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.

User avatar
hgm
Posts: 23787
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: kiwipete perft position

Post by hgm » Tue Oct 15, 2019 6:06 am

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

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: kiwipete perft position

Post by bob » Tue Oct 15, 2019 5:55 pm

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
Posts: 202
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: kiwipete perft position

Post by abulmo2 » Tue Oct 15, 2019 8:31 pm

bob wrote:
Tue Oct 15, 2019 5:55 pm
(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.
Richard Delorme

JohnWoe
Posts: 102
Joined: Sat Mar 02, 2013 10:31 pm

Re: kiwipete perft position

Post by JohnWoe » Wed Nov 06, 2019 11:36 pm

bob wrote:
Tue Oct 15, 2019 5:55 pm
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.

Post Reply