legal moves vs pseudolegal moves

[hgm]

The question, though, is how often it does happen that you are in double check. If that only happens in 0.01% of the nodes, reducing the number of moves from 45 to 2 saves you about 0.0095% on the total time. And the test whether you would be in double check would be done in every node. So then it has to be a really cheap test indeed to get any advantage from it.

Of course when you make such tests anyway for other reasons (like deciding whether you should give an extension, or move ordering), the info would be available for free, and it would always pay off to use it, no matter how little using it gains you in terms of eliminated nodes.

This is always the dilemma. Of course you can reduce the number of nodes by only seaching legal moves. But that qualification doesn't just pop out of nowhere, and it would take computation time to determine legality. And that especially hurts when the large majority of pseudo-legal moves is legal, as you would then in most cases you would not save anything by running the test. This is why engines often only employ legal move generarion in positions where you are in check. As in such positions most of the pseudo-legal moves tend to be illegal. And then you gain if the test for legality is less than doing an extra node. Even when you defer the testing to the point where the move comes up for search.

[Chessnut1071]

The question, though, is how often it does happen that you are in double check. If that only happens in 0.01% of the nodes, reducing the number of moves from 45 to 2 saves you about 0.0095% on the total time. And the test whether you would be in double check would be done in every node. So then it has to be a really cheap test indeed to get any advantage from it.

Of course when you make such tests anyway for other reasons (like deciding whether you should give an extension, or move ordering), the info would be available for free, and it would always pay off to use it, no matter how little using it gains you in terms of eliminated nodes.

This is always the dilemma. Of course you can reduce the number of nodes by only seaching legal moves. But that qualification doesn't just pop out of nowhere, and it would take computation time to determine legality. And that especially hurts when the large majority of pseudo-legal moves is legal, as you would then in most cases you would not save anything by running the test. This is why engines often only employ legal move generarion in positions where you are in check. As in such positions most of the pseudo-legal moves tend to be illegal. And then you gain if the test for legality is less than doing an extra node. Even when you defer the testing to the point where the move comes up for search.

"This is why engines often only employ legal move generarion in positions where you are in check. As in such positions most of the pseudo-legal moves tend to be illegal. And then you gain if the test for legality is less than doing an extra node. Even when you defer the testing to the point where the move comes up for search."

I like that idea.

[fasterik]

I can't believe a fully legal move generator would be worth it compared to one that generates 90% legal moves and 10% pseudo-legal. It takes extra work to generate legal king moves and en passant, which are rare. Granted, with fully legal you eliminate some branching from the search, but with 90% legal the branch predictor should do a pretty good job.

That being said, I would guess that the 90% legal is better than naive pseudo-legal and legality testing every move, which is what I'm doing in the engine I just started. Once my search has improved a bit, I plan on writing a second move generator that's easy to swap in and out. That way I will be able to profile both and see how much check/pin detection contributes to search performance.

[Chessnut1071]

I can't believe a fully legal move generator would be worth it compared to one that generates 90% legal moves and 10% pseudo-legal. It takes extra work to generate legal king moves and en passant, which are rare. Granted, with fully legal you eliminate some branching from the search, but with 90% legal the branch predictor should do a pretty good job.

That being said, I would guess that the 90% legal is better than naive pseudo-legal and legality testing every move, which is what I'm doing in the engine I just started. Once my search has improved a bit, I plan on writing a second move generator that's easy to swap in and out. That way I will be able to profile both and see how much check/pin detection contributes to search performance.

I was planning the same thing; however, I have a very critical program I'm working on right now and can't afford the time. I'm interested in checkmate solutions, not ELO enhancement. The two objectives are very different. Please, let me know what you find.

[alessandro]

I was planning the same thing; however, I have a very critical program I'm working on right now and can't afford the time. I'm interested in checkmate solutions, not ELO enhancement. The two objectives are very different. Please, let me know what you find.

AdaChess implements an algoritm able to detect which kind of check is delivered by a move. The engine can distinguish between direct checks, discovery, doubled and checkmates. Any move that can result in a check is further investigate. According to the kind of check, the engine uses an optimized algorithm to detect whether it is a checkmate or not. I can give you more detail if you want.
As obvious, those investigation makes the move generator a bit slower compared to the same without them. But, let's say the truth, I like to implement cool stuffs not to reinvent the wheel every time.

[Chessnut1071]

I was planning the same thing; however, I have a very critical program I'm working on right now and can't afford the time. I'm interested in checkmate solutions, not ELO enhancement. The two objectives are very different. Please, let me know what you find.

AdaChess implements an algoritm able to detect which kind of check is delivered by a move. The engine can distinguish between direct checks, discovery, doubled and checkmates. Any move that can result in a check is further investigate. According to the kind of check, the engine uses an optimized algorithm to detect whether it is a checkmate or not. I can give you more detail if you want.
As obvious, those investigation makes the move generator a bit slower compared to the same without them. but, let's say the truth, I like to implement cool stuffs not to reinvent the wheel every time.

Actually, I have every type of legal move accounted for. Checkmate solutions end with a check, so the last ply must end with a check; otherwise, the move is discarded. You can have 40 legal or 50 pseudo moves, but only need a few legal checks to verify the last ply checkmate. I assume; therefore, that you need to examine only possible legal moves because checkmate solutions are dominated by check moves. If you examine only pseudo moves, you need an extra ply to verify checkmate. I'm assuming confining the search to legal moves only is faster than the extra ply from pseudo moves + an extra ply. When I get time, I plan to document that theory with 1000s of puzzle solutions from 4 - 26 ply. My guess is that the higher the ply the more efficient the legal moves only approach is. ELO optimization is probably better off with the pseudo + extra ply approach; however, I'm not certain of that either. If someone has this data, I would appreciate seeing it in relation to ply depth.