Perft speed and depth questions

[ajaxuk]

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

[brianr]

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]

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.

[abulmo2]

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.

[fabianVDW]

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

[phhnguyen]

...

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.

[brianr]

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.

[JVMerlino]

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.

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]

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]

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

@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.