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
stalemate detection and pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
-
- Posts: 1154
- Joined: Fri Jun 23, 2006 5:18 am
Re: stalemate detection and pruning
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.jdart wrote: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
-Sam
-
- Posts: 10283
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: stalemate detection and pruning
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).
-
- Posts: 2556
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: stalemate detection and pruning
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.jdart wrote:A fix would be to prune after the move is made and checked for legality but that would slow down the search.
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.
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: stalemate detection and pruning
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
--Jon
-
- Posts: 2556
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: stalemate detection and pruning
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.jdart wrote: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
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: stalemate detection and pruning
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?)jdart wrote:A fix would be to prune after the move is made and checked for legality but that would slow down the search.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: stalemate detection and pruning
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 wrote: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
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: stalemate detection and pruning
Yes, that is a possible solution.syzygy wrote: 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.
--Jon
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: stalemate detection and pruning
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.jdart wrote:Yes, that is a possible solution.syzygy wrote: 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.
--Jon
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