Question about testing legality of moves

[ambrooks1]

My questions involves the optimization of move legality testing after doing a make in the alpha-beta search.

A major chunk of the time spent by my chess engine is doing this.
It uses the typical isInCheck method of taking the king's index and looking for knight,rook, etc. moves from there.
I have optimized this routine about all that I can.

I also have a check-evasion move generator, so I am here referring to the case where we are NOT in check already.
Also, let's forget about king moves for the moment.

Intuitively, it seems wasteful to be doing so much verification just to catch the cases where you are moving an
absolutely pinned ( pinned against the king ) piece.

I know that some engines allow the king to be captured, but that sounds like too massive of a re-architecture
for a mature engine. ( Would need to be planned at the start, right)

Any thoughts are appreciated. Thanks in advance.

[Ron Murawski]

My questions involves the optimization of move legality testing after doing a make in the alpha-beta search.

A major chunk of the time spent by my chess engine is doing this.
It uses the typical isInCheck method of taking the king's index and looking for knight,rook, etc. moves from there.
I have optimized this routine about all that I can.

I also have a check-evasion move generator, so I am here referring to the case where we are NOT in check already.
Also, let's forget about king moves for the moment.

Intuitively, it seems wasteful to be doing so much verification just to catch the cases where you are moving an
absolutely pinned ( pinned against the king ) piece.

I know that some engines allow the king to be captured, but that sounds like too massive of a re-architecture
for a mature engine. ( Would need to be planned at the start, right)

Any thoughts are appreciated. Thanks in advance.

"My questions involves the optimization of move legality testing after doing a make"
It's too late to optimize move legality after doing a make. The most efficient approach is doing the verification *before* doing a make. I recommend that you create a legal move generator. An optimized legal move generator is similar in speed to a semi-legal generator.

In the move generator you can examine the 'from' square and the 'to' square of the moving piece for legality. Write code to make sure there are no revealed attacks on the moving side's king caused by vacating the 'from' square. You will want to remember if vacating the 'from' square caused a check to the opposing king (in-check). Also write code to keep track if the new 'to' square directly attacks the opposing king (in-check). Using this method, the in-check testing in the search becomes almost free.

The fastest way to do legal move generation is to maintain an incremental bitboard of pinned pieces. The details of a legal move generator are very difficult to get right. Expect to spend a long time debugging!

Ron

[H.G.Muller]

The best soluton might depend a great deal on whether tour engine is bitboard or mailbox. In a mailbox engine it is usually also a time saver to detect pinned pieces before you start generating moves, and limit generation of moves with pinned pieces to moves along the pin ray. This is faster than generating all pseudo-legal moves, and much faster than generating all pseudo-legal moves and then testing them for legality. You can then only blunder into check through King moves, or the extremely rare case of an e.p. capture where two blocking Pawns disappear at once.

So explicitly testing for legality would then still be needed after King moves. But they are comparatively rare, so how you do that doesn't have a large impact on performance.

[ambrooks1]

Ron, HG:

Thanks for the reply. This is very interesting - do you do this in your Horizon engine?

I happen to be using a bitboard representation, but also maintain a mailbox ( that
means 64 char array, right?) for the purpose of identifying capture victims quickly.

So if I understand correctly, during make/unmake you update a pinned pieces
bitboard. Then you consult this during move generation. It would be nice if
you could just consult the pin table and say "Nope, you're pinned, so you
cannot move". That would be fast- but in reality you also have to check if
the pinned piece can capture the pinning piece.

You seem to be forced to add a lot of complexity to the make routine:

Here are the cases then that affect the pinned piece bitboard during make move:
1) Did your moved piece interpose between an enemy sliding piece and your king? Your piece is pinned.
2) Did your pinned piece just get captured? Your piece is unpinned since it no longer exists.
3) king move ? Your piece is now maybe newly pinned or newly unpinned
4) If your piece is a sliding piece, did it just pin somebody?

I wonder if I am missing something? Not so clear to me that
this is a winning timesaver.

I just noticed this discussion on talkchess.com from 2008:
http://www.talkchess.com/forum/viewtopic.php?t=22550
where the the technical details of a pin bitboard are discussed.

[ambrooks1]

"...In a mailbox engine it is usually also a time saver to detect pinned pieces before you start generating moves, and limit generation of moves with pinned pieces to moves along the pin ray...".

I hadn't fully understood your comment before I made my last comment. Of course, it is not just capturing the pinning piece, during move generation - you can move anywhere along the pin ray, as you just said.

But in a mailbox engine, you would still need this setup with a pinned piece bitmap, which gets incrementally updated during make, with all those complex cases, right?

Otherwise, you have to figure out if the piece is pinned against the king at the start of generating its moves. That sounds kind of time consuming, but maybe it pays off when you do the math? Hmmm....

[H.G.Muller]

In mailbox checking for pins is comparatively cheap: only sliders can pin something, and the opponent has at most 5 sliders (in practice). So what I do in Joker, for example, is run through the slider part of the piece list to test for alignment with the King of the side to move. That is a simple test, and usually there is no alignment, and it stays at that. In the rare case there is alignment you have to scan the ray until the the second obstruction if the first obstruction is your own piece. That is some more work, but when a pin is detected the on-ray moves of that piece can be generated immediately, and the piece is then temporarily removed from the piece list during normal move generation.

I guess what makes it attractive is that as a spin-off you also detect if you are in check by the sliders: sometimes the first obstruction along the ray scan is your King! You want to do that anyway before move generation, to see if you should invoke the evasion generator. The remaining part of the in-check test is then reduced to just looking on two board squares for Pawns, and checking the Knights part of the piece list to see if one of those aligns. So basically the early part, detecting slider alignment with the King, and scanning the ray to the first obstacle is what you would do anyway. The only overhead occurs when the obstacle is your piece (but not King). Then you have to continue scanning the ray to the next obstacle, to see if it is your King (which you already know to be on the ray). But by that time the chances are pretty large that you are indeed dealing with a pin.

[ambrooks1]

I just had an idea.
Before move generation :

Why not just generate all the possible bitboards representing pins - your king,
your blocking piece and the enemy slider?

Taking just diagonal attacks or just vertical/horizontal attacks -

For each square for the king
For each of 4 rays
for each of 5 types of blocking pieces
for each of 2 types of enemy slider
for roughly 5 permutations of blocker, empty, enemy slider

This gives 64*4*5*2*5 or roughly 12,00 or so positions. Put them in a hashtable.
Then during move generation, you could create up to two bitboards:
ORing your King, your piece-to-move
and, successively, your opponents queen and bishop ( where the queen and bishop is serialized to one per bitboard).

And you use this to search the hashtable to check if the piece-to-move is pinned or not.

[ambrooks1]

oops - typo 12,000 positions

[Ron Murawski]

Ron:
Thanks for the reply. This is very interesting - do you do this in your Horizon engine?

I did not have a legal move generator in my old Horizon, but I do in the unfinished, unreleased, new version.

I just checked my latest code and it seems that I now do a full calculation for pinned pieces at the top of my movegen code. I found that trying to detect all of the special cases to avoid recalculating took longer than just blindly recalculating from scratch. The pinned-piece bitboard is stored in a game-history array indexed by move number, so no pinned-piece code appears in my make/unmake code.

Ron

[ambrooks1]

Maybe the legal move generator is the next idea I will try out.

I tested the simplest possible alternative first. I used some Gerd Isenberg code snippets from the chess programming wiki
which get the list of squares of pinned pieces. I stuck that into my search code right before make.

My results were sadly typical of trying out new features in general. I obviously saved time by doing less
inCheck testing ( only on pinned pieces and king moves [ and some other exceptional cases] ) , but this was compensated by the time spent checking each position for pinned pieces.

The net result was slightly slower code. Sigh...

[ambrooks1]

The pinned-piece bitboard is stored in a game-history array indexed by move number

I didn't quite understand this. When you are generating moves during search, I don't see how the game-history array would
be relevant - at least the way I understand this term. Did you perhaps mean to say the game-state?

The way I understand these terms, the game-history array is the actual moves played in the game so far. ( Maybe
different people use different terms for this stuff?)

[Ron Murawski]

The pinned-piece bitboard is stored in a game-history array indexed by move number

I didn't quite understand this. When you are generating moves during search, I don't see how the game-history array would
be relevant - at least the way I understand this term. Did you perhaps mean to say the game-state?

The way I understand these terms, the game-history array is the actual moves played in the game so far. ( Maybe
different people use different terms for this stuff?)

I have an array containing all the game moves (plus extra information). If I do a deep search this array includes possible future moves. Any move less than the current move is an actual game move.

The place I keep track of pinned pieces is at the beginning of my move generator. For all possible moves that I try from any current position, the pinned piece information will be the same. A piece that is flagged as pinned in this bitboard will be limited in its movement.

Ron

[ambrooks1]

Thanks Ron.

Obviously, if you are using it the pinned piece detector code
that you use in your legal move generator must be giving you good performance -
I wonder if you are doing something very different from the Gerd Isenberg
code that I referred to earlier?

[Ron Murawski]

Thanks Ron.

Obviously, if you are using it the pinned piece detector code
that you use in your legal move generator must be giving you good performance -
I wonder if you are doing something very different from the Gerd Isenberg
code that I referred to earlier?

My code is not much different from Gerd's but I do a lot of little optimizations; for instance, I use 'const' qualifiers on variables wherever I can. Minimizing global memory accesses is very important. A single memory access can takes hundreds of cpu cycles, so it is sometimes faster to calculate from scratch than to access the result of that calculation from a global array. It is sometimes possible to change a small global array into a local array, this can improve performance quite a bit. Another optimization trick is making sure that global memory access locations are physically close to each other. Sometimes changing the order of lines of code can speed things up too.

If you spend a lot of time optimizing, it sometimes surprises you how much improvement is possible, and other times it's a big waste of time.

Ron