Perft search speed bottleneck

[Sven]

You should have a look at my code:
https://github.com/lucasart/chess/blob/ ... movegen.cc

It may sound arrogant, but I'm quite confident that it blows away _almost_ anyone's perft here by a margin. About 5 million nodes/second: no hash table, no SMP, no cheating by counting leaves (I count interior nodes and do bulk counting at the leaves, if I coult the leaves, then it's 200 million nodes per second).

Something sounds off for those numbers. On my laptop, Jazz does a 22Mnps perft from the opening position (6-ply perft takes a little over 5 seconds), or 90 Mnps if I use a legal move generator rather than the pseudo-legal one (6-ply in 1.3 seconds, using bulk counting at the leaves). I don't think Jazz is particularly fast, so I'd be surprised if your code is slower, as the numbers you posted suggest...

You misread my post, yet I was very clear (interior nodes, no leaves, bulk counting). Anyway, in order to compare apples to apples, I compute perft(6) in about 0.6 seconds (with bulk counting).

Hi Lucas, my code's recursion returns 1 at depth 0, without any bulk counting ... so my perft's actually counting interior nodes?

No. (Sorry for replying instead of Lucas here ...)
There are two different things you can count in perft:

a) the number of leaves exactly at ply N (regardless whether you actually visit them or "only" know they exist), which is the desired result of the perft run to be compared to a trusted reference number,
b) the number of nodes visited (interior + leaves).

Counting a) is a requirement of the method itself. Counting b) is optional, I would recommend it for the purpose of movegen speed comparison between different programs. Comparing based on a) is less meaningful if only one engine does bulk counting, or if the legality testing methods differ significantly. Numbers for a) are much more impressive, though, when using bulk counting and an efficient legality check ...

For anyone actually comparing perft speeds it is also required to use exactly the same starting position (or to average over the same set of positions) and to use the same hardware.

Sven

[hgm]

Something sounds off for those numbers. On my laptop, Jazz does a 22Mnps perft from the opening position (6-ply perft takes a little over 5 seconds), ...

That is only 1 Mnps. The number you quote is moves/sec, not nodes/sec.

[hgm]

Maybe it would be better (when using perft for the purpose of optimising the move generator) to let perft only count the number of generated pseudo-legal moves at the leaves?

In principle you are right, but the problem is that there is no unique definition of what is a pseudo-legal move.

[Evert]

Something sounds off for those numbers. On my laptop, Jazz does a 22Mnps perft from the opening position (6-ply perft takes a little over 5 seconds), ...

That is only 1 Mnps. The number you quote is moves/sec, not nodes/sec.

Explain?
I count the number of positions reached, which is the same as the number of (legal) moves played.

[hgm]

But you don't do anything in those positions (no move gen, no eval). If you start counting things that take zero time, there is no limit to how many you can do per second...

[Evert]

You misread my post, yet I was very clear (interior nodes, no leaves, bulk counting).

In what way did I misread what you said? I said exactly the same thing you just did...

(i) it makes code cleaner and easier, and there's no post processing. i just straightforwardly compute the target squares so as to never even consider illegal moves

Maybe. It's a bit harder to write a legal move generator though (I know my first attempt was a dismal failure, although it didn't take me very long at all to make one on my second attempt).

you completely avoid the nightmare of filtering pseudo legal moves before playing them

Who does this? It's easier to play the move, realise the king is in check, and unmake/skip the move.
As you say though, speed-wise there doesn't seem to be much of a difference between the two approaches.

[Chan Rasjid]

you completely avoid the nightmare of filtering pseudo legal moves before playing them

Who does this? It's easier to play the move, realise the king is in check, and unmake/skip the move.
As you say though, speed-wise there doesn't seem to be much of a difference between the two approaches.

If I am not wrong, testing whether a move is illegal before making it (what I have in my is_move_valid()) is nothing more complicated than testing if the king is under attack after making the move. In both cases, we have to get the relevant slider attack bitboard. Basically, it is adjusting the allBits by taking away the from bits, adding the to bit. I think even scannnig the rest of the move list for illegal moves with the same from-sq should be easy once a move is found to be invalid (what I posted here earlier).

I have overhead in make/unmake(). But if the % of illegal moves is not high(my 30/40% I posted earlier is likely wrong), then the speed impact may still be slight.

Best Regards,
Rasjid.

[elcabesa]

my engine calculate with a legal move generator 5.8Kmps & 25Knps if at depth=1 I let him return the number of legal moves.

I think you could start with a pseudolegal move generator and after doing a move you could check if the move was legal ( test if the king was left in check). I did this way and my engine could reach over 2500 elo point.

Regarding the speed of your movegen I think it will slow as soon as you'll add some more instructions to your make/unmake move.
I calculate for example material with make/unmake. things like that will slow down your perft but probably will make you engine stronger.
Don't look only at the speed of your perft, even a slow engine could be strong

[tpetzke]

Hi,

an highly optimized function is not necessarily a clear and intuitive function for everybody.

You should use the code you are comfortable with, the impact of speed is usually overestimated. Especially is you are starting an engine.

If you do staged move generation (hash, captures ...) chances that a generated move is a tried move are very high.

Thomas...

[syzygy]

Maybe it would be better (when using perft for the purpose of optimising the move generator) to let perft only count the number of generated pseudo-legal moves at the leaves?

In principle you are right, but the problem is that there is no unique definition of what is a pseudo-legal move.

A solution to that is counting the leaves (as in a normal perft, giving the same numbers) while generating at each leaf all pseudo-legal moves.