Quiescence - Check Evaluation and Depth Control

[Jan Brouwer]

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.

This seems indeed to be the cause.

As an experiment I scored all promotion moves lower than all other capture moves for move ordering.
This caused the number of nodes in the quiescence search to drop from 24M to 325449 nodes!

Thanks for pointing this out, I'll do some further experimentation.

[Rebel]

[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...

1738 nodes here.

Another thing that might help is the introduction of a limited QS depth driven by iteration.

Code: Select all

static char qs_max[] = { 0, 8,10,12,14,16,16,18,20,22,24,26,28,30,32,34,36,
                         38,40,40,40,42,42,42,44,44,44,46,46,46,48,48,48,
                         50,50,50,52,52,52,52,54,54,54,54,56,56,56,58,58,
                         58,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60 };

qs_limit = qs_max[iteration];

[lucasart]

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.

This seems indeed to be the cause.

As an experiment I scored all promotion moves lower than all other capture moves for move ordering.
This caused the number of nodes in the quiescence search to drop from 24M to 325449 nodes!

Thanks for pointing this out, I'll do some further experimentation.

Indeed MVV/LVA should order all QxQ before any P=Q. The point is that:
1/ QxQ: victim_value = Q, attacker_value = Q
2/ P=Q: victim_value = Q-P, attacker_value = P.
So, despite the fact that P=Q has a lesser valuable attacker, it has a lower MVV/LVA than QxQ, because the victim value is Q-P < Q. Anyway, that's how I extended the MVV/LVA to promotions, and it seems to make sense.

But I would still recommend using a depth limit in the qsearch. In the QS recursion, I basically do this:

Code: Select all

if &#40;depth <= QS_LIMIT && !in_check&#41;
    score = static_eval + see&#40;move&#41;;  /* horizon, try to mittigate the horizon effect by using the SEE */
else
    score = -qsearch&#40;depth-1, -beta, -alpha&#41;    // normal recursion

This may be engine dependant, but for me, some experiment show that QS_LIMIT = -8 is a good choice.

[Sven]

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.

This seems indeed to be the cause.

As an experiment I scored all promotion moves lower than all other capture moves for move ordering.
This caused the number of nodes in the quiescence search to drop from 24M to 325449 nodes!

Thanks for pointing this out, I'll do some further experimentation.

Indeed MVV/LVA should order all QxQ before any P=Q. The point is that:
1/ QxQ: victim_value = Q, attacker_value = Q
2/ P=Q: victim_value = Q-P, attacker_value = P.
So, despite the fact that P=Q has a lesser valuable attacker, it has a lower MVV/LVA than QxQ, because the victim value is Q-P < Q. Anyway, that's how I extended the MVV/LVA to promotions, and it seems to make sense.

In general I agree but with one minor correction proposal:

MVV/LVA, in contrast to SEE which uses simple knowledge about existing attacks to a square, uses the basic assumption that the moving piece will (might) be lost. Promotions should not be handled differently, so I think we should not assume that a non-capturing promotion can win any material at all with MVV/LVA. For that reason I believe that it is better to set attacker_value = <promotion_piece>: if the promotion piece is lost afterwards then it is like a queen exchange with an additional loss of a pawn. The difference to your version is only marginal, it would lower the ordering priority of non-capturing promotions slightly more.

One might even argue that, following the MVV/LVA idea that we should try those captures first which reduce material (and therefore tree size) on the board, it should be better to put all non-capturing promotions behind all non-losing captures. I don't know which is better.

EDIT: SEE can handle that more precisely, of course, since you get an idea whether the promotion piece will (probably) be lost.

Sven

[Cheney]

Hi,

I finally finished the MVV/LVA. Yes, it does score a bit differently but I got the idea .

I used the board you provided for some extensive testing. Here are some numbers:

Quiesence with no sorting and calling AlphaBeta if King checked:
QSearch Moves/Nodes: 227820
Max Depth: 27
Checks: 43959

With MVV/LVA and correct sorting:
QSearch Moves/Nodes: 7204
Max Depth: 19
Checks: 1443

Removed under-promotions:
QSearch Moves/Nodes: 3577
Max Depth: 15
Checks: 797

*QSearch is counted for each move generated and iterated in the move loop.
*Max depth is the max PLY reached.

This is a significant improvement. Thanks for the help with this

I still do not enforce a limit on the qsearch's max depth but am reading where others do. I am also reading where some others do not evaluate check and call alphabeta if true.

I do run into an explosion in the search for this position if I set the depth to 4 or higher. At depth setting of 4:

Total Search Nodes: 84,732,700
QSearch Nodes: 62,577,913
Qsearch Checks: 11,880,123
Max Q-Search Depth: 45

I do not see bugs in the code, which has been suggested. It may be that I did not put much into the evaluation (basically matieral score right now and piece/square position) and the alphabeta does not yet have something to sort its moves, which is next I hope.

Just to rule out one side thought (I expect the answer to be yes) - is there a performance decrease with methods calling each other (or itself) over and over and if so can this performance degredation be controlled?

Thanks again for any insight or advice you can provide on this

[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...

1738 nodes here.

Another thing that might help is the introduction of a limited QS depth driven by iteration.

Code: Select all

static char qs_max[] = { 0, 8,10,12,14,16,16,18,20,22,24,26,28,30,32,34,36,
                         38,40,40,40,42,42,42,44,44,44,46,46,46,48,48,48,
                         50,50,50,52,52,52,52,54,54,54,54,56,56,56,58,58,
                         58,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60 };

qs_limit = qs_max[iteration];

I just tried a q-search depth limit (as also suggested by Lucas Braesch); a limit of -7 results in 2277 nodes (and still reporting a mate).

Still have to test the influence on playing strength, but this is more in line with what others have reported.

I wonder if it pays to perform an SEE, just returning the static eval score is simpler and may be sufficient, testing will tell.

[lucasart]

I wonder if it pays to perform an SEE, just returning the static eval score is simpler and may be sufficient, testing will tell.

It did pay for me. But to be able to measure it, you have to make it measurable first!
I would suggest modifying your limit to something quite aggressive like QS_LIMIT = -4 (instead of -7), only for the sake of doing the comparison. Then of course you need to set it back to -7 (I use -8 personally, but my testing showed that -6 and -8 were indistinguishable elowise, so I settled for -8 being the most conservative).