Detecting Checks

[beneficii]

My current chess program (which plays Omega Chess) tests each of the opponent's pieces to see if they are attacking the king, in order to detect check. In this, I will consider pieces and pawns separately Now, in a lot of situations, it seems that this would be a very ineffecient, slow way to detect check (especially with OmegaChess, which has a higher proportion of jumping pieces and more pieces total). Now, one idea I am thinking of is to start with the king, and look at the squares near the king, such as checking for the knight by doing knight jumps or by sliding out diagonally and orthogonally from the king to test for the champion/wizard (for the required number of squares) and for the sliding pieces (and of course stopping once the champions/wizards are ruled out and it comes up to an piece that is not attacking the king or the end of the board). In the opening, and possibly in the middlegame, it seems that this would be much quicker than testing every single one of the opponent's pieces, but in the endgame it seems like it would tend to waste more, because of the fewer pieces and more wide open spaces (meaning that the sliding tests would take longer) that are typical of endgames.

Perhaps it should be based on the existence of an opponent's piece? For example, if it knows from a(n incrementally updated) table that its opponent has no knights, then it should not test for knights, etc.

What are y'all's thoughts on this?

[Ron Murawski]

My current chess program (which plays Omega Chess) tests each of the opponent's pieces to see if they are attacking the king, in order to detect check. In this, I will consider pieces and pawns separately Now, in a lot of situations, it seems that this would be a very ineffecient, slow way to detect check (especially with OmegaChess, which has a higher proportion of jumping pieces and more pieces total). Now, one idea I am thinking of is to start with the king, and look at the squares near the king, such as checking for the knight by doing knight jumps or by sliding out diagonally and orthogonally from the king to test for the champion/wizard (for the required number of squares) and for the sliding pieces (and of course stopping once the champions/wizards are ruled out and it comes up to an piece that is not attacking the king or the end of the board). In the opening, and possibly in the middlegame, it seems that this would be much quicker than testing every single one of the opponent's pieces, but in the endgame it seems like it would tend to waste more, because of the fewer pieces and more wide open spaces (meaning that the sliding tests would take longer) that are typical of endgames.

Perhaps it should be based on the existence of an opponent's piece? For example, if it knows from a(n incrementally updated) table that its opponent has no knights, then it should not test for knights, etc.

What are y'all's thoughts on this?

For chess the classic way to detect check is to examine the king's square. Pretend that the king is a knight and see if it can capture any opponent knights; pretend it is a bishop and see if it can capture an opposing bishop, etc for all the different chess pieces.

But, all you really need to look at is the opponent's last move and answer two questions: Did the move cause check directly? Did it reveal check from a sliding piece? This is usually the fastest method, but moves like castling or ep are quite difficult to get things right, so you might want to revert to the classic method as described above for the uncommon cases of castling and ep captures.

An alternative approach is to maintain an incremental attack board which lets you know immediately if the king is attacked. Maintaining this board, however, will slow down your program noticeably...

Ron

[H.G.Muller]

Indeed, an incremental approch for the on-check test is usually the fastest. For determining if the opponent checks you after his move it always works, just use 0x88 (0x210?) tests to test alignment of the mover to-square for the moved piece type and the mover from-square for Queen alignment, and then scan the rays starting from the King (so the scan ends quickly when the King is well shielded). For e.p. capturesyou would have to do the latter alsoon the capture square.

In case of testing legality of your own moves you only have to do the from-square stuff. But you have problems if you were already in check before the move, or when you moved the King. For these cases I usually use one of the non-incremental methods after tmaking the move. (Which out of laziness I then also do for e.p.captures, as they hardly occur in the tree.)

Both the method starting from the King-square and the opponent piece list have their advantages. Which is faster depends on the number of pieces that could make the move. E.g. for Knight checks you would have to test 8 board squares around the King, while the piece list (normally) only contains 2 Knights maximum (and perhaps none...). For the Pawns, however, you woud have to test only 2 board squares, while there might be 8 (10?) in the piece list. So in Joker I use the piece-list test for all pieces except Pawns. For the sliders going by the piece list is much faster in the end-game, which is why I prefer that in Joker. But in variants with many sliders, or awkward sliders (Xiangqi Cannons!) the King-centered method is stillcompetative in the middle-game, because there the King is typically well shielded.