How do you signal stalemate in iterative deepening?

[kdjones]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

[bob]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

That is what most do, just continue searching. You might not want to accept the stalemate if a deeper search discovers a better alternative.

[sje]

In Symbolic, all draws are treated the same in the search: fiftymove, insufficient, stalemate, and threefold. There's no special scoring for any of them.

[syzygy]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

As Bob already wrote, you want to continue searching.

If the search returns a winning or losing mate score, then that is "proof" that the position is won or lost. But if the search returns a 0.00 score, then everything is still possible even if that 0.00 came from a stalemate or from a draw by repetition or even from a 50-move draw. The position may still turn out to be a win and it may still turn out to be a loss. So a draw score is no reason to stop searching.

[jwes]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

As Bob already wrote, you want to continue searching.

If the search returns a winning or losing mate score, then that is "proof" that the position is won or lost. But if the search returns a 0.00 score, then everything is still possible even if that 0.00 came from a stalemate or from a draw by repetition or even from a 50-move draw. The position may still turn out to be a win and it may still turn out to be a loss. So a draw score is no reason to stop searching.

It would be good to know if one or both sides could force stalemate or repetition in all branches of a sub-tree. This could allow not searching this sub-tree on deeper iterations.

[hgm]

That is what you get when you use depth bootstrapping. The score from a checkmate or stalemate position is valid to infinite depth, and that depth than propagates to the root (if all daughters have it in an all node, or the cut move has it in a cut node).

There is a pitfall with hashing, though. If you use the hashed depth also for replacement decisions, it would make the forced mates very difficult to replace, while in fact they represent very shallow trees. So you would have to decouple replacement from the stored depth somehow.

[syzygy]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

As Bob already wrote, you want to continue searching.

If the search returns a winning or losing mate score, then that is "proof" that the position is won or lost. But if the search returns a 0.00 score, then everything is still possible even if that 0.00 came from a stalemate or from a draw by repetition or even from a 50-move draw. The position may still turn out to be a win and it may still turn out to be a loss. So a draw score is no reason to stop searching.

It would be good to know if one or both sides could force stalemate or repetition in all branches of a sub-tree. This could allow not searching this sub-tree on deeper iterations.

But alpha-beta won't give you that information.

In any case, such subtrees will not take long to search at higher iterations anyway.

[bob]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

As Bob already wrote, you want to continue searching.

If the search returns a winning or losing mate score, then that is "proof" that the position is won or lost. But if the search returns a 0.00 score, then everything is still possible even if that 0.00 came from a stalemate or from a draw by repetition or even from a 50-move draw. The position may still turn out to be a win and it may still turn out to be a loss. So a draw score is no reason to stop searching.

It would be good to know if one or both sides could force stalemate or repetition in all branches of a sub-tree. This could allow not searching this sub-tree on deeper iterations.

alpha/beta does that already...

[jwes]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

As Bob already wrote, you want to continue searching.

If the search returns a winning or losing mate score, then that is "proof" that the position is won or lost. But if the search returns a 0.00 score, then everything is still possible even if that 0.00 came from a stalemate or from a draw by repetition or even from a 50-move draw. The position may still turn out to be a win and it may still turn out to be a loss. So a draw score is no reason to stop searching.

It would be good to know if one or both sides could force stalemate or repetition in all branches of a sub-tree. This could allow not searching this sub-tree on deeper iterations.

alpha/beta does that already...

But alpha-beta won't give you that information.

In any case, such subtrees will not take long to search at higher iterations anyway.

I'm confused.

[syzygy]

I am working on my first chess engine after learning C++. It uses iterative deepening and a principal variation search (PVS). When a stalemate occurs in the PV, I want to cut the search short, but the score of zero is not unique (as in a checkmate). Since I added the transposition table, the principal variation may not be complete, so I can't use it's length to detect end of game. How do I signal a stalemate otherwise? The iterations keep going until the depth or time runs out.

As Bob already wrote, you want to continue searching.

If the search returns a winning or losing mate score, then that is "proof" that the position is won or lost. But if the search returns a 0.00 score, then everything is still possible even if that 0.00 came from a stalemate or from a draw by repetition or even from a 50-move draw. The position may still turn out to be a win and it may still turn out to be a loss. So a draw score is no reason to stop searching.

It would be good to know if one or both sides could force stalemate or repetition in all branches of a sub-tree. This could allow not searching this sub-tree on deeper iterations.

alpha/beta does that already...

But alpha-beta won't give you that information.

In any case, such subtrees will not take long to search at higher iterations anyway.

I'm confused.

Bob probably means something close to what I wrote in my second sentence.

What you were saying is that if it can be proven that white can at least force a stalemate, then that is an "absolute truth" independent of search depth, so would remain true at higher iterations. So the hash table could store a bound with infinite depth and as long as that bound remains relevant, the search would not revisit the subtree in later iterations.

But as I said, alpha-beta does not return such information. The tree searched by alpha-beta will usually be considerably smaller than the tree one would need to search to prove that one side can force stalemate (the latter would be possible by performing a separate alpha-beta search that scores stalemate as mate). Well, a search trying to prove stalemate might not always lead to a bigger tree: it might be very easy to prove that stalemate cannot be forced. But such a stalemate search would be additional to the normal alpha-beta search.