And here is some code from the check evasion move generation routine. These three chunks do all the interposition moves, and it each one the pinned piece overhead is a single bitboard mask, done only once.
From observing the execution of the above code and similar code in the generation functions, I'd say that the pinned/frozen data actually make them run faster overall in part because no bogus moves are generated.
So the question of overhead is limited to the actual calculation of the pinned/frozen bitboards. The calculation is not trivial, but bitboards make it fairly fast.
The symbol rstrct-bb has the restricted bitboard value; this is the bitboard produced only once per move execution that contains the pieces that are pinned against the king but are not frozen. (Frozen pieces are pinned pieces that are pinned along a direction in which they can't move.) The pinned and frozen bitboards themselves are also computed once per move execution.
A beamer bitboard is the set of squares that is the open ray from the first square in the first square to second square direction.
At the start of move generation, the bitboard of active color piece locations is masked by the frozen bitboard, so the from-square scanner loop doesn't even do a dispatch.
What about the data that shows what is pinned? Has to be updated frequently...
sje wrote:And here is some code from the check evasion move generation routine. These three chunks do all the interposition moves, and it each one the pinned piece overhead is a single bitboard mask, done only once.
I have always had a legal move generator for use when I start off in check. But that is a different animal than generating legal moves when you are not in check to start with...
Looking at it though, I don't like the idea. I don't want a separate attack table just for pins, which would even be 4x bigger than my current ones. I'm not even sure if it works--you can't determine the type of situation (discovered checks, double checks, etc.) without the piece type and color of every piece between the king and the attacker. And you would need to separate it from either direction. This approach would need to differentiate between these situations in order to be useful to me:
r.B.K... -> abs. pinned on left
.rb.K... -> double check on left
rb..K.Rq -> discovered check on left, half pin on right
...and myriad other possibilities...
...which it clearly can't, unless I'm mistaken. I don't know if this approach would even be faster than my current (mental) approach, and it is far less flexible.
Well, I have it working. And now I'm re-writing my move generators to handle the information to produce only legal moves.
To get it working I have to handle the rank, file and two diagonals separately.
Example, the rank:-
If the king is checked along the rank on the left, a pin on the right can be ignored (and vice-versa), the index no. tells me the file no. of the checker and whether it's a contact check or distance check. The lookup gives me the defendable squares.
If there is a pin or two pins, (there are only 16 combinations) the index tells me that there is a pin and which combination. I create a bitboard of pinned/discovered_check pieces from the lookup.
If the king is also checked along the diagonal or by a knight I set the index to a certain number to trigger the king_moves_only move generator.
If there are other pins along the file and diagonals I just OR these in to the pinned/discovered_check bitboard to be filtered in the move generator.
The total of all tables added together is about 50K (good magics required).
The rank, file and two diagonals, each give an index if there is a check or pin. The information is combined and passed to the relevant move generator.
bob wrote:Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.
I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...
I personally don't think the cost is offset by the gain. most moves are legal, and it is, IMHO, better to delay verifying the legality until the very last minute, because you might not even search the move at all.
I'm not so sure. Generating legal moves has a relatively small constant cost, while you have to verify every move for legality.
But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.
Are you sure of that ? I ran some tests on crafty a while ago which said that crafty called incheck() more than once per move generated and that the number of nodes searched was not much smaller than the number of moves generated. I could have made a mistake, but you might want to run the tests yourself.
Zach Wegner wrote:Ha, I knew there would be someone to correct me. I suppose I should've said "bitboard-based legal generators in C", but even then I'm not sure.
Hi Zach,
I hope you don't mind being corrected again?
It may very well be true that the majority of current open source bitboard chess engines only do pseudo-legal move generation, but the best, most instructive and elegant program of them all does true legal move generation: Olithink.
bob wrote:Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.
I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...
I personally don't think the cost is offset by the gain. most moves are legal, and it is, IMHO, better to delay verifying the legality until the very last minute, because you might not even search the move at all.
I'm not so sure. Generating legal moves has a relatively small constant cost, while you have to verify every move for legality.
But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.
Are you sure of that ? I ran some tests on crafty a while ago which said that crafty called incheck() more than once per move generated and that the number of nodes searched was not much smaller than the number of moves generated. I could have made a mistake, but you might want to run the tests yourself.
It had better not do that. After a move is made, a call to InCheck() is made, unless we are in check when we start that ply, then we trust the legal move generator to get us out without the test. There are no InCheck() calls in the q-search where most of the moves are actually produced and searched. So I can't imagine how that could happen. Even if you only count move generated and InCheck() calls in the normal Search() function, I don't see how InCheck() could be called more than the number of moves actually searched, which is _far_ less than the total number of moves generated. I might try to verify this to be sure there is no bug anywhere, but this would usually show up on profile runs anyway...