Transposition table usage in quiescent search?

[Joost Buijs]

Last time i saw your program play, it played the same moves like latest rybka incarnation - so i totally do not believe you if you post: "improving the evaluation function".

We had a protest years ago when Fruit played well, it played like Fruit, this protest came from FAbien Letouzey. You failed to take the offer of Richard Pijl to get to your place and check out your source code.

Some years later now it plays exactly like Rybka 3 from evaluation viewpoint seen.

"Once a thief always a thief", is a Dutch saying.

And you write about improving evaluation, whereas what Bob writes is logical, it makes sense and it's the only truth in this case.

If you can AVOID researching the same part of the tree, that's a HUGE win, provided you have the system time to do so.

And if you really would've added lots of patterns to your evaluation function, instead of just cut'n paste the evaluation function of latest Rybka, your evaluation would slow down and therefore storing qsearch would make more sense.

I know you have a habit of accusing people, I have seen that many times in the past. Let me tell you there is not a single line copied and pasted in my program. The only thing I use is Pradu Kannan's magic, and even that has been rewritten.

My evaluation does just standard stuff everybody is doing, nothing special. It is not modelled after Fruit or Rybka3, in all these years I never looked longer than maybe 10 minutes at Fruit.

And yes, I remember that you and Richard accused me some 8 years ago of (cloning/using) Fruit. I don't blame you for that because I know you can't help it, but I am still angry with Richard about that.

There is another Dutch saying "Once a mad man always a mad man".

[PK]

For Rodent hashing qs nodes proved a small win.

However, the really funny thing occured after partially implementing root move list. The list was already in place, moves have been evaluated according to the quiescence search result, but root search still used the same move selection procedure as normal search. Root list was meant to support easy move at that time, but its trigger condition was faulty and never triggered. And all of a sudden I had 52% score after 1500 games, all because hash hits form qs.

[bob]

A q-search entry in the hash table cannot generally be used to cause a cutoff in the non-qsearch part of the tree, because it has searched only a restricted subset of moves and so the score there is not valid in a part of the search that is not so restricted. Normally this is handled by giving q-search nodes negative depth and then the usual depth test prevents cutoff (that is what I did)

In my "sophisticated" implementation q-search moves are not selected as a pv move in the non-qsearch part of the tree either, for similar reasons.
--Jon

In my implementation I always store q-search entries with a draft of 0.
A entry or move stored by the normal search will never be overwritten by one from the q-search because the normal entry has a greater draft.
I don't see any problem in using a move from the q-search in normal search if it just a choice between no move at all or the move from q-search as can happen in my implementation.

If that is true, you might want to test further. I am a firm believer, after years of testing this over and over, that when you complete a ply, you MUST store that result in the hash table. Why would you refuse to overwrite an entry that has the same signature, but which did not terminate the search? It is obviously useless, and the current search is an actual result you would like to avoid repeating if possible.

There is a great possibility that the scheme I use it not the best, and that there is room for improvement. But I am a firm believer that an entry that has been calculated to a greater depth has a value that is more accurate.

More accurate is irrelevant if the position is useless because of the bound it provides. That's a key point. There have been lots of studies shown that pure depth-preferred becomes problematic because if the table becomes filled with deep-draft entries that don't produce cutoffs, you may as well not have the table in the first place.

Anyway it is all about results, and my program plays not bad at all.
I believe it is better to spend my time in improving the evaluation function because that is where to expect the biggest gain.

[AlvaroBegue]

My intuition on this matter agrees with Joost Buijs's: The higher depth entry should be kept because it will save more work if it can be used. However, I know better than to trust my intuition in these matters, so I tested it. Always write is a +26 Elo improvement for me in self-test. I don't remember how many games I ran (I really should keep a log of these things), but the LOS was more than 99%.

Next I will try the idea of keeping both a lower bound and an upper bound (together with their depths) in the transpositions table.

[hgm]

Bob's argument is that the higher-depth entry should be overwritten, because it will NEVER save you ANY work. It has bounds that are not useful compared to the current search window, which apparently changed since the entry was created, and it is a blind guess whether it will ever change again (and in the right direction).

It will not only be wasting space in your hash table, but it will be actively preventing that you could save info on this position (which apparently still occurs in your tree) in the hash that could save you work. Even if there is plenty of empty space in the table.

[jdart]

I tested this strategy (always replace a hash signature match regardless of depth) and for me it is a win at hyper-bullet testing anyway (+8 elo plus or minus 4, BayesElo with an offset of 2400, 36000 games).

Note that I have a separate table for the q-search as previously discussed and that has always had an always replace strategy. So this change affects non-q-search nodes only.

--Jon

[Joost Buijs]

More accurate is irrelevant if the position is useless because of the bound it provides. That's a key point. There have been lots of studies shown that pure depth-preferred becomes problematic because if the table becomes filled with deep-draft entries that don't produce cutoffs, you may as well not have the table in the first place.

I have to be honest that I never looked at it in detail. This is something that has been grown historically. For a plain PVS you are completely right, but these modern searches are so complex, with many (p)re-searches, many different bounds and many different depths, that it is not easy to understand or follow what actually happens. Now everybody is telling me that 'always write' performs better than the scheme I use so I will certainly give this a try.

[bob]

I tested this strategy (always replace a hash signature match regardless of depth) and for me it is a win at hyper-bullet testing anyway (+8 elo plus or minus 4, BayesElo with an offset of 2400, 36000 games).

Note that I have a separate table for the q-search as previously discussed and that has always had an always replace strategy. So this change affects non-q-search nodes only.

--Jon

I tested the idea at all sorts of times, including 30K 40/2hr games which took beyond a month to run. It was always the right approach for my program. The current 4-bucket approach tested better than anything else I tried, although we are not talking huge Elo gains. But measurable ones for sure.

[pijl]

And yes, I remember that you and Richard accused me some 8 years ago of (cloning/using) Fruit. I don't blame you for that because I know you can't help it, but I am still angry with Richard about that.

I'm sorry to hear that the background of this has not been clear. The accusation certainly did not come from me and I only offered my help in clearing them. I hope we can clear this up soon in either a on-site tournament or online on one of the servers.
Regards,
Richard.