Bitboard of Pinned Pieces

[bob]

We're doing almost the same except that you make the move before determining if that still leaves the king hanging and therefore leads to an illegal position while my implementation is that I check before making the move if it is legal, thereby saving me the call to unmakemove if it is indeed illegal. It doesn't really matter anyway as most pseudo-moves are legal.

In the case of hash moves and killer moves, I have a routine to check if it is a valid move for that position, therefore it is safe from hash collisions as it makes sure that the move is valid, after that I double check with calling moveIsLegal and that should never leave the king hanging. It's pretty safe, I have not experience any crash or something due to illegal move, it's what Glaurung and Fruit is doing too. Glaurung even uses this technique to avoid using locks in the transposition table as the hash move is being validated anyway.

When in check I also have a legal move generator just like in Crafty and I don't call any move validation for that routine also.

Actually that is _the_ point. AKA procrastination. I only check for legality when I actually have to make the move on the board, In fail-high (CUT) nodes, I generally search just one move and only legality-check that move (if not already in check).

I ran some stats on crafty and got this
check called/moves generated = 1.09, check called/moves made = 1.54 , check called/incheck = 13.62
This makes a legal move generator look better, as it may be expensive, but I doubt it is more expensive than calling incheck 30 times.

I'm not sure I understand your numbers. but the issue is this: A legal move generator does more work screening out illegal moves as it produces the list. It does this extra work for _every_ move that is generated. Crafty Doesn't do the in check test on at least 1/2 of the moves generated, because for two consecutive plies, you look at all moves at one of them, and just one move at the other...

I tried it both ways when I first started Crafty. In fact I tried three approaches...

1. Just use pseudo-legal moves and in-check each one as it is actually made on the game board.

2. Do legal move generation. This was actually pretty easy in early versons of Crafty since I had the attacks_from and attacks_to bitboards handy. But this was slower.

3. use 1 above plus a legal move generator when in check. This has the added benefit of not trying illegal moves when most moves are illegal. This was the fastest approach I found and is what I use today.

A legal move generator has two isues.

(1) generating moves when not in check requires checking along a specific rank/file/diagonal that bears on the king, if a piece is moved from that diagonal/rank/file.

(2) generating moves when in check is a completely different animal because the move has to either remove the checking piece, or interpose on the rank/file/diagonal if checked by a sliding piece, or move the king. The GenerateCheckEvasions() code in crafty is a bit complex to think about but is not that big in terms of lines of code.

Different data structures might make my approach worse for other programs of course. But I've spent years trying to find the fastest solution for each performance issue identified in Crafty.

[Edsel Apostol]

Actually that is _the_ point. AKA procrastination. I only check for legality when I actually have to make the move on the board, In fail-high (CUT) nodes, I generally search just one move and only legality-check that move (if not already in check).

Procrastination is a good idea especially when you save a lot of processing time.

I had been using the same idea as yours when I'm just starting. In my futility pruning inside the move loop I used the in_check routine to determine if a move is a candidate for pruning (there are lots of other criteria). The in_check routine is called only after making the move. The problem is that in positions where the current position eval is much less than alpha, a lot of moves is being pruned.

In my old implementation just like yours, that means I have to call unmakemove for all these moves, a waste of processing time. I called makemove, unmakemove, check if king is hanging and check if a move is check, all of that is useless as in the end the move will only be pruned.

That's why I did like what Glaurung and Fruit does by determining first if a move is legal and if it gives check. I'm doing it per move, the first move being the hash table move, depending in my move ordering. That means that I can prune a move (futility pruning) without calling makemove, unmakemove, check if king is hanging, determine if move is check. It seems faster to me. Maybe Crafty didn't have Futility Pruning inside the move loop that's why it is fine with it to do that, just like in Strelka.

[bob]

Actually that is _the_ point. AKA procrastination. I only check for legality when I actually have to make the move on the board, In fail-high (CUT) nodes, I generally search just one move and only legality-check that move (if not already in check).

Procrastination is a good idea especially when you save a lot of processing time.

I had been using the same idea as yours when I'm just starting. In my futility pruning inside the move loop I used the in_check routine to determine if a move is a candidate for pruning (there are lots of other criteria). The in_check routine is called only after making the move. The problem is that in positions where the current position eval is much less than alpha, a lot of moves is being pruned.

In my old implementation just like yours, that means I have to call unmakemove for all these moves, a waste of processing time. I called makemove, unmakemove, check if king is hanging and check if a move is check, all of that is useless as in the end the move will only be pruned.

That's why I did like what Glaurung and Fruit does by determining first if a move is legal and if it gives check. I'm doing it per move, the first move being the hash table move, depending in my move ordering. That means that I can prune a move (futility pruning) without calling makemove, unmakemove, check if king is hanging, determine if move is check. It seems faster to me. Maybe Crafty didn't have Futility Pruning inside the move loop that's why it is fine with it to do that, just like in Strelka.

Crafty has had futility pruning for years, so that wasn't an issue in deciding which way to go. I suppose the deciding factor has to be how everything fits together and what is expensive to do and what is not...

[xsadar]

. . .

I tried it both ways when I first started Crafty. In fact I tried three approaches...

1. Just use pseudo-legal moves and in-check each one as it is actually made on the game board.

2. Do legal move generation. This was actually pretty easy in early versons of Crafty since I had the attacks_from and attacks_to bitboards handy. But this was slower.

3. use 1 above plus a legal move generator when in check. This has the added benefit of not trying illegal moves when most moves are illegal. This was the fastest approach I found and is what I use today.

I designed my move generator to do something almost the same as number 3 (although I still have yet to implement the in check part). The difference is that when in check it still may try to move into check (but by another piece) to avoid the current checking piece. For example in this position:

[d]4k3/8/8/q7/8/4r3/3Q4/4K3 w - - 0 1

It will generate the moves Qe2 and Qxe3, even though they're not legal because they block or take the original checking piece. However, no other queen moves would be generated, because it would leave the king still attacked by the rook. Also, Ke2 would not be generated, because it doesn't move the king out of the rook's line of attack.

So do you think my method would likely be any worse or better than generating fully legal moves when in check? I'm guessing any difference would be small, whether or not there is a difference.

A legal move generator has two isues.

(1) generating moves when not in check requires checking along a specific rank/file/diagonal that bears on the king, if a piece is moved from that diagonal/rank/file.

(2) generating moves when in check is a completely different animal because the move has to either remove the checking piece, or interpose on the rank/file/diagonal if checked by a sliding piece, or move the king. The GenerateCheckEvasions() code in crafty is a bit complex to think about but is not that big in terms of lines of code.

Different data structures might make my approach worse for other programs of course. But I've spent years trying to find the fastest solution for each performance issue identified in Crafty.

[bob]

. . .

I tried it both ways when I first started Crafty. In fact I tried three approaches...

1. Just use pseudo-legal moves and in-check each one as it is actually made on the game board.

2. Do legal move generation. This was actually pretty easy in early versons of Crafty since I had the attacks_from and attacks_to bitboards handy. But this was slower.

3. use 1 above plus a legal move generator when in check. This has the added benefit of not trying illegal moves when most moves are illegal. This was the fastest approach I found and is what I use today.

I designed my move generator to do something almost the same as number 3 (although I still have yet to implement the in check part). The difference is that when in check it still may try to move into check (but by another piece) to avoid the current checking piece. For example in this position:

[d]4k3/8/8/q7/8/4r3/3Q4/4K3 w - - 0 1

It will generate the moves Qe2 and Qxe3, even though they're not legal because they block or take the original checking piece. However, no other queen moves would be generated, because it would leave the king still attacked by the rook. Also, Ke2 would not be generated, because it doesn't move the king out of the rook's line of attack.

So do you think my method would likely be any worse or better than generating fully legal moves when in check? I'm guessing any difference would be small, whether or not there is a difference.

A legal move generator has two isues.

(1) generating moves when not in check requires checking along a specific rank/file/diagonal that bears on the king, if a piece is moved from that diagonal/rank/file.

(2) generating moves when in check is a completely different animal because the move has to either remove the checking piece, or interpose on the rank/file/diagonal if checked by a sliding piece, or move the king. The GenerateCheckEvasions() code in crafty is a bit complex to think about but is not that big in terms of lines of code.

Different data structures might make my approach worse for other programs of course. But I've spent years trying to find the fastest solution for each performance issue identified in Crafty.

I doubt it makes a lot of difference, although doing pure legal moves are easy enough. The point is that in a position like yours, there are something like 25 possible moves, most being illegal. In worse positions, there are many more possible moves but few are still legal. By eliminating the non-legal moves at generation time, you end up saving time by avoiding the make/check/unmake work to discard each illegal move. In normal positions, most, if not all moves are legal, and the extra work to generate legal moves is not such a good idea since in many positions, most of the moves are never even considered anyway.