Perft speed and depth questions

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, Dann Corbit, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
ajaxuk
Posts: 13
Joined: Tue Jun 09, 2020 4:44 pm
Full name: Mark Buisseret

Perft speed and depth questions

Post by ajaxuk » Thu Jun 11, 2020 5:19 pm

Hi all

I have just started the long journey of programming a Chess engine in c++. I'm not a programmer although I have enough knowledge to wite ugly but working code!

After several days of frustration I think I have a working move generator plus makemove and unmake move,so I can check against the 6 positions on https://www.chessprogramming.org/Perft_Results. So far I have checked up to depths 7,6, 8,6, 5 and 6 respectively with no errors. Can I reasonably assume that most if not all edge cases will have been covered by these depths?

The next is on the topic of speed and whether what I have written so far will be reasonably quick enough to not be the limiting factor later on for thhe rest of the engine. I have done some reading on the subject and my perft function is the most basic flavour with no bulk_counting, hashing or any other tweaks. Perft function below:

Code: Select all

uint64		Board::Perft(int depth)
{
	MoveList moves;
	int nMoves, i;
	uint64 nodes = 0;

	if (depth == 0) return 1;

	nMoves = genMoves(moves);

	for (i = 0; i < nMoves; i++)
	{
		if (makeMove(moves.move[i]))
		{
			nodes += Perft(depth - 1);
			undoMove(moves.move[i]);
		} 
		else
		{
			if (depth==1) nodes += 1;
		}
	}
	return nodes;
}
running on my PC (i7-6850 3.6Ghz) for x86 in Visual Studio I can get Position 1 at depth 7 completed in 228 seconds or 14 million nodes per second.

I can't recall where, but I think I read that the top engines are generating in the region of 200 million nodes per second.

It's a very subjective question but is 14 million a reasonable starting point to continue developing the rest of the engine?

Thanks for any pointers in the right directions :D

brianr
Posts: 453
Joined: Thu Mar 09, 2006 2:01 pm

Re: Perft speed and depth questions

Post by brianr » Thu Jun 11, 2020 6:19 pm

While correctly working code is most important, 14M nps seems a little on the slow side.
Tinker is far from the fastest at perft, but it is about 95M nps on a 3.6GHz CPU.
Move generation in Tinker is done with magic bitboards, BTW.

MOBMAT
Posts: 327
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: Perft speed and depth questions

Post by MOBMAT » Thu Jun 11, 2020 6:29 pm

What is your goal here?

Do you want to try to have the fastest perft, or just have a good working move generator?

Remember the old coding adage... first make it work, then make it faster.

Looking at your perft code, you are looping though your moves based on an index. Once you get the rest of your program finished, you won't be retrieving moves that way, because you will want to try moves based on some kind of move ordering.

So, your perft is fine for testing out your move generation (you want to try all the moves), but I wouldn't get hung up on how fast it is. You can try other techniques that might speed things up, but make sure they don't break the perft score.

Take baby steps and try to get a complete engine working with a known good move generator. Then you'll have all the time in the world to try to make it smarter and faster....no, i mean it will take all the time in the world LOL.
i7-6700K @ 4.00Ghz (using 6 threads), EGTBs on PCI SSD
Benchmark: Stockfish 11 64 bmi2 (nps): 2067669

abulmo2
Posts: 287
Joined: Fri Dec 16, 2016 10:04 am
Contact:

Re: Perft speed and depth questions

Post by abulmo2 » Thu Jun 11, 2020 8:33 pm

brianr wrote:
Thu Jun 11, 2020 6:19 pm
While correctly working code is most important, 14M nps seems a little on the slow side.
Tinker is far from the fastest at perft, but it is about 95M nps on a 3.6GHz CPU.
Move generation in Tinker is done with magic bitboards, BTW.
95M nps without bulk counting is very fast. 14 Mnps looks like a good start. On my computer, stockfish-8 does 180 Mnps, but with bulk counting. That's about 15M nps without bulk counting. So 14 M nps is not very far from the speed of the move generator of one of the strongest engine.
Richard Delorme

fabianVDW
Posts: 142
Joined: Fri Mar 15, 2019 7:46 pm
Location: Germany
Full name: Fabian von der Warth

Re: Perft speed and depth questions

Post by fabianVDW » Thu Jun 11, 2020 9:59 pm

abulmo2 wrote:
Thu Jun 11, 2020 8:33 pm
brianr wrote:
Thu Jun 11, 2020 6:19 pm
While correctly working code is most important, 14M nps seems a little on the slow side.
Tinker is far from the fastest at perft, but it is about 95M nps on a 3.6GHz CPU.
Move generation in Tinker is done with magic bitboards, BTW.
95M nps without bulk counting is very fast. 14 Mnps looks like a good start. On my computer, stockfish-8 does 180 Mnps, but with bulk counting. That's about 15M nps without bulk counting. So 14 M nps is not very far from the speed of the move generator of one of the strongest engine.
Not sure where you got those numbers from...
FabChess has ~150mnps on startpos with bulk counting, this turns out at ~35mnps without bulk counting. I am expecting SF speed to be similar higher, or if it is lower then it will be due to unnecessary work done at leafs for initiializing info like pinned pieces etc. (which is not needed in leaves in perft). Then it would be more fair to use bulk counting to evaluate SF's speed though
Author of FabChess: https://github.com/fabianvdW/FabChess
A UCI compliant chess engine written in Rust.
FabChessWiki: https://github.com/fabianvdW/FabChess/wiki
fabianvonderwarth@gmail.com

User avatar
phhnguyen
Posts: 858
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: Perft speed and depth questions

Post by phhnguyen » Thu Jun 11, 2020 10:14 pm

ajaxuk wrote:
Thu Jun 11, 2020 5:19 pm
...

Code: Select all

uint64		Board::Perft(int depth)
{
	MoveList moves;
	int nMoves, i;
	uint64 nodes = 0;

	if (depth == 0) return 1;

	nMoves = genMoves(moves);

	for (i = 0; i < nMoves; i++)
	{
		if (makeMove(moves.move[i]))
		{
			nodes += Perft(depth - 1);
			undoMove(moves.move[i]);
		} 
		else
		{
			if (depth==1) nodes += 1;
		}
	}
	return nodes;
}
...
I assumed your function makeMove returns false when the move is illegal (can't be made or make its side be checked). The ambiguity is that how comes you can increase the nodes when that function false? Of course, you know your code and so far the most important it can produce all correct results. Just curious as a code reviewer.
https://banksiagui.com
A freeware chess GUI, based on opensource Banksia - the chess tournament manager

brianr
Posts: 453
Joined: Thu Mar 09, 2006 2:01 pm

Re: Perft speed and depth questions

Post by brianr » Thu Jun 11, 2020 10:20 pm

abulmo2 wrote:
Thu Jun 11, 2020 8:33 pm
brianr wrote:
Thu Jun 11, 2020 6:19 pm
While correctly working code is most important, 14M nps seems a little on the slow side.
Tinker is far from the fastest at perft, but it is about 95M nps on a 3.6GHz CPU.
Move generation in Tinker is done with magic bitboards, BTW.
95M nps without bulk counting is very fast. 14 Mnps looks like a good start. On my computer, stockfish-8 does 180 Mnps, but with bulk counting. That's about 15M nps without bulk counting. So 14 M nps is not very far from the speed of the move generator of one of the strongest engine.
You are correct.
I posted the bulk counting number (95M nps).
The "regular" perft speed is 23M nps, so 14M is quite good for a new engine.

User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Perft speed and depth questions

Post by JVMerlino » Thu Jun 11, 2020 10:53 pm

As others have said, the most important thing is for it to be 100% correct. What hasn't been mentioned, and you may not be aware of, is how little CPU time an engine spends in move generation. With most engines, you could double the speed of the generator and only gain a handful of ELO.

Yours already seems perfectly fast. My very mediocre engine does only about 50M NPS with bulk counting, but that's because it's a full legal generator AND flags moves that give check. Something I added when I was first working on it many years ago and never bothered to improve. :oops:

Here are a few other quirky positions to try:

8/p7/8/1P6/K1k3p1/6P1/7P/8 w - - // Perft(8) == 8,103,790
n1n5/PPPk4/8/8/8/8/4Kppp/5N1N b - - // Perft(6) == 71,179,139
r3k2r/p6p/8/B7/1pp1p3/3b4/P6P/R3K2R w KQkq - // Perft(6) == 77,054,993
8/5p2/8/2k3P1/p3K3/8/1P6/8 b - - // Perft(8) == 64,451,405
r3k2r/pb3p2/5npp/n2p4/1p1PPB2/6P1/P2N1PBP/R3K2R w KQkq - // Perft(5) == 29,179,893

zullil
Posts: 6442
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: Perft speed and depth questions

Post by zullil » Thu Jun 11, 2020 11:05 pm

My legal move generator with bulk counting on a 3.10 GHz cpu:

./perft
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Depth = 7
Leaf nodes = 3195901860
Time taken = 50458 ms

~63 Mnps

ajaxuk
Posts: 13
Joined: Tue Jun 09, 2020 4:44 pm
Full name: Mark Buisseret

Re: Perft speed and depth questions

Post by ajaxuk » Fri Jun 12, 2020 6:02 am

Thank you everyone for your responses.

@phhnguyen good spot!
My genMove function only produces legal moves butI originally had in my makeMove function a routine that looked forward after the move was played to see if the opponent was in checkmate - simply checking if the opponents genMove returned zero moves. If it did return zero moves then makeMove returned false and I wanted to count the node (assuming at the end of the depth). It was a bit convoluted and at an early stage of development when I was lucky to get correct results at Perft(2) or more! I should have deleted the code in the Perft functions. It currently never returns false but now deleted the superflous code - thanks!

@MOBMAT
My initial goal is a chess engine that can beat me so I have set my sights at the lowest possible level :D

@JVMerlino
Thank you for those positions, I must admit I was slightly nervous when testing them, but it passed them all so I can sleep easier :)

In conlcusion and based on the comments I think I will move to the next step and call moveGen finished (at least for now).

Thank you.

Post Reply