Playing transposition table moves in the Quiescence search

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
AndrewGrant
Posts: 487
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Playing transposition table moves in the Quiescence search

Post by AndrewGrant » Thu Jan 17, 2019 12:52 am

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
Posts: 487
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Re: Playing transposition table moves in the Quiescence search

Post by AndrewGrant » Thu Jan 17, 2019 1:49 am

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
Posts: 201
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Playing transposition table moves in the Quiescence search

Post by tomitank » Thu Jan 17, 2019 1:56 am

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

User avatar
xr_a_y
Posts: 762
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Playing transposition table moves in the Quiescence search

Post by xr_a_y » Thu Jan 17, 2019 6:13 pm

tomitank wrote:
Thu Jan 17, 2019 1:56 am
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
Posts: 201
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Playing transposition table moves in the Quiescence search

Post by tomitank » Thu Jan 17, 2019 6:21 pm

xr_a_y wrote:
Thu Jan 17, 2019 6:13 pm
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.

User avatar
xr_a_y
Posts: 762
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Playing transposition table moves in the Quiescence search

Post by xr_a_y » Thu Jan 17, 2019 7:41 pm

Andrew, how about a small dedicated TT for qsearch ?

User avatar
silentshark
Posts: 236
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: Playing transposition table moves in the Quiescence search

Post by silentshark » Thu Jan 17, 2019 10:31 pm

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
Posts: 824
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Playing transposition table moves in the Quiescence search

Post by PK » Thu Jan 17, 2019 11:06 pm

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
Posts: 458
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Playing transposition table moves in the Quiescence search

Post by D Sceviour » Fri Jan 18, 2019 1:40 am

AndrewGrant wrote:
Thu Jan 17, 2019 12:52 am
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?

User avatar
silentshark
Posts: 236
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: Playing transposition table moves in the Quiescence search

Post by silentshark » Sat Jan 19, 2019 11:54 am

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.

Post Reply