seldepth: what is the correct way to calculate this?

[mvanthoor]

Even after this investigation, I'm still not sure.

[d]4k3/8/8/8/8/8/8/3QK3 w - - 0 1

Code: Select all

go
info score cp 940 depth 1 seldepth 2 time 0 nodes 12 nps 0 pv e1f2
info score cp 900 depth 2 seldepth 4 time 0 nodes 144 nps 0 pv d1h5 e8d7 e1f2
info score cp 930 depth 3 seldepth 6 time 0 nodes 886 nps 0 pv d1d5 e8e7 e1f2
info score cp 920 depth 4 seldepth 8 time 1 nodes 7923 nps 7923000 pv d1d5 e8e7 d5e5 e7f7 e1f2
info score cp 940 depth 5 seldepth 10 time 9 nodes 54826 nps 6091778 pv d1d6 e8f7 e1d2 f7g7 d2c3
info score cp 950 depth 6 seldepth 12 time 70 nodes 414610 nps 5923000 pv e1e2 e8e7 d1d5 e7f6 e2d3 f6g6
info score cp 980 depth 7 seldepth 14 time 559 nodes 3270308 nps 5850283 pv e1e2 e8f7 d1d5 f7f6 e2d3 f6g6 d5e6 g6g5 d3d4
info score cp 990 depth 8 seldepth 16 time 4014 nodes 23114306 nps 5758422 pv d1h5 e8d7 e1d2 d7c6 d2c3 c6b6 c3d4 b6c6 h5d5 c6b6
info score cp 990 depth 9 seldepth 18 time 29371 nodes 165779073 nps 5644311 pv e1d2 e8d7 d2c3 d7e6 c3c4 e6e5 d1e1 e5f4 c4d4 f4f3 e1e4 f3f2

That can't be right. I should indeed be resetting seldepth somehwere, but at the moment I seem to be too daft to find out where.

With my previous implementation (ply (actual depth) > requested depth ==> replace seldepth by ply) suddenly seems to be the correct way again.

[Sven]

After reverting your PR#18, the implementation is weird again, you determine a maximum by:
if (a > SOMETHING) MAX := a
instead of the natural:
if (a > MAX) MAX := a
And your result in MAX now depends on your move ordering, again, since the last node where you encounter "a > SOMETHING" by accident wins the race to set MAX := a. If, for instance, the last QS node you visit during iteration 9 is at ply 10 but a previous one had been at ply 15 you report "10".
You wrote:

Code: Select all

..
info score cp 990 depth 9 seldepth 18 time 29371 nodes 165779073 nps 5644311 pv e1d2 e8d7 d2c3 d7e6 c3c4 e6e5 d1e1 e5f4 c4d4 f4f3 e1e4 f3f2

That can't be right.

and indeed it looks unusual, but nevertheless it may be correct if you consider a kind of "perpetual check" which (correctly) didn't make it into the PV but was tried during search and triggered a lot of check extensions. To check this you might print the current ply at which you call quiescence() from alpha_beta().

I should indeed be resetting seldepth somehwere

You do that already when constructing SearchInfo in search.rs, right before calling iterative_deepening(). That looks sufficient for me, unless you would like to reset it to 0 before each new iteration (which would just be a different way of reporting but ok as well).

[mvanthoor]

After reverting your PR#18, the implementation is weird again, you determine a maximum by:
if (a > SOMETHING) MAX := a
instead of the natural:
if (a > MAX) MAX := a
And your result in MAX now depends on your move ordering, again, since the last node where you encounter "a > SOMETHING" by accident wins the race to set MAX := a. If, for instance, the last QS node you visit during iteration 9 is at ply 10 but a previous one had been at ply 15 you report "10".

Yes; that is exactly the reason why I changed this:

Code: Select all

if ply > requested_depth {
	seldepth = ply;
}

to this:

Code: Select all

if ply > seldepth {
	seldepth = ply;
}

The seldepth became ginormous. The investigation above SEEMS to prove that it is correct however, as I've had both the check extension and the QS print their plies. It still felt very strange though, to have such HUGE depths compared to the ones reported by other engines. (Maybe these engines are just much slower, or have bugs.... could be.)

and indeed it looks unusual, but nevertheless it may be correct if you consider a kind of "perpetual check" which (correctly) didn't make it into the PV but was tried during search and triggered a lot of check extensions. To check this you might print the current ply at which you call quiescence() from alpha_beta().

I know it _can_ be correct, but there's so much recursion going on that I can't reason about it that accurately anymore

It does seem however, that going for the MaxDepth approach is best; I've quickly looked into Ethereal's code, and it does so as well (but it does it mutlithreaded).

You do that already when constructing SearchInfo in search.rs, right before calling iterative_deepening(). That looks sufficient for me, unless you would like to reset it to 0 before each new iteration (which would just be a different way of reporting but ok as well).

Yes. In Rust, variables get dropped/destroyed automatically if they go out of scope. In the while { } loop in search.rs, search_info is created, and a reference to this is passed to iterative_deepening. When the search ends (and thus, the while { } ends), the variable is dropped, and the thread is going to wait for the next command again just after the beginning of the while { }.

This behavior is the reason that I almost never have to reset anything, except if an algorithm or situation _requires_ that something be reset, such as the board on receiving "ucinewgame".

[Sven]

It does seem however, that going for the MaxDepth approach is best; I've quickly looked into Ethereal's code, and it does so as well (but it does it mutlithreaded).

Ethereal does this:

Code: Select all

thread->seldepth = RootNode ? 0 : MAX(thread->seldepth, thread->height);

in both search() and qsearch(). Is that what you mean?

The problem that I see with your other approach is that it leads to random results, as explained in my previous post.

[mvanthoor]

Ethereal does this:

Code: Select all

thread->seldepth = RootNode ? 0 : MAX(thread->seldepth, thread->height);

in both search() and qsearch(). Is that what you mean?

Yes.

The problem that I see with your other approach is that it leads to random results, as explained in my previous post.

I suspected this (as I said, it's the reason why I included PR#18), but I got thrown off guard because some of the positions I tested seem to actually have a gargantuan QSearch extension.

[Sven]

Ethereal does this:

Code: Select all

thread->seldepth = RootNode ? 0 : MAX(thread->seldepth, thread->height);

in both search() and qsearch(). Is that what you mean?

Yes.

The problem that I see with your other approach is that it leads to random results, as explained in my previous post.

I suspected this (as I said, it's the reason why I included PR#18), but I got thrown off guard because some of the positions I tested seem to actually have a gargantuan QSearch extension.

At least in the KQK case you had shown it was definitely not QSearch (since there can only be one capture on the whole board) but check extension in a perpetual check scenario. And that alone should not justify to abandon a correct seldepth implementation