I'm never bothered with pseudo legal move generation. While generating the moves I check whether they are legal without doing them and I only check the ones that have the potential of being legal or illegal depending on whether I'm in check (only check moves that might bring you out of check) or not (only check moves that might leave you in check).
When I profile my engine the legal check is very cheap but the overall move generation is very cheap as well. So I not intend to change that.
Perfromance diff between legal / illegal move generator
Moderators: hgm, Rebel, chrisw
-
tpetzke
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
-
uaf
- Posts: 98
- Joined: Sat Jul 31, 2010 8:48 pm
- Full name: Ubaldo Andrea Farina
Re: Perfromance diff between legal / illegal move generator
When, few years ago, I've implemented a legal move generator, the slow down in perft was less than 5%.
-
syzygy
- Posts: 5563
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Perfromance diff between legal / illegal move generator
For me it was a speed up in perft and even a slight speed up in search.uaf wrote:When, few years ago, I've implemented a legal move generator, the slow down in perft was less than 5%.
I once changed SF to do legal move generation, but it was not a win. I think the main reason is that SF prunes a lot more than my engine, so does not play a much larger percentage of generated moves than my engine. Moves you end up not playing need not be tested for legality, so there is the win of an "illegal" move generator.
Of course having legal move generation removes a lot of complications in other parts of the code.
-
MahmoudUthman
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Perfromance diff between legal / illegal move generator
was it a fully legal "generates only legal moves" , or was it one that test the legality of the moves after generating it ? I use the first and it's extremely fast when it comes to perftuaf wrote:When, few years ago, I've implemented a legal move generator, the slow down in perft was less than 5%.
-
hgm
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Perfromance diff between legal / illegal move generator
I am always pretty flexible in this. For some types of illegal moves it can actually speeds up the generator to not generate them. E.g. in qperft detecting pins globally for the position saves time by not having to generate moves for the pinned pieces later. So you already come out with a gain even when you don't count the time you save on individual moves to test if they exposed your King. (Which might be none, because the moves are never made because of an early beta cutoff.)
Disadvantage is code complexity and lack of generality. E.g. it assumes blockable pieces (that could cause act to pin) move in certain simple ways, e.g. only onorthogonals and diagonals. If you have also sliders that move around corners, you probably don't want to bother figuring out what exactly constitutes a pin. So in Fairy-Max I do purely pseudo-legal, and just abort the daughter node if it detects captureof a King during its move generation. That is completely general, and trivial to do. It seems very slow, but only a small fraction of the moves expose their King to check. Which has to be weighed against doing a much cheaper test on all of the moves.
Subjecting individual pseudo-legal moves to a test to see if they are legal can be postponed to the time when you actually want to do the move rather than doing them in the move generator; then you might not have to do it at all if a move before it causes a cutoff. This becomes different when some form of bulk testing is available, which can clear many moves at one. E.g. if you establish that a piece is not pinned, all move with the piece must be legal, and you don't need to test them individually. Of course the ideal case is where you can selectively generate the legal moves. E.g. when generating drops in Crazyhouse when you are in check, you only have to generate drops on squares that ly between King and checker on the check ray.
In my latest engine (which is for games with drops) I have a dedicated test for capture of the enemy King over the from-square of the previous move (and, in case of e.p., over the victim square of that move), to intercept moves that were illegal because the piece was pinned. This wouldnot stop a King from stumbling into check. So in case the previous ply was a King move I just do move generation early, which would certainly detect King capture, and abort the node. (Normally I postpone move generation to after null move.) From an in-check position MakeMove already tests moves of any non-royal piece to see if they actually solve the existing check, (ifit is not a double check), by capturing the checker,or landing in between King and checker.
Disadvantage is code complexity and lack of generality. E.g. it assumes blockable pieces (that could cause act to pin) move in certain simple ways, e.g. only onorthogonals and diagonals. If you have also sliders that move around corners, you probably don't want to bother figuring out what exactly constitutes a pin. So in Fairy-Max I do purely pseudo-legal, and just abort the daughter node if it detects captureof a King during its move generation. That is completely general, and trivial to do. It seems very slow, but only a small fraction of the moves expose their King to check. Which has to be weighed against doing a much cheaper test on all of the moves.
Subjecting individual pseudo-legal moves to a test to see if they are legal can be postponed to the time when you actually want to do the move rather than doing them in the move generator; then you might not have to do it at all if a move before it causes a cutoff. This becomes different when some form of bulk testing is available, which can clear many moves at one. E.g. if you establish that a piece is not pinned, all move with the piece must be legal, and you don't need to test them individually. Of course the ideal case is where you can selectively generate the legal moves. E.g. when generating drops in Crazyhouse when you are in check, you only have to generate drops on squares that ly between King and checker on the check ray.
In my latest engine (which is for games with drops) I have a dedicated test for capture of the enemy King over the from-square of the previous move (and, in case of e.p., over the victim square of that move), to intercept moves that were illegal because the piece was pinned. This wouldnot stop a King from stumbling into check. So in case the previous ply was a King move I just do move generation early, which would certainly detect King capture, and abort the node. (Normally I postpone move generation to after null move.) From an in-check position MakeMove already tests moves of any non-royal piece to see if they actually solve the existing check, (ifit is not a double check), by capturing the checker,or landing in between King and checker.