Perfromance diff between legal / illegal move generator

[MahmoudUthman]

I'm currently using a completely legal move generator and it's quiet fast , compared to the others I tested , is it worth the effort to change the code to use a pseudo legal one ? In other words can a completely legal move generator constitute bottleneck on the long run ?

[kbhearn]

Unless your move generator is slow enough that speeding it up would speed up your program by an order of magnitude, you probably shouldn't worry about it at an early point in your engine's development. If it is order of magnitude size then you should probably find out why so you don't repeat that pattern elsewhere too :)

[Sven]

I'm currently using a completely legal move generator and it's quiet fast , compared to the others I tested , is it worth the effort to change the code to use a pseudo legal one ? In other words can a completely legal move generator constitute bottleneck on the long run ?

How do you ensure legality:
a) by making/unmaking each move and testing whether it leaves the king in check, or
b) by only doing this for the small set of moves that could actually be illegal (king moves, check evasions, ep captures, and moves of pinned pieces), or
c) by doing clever move generation that knows how to avoid generating illegal moves?
Only in case of a) I'd say you should spend effort to improve speed, since that could be done an order of magnitude faster, e.g. like b). Otherwise I'd keep it as it is, provided it is correct

[matthewlai]

I'm currently using a completely legal move generator and it's quiet fast , compared to the others I tested , is it worth the effort to change the code to use a pseudo legal one ? In other words can a completely legal move generator constitute bottleneck on the long run ?

Don't guess, profile, and you'll know for sure.

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

If you see that legality checking is using up 30% of the time, obviously changing it will help. If it's only using 2%, it won't.

[Joost Buijs]

I'm currently using a completely legal move generator and it's quiet fast , compared to the others I tested , is it worth the effort to change the code to use a pseudo legal one ? In other words can a completely legal move generator constitute bottleneck on the long run ?

Usually the move-generator takes only a very small fraction of the time the engine spends overall. For instance in my engine the move-generator (on a single core) runs at 100 to 150 million moves/sec. (including do and undo move) while the whole engine does maybe 2.5 million nodes/sec.
Most of the time is spend on evaluation, probing the hash-table, and SEE() is also a notorious time eater. When the move-generator is somewhat slow you will hardly notice it on engine performance.

[hgm]

That doesn't really mean much, because most of the moves that are generated are not made, in an engine. And the 2.5Mnps only includes the moves that are made.

For each move you do make, you would typically run the move generator, to see if there are more moves you can make. So you would run the move generator 2.5M times/sec. If that would generate 30 moves on average every time you run it, it would be generating 75M moves/sec while running the engine. And that is not such a small fraction on 150M/sec.

[MahmoudUthman]

Unless your move generator is slow enough that speeding it up would speed up your program by an order of magnitude, you probably shouldn't worry about it at an early point in your engine's development. If it is order of magnitude size then you should probably find out why so you don't repeat that pattern elsewhere too

by size do you mean code size ? 325 lines "including comments"

How do you ensure legality:
a) by making/unmaking each move and testing whether it leaves the king in check, or
b) by only doing this for the small set of moves that could actually be illegal (king moves, check evasions, ep captures, and moves of pinned pieces), or
c) by doing clever move generation that knows how to avoid generating illegal moves?
Only in case of a) I'd say you should spend effort to improve speed, since that could be done an order of magnitude faster, e.g. like b). Otherwise I'd keep it as it is, provided it is correct

c , does b hold any measureable advantage over c ?

Don't guess, profile, and you'll know for sure.

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

If you see that legality checking is using up 30% of the time, obviously changing it will help. If it's only using 2%, it won't.

I'm not doing a legality checking, I'm doing what Sven mentioned above "C"
, the entire move generator takes 4.41% of the total execution time , I guess this is good enough ,right ?!

Usually the move-generator takes only a very small fraction of the time the engine spends overall. For instance in my engine the move-generator (on a single core) runs at 100 to 150 million moves/sec. (including do and undo move) while the whole engine does maybe 2.5 million nodes/sec.
Most of the time is spend on evaluation, probing the hash-table, and SEE() is also a notorious time eater. When the move-generator is somewhat slow you will hardly notice it on engine performance.

I know it's not one of the most important factors but it has to count for something as pointed out by H.G.Muller , especially at extremely fast time controls ?

[kbhearn]

by size do you mean code size ? 325 lines "including comments"

I meant execution time. Making your program twice as fast can be a worthwhile investment of your time. 10% faster? not a big deal until you're scraping for every little bit of elo.

I'm not doing a legality checking, I'm doing what Sven mentioned above "C"
, the entire move generator takes 4.41% of the total execution time , I guess this is good enough ,right ?!

Then if it's correct, move on. Even if you made it take no time your program would only be 5% faster...

I know it's not one of the most important factors but it has to count for something as pointed out by H.G.Muller , especially at extremely fast time controls ?

Something but there's much bigger somethings early in an engine's development than speed. Look at it from the perspective of

time = constant * branching factor ^ depth

There is much more to be gained early from targetting the branching factor (move ordering, reductions/pruning) and the required depth to notice problems/opportunities (eval) than there is to playing with the constant term (speed optimisations). There's no reason to allow things to be grotesquely slow, but it's a waste of effort to obsess over it before you hit the point where there's not much to do elsewhere.

[Joost Buijs]

That doesn't really mean much, because most of the moves that are generated are not made, in an engine. And the 2.5Mnps only includes the moves that are made.

For each move you do make, you would typically run the move generator, to see if there are more moves you can make. So you would run the move generator 2.5M times/sec. If that would generate 30 moves on average every time you run it, it would be generating 75M moves/sec while running the engine. And that is not such a small fraction on 150M/sec.

This is partially true, in my engine (like probably in most engines) doing and undoing the moves cost more time than generating them, the numbers I showed were including move-do/move-undo, the sole move-generator runs much faster than 150 Mnps.
Staged move-generation has a big influence as well, I generate captures before the rest of the moves, usually the number of captures is small and in many cases after trying a capture there is an immediate cutoff.
Another thing is that in case of a hash-hit with a subsequent cutoff on score or after trying the hash-move (which happens very often) you don't have to generate moves at all.

The best way to determine the move-gen ratio is by profiling, and I can assure you that in my engine the overhead of the move-generator compared to the things I mentioned above is so small that making it 20 or 30% slower won't hurt engine performance significantly.

Of course I can only speak for my own engine, maybe your numbers look different.

[kinderchocolate]

Most moves aren't used in chess engine because they are pruned. Pseudo-legal is important, and you'll need it sooner or later. However, there're probably other things more worth for your time. Your don't have an engine until you have at least alpha-beta implemented...