Algorithm for mate recognition

[Fulvio]

I'm writing some code to convert a UCI move to a SAN move.
I'm surprised by how difficult is to recognize a mate position in an efficient way.
Below is my pseudo-code: does anyone know a better algorithm?

Code: Select all

nChecks:= number of adversary pieces that checks the king
if nChecks > 0
    kingMoves:= generate evasions, that is legal moves of the king
    if kingMoves is not empty
        return not_mate
    if nChecks > 1
        return is_mate
    blockCapture_squares:= squares that captures or block the enemy piece
    for each blockCapture_squares
        for each of my pieces
            if moving to the square is legal
                return not_mate
    return is_mate

[hgm]

Just do a 1-ply alpha-beta search that calls a King-capture test to determine which moves are legal. If none are legal, do a King-capture test after null move to determine whether you are in check. You can take a beta cutoff after the first legal move.

[Fulvio]

Thanks for the reply, I should have stated clearly my objective.

I profiled SCID code when exporting a database to PGN and discovered that a lot of time is spent testing for check/mate.
The current code works mostly like you suggested: it is only missing the cutoff.
Exporting 1 million games to PGN takes 74 seconds on my computer with the current code.
Implementing the cutoff reduce the time to 71 secs.
Removing the mate test: 67 sec.
Removing both the check and mate test: 54 sec.

Considering that most games have few positions with checks, my intuition is that there should be some trick to make thing faster.
Maybe with bitboards based on the king position, i do not know, but someone may have already researched this problem.
That's why I'm asking for suggestions.

[Teemu Pudas]

Check testing (after makemove):

Code: Select all

if (castling) tosq = rookSquare; 
if ((ray[kingsq][fromsq] | ray[kingsq][tosq]) & enemySliders) {
  // test for slider checks along the rays
  // Also: first look ahead at the next move. If it's not a king move or a move onto one of the rays, then this move can't have been a sliding check.
}
isContactCheck = contactBB[movingPiece][tosq] & bit(kingsq);

Mate testing: well, if the game continues then it must not have been mate. Likewise if the player that made the last move didn't win.

[hgm]

Exporting 1 million games to PGN takes 74 seconds on my computer with the current code.
Implementing the cutoff reduce the time to 71 secs.
Removing the mate test: 67 sec.
Removing both the check and mate test: 54 sec.

From this I calculate the check test takes 13 sec, and the (cutless) mate test 7 sec. Taking the cutoff reduces the 7 sec to 4 sec.

The latter already is suspect: most positions in a game should have 30-40 moves, and on most of them the first move you try would be legal (only in-check positions stand a large chace to leave a King in check, and they are rare). So cutting after the first legal move is expected to reduce the time spent in the mate test by a factor 30 for >90% of the positions. Even for in-check positions there usually is more than a single evasion. If there are 3 (say), searching the pseudo-legal moves in random order would give you a cutoff after searching 1/3 of the moves, and thus speed up the test a factor 3. You don't even gain a factor 2 in total, while something like 20 would be expected.

Note that when you are not interested in stalemate, you don't have to test for mate when not in check (i.e. you could start to see if the null move is legal, and cut when it is). It is testing for stalemate that makes it expensive.

Since your mate test takes less than your check test, and any mate test involves at least one check test (when the first pseudo-legal move turns out to be legal, and you take the cut), I assume you already do apply it to only a subset of the moves. (While the check test is applied to all.)

The question seems not so much how to best detect mate (as your original post addresses), but how to best detect whether a given move checks. In an engine this is usually done by testing if the moved piece checks the King, or whether a Queen on the from-square could check the King, and if it can, whether upstream along the check ray there is indeed a slider of the side to move that moves (sufficiently far) in that direction. Both tests can start with testing alignment, and leave it at that when there isn't any (which is the common case). So it should be quite fast.

[Fulvio]

Brilliant!!
The key idea is that moving a queen cannot create a discovered check.
With normal moves (no castle, no en-passant) it's possible to test an imaginary queen at the from-square.
If this queen cannot attack the enemy king, the from-square cannot block any check and no discovered checks are possible.
It is only necessary then to check the moved piece, but since it is known that the from-square cannot block any check, there is no need to do the move on the board.
It suffices to test if an imaginary piece of the same type placed at the to-square can attack the enemy king.

Just with this two simple optimizations I went down from 74 sec to 63 sec!
Thanks a lot!

[Fulvio]

Your analysis is correct, there are other details that contribute to the test results.
The code is here:
http://scid.sourceforge.net/doxygen/htm ... tml#l02114

In particular the SAN notation is generated before making the move, and to test for checks the move is done and undone.
Also my test for the cutoff was only partial: generate all king moves, stop if a move has been found, generate all queen moves, stop if a move has been found, etc...

With the two ideas suggested by Teemu Pudas the code is already much faster, and I'm sure it can be further improved.
However I would like to measure first how fast can be a re-written function that generates the SAN notation after making the move.
Below there is my updated pseudo-code.
Finding if a piece attacks a square is fast, and I considered it the basic operation for the Big O notation.
The part that I still do not like is the last one, when the moves that capture or block the attacker are generated.

Code: Select all

// Test if an imaginary queen at from-square attacks the king. O(1)
multiple_checks:= true_if(imaginary_queen, attack_the_enemy_king)

if multiple_checks_is_true
  // Test if an enemy attack the king. O(15)
  attacker:= find_if(enemy_pieces_excluding_the_king, attack_the_king_square)
else
  // Test if the moved piece attacks the enemy king. O(1)
  attacker:= find_if(last_moved_piece, attack_the_enemy_king)

if no_attacker_has_been_found
  return NOT_CHECK;

 // Test if the king can move to a non attacked square. O(16*8)
remove_the_king_from_the_board
evasion:= find_first_of(enemy_pieces, king_evasion_squares, the_square_is_not_attacked)
re-place_the_king_on_the_board
if an_evasion_square_has_been_found
  return CHECK;

// Double checks cannot be blocked, but pawns cannot double check. O(14)
if multiple_checks_is_true && attacker_is_not_a_pawn
  if find_if(a_different_enemy_queen_rook_bishop_knight, attack_the_king_square)
    return MATE;

 // Try to capture or block the attacker. O(15*7*13), 13 is the number of enemies that can pin.
if find_first_of(my_pieces_excluding_the_king, block_and_capture_squares, is_legal_to_move_to_the_square)
  return CHECK;

return MATE;

[jwes]

Thanks for the reply, I should have stated clearly my objective.

I profiled SCID code when exporting a database to PGN and discovered that a lot of time is spent testing for check/mate.
The current code works mostly like you suggested: it is only missing the cutoff.
Exporting 1 million games to PGN takes 74 seconds on my computer with the current code.
Implementing the cutoff reduce the time to 71 secs.
Removing the mate test: 67 sec.
Removing both the check and mate test: 54 sec.

Considering that most games have few positions with checks, my intuition is that there should be some trick to make thing faster.
Maybe with bitboards based on the king position, i do not know, but someone may have already researched this problem.
That's why I'm asking for suggestions.

Rethinking the problem and assuming the moves are all valid, you need to know three things:
1. Are there multiple moves to the to square by the same piece type?
2. Does the move give direct or discovered check?
3. Does the move give mate?
You do not need to generate moves to answer any of these questions.

Create an array of structures[from][to]:
struct {
BITMAP between;
BITMAP extend;
int attack;
} atks[64][64];

attack is a set of bits for which piece types on the from square could attack the to square:
1 - wp
2 - bp
4 - n
8 - b
0x10 - r
0x20 - q

between is a bitmap of the squares between the from square and the to square which need to be empty for a slider to attack (0 for non-sliders).
extend is a bitmap of the squares behind the from square which could give a discovered attack on the to square.

Now disambguation is done by:
for all other pieces of the same type:
if atks[square][to].attack and piece type bit
if (!(board & atks[square][to].between))
disambguate (you can check if the piece is pinned in the same way as discovered checks)

direct checks can be done by:
if atks[to][king sq].attack and piece type bit
if (!(board & atks[square][to].between))
it is check

discovered checks can be done by:
if atks[from][king sq].extend
if (!(board & atks[from][king sq].between)) // need to make move on board first for case of pawn or king move toward opposing king
if ((queen bitmap | (atks[from][king sq].attack & 8) ? bishop bitmap : rook bitmap) & atks[from][king sq].extend)
test each possible to see if it gives check

A simple way to test for checkmate is:
if (last move in game & in check)
remove checked king from board (to attack square behind king)
generate attacks
if all squares adjacent to king attacked or occupied by same color pieces it is checkmate.

[jwes]

I think after this, you would need to look at ASCII conversion and overlapped I/O to speed it up significantly.

[Fulvio]

I think after this, you would need to look at ASCII conversion and overlapped I/O to speed it up significantly.

ASCII conversion takes 12,69% of the time and fwrite 8,47%.

Thanks for your suggestions, I will test them.
However the atks array will be very huge: 20 bytes * 64 * 64 = 80kB

I suspect that all the cache misses will hurt performance.