legal move generator

[elcabesa]

hi,
I'm starting writing my second chess engine after my first try with "vajolet" some years ago.

I have finished writing a magic bitboard move generator and I'm testing it doing perft on a lot of position.

I'd like to write a legal move generator removing the needs of checking the safety of the king after each move.

Could you point me to some online resource??

I have thought that i need the following:
-check evade move generator (check and double check)
-not moving the king in check
-pinned piece

am I forgetting something??

thank you all!

[lorenzo]

You also don't need to worry about pinned pieces which move in the space between the king and the attacker. En passant can be tricky too, as it can reveal a check since when you capture en passant, you don't end up on the same square you have captured which normally negates that as a problem for exposing checks.

Stockfish has a nice move generator - https://github.com/mcostalba/Stockfish/ ... ovegen.cpp

Weak (my engine), which in part derives from stockfish, has finally got to a point where its passing all perfts, including evil ones from this board , move generation is done here - https://github.com/lorenzo-stoakes/weak ... /movegen.c

I am happy to answer any questions you have about it

[hgm]

I'd like to write a legal move generator removing the needs of checking the safety of the king after each move.

Yes, well, problem is that "removing the needs of checking the safety of the king after each move" usually means that you have to check the safety of the king after each move you generate (to reject it), in stead of checking it after you make it (which you often don't).

Suppressing illegalmoves of pinned pieces is fortunately not that difficult; it is comparativly cheap to determine which pieces are pinned, and easy to exclude them from the normal move-generation process, and generate their moves separately. For King moves and e.p. capture it is not that easy, so trying to weed them out during move generation is usually a losing deal. The golden rule of engine-efficiency remains: "don't do what you can postpone to later in the node".

[Dan Honeycutt]

hi,
I'm starting writing my second chess engine after my first try with "vajolet" some years ago.

I have finished writing a magic bitboard move generator and I'm testing it doing perft on a lot of position.

I'd like to write a legal move generator removing the needs of checking the safety of the king after each move.

Could you point me to some online resource??

I have thought that i need the following:
-check evade move generator (check and double check)
-not moving the king in check
-pinned piece

am I forgetting something??

thank you all!

You need a map of where pinned pieces can travel. Those are the squares from the friendly king to and including the pinning piece. When you come upon a pinned piece you 'and' the squares it could normally move to with the map squares then produce your moves as usual.

My program Cupcake does legal generation. It's Java but the syntax is nearly identical to C. It is open source and you can download it from Jim's site:

http://jim-ablett.co.de/

The single most troublesome piece of code for legal generation is en passant captures. You can see how I do that with Cupcake. It takes almost as much code to do the ep captures as there is for the rest of the pawn move code.

Good luck with your engine.
Dan H.

[elcabesa]

ok, so probably I don't need to do a real Legal move generator to have good speed.
I only need to check for pinned pieces ( it could also be important in evalutation later)

I'll try to check for pinned pieces and then see what speedup i can achieve.
to checkout for a pinned piece I think I have see if my king is sliding checked from one of my piece, then i have to remove the piece and see if now the king is checked by a real enemy sliding piece? Am I wrong?

after i have also to save from which direction the piece is pinned.

please correct me!

[Dan Honeycutt]

ok, so probably I don't need to do a real Legal move generator to have good speed.
I only need to check for pinned pieces ( it could also be important in evalutation later)

I'll try to check for pinned pieces and then see what speedup i can achieve.
to checkout for a pinned piece I think I have see if my king is sliding checked from one of my piece, then i have to remove the piece and see if now the king is checked by a real enemy sliding piece? Am I wrong?

after i have also to save from which direction the piece is pinned.

please correct me!

If you are not going to do legal generation why are you checking for pinned pieces? Do you have some other use for pinned piece data? if not, simply do nothing until it comes time to play the move. Then ...

Do you have a table telling you the direction from square 1 to square 2? Squares on the same rank or file would have a direction of +/- 1 or 8. Squares on the same diagonal would be +/- 7 or 9. Other square combinations have value 0. If the direction from the piece moving to the king is zero you're done - the move is legal.

Another way to achieve the same thing is a table of queen attacks on an empty board. If the piece moving does not 'attack' the king then, again, you're done - the move is legal.

Legality for the majority of your moves can be determined with one instruction using a method such as the above. For other moves you can decide if you want to calculate pins or, more simply, just play the move and see if the king is attacked.

Best
Dan H.

[Karlo Bala]

hi,
I'm starting writing my second chess engine after my first try with "vajolet" some years ago.

I have finished writing a magic bitboard move generator and I'm testing it doing perft on a lot of position.

I'd like to write a legal move generator removing the needs of checking the safety of the king after each move.

Could you point me to some online resource??

I have thought that i need the following:
-check evade move generator (check and double check)
-not moving the king in check
-pinned piece

am I forgetting something??

thank you all!

IMHO, GreKo(6.5) chess has a very nice legal move generator

[Sven]

ok, so probably I don't need to do a real Legal move generator to have good speed.
I only need to check for pinned pieces ( it could also be important in evalutation later)

I'll try to check for pinned pieces and then see what speedup i can achieve.
to checkout for a pinned piece I think I have see if my king is sliding checked from one of my piece, then i have to remove the piece and see if now the king is checked by a real enemy sliding piece? Am I wrong?

after i have also to save from which direction the piece is pinned.

please correct me!

One important note first: please take into account that changes in move generation speed usually have a low impact on overall search speed of an engine. An inefficient legality testing concept, though, may have a considerable impact.

If you are interested in a fast perft function then you definitely need a legal move generator that saves all make/unmake operations for the last ply of perft.

If you only use perft to validate your move generator, board representation, and make/unmake functions (as it was intended for) then a legal move generator is not really required. Even with a pseudo-legal move generator you can get quite a bit of speedup when restricting the legality check after makeMove() to only those moves that CAN be illegal. I think this is probably the most important optimization step when legality is concerned: most moves can be classified as "legal" very quickly.

These are potentially illegal moves (assuming standard pseudo-legal move generation techniques that will never generate knight moves from a3 to d7 or pawn moves from h2 to c6, for instance):

- king moves (including castling),
- check evasions,
- moves of pinned pieces,
- ep captures.

Check evasions can be omitted from that list if you have a separate check evasion generator since the latter will avoid to generate most illegal check evasions, and the remaining evasions can only be illegal when falling into one of the other three categories above.

Note that for castling moves there must also be code to check for attacks to the rook's target square.

Now the good news is that, as soon as you have managed to implement this kind of optimized legality check, you have almost reached the stage of a fully legal move generator. If your (search) code already looks like this:

Code: Select all

makeMove(board, m);
if (lastMoveCanBeIllegal(board, m) && kingLeftInCheck(board)) {
    unmakeMove(board, m);
    continue;
}
// recursive search code ...
unmakeMove(board, m);

and "lastMoveCanBeIllegal()" tests conditions as described above to avoid the expensive "kingLeftInCheck()" call in most cases then it is quite easy to perform similar tests within the move generator instead while completely omitting the "kingLeftInCheck()". The main difference would be that instead of detecting moves that CAN BE illegal (after they were made) you'd have to detect those that ARE illegal (prior to generating them). But this is not a difficult task when using bitboards:

- You could create a bitmap of all squares attacked by enemy pieces once in the beginning of move generation, and use it to filter out illegal king moves and illegal castle moves where the rook target square is atttacked.

- In case of double check you are done now.

- When not maintaining a check evasion generator, escapes to checks need special legality tests. For these to be efficient you need some information about the previous move and the piece giving check (here you know it is exactly one). E.g. when escaping from a direct check by a pawn or knight only capturing the checking piece can be legal (and king moves - but these were already handled above), otherwise also interpositions can be legal. I think that as soon as you implement these checks, you will find it easier to actually implement an evasion generator which does the same task but does not care about other moves that are definitely illegal evasions.

- You could calculate a bitmap of all pinned pieces once in the beginning, and when attempting to generate a move of a pinned piece you could test whether the "to" square is on the same ray as the "from" square and the own king's square; if not then it's an illegal move.

Since you asked about how to do the pin detection: there are probably a lot of ways to do it. With bitboards you could do it in 8 steps, 4 for all rook directions and 4 for all bishop directions. (There may be faster ways!) For each direction: get all corresponding attacks from the king square when ignoring all friendly pieces, and if these overlap with an enemy slider of matching type then "AND" these attacks with the bitboard of all friendly pieces, and if the result is non-zero, extract the LSB, and if the remainder is now zero then the extracted LSB indicates a pinned piece. I think that can be implemented more efficiently than it sounds here.

- For en passant captures, in addition to testing the moving pawn for pins you would also need to test the captured pawn for non-vertical pins, and furthermore the horizontal pin test must filter out the square of the enemy pawn that would get captured e.p.; since e.p. is a bit tricky for that reason you can also imagine a much simpler way of testing the legality of the very rare ep capture moves.

And that's it.

One possible way for an engine might be to have these four kinds of move generator "main" functions:

a) a fully legal check evasion generator (for perft, full-width search and qsearch if you detect being in check there),
b) a pseudo-legal move generator for non-evasion nodes in full-width search,
c) a fully legal move generator for non-evasion nodes, to be used in perft and as a possible alternative to b) in full-width search,
d) a pseudo-legal move generator for qsearch.

Obviously a) also makes mate detection a trivial task. Without it you usually need to count all legal moves that were made on the board, and if that counter is zero after the move loop is done and you are in check then you return a mate score. With a) your evasion search simply returns a mate score if the evasion move generator has generated zero legal moves.

Sven

[WinPooh]

IMHO, GreKo(6.5) chess has a very nice legal move generator

Yes, and after I returned back to pseudo-legal scheme the engine got stronger by 50 Elo points.

[lucasart]

hi,
I'm starting writing my second chess engine after my first try with "vajolet" some years ago.

I have finished writing a magic bitboard move generator and I'm testing it doing perft on a lot of position.

I'd like to write a legal move generator removing the needs of checking the safety of the king after each move.

That's exactly what I do in my engine DiscoCheck. Basically it works as follows:
* evasions are generated separately (ie. legal moves when in check)
* otherwise, filter moves where the moving piece is pinned and moves out of its pin-ray. do not move the king to a square attacked by the enemy. And a ton of other details, that are more fun to find out by youself
The source code of DiscoCheck can be found here:
http://wbec-ridderkerk.nl/html/details1 ... Check.html
Have a look at movegen.c