World Draughts Forum

It is currently Sun Jul 22, 2018 16:42

All times are UTC+02:00




Post new topic  Reply to topic  [ 247 posts ]  Go to page Previous 19 10 11 12 1317 Next
Author Message
 Post subject: Re: Perft
PostPosted: Wed Jun 15, 2016 20:53 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: 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:

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


Top
   
 Post subject: Re: Perft
PostPosted: Thu Jun 16, 2016 17:01 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: Joost Buijs
Just tweaked it a little further and I guess this is as good as it gets with the implementation I use.

Code:

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.


Top
   
 Post subject: Re: Perft
PostPosted: Thu Jun 16, 2016 21:55 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject: Re: Perft
PostPosted: Fri Jun 17, 2016 08:35 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: 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


Top
   
 Post subject: Re: Perft
PostPosted: Fri Jun 17, 2016 11:28 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1598
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


Top
   
 Post subject: Re: Perft
PostPosted: Fri Jun 17, 2016 12:53 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: 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:

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.


Top
   
 Post subject: Re: Perft
PostPosted: Fri Jun 17, 2016 13:02 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: Joost Buijs
This is the set of magics I use:

Code:

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 },
};



Top
   
 Post subject: Re: Perft
PostPosted: Fri Jun 17, 2016 13:52 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1598
Joost Buijs wrote:
This is the set of magics I use:


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


Top
   
 Post subject: Re: Perft
PostPosted: Fri Jun 17, 2016 14:19 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: Joost Buijs
Rein Halbersma wrote:
Joost Buijs wrote:
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.


Top
   
 Post subject: Re: Perft
PostPosted: Sat Jun 18, 2016 14:42 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1598
Joost Buijs wrote:
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.


Top
   
 Post subject: Re: Perft
PostPosted: Sat Jun 18, 2016 15:52 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: Joost Buijs
Rein Halbersma wrote:
Joost Buijs wrote:
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.


Top
   
 Post subject: Re: Perft
PostPosted: Wed Jul 20, 2016 12:55 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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


Top
   
 Post subject: Re: Perft
PostPosted: Thu Jul 21, 2016 07:48 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: Joost Buijs
BertTuyt wrote:
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


Top
   
 Post subject: Re: Perft
PostPosted: Thu Jul 21, 2016 12:39 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Here it is,
Code:

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


Top
   
 Post subject: Re: Perft
PostPosted: Thu Jul 21, 2016 19:31 
Offline

Joined: Wed May 04, 2016 11:45
Posts: 317
Real name: 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.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 247 posts ]  Go to page Previous 19 10 11 12 1317 Next

All times are UTC+02:00


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited