Search Halting Criteria When Probing Tablebases

[Ed Trice]

Now that I am probing Distance To Win data in RAM during the search, an interesting new facet has appeared.

It is possible that at some nominal depth, d, you enter into a known table win requiring N-ply, so you now have a bound of Mate in d + N.

Later, at d + 2, a different move might mate in d + 2 + R < d + N.

That doesn't mean d + 4, d + 6, d + 8... can't find faster checkmates. So at what nominal depth can you stop searching altogether?

Must you search until your new depth is >= the original d + N depth? I'm pretty sure the answer is 'No' but I also can't generalize a halting criteria.

[jdart]

The score is backed up the root. So if you have a mate score at the root you can terminate. You could do better by finding a faster mate. But you won't do worse.

The criterion I use is :

value >= Constants::MATE - iteration_depth - 1

(iteration_depth is the nominal search depth in plies; the search starts at 1).

Because of reductions and pruning this does not guarantee that you will find the fastest mate. If you want to guarantee that you need to search deeper or modify the search.

For Syzygy, the logic is different. In that case I just do not terminate the search, because it will only return the constant TbWin if winning. The search moves though are filtered so that the win or draw (if there is one) is always preserved, i.e. it will not search a losing move if there is a drawing one, or a drawing one if there is a win.

--Jon

[JVMerlino]

Everything Jon says is correct. So the question is, do you want your engine to be as accurate as possible or just play well? Finding a mate is good enough to win a game, so there's no need to continue the search unless you HOPE to find a shorter mate.

In my engine I take it a bit farther. If I find a mate for two successive root searches (i.e. depth N and depth N+1), in which the distance found to mate is equal to or less than the depth at the root of those searches, then I stop the search.

So, for example, if I find Mate in 5 (for the side to move) at search depths 9 and 10, then I stop. As Jon says, though, this doesn't ensure that there isn't a Mate in 4 somewhere, due to reductions and pruning.

jm

[AlvaroBegue]

When I did this in my checkers program in the 90s, it developed this "sadistic" style, so when it was far ahead in material it would often anounce a long mate, give away most of the material advantage (captures are forced in that game) and then proceed to win some very difficult endgame in many moves. Whether you like that style or not is a matter of personal taste. I thought it was hilarious, so I left it that way.

[Ed Trice]

Thanks for all of the input so far guys. And this is for my checkers engine as well, so I've seen similar behavior as you described.

My "ultimate objective" is to:

1. Play as perfectly as possible in terms of move count shortening.
2. Never iterate the search depth when a forced win has been exhaustively analyzed.

Counter example to item #2: Finding a forced mate in 7, then the depth++ is incremented to 8, and you're basically searching "above the tree" on hypothetically non-existent nodes (or at least nodes superfluous to the game).

The unfortunate occurrence seems to be:

Depths searched = d1, d2, d3, .... d10 finds Mate in 37-ply tablebase entry for a Mate in 47-ply overall score ceiling.

At d12 we're guaranteed at least one Mate in 35-ply line.
At d14 we find a different endgame has Mate in 19-ply, lowering the mate ceiling to 33-ply.

Of course, if we ever hit nominal depth 31 without the tablebases, a mate might exist there as well.

I'm guessing I have to track the MINIMUM DTW for any of the reported mates that use tablebases, and also the nominal depth at which each mate was found.

If iteration depth + minimum found mate depth > max found mate depth, then all paths cannot be improved upon, so then the search need not continue.

I think

[Ed Trice]

I think I have the quintessential example to demonstrate the issue.

Red to move and win in 295-ply "or better"



The position above is obviously for the game of checkers, but it makes the point excellently. Red is winning easily, 5 pieces to 4, with a 3-1 King majority as well. Any program with an 8-piece database will throw away one of the Kings to enter into a won 8-piece ending, 19-24 27x20, blissfully unaware that it is red to move and win in 293-ply after the forced return jump by white. Against the strongest defense, many programs with the red pieces won't be able to converge on the win!

The question is: With an upper bound of win-in-295, how deep should red search before announcing a win and making a move if the user selects an "infinite" search setting?