legal moves vs pseudolegal moves

[abulmo2]

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?

I did a fast check using code coverage on Amoeba's bench test.
About 0.5% of bishop/rook or queen are pinned and need a special code in Amoeba's legal move generator (about 20-30 lines of code, not so complicated). In a pseudo legal move generator, it means that in 99.5% of the time, the test for legality will be true and so useless. The sparsity of pinned pieces is not really in favor of a pseudo-legal move generator.
I want to insist a little bit: a (good) legal move generator does ZERO test for legality. It only generates legal moves. It adds some code complexity and some performance hit to compute a mask of pinned pieces, but then you are done, you do not test anything.

[hgm]

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?

That counter argument does not really work, because even when the Queen is not pinned you would still have to test the Queen moves for exposing your King in some way (if you want to generate legal moves only). So the issue here is whether it is faster to subject all Queen moves separately to a test for this, or whether you do 'bulk legality testing' by determining the pinned status of the Queen once. The latter is bound to be faster, as it can always be done as the individual test on a hypothetical self-destruction move of the Queen, whatever method you use for testing this.

In most cases this would indeed reveal the Queen is not pinned, but you still haven't done any extra work at this point if the Queen had at least one move. (Which is usually the case.) If a pin is detected, it is very likely you would have determined the pin ray as a side effect, and using that pin ray as the set of allowed destinations, rather than the normal attack set of a Queen, also saves you some work.

[syzygy]

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?

I implemented legal move generation in my patzer engine and achieved a small speedup.
Then I did the same in Stockfish, and it was a clear slowdown.

The reason it does not work well in Stockfish is that SF prunes much more. The extra work done when generating legal moves is offset by not having to test move legality later if the engine actually gets to those moves.

[Chessnut1071]

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?

My objective is checkmate; therefore, I think the shortest way to checkmate is legal moves that check for double check, pins and checks. The only cutoff is checkmate, and you can't prune. Consider a case where you have 50 pseudo moves with only 1 or 2 legal moves. The only option is to extend the search on pseudo moves to see if they're legal. I haven't tried it yet, but it would be nice to use a pseudo move list and compare it with a legal move list on a thousand puzzles at 12 - 24 ply and compare the difference in time. My guess is the higher the ply the longer the time for pseudo moves vs. legal move sets. If anybody else has already done that, it would be nice to hear your results.

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

My objective is checkmate; therefore, I think the shortest way to checkmate is legal moves that check for double check, pins and checks. The only cutoff is checkmate, and you can't prune. ..

My question is referring to positions without check.
OliThink has a separate move generation when the king is in check.

[RedBedHed]

I think it depends a lot on what kind of search algorithm you use. Classical Monte-Carlo Tree Search un-prunes the tree, and checking for legality there seems inefficient imo. Homura-- my amateur experimental engine with many hybrid searches-- has an extremely fast strictly-legal move generator. Pseudo-legal is not necessarily the fastest for a bitboard generator, where most filtering is done with bitmasks.

Here are Homura's single-threaded, no-hashing bulk-counted perft numbers:

Code: Select all

 	Startup  -  0.002 seconds

        perft(1) -  0.000 seconds -         20 nodes visited.
        perft(2) -  0.000 seconds -        400 nodes visited.
        perft(3) -  0.000 seconds -       8902 nodes visited.
        perft(4) -  0.001 seconds -     197281 nodes visited.
        perft(5) -  0.009 seconds -    4865609 nodes visited.
        perft(6) -  0.231 seconds -  119060324 nodes visited.
        perft(7) -  6.198 seconds - 3195901860 nodes visited.

[RedBedHed]

I think it depends a lot on what kind of search algorithm you use. Classical Monte-Carlo Tree Search un-prunes the tree, and checking for legality there seems inefficient imo. Homura-- my amateur experimental engine with many hybrid searches-- has an extremely fast strictly-legal move generator. Pseudo-legal is not necessarily the fastest for a bitboard generator, where most filtering is done with bitmasks.

Here are Homura's single-threaded, no-hashing bulk-counted perft numbers:

Code: Select all

 	Startup  -  0.002 seconds

        perft(1) -  0.000 seconds -         20 nodes visited.
        perft(2) -  0.000 seconds -        400 nodes visited.
        perft(3) -  0.000 seconds -       8902 nodes visited.
        perft(4) -  0.001 seconds -     197281 nodes visited.
        perft(5) -  0.009 seconds -    4865609 nodes visited.
        perft(6) -  0.231 seconds -  119060324 nodes visited.
        perft(7) -  6.198 seconds - 3195901860 nodes visited.

I forgot to include that this is on my 11th generation i7 with 5ghz clock speed.

[OliverBr]

I think it depends a lot on what kind of search algorithm you use. Classical Monte-Carlo Tree Search un-prunes the tree, and checking for legality there seems inefficient imo. Homura-- my amateur experimental engine with many hybrid searches-- has an extremely fast strictly-legal move generator. Pseudo-legal is not necessarily the fastest for a bitboard generator, where most filtering is done with bitmasks.

Here are Homura's single-threaded, no-hashing bulk-counted perft numbers:

Code: Select all

 	Startup  -  0.002 seconds

        perft(1) -  0.000 seconds -         20 nodes visited.
        perft(2) -  0.000 seconds -        400 nodes visited.
        perft(3) -  0.000 seconds -       8902 nodes visited.
        perft(4) -  0.001 seconds -     197281 nodes visited.
        perft(5) -  0.009 seconds -    4865609 nodes visited.
        perft(6) -  0.231 seconds -  119060324 nodes visited.
        perft(7) -  6.198 seconds - 3195901860 nodes visited.

I forgot to include that this is on my 11th generation i7 with 5ghz clock speed.

It's about the same speed as generating-legal-moves-only OliThink, created in the year 2008, on a notebook with i9 and 2.4ghz clock speed:

Code: Select all

$ ./oliperft 7
 1     0      0          20
 2     0      0         400
 3     0      0        8902
 4     0      0      197281
 5     0      3     4865609
 6     0     36   119060324
 7     0    518  3195901860

Nodes: 3320034396 ms: 5185 knps: 640191

But there are two tricks involved in oliperft: A position hash and just a count on the last ply.

[RedBedHed]

I think it depends a lot on what kind of search algorithm you use. Classical Monte-Carlo Tree Search un-prunes the tree, and checking for legality there seems inefficient imo. Homura-- my amateur experimental engine with many hybrid searches-- has an extremely fast strictly-legal move generator. Pseudo-legal is not necessarily the fastest for a bitboard generator, where most filtering is done with bitmasks.

Here are Homura's single-threaded, no-hashing bulk-counted perft numbers:

Code: Select all

 	Startup  -  0.002 seconds

        perft(1) -  0.000 seconds -         20 nodes visited.
        perft(2) -  0.000 seconds -        400 nodes visited.
        perft(3) -  0.000 seconds -       8902 nodes visited.
        perft(4) -  0.001 seconds -     197281 nodes visited.
        perft(5) -  0.009 seconds -    4865609 nodes visited.
        perft(6) -  0.231 seconds -  119060324 nodes visited.
        perft(7) -  6.198 seconds - 3195901860 nodes visited.

I forgot to include that this is on my 11th generation i7 with 5ghz clock speed.

It's about the same speed as generating-legal-moves-only OliThink, created in the year 2008, on a notebook with i9 and 2.4ghz clock speed:

Code: Select all

$ ./oliperft 7
 1     0      0          20
 2     0      0         400
 3     0      0        8902
 4     0      0      197281
 5     0      3     4865609
 6     0     36   119060324
 7     0    518  3195901860

Nodes: 3320034396 ms: 5185 knps: 640191

But there are two tricks involved in oliperft: A position hash and just a count on the last ply.

Nice! Homura's perft uses the "last ply" trick too... It just doesn't do any multithreading or hashing.

[Chessnut1071]

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?

This is a huge concern to me and I'm not sure of the answer. It's not complicated to program for double check, pins and check. Let's say you have a case of 45 pseudo moves with a double check. Now, that converges to 1 or 2 legal moves if you program for double check. Otherwise, you need an extra ply to find out if your king is enprize along with 43 other moves which are not legal before the extra ply. Although this is a rare case when you're dealing with 20 - 30 ply that extra time could be very significant. My thought is that legal moves become more significant the higher the ply. Before I rewrite my engine to prove or disprove, that, I'd like to see the results of somebody who already has that data. My only focus is on checkmate, but I suspect ELO priority is better off with no test for legality and the extra ply.