Perft

[Joost Buijs]

Hi to all,

I'm new here, so let me introduce myself, I'm the author of Nightmare chess, Nightmare draughts and Rev othello.

Gijsbert Wiesenekker, a former colleague of mine persuaded me in 1992 to write a draughts engine, which I did.
Basically the whole engine was written in about 3 weeks, nothing fancy, just a mailbox implementation with a basic evaluation function, piece values and a few simple patterns.

The engine played a few times in the Dutch computer championship with acceptable results, and ended somewhere in the middle pack.
After some time I lost interest because there was hardly any activity in draughts compared to the activity in the chess world.

Mainly inspired by the good results of Fabian I decided a couple of weeks ago to revive the old engine using bitboards and magics for move generation.
After a few weeks of fighting bugs the move generator is almost finished and it shows a reasonably good performance on the 3 positions used over here.

Code: Select all

1. (11)	1665861398	12.438	133,933,221
2. ( 9)	1216917193	6.356	 191,459,596    
3. (15)	 346184885	3.731	  92,786,085
 

This was measured on a 3600 MHz. Haswell using the Intel C++ compiler, maybe I can get a few percent extra speed by tweaking but that seems unimportant.

Next thing to do is to rewrite the search and the evaluation function, I can probably use the SMP search of my chess engine without too much modification.
The evaluation function which was written with a mailbox implementation in mind has to be totally rewritten, and I have to implement a protocol like DXP to be able to automatically play games.

I guess it will take a few months before my new engine is able to play games, at least now that I'm retired from work I have enough time to spend on it.

Joost Buijs

[Joost Buijs]

Just tweaked it a little further and I guess this is as good as it gets with the implementation I use.

Code: Select all

1. (11)	1665861398	12.100	137,674,496
2. ( 9)	1216917193	 6.266	194,209,574
3. (15)	 346184885	 3.583	 96,618,723

My implementation uses bitboards with ghost bits at 10, 21, 32 etc., recently I saw that other people over here are using that too.
The magics mask(square, occupancy) are use for the king-sliders and the king-captures, the man-sliders and captures are generated with shifts only.

Next thing to do is to implement a FEN reader, SMP search, evaluation and a communication protocol.

[BertTuyt]

Joost, welcome back in the Computer Draughts Community.
I checked the database and we have played against each other in 1992 and 1993.
If you write an engine with a very simple hub-like interface (see this forum), then you could also use the Damage GUI, so you dont need to bother abour windows and difficult communication.
Just drop me an email , and I can/will support you.

Bert

[Joost Buijs]

Hi Bert,

Thanks! That would be fantastic. I will take a look at the forum to find out how it works, when there are questions I will send yo a PM.

First I have to start working on the search, basically I can use the SMP search of my chess engine which can use 64 cores, there are several things that need to be changed or removed though.
Another thing is the evaluation, I have no experience with Draughts myself, my old program uses some patterns from a booklet by 'Harm Wiersma', nowadays automated learning seems to be a hot topic.
I can probably use the BMI2 'pext' instruction to calculate the indices for the patterns in an elegant and fast way, the move generator also needs BMI2, as a consequence the program won't run on old CPU's.
Emulating these instructions in software will make the program run much slower, at present I have no idea to do this.

Joost

[Rein Halbersma]

Hi Joost,

Welcome back to computer draughts, and nice to see you have a modern bitboard program with pretty good performance already. Is your program open source or do you distribute binaries?

I'd be interested to learn how you applied magics for move generation, it seems that this gives quite a speed gain for the last 2 of the 3 perft positions.

Rein

[Joost Buijs]

Rein,

Nice to see you here as well.

At the moment I don't distribute anything because the program is in a very early state, only the board representation and the move generator.
The magics are done in the same way like in chess, which makes it easy to generate sliders, unfortunately I have to use 1 extra mask for the for the king captures, maybe I can solve this by using an extra set of magics but it is already fast enough like it is right now.

For instance generating king sliders is very simple:

Code: Select all

void movegen_t::gen_king_sliders()
{
	for (uint64_t bb_fr = pos->kings(own); bb_fr; RLSB(bb_fr))
		for (uint64_t bb_to = magic1s(LSB(bb_fr), pos->occupied()) & pos->empty(); bb_to; RLSB(bb_to))
			store_move(BLSI(bb_fr), BLSI(bb_to));
}

RLSB() removes the LSB
BLSI() extracts the LSB

Captures are more complicated because I have to do this separately for each direction, and still recursive.
For the captures I have a separate set of magics for each direction.
Moves are stored binary (24 bytes per move, from, to, captured), this is large, but not really a problem.

[Joost Buijs]

This is the set of magics I use:

Code: Select all

struct magic_t
{
	size_t offset;
	uint64_t mask;
	uint64_t magic;
	size_t shift;
};

__declspec(align(64)) static const magic_t magics[54] =
{
		{     0, 0x0000041041041040ULL, 0x0100842010200088ULL, 57 },
		{   128, 0x00000000820828c0ULL, 0x4080812100240000ULL, 57 },
		{   256, 0x0000000000525180ULL, 0x4040402410020010ULL, 57 },
		{   384, 0x0000000210842300ULL, 0x0810300804002008ULL, 57 },
		{   512, 0x0000108421084200ULL, 0x0088100808240004ULL, 56 },
		{   768, 0x0000820820820800ULL, 0x0044040880c08000ULL, 57 },
		{   896, 0x0000041041041800ULL, 0x0088020211080080ULL, 57 },
		{  1024, 0x00000000824a3000ULL, 0x0206024010004800ULL, 57 },
		{  1152, 0x0000000210946000ULL, 0x000084804001c008ULL, 57 },
		{  1280, 0x0000108421084000ULL, 0x0c04220201020000ULL, 57 },
		{ 0, 0, 0, 0 },
		{  1408, 0x0000820820820040ULL, 0x0020900830202000ULL, 57 },
		{  1536, 0x00000410414600c0ULL, 0x2010880200100003ULL, 55 },
		{  2048, 0x00000002928c0180ULL, 0x0080060201020030ULL, 55 },
		{  2560, 0x0000108421180300ULL, 0x8020008030201001ULL, 55 },
		{  3072, 0x0000210842100200ULL, 0x0840010414020200ULL, 57 },
		{  3200, 0x0000410410400840ULL, 0x021401010a020000ULL, 57 },
		{  3328, 0x0000820820c01880ULL, 0x000800201810040cULL, 55 },
		{  3840, 0x0000041251803140ULL, 0x0002000800840123ULL, 53 },
		{  5888, 0x00001084a3006280ULL, 0x0221000806080040ULL, 53 },
		{  7936, 0x0000210842004100ULL, 0x0029005008808000ULL, 57 },
		{ 0, 0, 0, 0, },
		{  8064, 0x0000410410021080ULL, 0x0080c80080808008ULL, 57 },
		{  8192, 0x0000820a30062900ULL, 0x40100100c4008010ULL, 53 },
		{ 10240, 0x00001494600c5240ULL, 0x0480200414010004ULL, 50 },
		{ 26624, 0x00002108c0182080ULL, 0x04010a0010020012ULL, 55 },
		{ 27136, 0x0000421080104100ULL, 0x0010828028010100ULL, 57 },
		{ 27264, 0x0000208200421080ULL, 0x1281101004040000ULL, 57 },
		{ 27392, 0x0000410600c42100ULL, 0x1001010004009820ULL, 55 },
		{ 27904, 0x0000928c018a4a00ULL, 0x1001508000202010ULL, 50 },
		{ 44288, 0x0000251803141040ULL, 0x00205060002c0000ULL, 53 },
		{ 46336, 0x0000421002082080ULL, 0x008100c880820000ULL, 57 },
		{ 0, 0, 0, 0, },
		{ 46464, 0x0000208010842100ULL, 0x4010110080810008ULL, 57 },
		{ 46592, 0x0000518031484200ULL, 0x0a20100200100404ULL, 53 },
		{ 48640, 0x0000a30062920800ULL, 0x0142010200224000ULL, 53 },
		{ 50688, 0x00004600c1041040ULL, 0x004a204040020008ULL, 55 },
		{ 51200, 0x0000840082082080ULL, 0x0040480100112008ULL, 57 },
		{ 51328, 0x0000100210842100ULL, 0x0004018188020001ULL, 57 },
		{ 51456, 0x0000300621084200ULL, 0x10040824a0010000ULL, 55 },
		{ 51968, 0x0000600c52500000ULL, 0x05040080c0420000ULL, 55 },
		{ 52480, 0x0000c018a0820800ULL, 0x0002300408006020ULL, 55 },
		{ 52992, 0x0000801041041040ULL, 0x0501110808004000ULL, 57 },
		{ 0, 0, 0, 0, },
		{ 53120, 0x0000008421084200ULL, 0x0008240401800006ULL, 57 },
		{ 53248, 0x0000018a42100000ULL, 0x0482022010100040ULL, 57 },
		{ 53376, 0x0000031490400000ULL, 0x2008008084400240ULL, 57 },
		{ 53504, 0x0000060820820800ULL, 0x0000840408080083ULL, 57 },
		{ 53632, 0x0000041041041040ULL, 0x0102041200420200ULL, 57 },
		{ 53760, 0x0000108421084200ULL, 0x0094408050020000ULL, 56 },
		{ 54016, 0x0000310842100000ULL, 0x000026040a040100ULL, 57 },
		{ 54144, 0x0000629280000000ULL, 0x0008210030220040ULL, 57 },
		{ 54272, 0x0000c50410400000ULL, 0x0006010024201100ULL, 57 },
		{ 54400, 0x0000820820820800ULL, 0x4102040404028000ULL, 57 },
};

[Rein Halbersma]

This is the set of magics I use:

Great, I'll try them out later this weekend! Did you generate these by brute force?

[Joost Buijs]

This is the set of magics I use:

Great, I'll try them out later this weekend! Did you generate these by brute force?

Yes, by brute force, it takes no more than a few seconds.
These magics are for a board representation with ghost bits at 10, 21, 32 etc.
I couldn't find a magic number for the long diagonals with the expected shift, in that case I had to increase the shift by 1 (64 - shift in the table).
Magic multipliers have limitations when the number of occupancy bits get higher.

[Rein Halbersma]

Moves are stored binary (24 bytes per move, from, to, captured), this is large, but not really a problem.

My move struct is 16 bytes because I only store the captured_pieces bitboard, not the captured_kings. I don't need the latter because I use copy-make instead of make-unmake (my state is only 32 bytes, so it's very cheap to copy). Only for Frisian/Spanish/Italian draughts do I have 24 byte moves since those variants need to compare how many king are captured. In fact, for Italian draughts, my move struct is even 32 bytes since also the order in which kings are captured is important to determine legal captures. One can even reduce move structs to 8 bytes by only storing the bits that change during a move, but that does not work for Thai draughts where one can land on a square where a captured piece used to sit.

[Joost Buijs]

Moves are stored binary (24 bytes per move, from, to, captured), this is large, but not really a problem.

My move struct is 16 bytes because I only store the captured_pieces bitboard, not the captured_kings. I don't need the latter because I use copy-make instead of make-unmake (my state is only 32 bytes, so it's very cheap to copy). Only for Frisian/Spanish/Italian draughts do I have 24 byte moves since those variants need to compare how many king are captured. In fact, for Italian draughts, my move struct is even 32 bytes since also the order in which kings are captured is important to determine legal captures. One can even reduce move structs to 8 bytes by only storing the bits that change during a move, but that does not work for Thai draughts where one can land on a square where a captured piece used to sit.

My move structure is 3 bit-boards: from, to and captured, hence the 24 byte, for the captured bit-board I don't distinguish between men and kings, this is handled in the move-make.
I also tried to put the from and to square-numbers into 2 bytes, it needs a few extra instructions but the speed is about the same, I still have to decide what I will finally do.

My board structure is 40 bytes, 4 piece bit-boards and 1 empty bit-board I copy the whole board structure once for each node and I have a make copy-unmake.
I still have to add a hash-key, which will make it a total of 48 bytes, and I still have to check what is faster copy make-unmake or a non-copy make-unmake.
When the board structure remains <= 64 bytes (the size of a cache-line) I guess the copy-make will do fine.

A couple of days ago I searched several hours for a stupid bug, I know that with a capture in Draughts the destination can be the same as the origin, the move generator did this fine, but in the make I first dropped the piece on the destination and then I removed it from the origin.
The result was 180 nodes missing at 10 ply from the starting position, I overlooked this several times and it completely drove me crazy...
Now I remember that I made the same mistake in 1992 with my first program, I just forgot about it.

[Edit]

Because I have to store the move in the transposition table as well I finally decided to store 'from, to' as square numbers and not as bit-boards.
This slows things down by 3%, this is not so important anyway, bigger performance hogs are Zobrist hashing and the index calculation for the evaluation function.

At the moment I try to calculate the hash value for the position directly from the bit-board information, it seems to be working but I still have to measure how many false positives I get.

Calculating the evaluation indices by 'multiply accumulate' is incredible slow, it slows the engine down to ~7 mnps on a single core, when I use PEXT for the calculation it runs about 4 times as fast. The only drawback is that the evaluation tables will be larger and that I have to use separate tables for black and white because flipping the board or flipping the index each time hurts performance too much.

[BertTuyt]

Joost, slightly off Perft topic.

I also abandoned Zobrist hashing.
When you base the movelist on the new positions (so 3 bitboards), than deriving the info for the Zobrist update might be time consuming.

Therefore I also implemented a hash-signature, based upon bitboards (in my case 4 bitboards, as I use whiteman, blackman, whiteking and blacking).
Think Ed does something similar.

If you want I can forward/post you the code.

Bert

[Joost Buijs]

I also abandoned Zobrist hashing.
When you base the movelist on the new positions (so 3 bitboards), than deriving the info for the Zobrist update might be time consuming.

Therefore I also implemented a hash-signature, based upon bitboards (in my case 4 bitboards, as I use whiteman, blackman, whiteking and blacking).

Bert,

Indeed, on the contrary when used for chess, Zobrist hashing when used for draughts/checkers is slowing down things considerably because on many occasions you have to capture several pieces at once.
At the moment I use a scheme by multiplying the 4 bit-boards (wm,wk,bm,bk) with 4 different arbitrary (64 bit) random numbers (like magic multiplication) and xor-ing everything together (maybe multiplying only 3 bit-boards and leaving one untouched will do as well).
At first sight this seems to work fine, it hardly slows things down, but I still have to measure how many collisions I get over a longer period of time.

Of course I'm also very interested in knowing how you addressed this problem.

Joost

[BertTuyt]

Here it is,

Code: Select all

HASHCODE CSearch64::Hash64(BITBOARD* pbbField)	// Murmur-inspired hashing.
{
	HASHCODE HashMan0, HashMan1, HashKing0, HashKing1;

	const HASHCODE hMul = 0x9ddfea08eb382d69ULL;
    
	// Hash64 Man
	HashMan0 = ( pbbField[BB_WHITEMAN] ^ pbbField[BB_BLACKMAN] ) * hMul;
	HashMan0 ^= ( HashMan0 >> 47 ); 
   
	HashMan1  = ( pbbField[BB_BLACKMAN] ^ HashMan0 ) * hMul;    
	HashMan1 ^= ( HashMan1 >> 47 );  
	HashMan1 *= hMul;  

	// Hash64 King
	HashKing0  = ( pbbField[BB_WHITEKING] ^ pbbField[BB_BLACKKING] ) * hMul;
	HashKing0 ^= ( HashKing0 >> 47 ); 
   
	HashKing1  = ( pbbField[BB_BLACKKING] ^ HashKing0 ) * hMul;    
	HashKing1 ^= ( HashKing1 >> 47 );  
	HashKing1 *= hMul;  

	return (HashKing1 ^ HashMan1);
}

Bert

[Joost Buijs]

Thanks!

At the moment it is a little bit too hot at the attic where I have my computers (no AC), when temperatures are back to normal I will try to compare your solution with mine.
Basically I can check it by storing the 4 bit-boards together with the hash-key and see how many false positives will occur over time.

Two weeks ago I started with a first attempt to generate endgame table-bases, the source for doing this is almost finished, I still have to check whether it is free of bugs and oversights before I can start generating them, otherwise it would be a waste of time.
Gijsbert Wiesenekker kindly offered me to use his table-bases, but I would like to use my own indexing scheme and source code so I decided to build them from scratch.

Next month I'm on vacation, so I guess it will take at least three months before I have something that can actually play a game.