Playing transposition table moves in the Quiescence search

[AndrewGrant]

Recently I've found elo by probing the Transposition Table (TT) during the Quiescence Search (QS) in order to generate cutoffs. However, I am not currently making any use of the ttmove which can be found. Currently my QS only generates tactical moves -- no quiets what-so-ever, not even checks or evasions.

I have tried to use tactical moves from the TT in the QS, but that does not win any elo. Neither does using the tactical moves and still applying the same criteria as the other tactical moves for being considered to play (IE, using the table only changes the order in which moves are tried, not the conditions which must be met to play them).

The final step of course is to allow the QS to use ANY type of move found in the TT. Some initial testing suggests this is worth maybe two elo in Ethereal. But allowing these quiet moves in the QS could pose a potential problem. I imagine a scenario in which each quiet move leads to another TT position holding a quiet move, causing a very long chain of TT moves to be played (if unlucky enough to produce zero cutoffs by the TT or any other means).

I suppose the natural response is to do something like only take quiet moves from the TT if above a certain depth, say -3 or -5. However, this sort of arbitrary cutoff is strange, and I would not like to put such a construct in Ethereal if not needed. I will be running some tests to see how deep QS lines go on occasion, but I am interested in hearing from others on this topic.

Cheers, Andrew Grant

[AndrewGrant]

I did an experiment where I summed up the number of times that depth -<N> was reached during the QS.

First result uses ./Ethereal bench 20 32 4096 (Depth 20, 32 threads, 4GB hash). Column one is with TT moves in QS, column two is without.

Code: Select all

|-------------|-------------|-------------|
|    DEPTH    |    COUNT    |    COUNT    |
|-------------+-------------+-------------|
|           0 |   544135503 |   663472806 |
|           1 |   229592424 |   261667947 |
|           2 |    86076295 |    95900333 |
|           3 |    29882982 |    31365997 |
|           4 |    11214866 |    11517317 |
|           5 |     3967730 |     3817134 |
|           6 |     1437253 |     1301603 |
|           7 |      498706 |      417163 |
|           8 |      175997 |      134702 |
|           9 |       58318 |       40410 |
|          10 |       19086 |       12428 |
|          11 |        6110 |        3398 |
|          12 |        1558 |         909 |
|          13 |         419 |         201 |
|          14 |         110 |          62 |
|          15 |          46 |           6 |
|          16 |          24 |           0 |
|          17 |           3 |           0 |
|-------------+-------------+-------------|
| TOTAL NODES |  5669389655 |  7120181502 |
|-------------|-------------|-------------|

First result uses ./Ethereal bench 20 1 256 (Depth 20, 1thread, 256MB hash). Column one is with TT moves in QS, column two is without.

Code: Select all

|-------------|-------------|-------------|
|    DEPTH    |    COUNT    |    COUNT    |
|-------------+-------------+-------------|
|           0 |    55001802 |    61607734 |
|           1 |    15881156 |    17257581 |
|           2 |     4477841 |     4579736 |
|           3 |     1465073 |     1446399 |
|           4 |      515909 |      500711 |
|           5 |      172925 |      169845 |
|           6 |       59497 |       58004 |
|           7 |       19050 |       18602 |
|           8 |        5706 |        6776 |
|           9 |        1737 |        2020 |
|          10 |         480 |         674 |
|          11 |         130 |         222 |
|          12 |          21 |          69 |
|          13 |           6 |           9 |
|          14 |           2 |           0 |
|-------------+-------------+-------------|
| TOTAL NODES |   226268454 |   246467602|
|-------------|-------------|-------------|

Node that in both cases the version with TT moves in the QS spent LESS nodes in the QS than the version without TT in the QS, but also went deeper, although slightly.

[tomitank]

I came to the conclusion that only at the horizon is worth checking the transplant table. if (depth == 0)
Beyond that, it's very rare to help. It's just a waste of time..

The Mvv-Lva sorting is good enough in qsearch and hash move is futile (IMO)

-Tamás

[xr_a_y]

The Mvv-Lva sorting is good enough in qsearch and hash move is futile (IMO)
-Tamás

But you still prune bad SEE move in qsearch right ?

[tomitank]

But you still prune bad SEE move in qsearch right ?

Yes, but only if i'm not in check! When i'm in check, then i call evasion moves and i don't pruning.

Earlier i used "See" for the evasion moves sorting, but it's was futile also.

[xr_a_y]

Andrew, how about a small dedicated TT for qsearch ?

[silentshark]

Interesting, I recently put tt probing back into my engine, and it was a win. But I haven't kept good records (recently addressed that). So I will try

1. No tt probing in q search
2. Probe at depth==0 only in q search

..and compare with the current approach - probe throughout q search

Cheers,
Tom

[PK]

Tested that, probably with some depth limit, but failed narrowly (which does not mean anything for Your engine, the rating gap implies I must have failed on several techniques that work for You). IIRC Andscacs might be using it. The real fun comes when you print all the positions when quiescence search says that non-capturing move is the best. It is usually something that changes static score drastically: castling, passed pawn push etc.

[D Sceviour]

However, I am not currently making any use of the ttmove which can be found.

The tt move, if any, should be tried first. As long as it does not lose elo, this seems to be theoretically correct. I never found a non-capture move in the tt table on the horizon. This is because a non-capture tt best move would have a greater depth stored and the hash probe should prune.

The final step of course is to allow the QS to use ANY type of move found in the TT.

I have seen this idea used in RobboLito for PV quiescent nodes. It looks like a type of ProbCut where full width responses are made on captures. However, if ProbCut was used on the previous ply then it seems to be a waste in quiescence.

With multiple threads and staggered aspiration depths, it is unclear what might might take place on the horizon. Maybe a quiet move is best ignored.

I suppose the natural response is to do something like only take quiet moves from the TT if above a certain depth, say -3 or -5.

Would not quiet moves explode and make the position noisy? Daniel Jose Queralto (Andscacs) suggested a complete QS cutoff at depth of -6. Current tests on my engine demonstrate an elo loss with any QS depth cutoff. The exchange combinations are necessary. There are SEE methods that try to reduce the exchange calculations, but are they really any faster or more effective than a standard quiescent exchange search?

[silentshark]

ok.. running a little "probe TT in qsearch vs don't probe TT in qsearch" test. Will feedback. Probably won't have patience to test enough games, but anyway.