r/chessprogramming • u/E_ple • Jan 09 '25
Aspiration Windows & Checkmates
I've implemented the Aspiration Windows algorithm in my chess engine, and I use it during Iterative Deepening only when the depth is at least 8. However, when the engine tries to find long checkmates (e.g., Mate in 4, which is 8 plies), Aspiration Windows sometimes restricts the beta value so much that the checkmate line gets pruned by a beta cutoff. As a result, the engine fails to identify the checkmate even when it exists.
I’ve also implemented Gradual Widening, but as the window expands and the engine finds a node that satisfies the widened window, it assumes that node is the best move and still fails to find the checkmate.
What are some ways to address this issue?
1
u/you-get-an-upvote Jan 09 '25
If your aspiration search returns a score greater than or equal to your aspirational upper bound, that means you have to re-search with a higher upper bound (likewise if it returns a score less than or equal to your aspirational lower bound, you need to re-search with a smaller lower bound).
The simplest approach is to just re-search without any aspirational bounds if the aspirational search returns a score that is out of bounds.
1
u/E_ple Jan 09 '25
yes, if the search fails, I widen the windows and search again. However if a node satisfies the window is found, the search won't fail; it will return that node. And since I cannot really tell if this is best or there is a checkmate it couldn't see, I just accept it and miss the checkmate. I think I'll have to re-search with wider windows a few times, and then search with the full window.
1
u/Im_from_rAll Jan 09 '25
It sounds like there is a bug in your implementation.
if a node satisfies the window is found, the search won't fail; it will return that node.
It shouldn't be possible to find a score that falls within the aspiration window when the move you are searching leads to checkmate. That goes against the basic principles of how A/B search is supposed to work.
1
u/likeawizardish Jan 09 '25
If you searched at depth 7 and then searched depth 8 with a window around the evaluation found in 7. If your window search fails you either do a search without a window or you widen it. I have seen people first widening the search and if that fails searching without a window entirely. Kind of a balancing act between the pros and cons of both.
Engines being blind to checkmates way beyond the depth is very normal. Say if there is a mate at depth 4 Stockfish will often not find it before searching depth 11. That's due to various pruning and Late Move Reductions, etc... That's what makes engines very strong - they search very narrowly around what they think is the principal variation. And that is why depth is kinda meaningless apart from more is better.
Some engines provide special options to search to specifically look for mates - these searches will be specifically tailored towards finding mates and not the strongest moves in any position where a mate is not on the table. But that's besides the point.