stalemate detection and pruning

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jdart
Posts: 3663
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

stalemate detection and pruning

Post by jdart » Sun Sep 22, 2013 9:18 pm

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
Posts: 1154
Joined: Fri Jun 23, 2006 3:18 am

Re: stalemate detection and pruning

Post by BubbaTough » Sun Sep 22, 2013 9:23 pm

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
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
Posts: 8309
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: stalemate detection and pruning

Post by Uri Blass » Sun Sep 22, 2013 9:51 pm

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
Posts: 1909
Joined: Fri Nov 26, 2010 1:00 pm
Full name: Martin Sedlak

Re: stalemate detection and pruning

Post by mar » Sun Sep 22, 2013 9:54 pm

jdart wrote: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
Posts: 3663
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: stalemate detection and pruning

Post by jdart » Sun Sep 22, 2013 10:11 pm

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
Posts: 1909
Joined: Fri Nov 26, 2010 1:00 pm
Full name: Martin Sedlak

Re: stalemate detection and pruning

Post by mar » Sun Sep 22, 2013 10:20 pm

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
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
Posts: 4368
Joined: Tue Feb 28, 2012 10:56 pm

Re: stalemate detection and pruning

Post by syzygy » Mon Sep 23, 2013 12:34 am

jdart wrote: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?)

User avatar
lucasart
Posts: 3023
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: stalemate detection and pruning

Post by lucasart » Mon Sep 23, 2013 1:56 am

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
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).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

jdart
Posts: 3663
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: stalemate detection and pruning

Post by jdart » Mon Sep 23, 2013 3:16 am

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.
Yes, that is a possible solution.

--Jon

Sven
Posts: 3743
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: stalemate detection and pruning

Post by Sven » Mon Sep 23, 2013 8:10 am

jdart wrote:
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.
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

Post Reply