Draw and check mate detection

[eligolf]

Hi,

I am sory if these type of "simple" questions are not allowed, please let me know in that case.

I have recently started to calculate only pseudo legal moves for the king to not having to check for checks at move generation (saves time since many king moves are pruned away during negamax search). The big issue I am having is that I have to check and for checkmate at so many other places right now, and was wondering if there is any better way of solving this? As of now my code sort of looks like this:

1. Calculate pins and legal moves for pieces, calculate pseudo legal moves for the king and castling.
2. During the negamax possible move loop I have to check if the move is a king, and if the king end up in check. If so, try next move. This is trivial and don't take much time since most moves are not king moves.
3. The main issue is during evaluation when I have to check for checkmate or draw. To do this I have to calculate all legal moves in the position, do the king check thing again, and see if there are any legal moves left after king moves are removed. If in check and no legal moves -> checkmate, if not in check and no legal moves -> stalemate.

This is all getting very complicated, with the same check for check thing happening all over the place (also in the GUI when I as a human make a move). Before I simply got this lookup during search of moves, since I searched for only legal moves and could do the "if no legal moves and in check -> checkmate" thing there for free, timewise.

Should I somehow check for checkmate during legal move search as before and set a flag to checkmate? Or in Negamax loop? Or only in evaluation?

Do you have any concept of how you are solving this if you only do pseudo legal moves in your code?

[Joost Buijs]

In my engine I have two routines, one to check if the king is in check, and another one to check if a pseudo legal move doesn't put the king in check, this routine needs pin information. With bitboards you can calculate these very fast.

I start by:

1) calculate the pins and calculate whether the king is in check.
2) if the king is in check generate all legal evasion moves to get the king out of check, otherwise generate all pseudo legal moves.
3) if the king is in check and there are no legal evasion moves I score a checkmate.
3) in the negamax loop I only have to check for legality if the king is not in check and if the move is illegal continue to the next.
4) when the negamax loop is finished and the king is not in check and there were no legal moves I score a draw (stalemate).

Usually you only have to evaluate in quiescence when the king is not in check, and you can't score a stalemate in quiescence because you only try captures.

In quiescence I do:

1) calculate the pins and calculate whether the king is in check.
2) if the king is in check generate all legal evasion moves to get the king out of check, otherwise generate pseudo legal captures.
3) if the king is in check and there are no legal evasion moves I score a checkmate.
4) if the king is not in check I call the evaluation function and check for the stand pat condition if (alpha < eval) alpha = eval; if (alpha >= beta) return alpha; // for fail hard return beta;
5) in the negamax loop I only have to check for legality if the king is not in check and if the move is illegal continue to the next.

Of course there are many refinements possible like delta pruning in quiescence, but this is not the topic here.

In my engine checkers is just a bitboard with piece locations checking the king, I only calculate this once at each ply, you can think of this as a flag.

[hgm]

Normally you would not evaluate when in check. You would extend one ply to play evasions, and evaluate after those. Since you check the legality of the evasions when you try to make them, you can count the legal ones, and after your move loop conclude checkmate. In my engines the counting goes automatic, because I keep a variable bestScore, which starts at -INF, which is also the checkmated score, and illegal moves also get score -INF, so they don't improve bestScore. Thus, if bestScore == -INF after all moves, and I am in check, I am checkmated, and the bestScore already is the correct score for that, so I can return bestScore as always.

Stalemate is more troublesome. You are not in check there, so it can happen at d=0 (QS) that you are stalemated. And in QS you would normally not search all moves; perhaps you only search captures. And perhaps there are no captures, so you search nothing. So how could you know if you have a legal move? Even the stand-pat is troublesome: if eval >= beta, but beta > 0 (the draw score), it superficially looks like you have a stand-pat cutoff. But you could be stalemated, and then your score would not be eval, but 0. So returning eval can be 0. Now it is not very likely that the side with the positive eval is stalemated, but in can happen (e.g. in KPK with Rook Pawn). It would be quite expensive to generate moves in QS nodes where eval >= beta, just to catch the minuscule chance that you are stalemated. So normally you would ignore the problem, and refrain from move generation when you can stand pat. (Or actually, already not even make the move to this node in the parent, but prune it for futility.)

If you cannot stand pat, and have no captures that cause a beta cut (which then automatically would be legal), you could still be stalemated, and this still could make the difference between a fail low and a fail high. E.g. eval < beta < 0 would look like a fail low based on eval, but would be a fail high when stalemated. Strictly speaking you should start checking non-captures for legality, until you find a legal one. When piece moves are automatically legal, the checking of those is not very expensive; you only have to conclude they are there. But if there aren't any, you would have to check the King non-captures. Or just ignore the problem. During most f the game you have no chance whatsoever to be stalemated, so slowing down your engine with complex testing for things that will almost never happen is counter-productive.

This all applies to QS. At larger depth all moves get a chance to be searched, so if you didn't encounter any legal moves you would know it (e.g. bestScore stayed at -INF). When that happens without being in check, you have to correct the bestScore to 0 before you return it.

[Joost Buijs]

Of course I only generate captures in quiescence when not in check and the evaluation < beta.
What I outlined above was a little bit too much simplified. Probably it doesn't even hurt much becouse generating captures is way faster than evaluation.

[Sven]

3. The main issue is during evaluation when I have to check for checkmate or draw. To do this I have to calculate all legal moves in the position, do the king check thing again, and see if there are any legal moves left after king moves are removed. If in check and no legal moves -> checkmate, if not in check and no legal moves -> stalemate.

This is all getting very complicated, with the same check for check thing happening all over the place (also in the GUI when I as a human make a move). Before I simply got this lookup during search of moves, since I searched for only legal moves and could do the "if no legal moves and in check -> checkmate" thing there for free, timewise.

Should I somehow check for checkmate during legal move search as before and set a flag to checkmate? Or in Negamax loop? Or only in evaluation?

Do you have any concept of how you are solving this if you only do pseudo legal moves in your code?

Usually both checkmate and draw detection are done during search, not within eval. You may assume a non-terminal position when calling eval. By extending one ply when being in check you can already guarantee that eval calls from qsearch do not happen when being in check. In other cases where you might call eval to support specific search features, like nullmove, razoring, or futility pruning, you obviously don't do this when being in check, too.

The other part is draw detection. This is a search task as well, and all kinds of draws can be detected within search. A draw by fifty-moves rule or by repetition can only occur during full-width search or at the root node of qsearch. When adding quiet check moves during qsearch within the first N plies this is no exception since the node following a check is an evasion node, not a normal qsearch node. A draw by insufficient material can be detected anywhere. The only problem may be stalemate detection during qsearch. You might solve it by applying a heuristic: For bare king positions you might implement a simple static stalemate detection routine that checks whether any of the squares near our king is neither occupied by a friendly piece nor attacked by an enemy piece. If the moving side has more pieces than the bare king then stalemate is quite rare so you may safely assume that it won't happen during qsearch. There are few positions where all pawns are blocked and can't capture and all existing pieces are blocked or pinned, too. Missing such a stalemate during qsearch would introduce an error that can be considered reasonably small.

For this purpose, it does not matter at all whether your search works with pseudo-legal or fully legal moves. Since with pseudo-legal moves you will usually test whether your king has been left in check immediatly after making a pseudo-legal move, you will never search a subtree of an illegal move - unless your engine follows the "king capture" principle (a move is found to be illegal by capturing the king).

[hgm]

One small correction on that: futility pruning can be done at d<=1, so it can also be done when in check, and are extended to d=1 for the evasion.