Transposition table usage in quiescent search?

[lucasart]

My tests so far with this show that using a traditional hash table in the q-search (vs. Arasan's evaluation cache) is a loser, about -10 elo. The difference is outside the error bars.

When you probe the TT in the search, you do not use QS TT entries, right ? (even for move ordering)
Because if you do, I can imagine why TT in the QS is a regression for you.

[AlvaroBegue]

My tests so far with this show that using a traditional hash table in the q-search (vs. Arasan's evaluation cache) is a loser, about -10 elo. The difference is outside the error bars.

When you probe the TT in the search, you do not use QS TT entries, right ? (even for move ordering)
Because if you do, I can imagine why TT in the QS is a regression for you.

Why would you not want to use the hash move from the QS? You are going to try captures first, so if there is a capture that was a gain in QS (with respect to standing pat), it might not be a bad place to start searching... Am I missing something?

[jdart]

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.

As to why it is a regression: not totally sure about that but the previous implementation is pretty similar already (it contains a cache from which the previous static eval score and qsearch pv move can be obtained). It is just separate from the regular hash table and separately restricted in size.

--Jon

[bob]

The point I was making is that if you have a position P that you store in the normal search with a non-capture best move, what do you do when you store a q-search tt entry for the SAME position? You just about can't refuse to store, that's pretty well-known. So do you overwrite and lose the non-capture best move and replace it with a capture? That can break ordering earlier in the tree where it is more important...

If you don't store in the q-search, I suppose there is no problem, although I would then wonder what the advantage of a probe might be...

Wouldn't the draft be deeper for the normal search entry? In that case the primary slot would still contain the normal search entry and the "always-replace" slot would eventually be overwritten. I think you might be able to stand a bit of this without it being too detrimental. I remember it was a win when I started hashing in the qsearch, but to be honest I haven't re-measured it in a while. It might be time to run a test or two.

I don't allow duplicates. Doesn't make much sense to fill up a 4-slot bucket with different entries for the same signature, IMHO. When I do a store, if I get a signature match, I overwrite that position, period. NO reason to not do so, something about it failed to terminate the search when you got the hit, so replacing it with something useful makes sense to me.

So in Crafty your hash table is one entry per signature match, replace-always? That's fine of course, I just seem to remember that you used to do things differently. All of this is worth re-testing. It's been a while since I collected statistics from the hash table. It's always interesting.

I have four entries per bucket, and on a store, I replace the best candidate. But if there is an exact signature match, I always replace that entry, I don't want the same signature in the tt multiple times. What's the gain?

Even when I used the Belle 2-level table, (depth-preferred and always store) I still wrote over a signature match entry, no matter which of the two tables it was in.

Perhaps its a nomenclature issue, (and I know this is pedantic), but I want to make sure we're discussing the same thing. What needs to match between two hash table entries for an exact signature match? Or to frame it another way, which minimal subset of the following do you require to be the same for a valid signature match?

• 1. hash key
  2. draft
  3. bound
  4. side to move
  5. the actual move
  6. score
  7. ?? (anything else)

BTW, I experimented last night with disabling all checks in the qsearch except for those at the first ply. So far, after about 2000 (3sec+1sec) games this is testing about -30 elo. I'm going to let it run for about 8000 games before I kill it, which should give a value with small enough error bars to trust if the elo loss stays this large. I may not be seeing the benefit from this because Djinn is pretty restrictive on the checks it allows in the qsearch.

Just signatures. The rest of the stuff (draft, bound) can make the entry unusable, but I was talking specifically of what happens when I want to store a table entry T, with signature S, and S matches an entry already in the table (but which was apparently not useful enough to terminate the search when the probe hit).

[bob]

Crafty counts nodes like everyone else. Each "MakeMove()" produces a new position (node). The q-search is pretty fast. It's been around since 1994 and has been modified many times to improve speed.

Not all programs work the same, and counting nodes like this would not cause the same count for the sames tree in all programs. In some designs counting MakeMoves would make sense, in others it wouldn't. I doubt if it makes sense in Crafty.

Moves are not nodes. MakeMove() is very fast (especially in mailbox designs). What takes time is evaluation, move generation and hash probing. Having a 'node' where you do none of these things, and yet counting the MakeMove-UnMake to it as a node, is therefore a very good way to drive up NPS. Another way of looking at it, however, is that it is a good way to waste time on superfluous MakeMoves...

In Joker, for example, I do the hash probe for a node in the parent node, before MakeMove(). So that when I have a hash hit, I can skip the MakeMove alltogether. That speeds up the number of positions my search visits per second. But it would of course lower the NPS if I counted MakeMoves.

In engines with very light evaluation, it is more meaningful to count MoveGens. Many QS nodes do not get to that stage, because the stand-pat already produces a cut. (And many full-width nodes would not get there because the null move or hash move produces a cutoff.)

Not doing hash probes in QS also helps to drive up NPS. Hash probes are expensive. Micro-Max 4.8 runs about 1Mnps on my PC, but micro-Max 1.6, which has no hash table, runs 6Mnps!

It seems clear that Crafty has a very 'light' definition of a node.

Moves actually are nodes. In fact, in classic tree search terminology, a move is the "arc" that connects the parent node to the child...

A node is not that cheap, period. Then you ammortize the eval costs across many nodes (in a depth-first approach obviously). I update the board, history, hash signatures, etc. I don't see any difference between counting MakeMove()'s and Search() calls, because if I make a move, I'm going to call search. (or quiesce of course).

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

[Joost Buijs]

Crafty counts nodes like everyone else. Each "MakeMove()" produces a new position (node). The q-search is pretty fast. It's been around since 1994 and has been modified many times to improve speed.

Not all programs work the same, and counting nodes like this would not cause the same count for the sames tree in all programs. In some designs counting MakeMoves would make sense, in others it wouldn't. I doubt if it makes sense in Crafty.

Moves are not nodes. MakeMove() is very fast (especially in mailbox designs). What takes time is evaluation, move generation and hash probing. Having a 'node' where you do none of these things, and yet counting the MakeMove-UnMake to it as a node, is therefore a very good way to drive up NPS. Another way of looking at it, however, is that it is a good way to waste time on superfluous MakeMoves...

In Joker, for example, I do the hash probe for a node in the parent node, before MakeMove(). So that when I have a hash hit, I can skip the MakeMove alltogether. That speeds up the number of positions my search visits per second. But it would of course lower the NPS if I counted MakeMoves.

In engines with very light evaluation, it is more meaningful to count MoveGens. Many QS nodes do not get to that stage, because the stand-pat already produces a cut. (And many full-width nodes would not get there because the null move or hash move produces a cutoff.)

Not doing hash probes in QS also helps to drive up NPS. Hash probes are expensive. Micro-Max 4.8 runs about 1Mnps on my PC, but micro-Max 1.6, which has no hash table, runs 6Mnps!

It seems clear that Crafty has a very 'light' definition of a node.

Moves actually are nodes. In fact, in classic tree search terminology, a move is the "arc" that connects the parent node to the child...

A node is not that cheap, period. Then you ammortize the eval costs across many nodes (in a depth-first approach obviously). I update the board, history, hash signatures, etc. I don't see any difference between counting MakeMove()'s and Search() calls, because if I make a move, I'm going to call search. (or quiesce of course).

I agree with you that counting MakeMove()'s is the most natural way to count nodes. But I disagree that counting MakeMoves()' is the same as counting Search() calls because in most search implementations in use today it can happen that you call Search() several times after a MakeMove(). For instance with IID etc.

[hgm]

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

[Joost Buijs]

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

In my case MakeMove() does almost everything, updating the board, the hashkeys, the material evaluation and the like. The only exception is the positional evaluation, that is done separately. I agree that in some cases it is not necessary to do it this way. The speed gain is negligible if you split all this stuff in separate functions. It is much cleaner to do this all at once.

[bob]

Crafty counts nodes like everyone else. Each "MakeMove()" produces a new position (node). The q-search is pretty fast. It's been around since 1994 and has been modified many times to improve speed.

Not all programs work the same, and counting nodes like this would not cause the same count for the sames tree in all programs. In some designs counting MakeMoves would make sense, in others it wouldn't. I doubt if it makes sense in Crafty.

Moves are not nodes. MakeMove() is very fast (especially in mailbox designs). What takes time is evaluation, move generation and hash probing. Having a 'node' where you do none of these things, and yet counting the MakeMove-UnMake to it as a node, is therefore a very good way to drive up NPS. Another way of looking at it, however, is that it is a good way to waste time on superfluous MakeMoves...

In Joker, for example, I do the hash probe for a node in the parent node, before MakeMove(). So that when I have a hash hit, I can skip the MakeMove alltogether. That speeds up the number of positions my search visits per second. But it would of course lower the NPS if I counted MakeMoves.

In engines with very light evaluation, it is more meaningful to count MoveGens. Many QS nodes do not get to that stage, because the stand-pat already produces a cut. (And many full-width nodes would not get there because the null move or hash move produces a cutoff.)

Not doing hash probes in QS also helps to drive up NPS. Hash probes are expensive. Micro-Max 4.8 runs about 1Mnps on my PC, but micro-Max 1.6, which has no hash table, runs 6Mnps!

It seems clear that Crafty has a very 'light' definition of a node.

Moves actually are nodes. In fact, in classic tree search terminology, a move is the "arc" that connects the parent node to the child...

A node is not that cheap, period. Then you ammortize the eval costs across many nodes (in a depth-first approach obviously). I update the board, history, hash signatures, etc. I don't see any difference between counting MakeMove()'s and Search() calls, because if I make a move, I'm going to call search. (or quiesce of course).

I agree with you that counting MakeMove()'s is the most natural way to count nodes. But I disagree that counting MakeMoves()' is the same as counting Search() calls because in most search implementations in use today it can happen that you call Search() several times after a MakeMove(). For instance with IID etc.

IID is used so rarely in Crafty I don't think it matters. And it actually causes Crafty to "understate" node counter. However, if you use IID 5 successive times on the same position, did you search 5 nodes or one? I still think one.

I do not remember the reason for making this change, as old versions of Crafty simply had a "nodes_searched++;" at the top of search and quiesce.

It'll come back to me at some point, but there was a reason for doing this.