stalemate detection and pruning

[jdart]

Some time ago my program lost a game by playing into a stalemate, when it actually had a win. I found this hard to reproduce and never did fix it. But in thinking about it later, a possible cause has occurred to me. Stalemate detection depends on generating all moves and discovering none are legal. But when pruning is done, you don't know that there are no legal moves (I do legal move detection only after the move is made, pruning is done before). So it is possible a position deep enough in the tree so that pruning is happening will not be scored as a draw when in fact it should be.

A fix would be to prune after the move is made and checked for legality but that would slow down the search.

Don't know if other programs have this issue but I suspect some do.

--Jon

[BubbaTough]

Some time ago my program lost a game by playing into a stalemate, when it actually had a win. I found this hard to reproduce and never did fix it. But in thinking about it later, a possible cause has occurred to me. Stalemate detection depends on generating all moves and discovering none are legal. But when pruning is done, you don't know that there are no legal moves (I do legal move detection only after the move is made, pruning is done before). So it is possible a position deep enough in the tree so that pruning is happening will not be scored as a draw when in fact it should be.

A fix would be to prune after the move is made and checked for legality but that would slow down the search.

Don't know if other programs have this issue but I suspect some do.

--Jon

I have seen this effect not only in the primary search, but also in the Qsearch where after a capture stalemate is triggered but not detected. It is a significant challenge, particularly for those engines no employing tablebases.

-Sam

[Uri Blass]

Another fix may be to have a function to do legal move detection before you make the move when you should also use a function to find the pinned pieces for that purpose(stockfish does it based on my understanding).

[mar]

A fix would be to prune after the move is made and checked for legality but that would slow down the search.

Why not simply use a counter/flag which is incremented once a move goes out of movegenerator and later only check whether it's zero? This is done before the move is pruned.
EDIT: of course this implies that your movegenerator outputs only legal moves and it won't work in qsearch where not all moves are generated but I can live without detecting stalemates in qsearch.

[jdart]

My move generator, like many, generates pseudo-legal moves, for efficiency reasons, on the theory that many moves won't ever be used, due to pruning or cutoff by an earlier move in the move list.

--Jon

[mar]

My move generator, like many, generates pseudo-legal moves, for efficiency reasons, on the theory that many moves won't ever be used, due to pruning or cutoff by an earlier move in the move list.

--Jon

Well my move generator generates pseudolegal moves too but before it goes out of it there is a check whether a pseudolegal move is really legal. Your approach is probably faster but it suffers from the problem you described above.

[syzygy]

A fix would be to prune after the move is made and checked for legality but that would slow down the search.

You only need to check for legality of the move being pruned if you have not yet seen a single legal move for that position. (And I'm not sure you would want to prune a move if it might be the only legal move?)

[lucasart]

Some time ago my program lost a game by playing into a stalemate, when it actually had a win. I found this hard to reproduce and never did fix it. But in thinking about it later, a possible cause has occurred to me. Stalemate detection depends on generating all moves and discovering none are legal. But when pruning is done, you don't know that there are no legal moves (I do legal move detection only after the move is made, pruning is done before). So it is possible a position deep enough in the tree so that pruning is happening will not be scored as a draw when in fact it should be.

A fix would be to prune after the move is made and checked for legality but that would slow down the search.

Don't know if other programs have this issue but I suspect some do.

--Jon

yet another reason why i am convinced i made the right choice with legal move generation (as opposed to pseudo legal with filtering before playing moves).

[jdart]

You only need to check for legality of the move being pruned if you have not yet seen a single legal move for that position.

Yes, that is a possible solution.

--Jon

[Sven]

You only need to check for legality of the move being pruned if you have not yet seen a single legal move for that position.

Yes, that is a possible solution.

--Jon

This solves the problem for full-width search. For QS you could add a "simple stalemate detection" that covers many practical cases: if the moving side has only the king left then do a static stalemate detection, i.e. try to find any attack to squares that are potential targets of pseudo-legal moves of the king. I think Fruit 2.1 does something similar.

One might even extend this to positions with only king + pawns (for the moving side). In this case, to keep the computation effort low (e.g. avoid dealing with pins etc.) I would restrict it to cases where
- all friendly pawns are blocked,
- no friendly pawn can capture an enemy pawn and
- the position has no ep target square set.
For a bitboard engine this could be done quite easily with a few shifts + AND's.

With any friendly non-pawn pieces on the board the probability for a stalemate is quite low but of course not zero, so you can still miss a few stalemates in QS. As usual the key questions are,
1) will it matter much to miss a few stalemates during QS, and
2) will the whole thing improve or hurt strength?

To be on the safe side one would perform such a static stalemate detection prior to calling EVAL, although it is quite unlikely that EVAL returns an advantage for the moving side in a pawn ending with all friendly pawns blocked but the position is stalemate, occasionally leading to a wrong stand-pat cutoff.

Sven