Check idea + bittwiddler request

[jwes]

I had an idea about deternining if a move gives check (the new? part is about discovered check).

A move gves check iff
1. a. The piece moved is not a slider and it attacks the opposing king.
b. The piece moved is a slider and there is a horizontal, vertical, or diagional line between the to square and the opposing king and the piece moves in the direction of the line and the squares on the line between the piece and the opposing king are all empty.

2. There is a horizontal, vertical, or diagional line between the from square and the opposing king and the squares on the line between the from square and the opposing king are all empty and the from square is attacked by a slider of the side moving in the direction of the line.

The from square being attacked can be calculated cheaply if the program generates attacks for each piece and each direction during move generation. Simply make bitmaps for the four directions and or in the attacks for each slider as you generate moves.

The bittwiddling part of this is finding the best way to determine if two squares are on a line, what direction the line is, and get a mask to determine if the squares between the two are vacant.

[sje]

The bittwiddling part of this is finding the best way to determine if two squares are on a line, what direction the line is, and get a mask to determine if the squares between the two are vacant.

Symbolic's toolkit has a lookup table dir[64][64] that returns the direction from the first square index to the second. It also has a lookup table bb[64][64] that gives a bitboard that has the intersquare pathway between the two index squares.

[hgm]

If your board is sufficiently large (from 12x15 on) you don't even need 64 x 64 tables for these lookups indexed by FROM and TO, but you can do with a 1-dim table of 239 elements indexed by TO-FROM. This is known as a 0x88 attack test.

Indeed, if you want to detecht checking moves, for the discovered checks it is much more efficient to do bulk testing starting from the sliders of the STM. There are typically only 5, and after the first lookup most are eliminated because they don't line up with the enemy King. For the few that do you can scan the line between them and King (the board step coming from te table), and if there is only a single piece of the STM all its moves in different directions will deliver discovered check.

It would probably be fastest to generate moves with these pieces immediately, and then temporarily mark them as captured so that the normal move-generation process will ignore them. That is also how I do it for pinned pieces, except that ther you have to generate only the moves on the pin line. The pin check should take precendence, though, meaning that you would have to go back to mark already generated moves as checks in the rare case that you can deliver discovered checks with a pinned piece.

I have also been thinking for an algorithm to selectively generate normal checks (i.e. without generating all moves and applying the 0x88 capture test between TO square and enemy King for all of them). The idea would be to have a table indexed by KING-FROM similar to that for the attack test. But in stead of listing in which directions the attack is possible, it should list the squares on which the attack is possible, as Sliders can generally get everywhere in two moves. In a bitboard engine you could store the path that needs to be empty for each of the checking possibilities.

This would work great for most pieces, that can deliver checks in at most two ways. (You would have to take separate care of the case where they are already aligned, but can check through a capture.) The problem is Queens: they can deliver check in upto 12 ways...

[sje]

To determine if a move will give check before actually executing the move requires a lot a work. This is because of the special case moves: castling, en passant, and the promotions.

Symbolic has a routine for efficiently determining move checking status without move execution and it's rather long and detailed. If you should try writing one, be prepared for a lot of testing to make sure that it's correct.

[hgm]

Well, I don't care so much about the special moves. In cases where you want to search checks only, you can easily afford to search the promotions, e.p. and castlings as well, as these are rare. Probably you extend promotions anyway, and e.p. is a capture and therefore even searched in QS. Remains castling, which is not possible during most of the game anyway. I could live with a search that overlooked checks by castling, as the corresponding bare Rook move would still be searched.

But even then, it is a lot of work to find checks. I guess special accounting of the Pawn shield could be crucial here. Pawn-shield awareness can make you discard the possibility for non-capture checks from many directions at a glance. That only leaves Q+R checks from the last rank with an intact Pawn shield (and enemy pieces are seldom there).

[sje]

Symbolic has two routines that work directly with checking determination without move execution. The first is a rather long and complicated function that takes a move list and sets the checking flag in each checking move. The second is the routine that generates capturing and/or checking moves. Both routines do a lot of initialization work that makes the later scanning work much faster.

The program does not have a routine that generates only checking moves as this is rarely needed. Instead, the regular move generator is called, the checking marking routine is called on the result, and finally a third routine edits the move list to delete the non checking moves. All of this is done without doing any actual move execution.

The capture/check move generator is used in Symbolic's A/B searcher usually between the full width search region and the capture/evasion region. It was inspired by a similar technique described in the Northwestern Chess 4.x report.

[hgm]

My application would be in futility pruning. If current eval is so much below alpha that even capture of the highest piece still on the board would not bring you back in window, you can prune the node even before move generation. This saves a lot of time compared to generating all captures, look at what they capture and decide it is not enough on an individual basis.

But if your QS does not allow stand pat when in check, pruning the checking moves would not be theoretically sound. So in that case you would want to search only checking moves. Having to generate all moves and do the check test on them spoils the advantage entirely. And in most cases, there would not even be any checking moves. Having a quick test that rules out that there are checking moves would thus already come in very handy.

[bob]

I had an idea about deternining if a move gives check (the new? part is about discovered check).

A move gves check iff
1. a. The piece moved is not a slider and it attacks the opposing king.
b. The piece moved is a slider and there is a horizontal, vertical, or diagional line between the to square and the opposing king and the piece moves in the direction of the line and the squares on the line between the piece and the opposing king are all empty.

2. There is a horizontal, vertical, or diagional line between the from square and the opposing king and the squares on the line between the from square and the opposing king are all empty and the from square is attacked by a slider of the side moving in the direction of the line.

The from square being attacked can be calculated cheaply if the program generates attacks for each piece and each direction during move generation. Simply make bitmaps for the four directions and or in the attacks for each slider as you generate moves.

The bittwiddling part of this is finding the best way to determine if two squares are on a line, what direction the line is, and get a mask to determine if the squares between the two are vacant.

This goes back to the 1980's versions of Cray Blitz.

Assume you use mailbox rather than bitboards:

direct[from][to] is an array that contains "0" if from/to are not on the same rank/file/diagonal, else a number representing the "direction" from <from> to <to> (which would depend on how you number your squares.) The basic idea is that from + direc[from][to] + direc[from][to] ... will eventually get you to <to>

Now you can define bitmasks in an array say "obstructed[from][to]" And there you initialize every square of that 64 bit mask (each obstructed[from][to] is a 64 bit value) so that any squares between <from> and <to> are set to "1" while all other squares are set to zero. Now you just AND obstructed[from][to] with "occupied_squares" and a non-zero value means that set of squares is blocked at least once...

[jwes]

You have given me a better idea. At the start of move generation, calculate bitmaps of squares that attack the opposing king for each of Q,R,B,N, and P. Then use these bitmaps with the move bitmaps to generate checking moves separately.

Discovered checks are only a little more work. When finding the squares that could attack the opposing king for each slider direction, if one of these is one of your pieces, calculate a second attack map for that direction with that piece removed. Then if the second attack map also attacks one of your pieces and that piece can move in that slider direction, then moving the first piece could give discovered check.

A similar idea could find pieces pinned against the oppposing king.

[sje]

There are many optimizations available, albeit at a cost in complexity.

An example: When scanning through a move list to mark checks, it's possible to take advantage of the situation where moves of the same man appear contiguously in the list. This can be done by computing (or looking up) data specific to the man and the from square just once and then using it for each move with the same man.