Compiling qperft as c++ code

[Ajedrecista]

Hello Stefano:

Embedding quick perft in my engine has speed-up development and this doesn't find bugs only in Satana, but in qperft too!!!

In this position, qperft gives me the wrong count, both in the embedded and in the command line version:

FEN: k7/8/8/8/8/8/3b1P2/4K3 w

Satana reports 4 while perft reports 6:

Code: Select all

D:\A\Cpp\Scacchi\AltriMotori>perft 1 "k7/8/8/8/8/8/3b1P2/4K3 w"
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - k . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . b . P . . - -
 - - . . . . K . . . - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=            6 ( 0.000 sec)

Good catch! I also spotted a bug in qperft which people said it was due to hashing. These little things do not fog the great work by HGM.

Using JetChess in this position, just for verification purposes:

Code: Select all

k7/8/8/8/8/8/3b1P2/4K3 w - -

Only moves: Kf1, Kd1, Kxd2, Ke2.

 perft(1) =                          4
 perft(2) =                         39
 perft(3) =                        244
 perft(4) =                      2,653
 perft(5) =                     17,386
 perft(6) =                    202,238
 perft(7) =                  1,390,017
 perft(8) =                 17,262,346
 perft(9) =                119,631,160
perft(10) =              1,555,125,531
perft(11) =             10,835,983,182
perft(12) =            145,708,543,492
perft(13) =          1,015,505,344,951
perft(14) =         13,975,998,741,382
perft(15) =         97,423,123,713,706
perft(16) =      1,361,998,961,400,591
perft(17) =      9,519,034,301,245,381
perft(18) =    134,399,711,650,205,020
perft(19) =    949,523,553,081,699,655
perft(20) = 13,466,358,044,176,829,892

The original output for perft(20) was:

Code: Select all

  1  Ke1-f1  3898242640434849350
  2  Ke1-d1  3493098502582001309
  3  Ke1*d2  9907521647705099
  4  Ke1-e2  6065109379512274134

Total:   -4980386029532721724

-4.980.386.029.532.721.724   (Move pathes after 20 half moves)

Time: 932.302 s

There was an integer overflow but adding the sub-perft values (which do not have integer overflows, simply seeing the branching factors) gives the result perft(20) ~ 1.3466e+19.

Of course: 2^(64) - 4,980,386,029,532,721,724 = 13,466,358,044,176,829,892 (as expected, so there was an overflow only).

I hope no typos.

Regards from Spain.

Ajedrecista.

[Rein Halbersma]

I guess qperft does not work for positions where you are in check. Amazing that no one noticed this before. But check detection is done based on the previous move, passed to it from the parent node. But in the root there is no previous mode. So it fails to detect contact checks there. (Distant slider checks are always recognized as a side effect of pin detection.)

So some code should be added for detecting contact checks in the given position, and if there are, pass the location of the checker (as to-square of the 'lastPly' argument) to the perft call.

In fact it is very strange that a software used for years have such a "simple" bug. The bug occurs anytime the actual color is in check and the piece that give check is near the king. This happens frequently if you call qperft at any ExecuteMove, as i have to do.

For now, i've removed the embedded qperft function and i use an old version of satana, that is slower but with a good perft.

From a modern software engineering perspective it is not very surprising that such move generation bugs are not discovered through perft() testing. Perft() is a bit of "hit and hope" (or "random sampling", depending whether you want to use fancy words) and cannot really cover all the critical cases that systematic and exhaustive (in the sense of e.g. generating all three piece positions) unit testing of corner cases will do.

[hgm]

Good catch! I also spotted a bug in qperft which people said it was due to hashing.

Note that when it is due to hashing, it is not necessarily a bug. The hashing is intrinsically unreliable, because you can get key collisions.

[zullil]

Using JetChess in this position, just for verification purposes:

Code: Select all

k7/8/8/8/8/8/3b1P2/4K3 w - -

Only moves: Kf1, Kd1, Kxd2, Ke2.

 perft(1) =                          4
 perft(2) =                         39
 perft(3) =                        244
 perft(4) =                      2,653
 perft(5) =                     17,386
 perft(6) =                    202,238
 perft(7) =                  1,390,017
 perft(8) =                 17,262,346
 perft(9) =                119,631,160
perft(10) =              1,555,125,531
perft(11) =             10,835,983,182
perft(12) =            145,708,543,492
perft(13) =          1,015,505,344,951
perft(14) =         13,975,998,741,382
perft(15) =         97,423,123,713,706
perft(16) =      1,361,998,961,400,591
perft(17) =      9,519,034,301,245,381
perft(18) =    134,399,711,650,205,020
perft(19) =    949,523,553,081,699,655
perft(20) = 13,466,358,044,176,829,892

I hope no typos.

Regards from Spain.

Ajedrecista.

I got the same total for perft(10). But that already took more than a minute. So I won't be confirming any others.

[stegemma]

I can confirm with satana up to ply 10 me too, in about 56 seconds:

Code: Select all

 FEN: k7/8/8/8/8/8/3b1P2/4K3 w -
perft 1 Nodes: 4, Time: 0 ms, Nodes/s: 4000
perft 2 Nodes: 39, Time: 0 ms, Nodes/s: 39000
perft 3 Nodes: 244, Time: 0 ms, Nodes/s: 244000
perft 4 Nodes: 2653, Time: 0 ms, Nodes/s: 2653000
perft 5 Nodes: 17386, Time: 1 ms, Nodes/s: 8693000
perft 6 Nodes: 202238, Time: 9 ms, Nodes/s: 20223800
perft 7 Nodes: 1390017, Time: 70 ms, Nodes/s: 19577704
perft 8 Nodes: 17262346, Time: 640 ms, Nodes/s: 26930336
perft 9 Nodes: 119631160, Time: 5794 ms, Nodes/s: 20643858
perft 10 Nodes: 1555125531, Time: 56936 ms, Nodes/s: 27313092

[Sven]

I guess qperft does not work for positions where you are in check. Amazing that no one noticed this before. But check detection is done based on the previous move, passed to it from the parent node. But in the root there is no previous mode. So it fails to detect contact checks there. (Distant slider checks are always recognized as a side effect of pin detection.)

So some code should be added for detecting contact checks in the given position, and if there are, pass the location of the checker (as to-square of the 'lastPly' argument) to the perft call.

Please don't forget knight checks.

[ibid]

Good catch! I also spotted a bug in qperft which people said it was due to hashing. These little things do not fog the great work by HGM. ;)

Using JetChess in this position, just for verification purposes:

Code: Select all

k7/8/8/8/8/8/3b1P2/4K3 w - -

Only moves: Kf1, Kd1, Kxd2, Ke2.

 perft(1) =                          4
 perft(2) =                         39
 perft(3) =                        244
 perft(4) =                      2,653
 perft(5) =                     17,386
 perft(6) =                    202,238
 perft(7) =                  1,390,017
 perft(8) =                 17,262,346
 perft(9) =                119,631,160
perft(10) =              1,555,125,531
perft(11) =             10,835,983,182
perft(12) =            145,708,543,492
perft(13) =          1,015,505,344,951
perft(14) =         13,975,998,741,382
perft(15) =         97,423,123,713,706
perft(16) =      1,361,998,961,400,591
perft(17) =      9,519,034,301,245,381
perft(18) =    134,399,711,650,205,020
perft(19) =    949,523,553,081,699,655
perft(20) = 13,466,358,044,176,829,892

Ajedrecista.

Not sure if this is a known bug or not, but JetChess has a related issue:

[d]rnbqkbnr/ppN5/3ppppp/8/B3P3/8/PPPP1PPP/R1BQK1NR b KQkq - 0 6

It sees 7 moves here, missing the double check...

-paul

[stegemma]

[...]
Not sure if this is a known bug or not, but JetChess has a related issue:

[d]rnbqkbnr/ppN5/3ppppp/8/B3P3/8/PPPP1PPP/R1BQK1NR b KQkq - 0 6

It sees 7 moves here, missing the double check...

-paul

I've completed yesterday the new move generator of satana, it seems to be up to 2 times faster than the previous one. Here's my perft for this position:

Code: Select all

FEN: rnbqkbnr/ppN5/3ppppp/8/B3P3/8/PPPP1PPP/R1BQK1NR b KQkq
perft 1 Nodes: 2, Time: 0 ms, Nodes/s: 2000
perft 2 Nodes: 70, Time: 0 ms, Nodes/s: 70000
perft 3 Nodes: 1454, Time: 0 ms, Nodes/s: 1454000
perft 4 Nodes: 51654, Time: 2 ms, Nodes/s: 17218000
perft 5 Nodes: 1171698, Time: 56 ms, Nodes/s: 20556105
perft 6 Nodes: 42212557, Time: 1565 ms, Nodes/s: 26955655
perft 7 Nodes: 1029536265, Time: 44194 ms, Nodes/s: 23295310

Of course the little problem in qperft doesn't diminish its great value, i think that it will be corrected very soon. I would try to do it... but the source are too complex, for me

[stegemma]

PS: and here's my test for check function, i'm very proud of this code because i've worked a lot, to make it works properly. This is just the final version of a number of try and seems to be the faster approach, for my engine:

Code: Select all

...
		#define slideAll   0
		#define slideFirstR 1
		  // dispari > | pari <
			#define slideN  1
			#define slideE  2
			#define slideW  3
			#define slideS  4
		#define slideLastR  4
		#define slideFirstB 5
			// dispari > | pari <
			#define slideNE  5
			#define slideSE  6
			#define slideNW  7 
			#define slideSW  8
		#define slideLastB  8
			// slide riassuntive
			#define slideR    9 
			#define slideB   10
		#define slideLast 11

		uint64_t slides&#91;slideLast&#93;&#91;64&#93;;
		uint64_t knightSquares&#91;64&#93;;
		uint64_t kingSquares&#91;64&#93;;
		uint64_t pawnAttacks&#91;2&#93;&#91;64&#93;;
		uint64_t Brays&#91;64&#93;&#91;64&#93;; // Bishop path from source to dst squares &#40;src square are not included&#41;
		uint64_t Rrays&#91;64&#93;&#91;64&#93;; // Rook path
		uint64_t BFullRays&#91;64&#93;&#91;64&#93;; // Bishop path from source to end of chessboard, passing through dst &#40;src square is not included&#41;
		uint64_t RFullRays&#91;64&#93;&#91;64&#93;; // Rook path to end
...

bool clsEngineSimple2&#58;&#58;CheckSlide&#40;int idx, int slide, uint64_t boType&#41; const
	&#123;
		for &#40;int i = slide; i < slide + 4; i++)
		&#123;
			// slideNE slideSE slideNW slideSW // N E W S
			uint64_t boSlide = slides&#91;i&#93;&#91;idx&#93;;
			uint64_t boOnSlide = boSlide & board.boAllPieces;
			uint64_t boTypeOnSlide = boType & boSlide;
			if &#40;boTypeOnSlide == boEmpty&#41; continue;
			if &#40;boTypeOnSlide == boOnSlide&#41; return true;
			if &#40;i & 1&#41; // slide in direzione > square
			&#123;
				/*   sample     boTypeOn  boOnSlide   -1      &boTypeOn
			  	  ..x.R..+    00001000  00101000  00100111  00000000 != boTypeOn => check
				    ..R.x..+    00100000  00101000  00100111  00100000 == boTypeOn => !check
				    ..Q.R..+    00101000  00101000  00100111  00100000 != boTypeOn => check							*/
				if ((&#40;boOnSlide - 1&#41; & boTypeOnSlide&#41; != boTypeOnSlide&#41;
					return true;
			&#125;
			else
			&#123;
				/*   sample      boTypeOn    boOnSlide  ~boTypeOn
						 +..R....    00010000 >  00010000 & 11101111 = 00000000
						 +..R.x..    00010000 >  00010100 & 11101111 = 00000100
				     +..x.R..    00000100 <  00010100	& 11111011 = 00010000
				*/

				if &#40;boTypeOnSlide > &#40;boOnSlide & ~boTypeOnSlide&#41;)
					return true;
			&#125;
		&#125;
		return false;
	&#125;

	bool clsEngineSimple2&#58;&#58;IsInCheck&#40;const uint64_t boSquare&#41; const
	&#123;
		const uint64_t boOtherPieces = board.boEnemies;
		int idx = GetSquareIndex&#40;boSquare&#41;;

		// CHDEBUG&#40;slides&#91;slideB&#93;&#91;idx&#93;);

		uint64_t boQR = &#40;board.boQueens | board.boRooks&#41;   & boOtherPieces & slides&#91;slideR&#93;&#91;idx&#93;;
		uint64_t boQB = &#40;board.boQueens | board.boBishops&#41; & boOtherPieces & slides&#91;slideB&#93;&#91;idx&#93;;
		if (&#40;pawnAttacks&#91;color&#93;&#91;idx&#93; & board.boPawns & boOtherPieces&#41; != boEmpty&#41; return true;
		if (&#40;knightSquares&#91;idx&#93; & board.boKnights & boOtherPieces&#41; != boEmpty&#41;    return true;
		if (&#40;boQB != boEmpty&#41; && CheckSlide&#40;idx, slideFirstB, boQB&#41;)              return true;
		if (&#40;boQR != boEmpty&#41; && CheckSlide&#40;idx, slideFirstR, boQR&#41;)              return true;
		if (&#40;kingSquares&#91;idx&#93; & board.boKings & boOtherPieces&#41; != boEmpty&#41;        return true;
		return false;
	&#125;

[Sven]

I guess qperft does not work for positions where you are in check. Amazing that no one noticed this before. But check detection is done based on the previous move, passed to it from the parent node. But in the root there is no previous mode. So it fails to detect contact checks there. (Distant slider checks are always recognized as a side effect of pin detection.)

So some code should be added for detecting contact checks in the given position, and if there are, pass the location of the checker (as to-square of the 'lastPly' argument) to the perft call.

Please don't forget knight checks.

And double check, of course. Btw, is double check covered by the current implementation for nodes except the root?

I think an appropriate solution would be to add a root_perft() function that does not require to know the previous move but simply detects whether the moving side is in check. Problem is, also move_gen() takes the previous move as an argument. Extending move_gen() for the "root" case would hurt performance, so the most logical action would be to also maintain a root_move_gen() function. All those side effects on global variables like ep1, ep2, msp, Promo, board, pos, stack, ... would need to be considered, of course, in a way that ensures that the root_*() functions behave like the non-root functions from the viewpoint of a node below the root.

@HGM: Can you ask the author of QPerft to do that?

EDIT: Checked the code again. Knight check is a kind of contact check in QPerft, and double checks are handled as well, at the root and also below the root. So in fact only contact check at the root remains as an open issue.