Transposition table usage in quiescent search?

[bob]

What makes it unnatural, IMO, is that removing wasteful MakeMove() UnMake() pairs would decrease your NPS, while it is obviously beneficial speedwise. Besides, MakeMove() does not seem to be a uniquely defined concept. For me, MakeMove() does just that: making the move on the internal board. Updating hash keys is done elsewhere, as I need them earlier, and in many cases use of the hash key (for detecting repetition or doing a hash probe) makes it unnecessary to make the move (which basically is only needed when I want to do a full evaluation).

I suppose the question that must be asked, then, is "what is a node"? In game trees, a node is a position reached by making a move from the parent node. Note I don't increment the node counter in MakeMove(). I increment it only in the search/quiesce code where MakeMove() is called. I have to use "MakeMove()" to walk down the PV to print it out, those don't get counted.

And now that I think about it, the reason I chose to make this change was for exactly that reason. The old code would make a move, test and notice it was illegal, and unmake the move, without counting that work. Make/Unmake are fairly expensive in my code, and I wanted to try to count the "nodes" one would see in the tree search space. If I dump my tree (trace=999) my node counter matches the output produced, exactly.

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

[Joost Buijs]

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

[hgm]

More accurate, but still useless. Or you would not have had to search again at lower depth. It tells you very accurately something that you don't need to know...

[Joost Buijs]

More accurate, but still useless. Or you would not have had to search again at lower depth. It tells you very accurately something that you don't need to know...

Let it be useless then, I don't miss a single hour of sleep over it.

[Chan Rasjid]

More accurate, but still useless. Or you would not have had to search again at lower depth. It tells you very accurately something that you don't need to know...

If Bob said he tested it, it should be for the better unless others too tested it and found contradictory conclusion. What Bob's test show may be that a most recent search has greater relevance beyond search draft.

I am not to sure that not having a cutoff at a lower depth confirms that the higher draft entry is definitely useless:-
assume the earlier entry is an upper bound value UB and QS search alpha bound is A; then QS will still search if A < UB, not a cutoff. For different root iterations, the aspiration windows shift left or right unpredictably and any UB entry of the normal search searched all moves and time spent is much more than for any QS search; this UB entry may come in useful at the next root iteration.

Best Regards,
Rasjid.

[hgm]

assume the earlier entry is an upper bound value UB and QS search alpha bound is A; then QS will still search if A < UB, not a cutoff.

The usual way to remedy that (e.g. used in Fruit 2.1) is to store both an upper and a lower bound.

In PVS the situation you describe almost never occurs, as almost the entire tree is searched with the same null window. You can get it if the root score changes, but that is exactly the situation where it is likely to be rather permanent, so that for every future hit on the position you will have the opposite bound type from what you need. That is what I (and Bob) mean by 'useless'.

[diep]

Hi,

I was wondering whether the transposition (or hash) table should be used in the quiescent search, to cutoff already searched positions as well as to store the result. I see that Stockfish does it.

I tried a simple implementation, just store all q-search results and returning the hash value if I get a useful hit (i.e exact value, or > beta and lower bound, etc.)

It scored +25 elo after 4000 games at 5 s + 100 ms a move with 32MB hash size.

However, although the LOS is good, I am reluctant to commit the patch as I am worried that it will not be good when the hash is full, e.g. at long time control. How should I test to ensure that this is not a problem? Do any of you have experience with this sort of thing?

And one other question, am I right to assume that the quiescent best move should not be promoted to the top of the full search move list, unlike a normal hash move?

Thanks,
Jerry

Results are similar for Diep like you reported. A good overwrite strategy always is important. Hashing quiescencesearch for Diep is a necessity.

Using the best move from qsearch is a nice profit for your search, if it has a best move.

Note that 32MB hashtable is pretty small. Why not use 32GB ram if you got it?

Using default 4-8GB here or so. The SMP starts to work crap under 400MB for hashtables or so.

[diep]

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

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.

[diep]

Hi,

I was wondering whether the transposition (or hash) table should be used in the quiescent search, to cutoff already searched positions as well as to store the result. I see that Stockfish does it.

I tried a simple implementation, just store all q-search results and returning the hash value if I get a useful hit (i.e exact value, or > beta and lower bound, etc.)

It scored +25 elo after 4000 games at 5 s + 100 ms a move with 32MB hash size.

However, although the LOS is good, I am reluctant to commit the patch as I am worried that it will not be good when the hash is full, e.g. at long time control. How should I test to ensure that this is not a problem? Do any of you have experience with this sort of thing?

And one other question, am I right to assume that the quiescent best move should not be promoted to the top of the full search move list, unlike a normal hash move?

Thanks,
Jerry

I don't have recent result of todays Diep with respect to the 'win' of qsearch, yet last time i measured some years ago, it speeded up Diep 20% in time to depth. That's such a huge win that even one for sure doesn't need to retest that until RAM starts to get really really slow - and it won't - we still have the L3 (SRAM) then to store it so to speak