Quiescence - Check Evaluation and Depth Control

[syzygy]

I decided to fix this qsearch explosion problem by introducing a depth limit. Basically when the depth is QS_LIMIT, we don't call qsearch() recursively, and return eval + SEE instead.

This will make the implementation of the hash table a bit trickier. The depth that I'll have to enter in the hash entries will have to be

Code: Select all

depth == 0 ? 0 &#58; &#40;depth <= QS_LIMIT &#58; -2 &#58; -1&#41;

Something to remember for when I implement a hash table.

Unless QS_LIMIT is set to -2, this won't be entirely accurate. Suppose you set QS_LIMIT to -7, then your hashtable won't distinguish between positions qsearched with depth -6 and positions qsearched with depth -1, but these qsearches clearly have different accuracies.

So to be accurate I think you would have to enter "depth". Since you have just limited depth to >= QS_LIMIT, there is no danger of underflowing.

Of course you could also choose not to hash the qsearch at all, or only hash positions with "high" depth. (I have not found hashing the qsearch to be worth it in my current engine, but I'm sure this is engine-dependent.)

[Jan Brouwer]

[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
(...) I need to test it and find out why my program didn't find this mate with SEE pruning removed.

with or without SEE pruning it should find it, so long as checking moves are not subject to SEE pruning (like Qg7+ and later Bxf7+).

I found the bug in my program. I was not generating promotions!

So Jan Brouwer was right. This position really *is* a qsearch explosion.

I'll experiment with forcefully limiting the depth of the qsearch.

Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...

[syzygy]

Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...

Do you do underpromotions in the qsearch?

[Jan Brouwer]

Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...

Do you do underpromotions in the qsearch?

No, just queen promotions.

[Edsel Apostol]

[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
(...) I need to test it and find out why my program didn't find this mate with SEE pruning removed.

with or without SEE pruning it should find it, so long as checking moves are not subject to SEE pruning (like Qg7+ and later Bxf7+).

I found the bug in my program. I was not generating promotions!

So Jan Brouwer was right. This position really *is* a qsearch explosion.

I'll experiment with forcefully limiting the depth of the qsearch.

Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...

Do you check for repetition when moving out of check in qsearch?

[lucasart]

Do you check for repetition when moving out of check in qsearch?

That's a bizarre idea. Do you really get some significant node reduction from that ?
In general, I mean, not this position in particular. My intuition tells me that the cases where it will be used are so rare, that it doesn't make sense to slow down all the check escapes QS nodes for it.

[Edsel Apostol]

Do you check for repetition when moving out of check in qsearch?

That's a bizarre idea. Do you really get some significant node reduction from that ?
In general, I mean, not this position in particular. My intuition tells me that the cases where it will be used are so rare, that it doesn't make sense to slow down all the check escapes QS nodes for it.

I'm just thinking of the reasons why it causes search explosion in that particular position. One thing I could think of is that when in giving check it was extended in qsearch and when moving out of check the depth is also extended, so it is possible that there is a check repetition that repeats for the nth time that will bloat the nodecount.

Another thing might be ordering the queen promotion over the queen capture, so all the pawns will be promoted first. Imagine the branching factor with 12 queens on the board.

As for your question if it saves a lot of nodes, I don't think so. I think though that it is important to make the search more accurate than faster in this case. It might be that the check repetition is the only move that saves the game and all the other moves are losing and the engine did not choose this correct move because it didn't score it correctly.

[syzygy]

Do you check for repetition when moving out of check in qsearch?

That's a bizarre idea. Do you really get some significant node reduction from that ?
In general, I mean, not this position in particular. My intuition tells me that the cases where it will be used are so rare, that it doesn't make sense to slow down all the check escapes QS nodes for it.

As long as your first test is checking the number of ply since the last capture, this won't slow down the qsearch noticeably. I would certainly want to check for repetition in the first ply of qsearch, unless you do that in the main search right before calling the qsearch. If you give checks in qsearch, I would want to check for repetition as well. Otherwise you're going to miss some draws.

I don't think repetition check wil help in this position though. Captures and promotions are irreversible, so I don't see how a repetition could occur when qsearching this positions (unless one gives unlimited amounts of checks, but I don't think this is the problem here).

Another thing might be ordering the queen promotion over the queen capture, so all the pawns will be promoted first. Imagine the branching factor with 12 queens on the board.

I was thinking of that too. I do captures before non-capturing promotions, and my first ply "only" needs about 640k nodes. (I just recently got rid of underpromotions in the qsearch. The old version needs 48M nodes for the first ply.)

[lucasart]

Yo i'm just a FM but i'd do Qg7+ Kg7 h8Q+ Kg6 Qh6+ mate.

Many paths lead to Rome!
But the shortest mate is simply: Bxf7, followed by Qg8# (regardless of whichever pawn black decides to promote after Bxf7). The point is that your Qh6# cannot be found by a qsearch that doesn't consider quiet checks below depth 0, which is why I posted the mating line: Qg7+ Kxg7 h8=Q+ Kg6 Bxf7+ Kxf7 e8=Q#.
If Diep indeed plays quiet checks until depth = -32 as you mentionned, then it should find the mating line that you gave at depth == 0 (qsearch).
[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1

[Jan Brouwer]

[d]6Bk/PPPPPp1P/8/7R/7K/8/ppppppQ1/6B1 w - - 0 1
(...) I need to test it and find out why my program didn't find this mate with SEE pruning removed.

with or without SEE pruning it should find it, so long as checking moves are not subject to SEE pruning (like Qg7+ and later Bxf7+).

I found the bug in my program. I was not generating promotions!

So Jan Brouwer was right. This position really *is* a qsearch explosion.

I'll experiment with forcefully limiting the depth of the qsearch.

Note that the 24M moves was for a 1 ply search.

So I added the possibility to do a quiescence search only, the result: 24 M nodes (and a mate score, I examine all checks in first ply of quiescence search)

Some investigation is in order...

Do you check for repetition when moving out of check in qsearch?

Yes, I check for repetitions everywhere.