legal moves vs pseudolegal moves

[OliverBr]

There are two ways of move generation: 1) Legal moves and 2) pseudolegal moves.

In 1) The generation itself ist more complicated, but there is no test needed.
In 2) Also "illegal" moves are generated, where the king could be captured. Later, in the search, those moves will be omitted.

OliThink uses 1) but it looks as it is one of the only engine who does it this way.

Is there are common sense, which way is the better, the more effective way? Oder it is just a matter of taste?

[AndrewGrant]

Pseudo is almost certainly faster in practice. You can make some minimal efforts to reduce the # of illegal moves generated with cheap operations. For example, if attackers > 2, return only king moves. If attackers == 1, do some masking to either only capture or block the attack and/or move the king. It would be nice if pure legal was faster, but it is just not. Especially when you consider that you might prune an illegal move without ever verifying it is correct.

[Aldus]

If you have 36 pseudo-legal moves and after searching 2 of them you get a cutoff, you no longer need to test the legality of the remaining 34. Move generation can be kept simple and the legality test is only performed for the first 2 moves (in Search).

Being lazy really pays off.

[expositor]

OliThink uses 1) but it looks as it is one of the only engine who does it this way.

Expositor does legal-only move generation, too! and the move generator includes a fair amount of information in each move it emits:

• source square
• destination square
• the kind of piece moving
• the kind of piece a pawn is promoting to
• the kind of piece being captured
• a bitmask characterizing the move type, such as whether it is a manoeuvre, capture, castling move, pawn manoeuvre, pawn capture, capture en passant, promotion, or capture by promotion
• whether the move gives direct check
• whether the move gives discovered check

Each move is one machine word (eight bytes), but these are lossily compressed down to two bytes for storage in the transposition table.

I was getting single-threaded perft numbers of around 35 to 50 Mnps (depending on the position) before I added the updates to NNUE first-layer activations during move application, which was fast enough for my needs.

Although I certainly prefer doing it this way (i.e. legal-only move generation), it's hard to say whether I'd recommend it to anyone.

[Patrice Duhamel]

Especially when you consider that you might prune an illegal move without ever verifying it is correct.

This will change the move count used for LMR and LMP ?

[hgm]

It all depends on how you test the legality. If you do that on a per-move basis for each pseudo-legal move you generate, it is petty obvious that it is better to postpone such testing to the point where the move comes up for searching. Otherwise you would be subjecting many moves that you would never even want to search to the test. And the worst way to do such a test is through a general IsKingAttacked() routine, making no use about known characteristics of the current position (such as whether you are in check and which piece is checking you) and the move.

There are methods to do 'bulk-testing', where a simple test decides about the legality of an entire group of moves. Then it is not so clear. E.g., when a piece is pinned, it would make a lot of its moves illegal. So your initial move generator could start testing whether the piece it is going to generate moes for is pinned, and if it is, fall back on generation code that only generates moves along the pin ray (which presumably is known as a side effect of the pin test). That would not only relieve you of the necessity to test whether the move with the piece discovered a check on your King, but it would actually save time during the generation of the pseudo-legal moves, as you now have to generate fewer.

The case of being in check was already mentioned. King moves will always be potential evasions, but on a double check these are the only moves you have to generate and verify. On a contact check you only have to generate capture of the checker, which usually can be done far faster than generating all moves, and testing each of those for whether they capture the checker.

[lithander]

In the last couple of days I've worked on something that could probably be called semi-legal move generation where there's a dedicated bit in the move to store whether this move needs to be validated or not. I hope that this will give me the best of both worlds because for about 50% of the moves it's trivial to say they are legal. But when it would be expensive to filter out the illegal moves I just generate them all but their flag indicates that it's not safe to play them without the validation through IsKingAttacked() afterwards.

[abulmo2]

There are two ways of move generation: 1) Legal moves and 2) pseudolegal moves.

In 1) The generation itself ist more complicated, but there is no test needed.
In 2) Also "illegal" moves are generated, where the king could be captured. Later, in the search, those moves will be omitted.

OliThink uses 1) but it looks as it is one of the only engine who does it this way.

Is there are common sense, which way is the better, the more effective way? Oder it is just a matter of taste?

Olithink is not alone. My too engines, Amoeba and Dumb only generate legal moves too. I do not believe that Olithink Amoeba or Dumb can be qualified as slow engines. So I think it is just a matter of taste.

[alessandro]

There are two ways of move generation: 1) Legal moves and 2) pseudolegal moves.

In 1) The generation itself ist more complicated, but there is no test needed.
In 2) Also "illegal" moves are generated, where the king could be captured. Later, in the search, those moves will be omitted.

OliThink uses 1) but it looks as it is one of the only engine who does it this way.

Is there are common sense, which way is the better, the more effective way? Oder it is just a matter of taste?

AdaChess do generate legal moves. The move generator is optimized and smart enought to test for legalty only when necessary and in a relatively optmized way.

Some considerations:
1) Engines spent 5-10% of their time in generating moves, therefore a fast generator can be "fast enough" without the need to optimize it further.
2) If the procedure to test for legality is smart enough, it won't waste too much time to check it.
3) Although I havent a proof, I suspect that a legal move generator can be implemented smart enough to be even faster than a pseudo legal (consider the situation of an absolute-pinned queen: a smart generator detect it and accept moves only along the pinned direction(s). A pseudo-legal will loop through all the queen moves wasting a lot of effort. Another example: a king under double-check can only escape from his position, avoiding the generation of pseudo legal moves that will be only waste of time.. AdaChess do generate moves this way and the algorithm is well optimized and, imho, very good and cool
4) Generating pseudo legal moves is also more error prone because you can't prove the correctenss easily in a perft test.

[Bo Persson]

3) Although I havent a proof, I suspect that a legal move generator can be implemented smart enough to be even faster than a pseudo legal (consider the situation of an absolute-pinned queen: a smart generator detect it and accept moves only along the pinned direction(s). A pseudo-legal will loop through all the queen moves wasting a lot of effort. Another example: a king under double-check can only escape from his position, avoiding the generation of pseudo legal moves that will be only waste of time.. AdaChess do generate moves this way and the algorithm is well optimized and, imho, very good and cool

The counter argument is of course that in most positions the queen is not pinned, and the king is hardly ever double-checked. So does this save any search time, or does it only complicate the code?