Search Halting Criteria When Probing Tablebases

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Ed Trice
Posts: 100
Joined: Fri Sep 19, 2014 3:03 am

Search Halting Criteria When Probing Tablebases

Post by Ed Trice » Thu Mar 02, 2017 8:04 am

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

Re: Search Halting Criteria When Probing Tablebases

Post by jdart » Thu Mar 02, 2017 2:25 pm

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

User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Search Halting Criteria When Probing Tablebases

Post by JVMerlino » Thu Mar 02, 2017 3:40 pm

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
Posts: 925
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Search Halting Criteria When Probing Tablebases

Post by AlvaroBegue » Thu Mar 02, 2017 4:02 pm

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
Posts: 100
Joined: Fri Sep 19, 2014 3:03 am

Re: Search Halting Criteria When Probing Tablebases

Post by Ed Trice » Fri Mar 03, 2017 10:29 am

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
Posts: 100
Joined: Fri Sep 19, 2014 3:03 am

Re: Search Halting Criteria When Probing Tablebases

Post by Ed Trice » Sat Apr 15, 2017 10:39 pm

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

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

Image

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?

Post Reply