Minimax tree search checkmates

[tetra]

When searching using any minimax tree search algorithm at the beginning of the search we should always check if that node we are searching is a leaf node to return the evaluation score. Imagine a position that we have mate in 1.. What programmers do to detect Mate? Do I have to generate at evaluation function the moves for the opposite side and see if are none and therefore return the mate value? Isn't this expensive (two move generations at a call)?

I had an idea to extend the search 1 depth only if the move is a checking move but again we have to check every move and that is expensive right?

If I don't do any of this ideas it will only detect Mate on the next depth because here we will generate moves for the opposite side and we will find for sure the Mate.

Tell me your ideas..

[User923005]

If a given position is a checkmate, then there are no legal moves. So in that situation, if you are in check, you do not even need to call eval.
If you are trying to create a mate solver, then you can use proof search.

There is no penalty at all for using alpha-beta over pure mini-max search, so I assume that you are doing at least that. Is that correct?

[tetra]

If a given position is a checkmate, then there are no legal moves. So in that situation, if you are in check, you do not even need to call eval.
If you are trying to create a mate solver, then you can use proof search.

There is no penalty at all for using alpha-beta over pure mini-max search, so I assume that you are doing at least that. Is that correct?

You didn't understand my questions.. The question here isn't about alpha-beta over mini-max or any other algorithm and I'am not trying to create a mate solver. Let me explain it again better.

Imagine this position:
rnbqkbnr/pppp1ppp/8/4p3/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq - 0 1

If you use stockfish:
>> position fen rnbqkbnr/pppp1ppp/8/4p3/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq - 0 1
>> go depth 1

The output is this:
info depth 1 seldepth 2 score mate 1 nodes 39 nps 9750 time 4 multipv 1 pv d8h4
info nodes 39 time 4

So he knows that is mate at only depth 1. In any search algorithm you have to evaluate the leafs. In this position when you evaluate the leaf Qh4 to know that is mate I have to generate the moves for the opposite side and see if I get none. So this is basically 2 evaluations, the first one is to evaluate the board as it is and the second evaluation, that is not really an evaluation, but only to check if that move resulted in mate, the generation of moves for the opposite side.

My other question.. isn't this expensive? check for each move if that move resulted in mate? and what programmers do to make this mate validation not expensive?

In my current engine the output is this:
depth 1 score -0.53
depth 2 score mate 1
depth 3 score mate 1
etc...

It will only detect mate at depth 2 and I understand why..

[hyatt]

There are two tricks here.

(1) Stockfish and many others extend a check when it is given, rather than when escaping the check. That means a check at ply=1 on a 1 ply search will NOT hit the q-search at ply 2. Ply 1 gets extended which takes us to ply 2 full width, then ply=3 might start the q-search. If you extend escaping rather than giving check, this behaves differently because now you will get to the qsearch and be in check also.

(2) some generate checks at the first ply of q-search, and then escape them at ply=2. Some do this for 2 more plies, and then most drop into a capture-only search. In Crafty, for example, I don't need to escape checks in the first ply of q-search, because I can never get to the first ply of q-search if I am in check, I would have extended the check which would have kept me in the regular search.

Mate is not an evaluation "item". It is a pure search issue.

[tetra]

There are two tricks here.

(1) Stockfish and many others extend a check when it is given, rather than when escaping the check. That means a check at ply=1 on a 1 ply search will NOT hit the q-search at ply 2. Ply 1 gets extended which takes us to ply 2 full width, then ply=3 might start the q-search. If you extend escaping rather than giving check, this behaves differently because now you will get to the qsearch and be in check also.

(2) some generate checks at the first ply of q-search, and then escape them at ply=2. Some do this for 2 more plies, and then most drop into a capture-only search. In Crafty, for example, I don't need to escape checks in the first ply of q-search, because I can never get to the first ply of q-search if I am in check, I would have extended the check which would have kept me in the regular search.

Mate is not an evaluation "item". It is a pure search issue.

Currently I'm only generating captures in qsearch and the first trick is what I'm looking for and what I had thought but I wanted a proof and an explanation and you gave me that.

Thanks hyatt