legal or pseudolegal move generator?

[tcusr]

do you verify the legality of those moves in your make_move function then?

Yes, enpassants and king moves I do verify in MakeMove function, but every other move is always strictly legal (regardless of king being in check or not).

is your engine open source? you gave me some solid advices and i'd like to learn from your code

[R. Tomasi]

If you have a classic bitboard engine, checking for whether moving a piece will leave the king in check or not should be just a case of one extra & operation per piece + possibly a little bit of a setup when initializing the generator, depending on whether you already compute the piece giving the check anyway. In my opinion, there really is almost no reason not to do it. The only problems are king moves and enpassants, those can be expensive to verify.

I generate almost only legal moves (except enpassants and some king moves), and having to score and sort through less moves, even with staged move generation, makes a big difference ... at least for me.

It's stuff like discovered attacks that gives me headaches there and those you will not just find by some simple bit-operation (at least I am not aware of any such technique). I can see how doing legal-only move generation can work (when done in a similar fashion to what bob describes), but I guess for my engine it will probably just hurt, so it does not seem worth spending time on that.

[Mergi]

is your engine open source? you gave me some solid advices and i'd like to learn from your code

Not at the moment, i would like to release it one day, when i'm happy with the code, but there's still much work to be done on that front .

I can very much recommend this article , where the author talks about fully legal move generation. While i don't think fully legal move generation is too useful in an actual engine (and not just a perft machine), for cases such as when the king is in a single check, it's very easy to compute a "legality mask", that is just the checking piece combined with a ray between the king and the checker -> you either have to capture the checker, or step on a square between the king and the checker. With rays already being precalculated on program startup, this should be very cheap and fast.

It's stuff like discovered attacks that gives me headaches there and those you will not just find by some simple bit-operation (at least I am not aware of any such technique). I can see how doing legal-only move generation can work (when done in a similar fashion to what bob describes), but I guess for my engine it will probably just hurt, so it does not seem worth spending time on that.

Indeed, discovery attacks are a bit move expensive, but in my case it was very much faster to not generate those either. You only need to generate all the diagonal/antidiagonal/vertical/horizontal rays from the king's square, add these rays together, and see whether any of these rays intersects with an enemy rook/queen/bishop. That gives you the possible attackers (if they were not blocked by anything). To get the actual blockers, we have to go through all these possible attackers, generate another ray between the king and the possible attacker, then we & this ray with all_pieces and if there's exactly one piece on that ray, then that piece is a blocker and we can add it to our blockers mask that we use later for move generation.


This is my generic move generator function for every piece except pawns. It's very convenient because the legality mask is not only used for not leaving the king in check, as destribed above, but you can also influence what kind of moves are generated for staged move generation. For example if you want only captures, we can just & the original legality mask with enemy_pieces and pass that to the function, etc.

Code: Select all

    template<PieceType PT, Color C>
    void MoveGen::GenMovesForPieceType(Bitboard legality_mask, const Board &board) {
        Bitboard pieces = board.GetPieces(PT, C);
        while (pieces) {
            Square origin_s = PopLsb(pieces);
            // this is for the case of king being in a single check
            // if king isnt in check, legality mask is just 0xFFF...FF -> no restrictions
            Bitboard possible_moves = GetAttacks<PT>(origin_s, occ_mask) & legality_mask;
            if (blockers & SquareToBB(origin_s)) { // this takes care of the discovery attacks
                // only allow moves on a ray between the king and the attacker that we are blocking.
                // Even though we don't know exactly where the attacker is, we can just get a ray
                // all the way to the edge of the board and limit our moves that way.
                possible_moves &= GetRayToBorders(king_square, origin_s);
            }
            while (possible_moves) {
                Square destination_s = PopLsb(possible_moves);
                PutMove(NewMove(origin_s, destination_s));
            }
        }
    }

Btw i don't want to claim that the way i do it is good, or perhaps superior to another. It's just something that worked super well for me in my own engine, especially since all the rays, attacks and such are already precalculated, so it's just the cost of accessing the arrays for me.

[R. Tomasi]

Btw i don't want to claim that the way i do it is good, or perhaps superior to another. It's just something that worked super well for me in my own engine, especially since all the rays, attacks and such are already precalculated, so it's just the cost of accessing the arrays for me.

Don't worry, it did not come across as such a claim at all. I think this is one of the many things that may be better or not depending on what engine you look at. In this particualar case our engines seem to be rather different. In yours legal-only is better, whereas in mine pseudo-legal wins. I'm very interested in seeing how other ppl do it, though - I always learn lot's when hearing about the ways other engines work.

[R. Tomasi]

You only need to generate all the diagonal/antidiagonal/vertical/horizontal rays from the king's square, add these rays together, and see whether any of these rays intersects with an enemy rook/queen/bishop. That gives you the possible attackers (if they were not blocked by anything). To get the actual blockers, we have to go through all these possible attackers, generate another ray between the king and the possible attacker, then we & this ray with all_pieces and if there's exactly one piece on that ray, then that piece is a blocker and we can add it to our blockers mask that we use later for move generation.

Btw, I think you can speed that up a little, assuming you're using magic bitboards: use the king square and the opponent occupancy bitboard to perform a magic lookup, then & mask it with the occupancy bitboard of your own pieces. That will give you any of your pieces that are pinned to your king and have to be excluded from move generation.

[Mergi]

Btw, I think you can speed that up a little, assuming you're using magic bitboards: use the king square and the opponent occupancy bitboard to perform a magic lookup, then & mask it with the occupancy bitboard of your own pieces. That will give you any of your pieces that are pinned to your king and have to be excluded from move generation.

You will still run into the problem of 2 or more pieces blocking at the same time, meaning that none of them is actually pinned. So you still need to go through every single attacker individually, cast a ray towards the king, and check that there's only 1 piece blocking. Also the magic lookups are not exactly free either, there's quite a lot of (cache unfriendly) operations needed to get the correct bitboard.

With your method, you get to immediately exclude attackers that are behind each other on the same ray, whereas i still go through all of them, but that should be fairly rare.

[tcusr]

Btw, I think you can speed that up a little, assuming you're using magic bitboards: use the king square and the opponent occupancy bitboard to perform a magic lookup, then & mask it with the occupancy bitboard of your own pieces. That will give you any of your pieces that are pinned to your king and have to be excluded from move generation.

You will still run into the problem of 2 or more pieces blocking at the same time, meaning that none of them is actually pinned. So you still need to go through every single attacker individually, cast a ray towards the king, and check that there's only 1 piece blocking. Also the magic lookups are not exactly free either, there's quite a lot of (cache unfriendly) operations needed to get the correct bitboard.

With your method, you get to immediately exclude attackers that are behind each other on the same ray, whereas i still go through all of them, but that should be fairly rare.

what if you generate the opponents rooks/queens attacks with the kogge stone algorithm and & those attacks with the rook attacks from your king?
if there are rooks/queens in this mask it means they are pinned and you can generate the moves for them separately, you wouldn't need "if (blockers & SquareToBB(origin_s))" anymore. you would need to do again for bishops/queens though

[R. Tomasi]

Btw, I think you can speed that up a little, assuming you're using magic bitboards: use the king square and the opponent occupancy bitboard to perform a magic lookup, then & mask it with the occupancy bitboard of your own pieces. That will give you any of your pieces that are pinned to your king and have to be excluded from move generation.

You will still run into the problem of 2 or more pieces blocking at the same time, meaning that none of them is actually pinned. So you still need to go through every single attacker individually, cast a ray towards the king, and check that there's only 1 piece blocking. Also the magic lookups are not exactly free either, there's quite a lot of (cache unfriendly) operations needed to get the correct bitboard.

With your method, you get to immediately exclude attackers that are behind each other on the same ray, whereas i still go through all of them, but that should be fairly rare.

You're right. Also, even if a piece is actually pinned, it cannot be just excluded: it may still be allowed to move along the respective ray. It's all these complications that scare me away from doing legal-only move generation, even if it may be that tiny tad faster.

[R. Tomasi]

Btw, I think you can speed that up a little, assuming you're using magic bitboards: use the king square and the opponent occupancy bitboard to perform a magic lookup, then & mask it with the occupancy bitboard of your own pieces. That will give you any of your pieces that are pinned to your king and have to be excluded from move generation.

You will still run into the problem of 2 or more pieces blocking at the same time, meaning that none of them is actually pinned. So you still need to go through every single attacker individually, cast a ray towards the king, and check that there's only 1 piece blocking. Also the magic lookups are not exactly free either, there's quite a lot of (cache unfriendly) operations needed to get the correct bitboard.

With your method, you get to immediately exclude attackers that are behind each other on the same ray, whereas i still go through all of them, but that should be fairly rare.

what if you generate the opponents rooks/queens attacks with the kogge stone algorithm and & those attacks with the rook attacks from your king?
if there are rooks/queens in this mask it means they are pinned and you can generate the moves for them separately, you wouldn't need "if (blockers & SquareToBB(origin_s))" anymore. you would need to do again for bishops/queens though

Interesting idea. Kogge-Stone isn't completely free, either. I guess you would have to implement it and measure how that fits with the rest of your engine/movegenerator design.

[Chessnut1071]

I went the other way, computing legal moves that handle every variation. This isn't easy. It took me over a year to find every issue after I first thought it was perfect. If you follow this route I suggest you use known checkmate puzzle up to 20 ply. There are hundreds of tiny issues that must be programmed for and the time will be magnitudes greater than pseudo-moves. If your objective is ELO score, this is definitely not the optimum method. However, if your objective is to find the minimum mate, 100% of the time in the shortest possible time, pseudo-moves will fail at least 2% of the time.

Not many years from now, chips will be available with speeds much greater that today. Quantum computing may offer speeds over 100x the current chips. When that happens, the advantage of fast searches will begin to disappear.