Perfromance diff between legal / illegal move generator
Moderators: hgm, Rebel, chrisw
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Perfromance diff between legal / illegal move generator
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 ?
-
- Posts: 411
- Joined: Thu Dec 30, 2010 4:48 am
Re: Perfromance diff between legal / illegal move generator
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 :)
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Perfromance diff between legal / illegal move generator
How do you ensure legality:MahmoudUthman wrote: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 ?
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
-
- Posts: 793
- Joined: Sun Aug 03, 2014 4:48 am
- Location: London, UK
Re: Perfromance diff between legal / illegal move generator
Don't guess, profile, and you'll know for sure.MahmoudUthman wrote: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 ?
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.
Disclosure: I work for DeepMind on the AlphaZero project, but everything I say here is personal opinion and does not reflect the views of DeepMind / Alphabet.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Perfromance diff between legal / illegal move generator
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.MahmoudUthman wrote: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 ?
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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perfromance diff between legal / illegal move generator
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.
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.
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Perfromance diff between legal / illegal move generator
by size do you mean code size ? 325 lines "including comments"kbhearn wrote: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
c , does b hold any measureable advantage over c ?Sven Schüle wrote: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
I'm not doing a legality checking, I'm doing what Sven mentioned above "C"matthewlai wrote: 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.
, the entire move generator takes 4.41% of the total execution time , I guess this is good enough ,right ?!
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 ?Joost Buijs wrote: 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.
-
- Posts: 411
- Joined: Thu Dec 30, 2010 4:48 am
Re: Perfromance diff between legal / illegal move generator
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.MahmoudUthman wrote: by size do you mean code size ? 325 lines "including comments"
Then if it's correct, move on. Even if you made it take no time your program would only be 5% faster...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 ?!
Something but there's much bigger somethings early in an engine's development than speed. Look at it from the perspective ofI 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 ?
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.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: Perfromance diff between legal / illegal move generator
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.hgm wrote: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.
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.
-
- Posts: 454
- Joined: Mon Nov 01, 2010 6:55 am
- Full name: Ted Wong
Re: Perfromance diff between legal / illegal move generator
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...