Is this trivially obvious?

[Chan Rasjid]

Hello,

If search of a node returns a mate score, does searching with a greater depth return the same score?

If yes, is the explanation trivially obvious?

Thanks
Rasjid.

[Desperado]

Hello Chan,

1: no selectivity

In this case the search should return always the same mate score.

2: practice

There is no real engine without selectivity. it starts with qSearch,
and depends even here if qsearch is able to report mate scores.

Other selectivity issues like reductions,extensions,prunings will depend
on moveordering if a matescore will be found again or not.
But if everything is done correctly it should always report a mateScore
<= previousMateScore (so if mate was announced in 12 it should report
a mate <= 12 at next iteration(depth))

in any case, if the score raises up, then keep attention and try to check
out following points:
- moveordering,selectivity parts
- transtable contents
- or simply bug.

Michael

[Chan Rasjid]

Hello Chan,

1: no selectivity

In this case the search should return always the same mate score.

2: practice

There is no real engine without selectivity. it starts with qSearch,
and depends even here if qsearch is able to report mate scores.

Other selectivity issues like reductions,extensions,prunings will depend
on moveordering if a matescore will be found again or not.
But if everything is done correctly it should always report a mateScore
<= previousMateScore (so if mate was announced in 12 it should report
a mate <= 12 at next iteration(depth))

in any case, if the score raises up, then keep attention and try to check
out following points:
- moveordering,selectivity parts
- transtable contents
- or simply bug.

Michael

I wonder if there is a rigorous explanation. I don't see it easily as I think I only vaguely understand minimax.
But I sense that it could be explained in terms of nodes terminating in checkmates :-

The child nodes all have mate scores which imply that the PVs all terminate with checkmates. Seaching to a higher depth only affects the non-pv branches, but the same checkmate PVs should still apply. So I am not sure if selectivity changes anything. But this is not a rigorous explanation and could be wrong somehow.

Rasjid.

[hgm]

Not if you use a hash table. It is very common that one iteration will see an over-the-horizon mate by grafting, which will then disappear in the next iteration. Because that iteration will now try the best move (i.e. the mate branch) first, so that there will be no grafting if the hash entry that caused the graft from the previous iteration is lost. The grafting only occurred because a line with stupid defense was searched before the best defence, providing a shorter path to the over-the-horizon mate.

[Sven]

Hello,

If search of a node returns a mate score, does searching with a greater depth return the same score?

If yes, is the explanation trivially obvious?

Not necessarily the same score, but under very limited conditions (see below) you should get the same mate score or a shorter one, both in case of winning or losing.

As to the limited conditions: without hash table and without forward pruning you can get the following effect.

a) Searching to depth 12 returns a mate in 15 plies, which is found based on normal techniques like check extensions or qsearch, i.e. using selectivity beyond the full-width horizon. (The selectivity can only affect the winning side in case of mate scores since selectivity on the losing side can't establish a forced mate.)

b) But searching to depth 13 returns a shorter mate, i.e. mate in 13 plies, since the full-width search now goes one ply deeper and sees a quiet move which was not considered during depth 12 search. (Here I assume that qsearch does not consider non-capturing checks in the first ply.)

c) Searching deeper than to depth 13 should usually not return a mate shorter than 13 plies since that should have been found in a previous iteration.

Adding forward pruning will invalidate part c). Adding a hash table will introduce the grafting effect described by HGM.

I think that a), b), c) are pretty obvious in the context I mentioned. Whether you regard the "real life" situation which includes both forward pruning and hash table as obvious or not depends on your personal taste, I'd say it is not so obvious to accept that a deeper search might occasionally "forget" a mate that was already found before, while the effect of forward pruning can be understood quickly.

Sven

[Sven]

The child nodes all have mate scores which imply that the PVs all terminate with checkmates. Seaching to a higher depth only affects the non-pv branches, but the same checkmate PVs should still apply. So I am not sure if selectivity changes anything. But this is not a rigorous explanation and could be wrong somehow.

Don't forget that the winning side needs only one move at a PV node that is forcing mate (so the winning side can be selective at that point as long as the mating move is one of the selected moves), while for the losing side the mate is only confirmed if all legal moves lead to being mated (so you can only see that you are mated at a node if you do full-width there). This is the way how selectivity has an influence.

Sven

[Chan Rasjid]

I have been thinking a little and it seems there should be a very simple, clean and rigorous explanation through some manner of 'minimaxing'. But I don't know minimax well enough.Hashing has obvious 'grafting' effect and so we don't consider hashing. Also no prunning. It should be something like this:-

The search of the node returns a PV with a mate score. When the node is searched with a greater depth, we could consider first searching the 'expanded' tree but follows the same nodes as in the earlier search and it returns the same exact mate PV as before. Now we consider searching the 'additional' branches, but they would all be refuted (why?). So without hashing and forward pruning, the same mate score would be found.

With forward pruning, we could of course miss the PV. This is as far as I could go.


Best regards,
Rasjid.

[hgm]

Are you talking now about fixed-depth full-width searches? Because then it is trivially obvious. And if it is not fixed-depth, but can use extensions, then it is obviously not true, so there would be nothing to prove.

[Chan Rasjid]

Are you talking now about fixed-depth full-width searches? Because then it is trivially obvious. And if it is not fixed-depth, but can use extensions, then it is obviously not true, so there would be nothing to prove.

Say yes, fixed-depth full-width searches with no extensions. Why is it trivially obvious.

Rasjid.

[hgm]

If there is a mate in N ply, you will see it with certainty when you search N ply(fixed depth). Searching deeper cannot bring any faster mate in view. And searching less deep will with equal certainty not make you see any mate in N. Not only that you cannot force it: when you do not search N ply, you will not find a single node in your tree that has a mate-in-N-ply score.

The score of mate nodes is coupled hard to the tree level where you find them.