Perft

[Joost Buijs]

Joost, think further optimization does not make sense, as the Movegenerator is already very fast.
As I want to make some changes to the overall architecture of Damage, I want to spent still somewhat time on the Movegenerator.
I still believe that the King Capture (even without Magic) can be faster.
I will to do some tests with RAYMASK based solutions, as is also embedded in the program of Harm Jetten (Moby Dam).

Another question think the Intel Compiler is not for free, and ballpark figure for costs?
Bert

I fully agree with you, at the moment my move-generator is 5 to 10 times as fast as my evaluation function, improving the move-generator by a few percent is something I won't notice at all.

Intel wants an arm and a leg for their compiler, I am programming stuff for both Amsterdam Universities and I use it with an academic license which is $799,-.
There is a free version for people writing open-source software e.g. publishing at GitHub, unfortunately this holds only for the Unix version.
Another thing is that I don't know if the Intel compiler integrates with VS2015 community ed. but you can always use it from the command-line or with a make-file.
Most of the time I use the MSVC compiler because it compiles faster which is nice for development work, maybe you can gain 10 Elo points by using the Intel compiler, when you improve your search and/or evaluation function you can gain a lot more, that is my opinion.

Joost

[Joost Buijs]

To determine king captures I basically do the following: ((magic_mask_for_current_direction & opposite_pieces & ~edge_squares) >> current_direction) & empty_squares;
This gives you the first empty square after the opposite piece you are allowed to capture.
It is possible to generate another set of magic_masks to avoid masking the edge-squares but that is bean counting, you only have to mask the opposite_pieces and edge_squares once for all directions.

Hi Joost,

Could you show us your code how you use magics to generate king captures?

I think you can do it with only one magic multiplication mask for all 4 directions simultaneously, combined with 4 post-processing steps (1 for each direction). Basically you re-use your king move magic generation function

Code: Select all

passing_sqrs = king_magic_moves(from, ~empty_sqrs); // 1 magic multiplication, gives all squares a king can travel: "from" until blocked by the first bit along a direction in "~empty_sqrs"
target_LU = (passing_sqrs & diag_LU[from] >> dir_LU) & opponent_pieces & (empty_sqrs << dir_LU); // at most 1 bit
recursive_find_king_jumps(from, target_LU, dir_LU); 
// ...
// same for LD, RU and RD directions

It takes only an extra 4 bitboard tables (called diag_LU etc. above) per square (for each half-diagonal from each square). So 64 * 8 * 4 = 2Kb.

My king_capture routine uses 4 separate directions because for me that is easier to comprehend, basically it goes like:

Code: Select all

void movegen_t::king_capture_m6(bitboard_t captured, bitboard_t captures, int count)
{
	const magic4_t magic = magic4(LSB(captured >> 6), pos->occupied());
	const bitboard_t target = pos->occupied(opp)) & ~captures;
	bitboard_t capture;

	// capture
	if (capture = magic.m6 & target & pos->empty() << 6)
		king_capture_m6(capture, captures | capture, count + 1);

	if (capture = magic.m5 & target & pos->empty() << 5)
		king_capture_m5(capture, captures | capture, count + 1);

	if (capture = magic.p5 & target & pos->empty() >> 5)
		king_capture_p5(capture, captures | capture, count + 1);

	update_captures(captured >> 6, captures, count);

	// scan forward
	for (bitboard_t bb_fr = magic.m6 & pos->empty(); bb_fr; RLSB(bb_fr))
	{
		const magic4_t magic = magic4(LSB(bb_fr), pos->occupied());

		if (capture = magic.m5 & target & pos->empty() << 5)
			king_capture_m5(capture, captures | capture, count + 1);

		if (capture = magic.p5 & target & pos->empty() >> 5)
			king_capture_p5(capture, captures | capture, count + 1);

		update_captures(BLSI(bb_fr), captures, count);
	}
}

update_captures() updates the list when the capture has a higher or equal count and checks for redundancy, RLSB() resets the least significant bit and BLSI() gets the least significant bit.

Instead of pos->occupied(opp) & ~pos->empty(); I can also XOR pos->occupied(opp) ^ pos->empty(); this makes no difference in speed at all.
Modern processors try to execute several instructions in parallel, changing the order of instructions in a program sometimes makes a difference of several percent.

[BertTuyt]

I also tried now the approach also used by Harm Jetten to detect first non-empty square in the main KingCapture detection routine.
Timing for the last Perft(9) position is now 7.40s, 7.44s, 7.43s and 7.43s.
See below code for the routine.
I guess some small optimizations are still possible.
As you see no loops nor MAGIC, nor memory access (as the RAYMASK) is coded into the program.
Guess this should be faster compared with MAGIC in the end.
A pity there is no simple way to detect the MSB alike the LSB.

Bert

Code: Select all

int CMoveGenerate128::QWhiteKingCapture128(PTSTACK pTDepth)
{
	DWORD dKingPosition, dRay;
	BITBOARD bbPosition, bbPosition0;
	BITBOARD *pbbField;

	pbbField = pTDepth->pbbField;

	BITBOARD bbEmpty	= pbbField[BB_EMPTY];
	BITBOARD bbKing		= pbbField[BB_WHITEPIECE] & pbbField[BB_KING];
	BITBOARD bbOpponent = pbbField[BB_BLACKPIECE];

	int iXMoves = pTDepth->iXMoves;

	while (bbKing) {

		BITSCANFORWARD64(&dKingPosition, bbKing);

		bbPosition0 = (BITBOARD)1<<dKingPosition;
		bbKing ^= bbPosition0;

		pTDepth->bbFrom = bbPosition0;

		pbbField[BB_EMPTY] = (bbEmpty | bbPosition0);		// Set bit in Empty Field

		bbPosition = (RAYMASK_DFL >> (DFLDI50 - dKingPosition)) &  ~bbEmpty;
		BITSCANREVERSE64(&dRay, bbPosition | DGHOST0);
		bbPosition = (BITBOARD)1 << dRay;

		if (bbOpponent & bbPosition & DBR(bbEmpty))			// DFL Capture
			KingNextCapture0_128(pTDepth, 1, DFL(bbPosition), bbOpponent ^ bbPosition);

		bbPosition = (RAYMASK_DFR >> (DFLDI50 - dKingPosition)) &  ~bbEmpty;
		BITSCANREVERSE64(&dRay, bbPosition | DGHOST0);
		bbPosition = (BITBOARD)1 << dRay;

		if (bbOpponent & bbPosition & DBL(bbEmpty))			// DFR Capture					
			KingNextCapture1_128(pTDepth, 1, DFR(bbPosition), bbOpponent ^ bbPosition);

		bbPosition = (RAYMASK_DBR << (dKingPosition-1)) &  ~bbEmpty;
		bbPosition &= ~bbPosition + 1;						// Least significant Bit

		if (bbOpponent & bbPosition & DFL(bbEmpty))			// DBR Capture
			KingNextCapture2_128(pTDepth, 1, DBR(bbPosition), bbOpponent ^ bbPosition);

		bbPosition = (RAYMASK_DBL << (dKingPosition-1)) &  ~bbEmpty;
		bbPosition &= ~bbPosition + 1;						// Least significant Bit

		if (bbOpponent & bbPosition & DFR(bbEmpty))			// DBL Capture
			KingNextCapture3_128(pTDepth, 1, DBL(bbPosition), bbOpponent ^ bbPosition);

		pbbField[BB_EMPTY] = bbEmpty;						// Reset bit in Empty Field
	}

	if (iXMoves == pTDepth->iXMoves) return (MOVEGEN_CAPTURE_NOCAPTURE);

	return (MOVEGEN_CAPTURE_WHITEKING);
}

And the RayMasks

Code: Select all

#define RAYMASK_DBR (DFLD7 | DFLD12 | DFLD18 | DFLD23 | DFLD29 | DFLD34 | DFLD40)
#define RAYMASK_DBL (DFLD6 | DGHOST10 | DFLD15 | DFLD20 | DFLD24 | DFLD29 | DFLD33 | DFLD38)
#define RAYMASK_DFR (DFLD45 | DGHOST40 | DFLD36 | DFLD31 | DFLD27 | DFLD22 | DFLD18 | DFLD13)
#define RAYMASK_DFL (DFLD11 | DFLD17 | DFLD22 | DFLD28 | DFLD33 |DFLD39 | DFLD44)

[Joost Buijs]

I also tried now the approach also used by Harm Jetten to detect first non-empty square in the main KingCapture detection routine.
Timing for the last Perft(9) position is now 7.40s, 7.44s, 7.43s and 7.43s.
See below code for the routine.
I guess some small optimizations are still possible.
As you see no loops nor MAGIC, nor memory access (as the RAYMASK) is coded into the program.
Guess this should be faster compared with MAGIC in the end.
A pity there is no simple way to detect the MSB alike the LSB.

There are many roads leading to Rome, I will leave my move-generator like it is for the time being, otherwise I will never get my program to play.
I see you are using BitScanForward64() and BitScanReverse64(), I use the _tzcnt_u64() and _lzcnt_u64() (BMI1) instructions which perform (in my case) a little bit better.
What do you mean by MSB()? in the terminology I use it is the most significant bit-number, I guess you want to isolate or extract that bit?
The fastest way to get the MSB is probably 0x8000000000000000 >> _lzcnt_u64(bitboard);

Since I want to start programming the DXP protocol I tried yesterday evening to get the Damage 2015 GUI running with one of the engines supplied (Horizon40, Horizon45 and Scan20) but I could not get the communication via localhost (127.0.0.1) to work.
At a certain point I had to allow your GUI to get past the firewall, but that was the only thing that happened, I use the latest version of Windows 10 (build 14393.51), are there special things I have to look at and what is the best order to start things, GUI first or engine first?

Joost

Edit:

After allowing scan20 through the firewall as well there seems to be a connection between scan20 and the GUI, but whatever I try I cannot get the engine to move, probably my fault because I have no clue what I'm doing.
Too many variables, and what is hub and guide?

[BertTuyt]

Couldnt resist to also include the RAYMASK method (again credits to Harm, as I have seen this method in his source code), in the KingNextCapture routines.
See below output (for the Peft 2 Position Perft(9) ), which is ( I guess) quite fast on a 2.7 GHZ Laptop.

Code: Select all

Perft(1)        N = 14     0.00 sec.    KN/sec = 0
Perft(2)        N = 55     0.00 sec.    KN/sec = 0
Perft(3)        N = 1168           0.00 sec.    KN/sec = 0
Perft(4)        N = 5432           0.00 sec.    KN/sec = 0
Perft(5)        N = 87195          0.00 sec.    KN/sec = 0
Perft(6)        N = 629010         0.00 sec.    KN/sec = 0
Perft(7)        N = 9041010        0.04 sec.    KN/sec = 226025
Perft(8)        N = 86724219       0.46 sec.    KN/sec = 188530
Perft(9)        N = 1216917193     5.91 sec.    KN/sec = 205908

Will have a look at the Damage GUI later, and will post a reply.

Bert

[BertTuyt]

And here the link towards the dropbox folder containing the latest Perft(), including sources.

Bert

https://www.dropbox.com/sh/2stq4b20k64w ... JyUNa?dl=0

[Joost Buijs]

Will have a look at the Damage GUI later, and will post a reply.
Bert

What I would like to know is what the various DXP buttons (Make, Wait, Run, Terminate) are doing.
I already saw that with 'Wait' it starts to wait for a connection and when I start an engine after this it does connect, but I have no clue who should be initiator and follower.
With 'Terminate' the connection terminates, but this is all I could get out of it.

There is another option 'Engine Load on Start' which uses Port 27553 at default, when I put this on 'Recent Engine' I assumes it want to connect to an engine that is already running? And should this engine be initiator or follower?

I'm halfway finished with my DXP implementation, when this is finished (hopefully this weekend) it will be a lot easier to see what commands your GUI sends.

Joost

[Joost Buijs]

And here the link towards the dropbox folder containing the latest Perft(), including sources.

Bert

https://www.dropbox.com/sh/2stq4b20k64w ... JyUNa?dl=0

Ok... I will compile it and let you know the results somewhat later. I believe you that raymask can be faster as magics (less memory accesses), but I don't think it will add much in playing strength (if any).
Right now my move-generator is working very fast and I will leave it like it is.

There is probably a lot more to gain by a smart index function for the structure evaluation because the standard way: index = a; index *= 3; index += b; index *= 3; etc. is slow like molasses.

Joost

The results are indeed very fast for 3600 MHz.

Code: Select all

Perft(1)        N = 9      0.00 sec.    KN/sec = 0
Perft(2)        N = 81     0.00 sec.    KN/sec = 0
Perft(3)        N = 658    0.00 sec.    KN/sec = 0
Perft(4)        N = 4265           0.00 sec.    KN/sec = 0
Perft(5)        N = 27117          0.00 sec.    KN/sec = 0
Perft(6)        N = 167140         0.00 sec.    KN/sec = 0
Perft(7)        N = 1049442        0.00 sec.    KN/sec = 0
Perft(8)        N = 6483961        0.04 sec.    KN/sec = 162099
Perft(9)        N = 41022423       0.25 sec.    KN/sec = 164089
Perft(10)       N = 258895763      1.60 sec.    KN/sec = 161809
Perft(11)       N = 1665861398     9.99 sec.    KN/sec = 166752


Perft(1)        N = 14     0.00 sec.    KN/sec = 0
Perft(2)        N = 55     0.00 sec.    KN/sec = 0
Perft(3)        N = 1168           0.00 sec.    KN/sec = 0
Perft(4)        N = 5432           0.00 sec.    KN/sec = 0
Perft(5)        N = 87195          0.00 sec.    KN/sec = 0
Perft(6)        N = 629010         0.00 sec.    KN/sec = 0
Perft(7)        N = 9041010        0.03 sec.    KN/sec = 301367
Perft(8)        N = 86724219       0.35 sec.    KN/sec = 247783
Perft(9)        N = 1216917193     4.79 sec.    KN/sec = 254053


Perft(1)        N = 6      0.00 sec.    KN/sec = 0
Perft(2)        N = 12     0.00 sec.    KN/sec = 0
Perft(3)        N = 30     0.00 sec.    KN/sec = 0
Perft(4)        N = 73     0.00 sec.    KN/sec = 0
Perft(5)        N = 215    0.00 sec.    KN/sec = 0
Perft(6)        N = 590    0.00 sec.    KN/sec = 0
Perft(7)        N = 1944           0.00 sec.    KN/sec = 0
Perft(8)        N = 6269           0.00 sec.    KN/sec = 0
Perft(9)        N = 22369          0.00 sec.    KN/sec = 0
Perft(10)       N = 88050          0.00 sec.    KN/sec = 0
Perft(11)       N = 377436         0.00 sec.    KN/sec = 0
Perft(12)       N = 1910989        0.02 sec.    KN/sec = 95549
Perft(13)       N = 9872645        0.09 sec.    KN/sec = 109696
Perft(14)       N = 58360286       0.53 sec.    KN/sec = 110113
Perft(15)       N = 346184885      3.03 sec.    KN/sec = 114252

[Joost Buijs]

Just for fun I changed my perft() function from semi bulk-counting to true bulk-counting and it seems that the very simple operation of storing the moves already takes 30% of the time.
Now my results at 3600 MHz. are:

Code: Select all

    m  m  m  m  m
  m  m  m  m  m
    m  m  m  m  m
  m  m  m  m  m
    -  -  -  -  -
  -  -  -  -  -
    M  M  M  M  M
  M  M  M  M  M
    M  M  M  M  M
  M  M  M  M  M

perft( 1)  nodes            9  time  0.0000000  nps         0
perft( 2)  nodes           81  time  0.0000007  nps 118652445
perft( 3)  nodes          658  time  0.0000024  nps 275390860
perft( 4)  nodes         4265  time  0.0000229  nps 186494446
perft( 5)  nodes        27117  time  0.0001403  nps 193295386
perft( 6)  nodes       167140  time  0.0008803  nps 189867540
perft( 7)  nodes      1049442  time  0.0054627  nps 192110706
perft( 8)  nodes      6483961  time  0.0346719  nps 187008956
perft( 9)  nodes     41022423  time  0.2147855  nps 190992495
perft(10)  nodes    258895763  time  1.3433841  nps 192719090
perft(11)  nodes   1665861398  time  8.4509955  nps 197120138
perft(12)  nodes  10749771911  time 53.5439661  nps 200765328

    -  -  -  -  -
  M  -  -  M  M
    M  -  -  -  -
  -  k  -  -  M
    M  M  M  k  -
  -  -  -  -  M
    K  -  M  -  -
  -  M  -  -  -
    M  M  M  M  -
  M  -  -  -  -

perft( 1)  nodes           14  time  0.0000249  nps    561858
perft( 2)  nodes           55  time  0.0000157  nps   3502890
perft( 3)  nodes         1168  time  0.0000171  nps  68437558
perft( 4)  nodes         5432  time  0.0000519  nps 104697869
perft( 5)  nodes        87195  time  0.0002935  nps 297039906
perft( 6)  nodes       629010  time  0.0028259  nps 222587789
perft( 7)  nodes      9041010  time  0.0287262  nps 314729935
perft( 8)  nodes     86724219  time  0.3061938  nps 283233072
perft( 9)  nodes   1216917193  time  4.0037437  nps 303944826
perft(10)  nodes  13106503411  time 42.6710454  nps 307152152

    -  -  -  -  -
  -  -  -  -  -
    -  m  m  m  -
  m  -  m  m  -
    m  -  m  m  M
  m  M  M  -  M
    -  M  M  M  M
  -  M  M  -  -
    -  -  -  -  -
  -  -  -  -  -

perft( 1)  nodes            6  time  0.0000000  nps         0
perft( 2)  nodes           12  time  0.0000010  nps  11718760
perft( 3)  nodes           30  time  0.0000010  nps  29296900
perft( 4)  nodes           73  time  0.0000034  nps  21386737
perft( 5)  nodes          215  time  0.0000075  nps  28631061
perft( 6)  nodes          590  time  0.0000181  nps  32613530
perft( 7)  nodes         1944  time  0.0000430  nps  45200931
perft( 8)  nodes         6269  time  0.0001260  nps  49772972
perft( 9)  nodes        22369  time  0.0003867  nps  57841338
perft(10)  nodes        88050  time  0.0012687  nps  69399840
perft(11)  nodes       377436  time  0.0046111  nps  81854354
perft(12)  nodes      1910989  time  0.0188303  nps 101484680
perft(13)  nodes      9872645  time  0.0892972  nps 110559450
perft(14)  nodes     58360286  time  0.4671504  nps 124928245
perft(15)  nodes    346184885  time  2.7377518  nps 126448602
perft(16)  nodes   2272406115  time 16.3555820  nps 138937649
perft(17)  nodes  14962263728  time 107.9974048  nps 138542808

[BertTuyt]

Joost, first of all you are fully right that further improvement of the MoveGenerator will not yield any improvement of the overall playing strength.

On the other hand it is fun to find new creative ways. And I also found that the principle less is more is also applicable here.
Think there is still further improvement possible, but may be not so much.

If you omit the move storage on the last ply in the case of bulk counting and only do a count of moves, which I guess only works for a non-capture as move duplication for a capture is a little more tricky) (although only relevant if the number of captured opponents is 4 or more), you see indeed a further speed increase .

So maybe we need a trick for faster move storage. I thought if we could use 256 bit storage instructions, so we could access memory with 1 call, but i never tried.

Bert

[Joost Buijs]

Bert,

Memory accesses are very complex on modern CPU's with prefetching, 3 levels of cache and out of order execution. I have the feeling that there won't be much difference between four 64 bit stores or one 256 bit store, and don't underestimate how smart the compilers are nowadays.

For perft() alone I can optimize it even further, it might be a nice experiment to make it multiprocessor and to add hashing to it, although I suspect that hashing will slow the speed down enormously.

Joost

[BertTuyt]

Joost,

Perft() optimization is indeed possible with Full Bulk counting (so dont store the Moves at Ply 1), parallel Perft(),and Hash-like implementation.
But from that moment onwards you are optimizing Perft() and not the MoveGenerator().
So that is also not the way forward for me, as I want to check if my MoveGenerator() has bugs and how fast it is compared with others.

Bert

[Joost Buijs]

Bert,

You are right, it is not my intention to make the fastest perft() possible, it is just a means of checking my move-generator, however as a side project it can be a nice experiment.

In the chess forum Aart Bik is talking about perft() for checkers 8x8, also checkers 10x10 is mentioned, there is some interest in calculating perft() for high depths.

http://talkchess.com/forum/viewtopic.php?t=27814

Joost

[Joost Buijs]

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

Hi Bert,

Last week I tried several simple hashing schemes including BCH codes, unfortunately they are all behaving very badly with respect to collisions.
I guess I have to revert back to Zobrist hashing, the problem is that the capture sequences in draughts are rather lengthy, because of this the engine will slow down considerably when updating the hash incrementally.

Maybe the best alternative is to omit updating the hash and probing the table in quiescence, in my chess engine I hardly notice improvement by probing in quiescence, the improvement by probing is cancelled out by the decreased speed.

Do you have any thoughts about this?

Maybe there is a possibility to use magic multiplication to calculate an index into a table with Zobrist numbers without the need to loop over the captured pieces each time.

Joost

[Rein Halbersma]

I guess I have to revert back to Zobrist hashing, the problem is that the capture sequences in draughts are rather lengthy, because of this the engine will slow down considerably when updating the hash incrementally.

I never noticed this as a bottleneck. Is it really that bad? E.g. a regular move has 3 bits to update (color, from, dest), and a capture with N pieces only 1 bit per piece extra (1 more if it's a king). It's been a while since I measured the average number of captured pieces, but IIRC, it was around 2.