Perfromance diff between legal / illegal move generator

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Perfromance diff between legal / illegal move generator

Post by MahmoudUthman » Sat Oct 22, 2016 10:27 pm

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
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Perfromance diff between legal / illegal move generator

Post by kbhearn » Sat Oct 22, 2016 10:47 pm

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
Posts: 3830
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Perfromance diff between legal / illegal move generator

Post by Sven » Sat Oct 22, 2016 11:06 pm

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 ?
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
Posts: 793
Joined: Sun Aug 03, 2014 2:48 am
Location: London, UK
Contact:

Re: Perfromance diff between legal / illegal move generator

Post by matthewlai » Sun Oct 23, 2016 10:22 am

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

Joost Buijs
Posts: 987
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Perfromance diff between legal / illegal move generator

Post by Joost Buijs » Sun Oct 23, 2016 2:41 pm

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

User avatar
hgm
Posts: 23772
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Perfromance diff between legal / illegal move generator

Post by hgm » Sun Oct 23, 2016 3:05 pm

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
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Re: Perfromance diff between legal / illegal move generator

Post by MahmoudUthman » Sun Oct 23, 2016 11:18 pm

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 :)
by size do you mean code size ? 325 lines "including comments"
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 :-)
c , does b hold any measureable advantage over 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.
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 ?!
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.
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
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Perfromance diff between legal / illegal move generator

Post by kbhearn » Mon Oct 24, 2016 1:19 am

MahmoudUthman wrote: 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
Posts: 987
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Perfromance diff between legal / illegal move generator

Post by Joost Buijs » Mon Oct 24, 2016 6:14 am

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.
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
Posts: 411
Joined: Mon Nov 01, 2010 5:55 am
Full name: Ted Wong
Contact:

Re: Perfromance diff between legal / illegal move generator

Post by kinderchocolate » Mon Oct 24, 2016 7:32 am

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

Post Reply