Transposition table usage in quiescent search?

[bob]

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.

My implementation stores the static value in the hash table so that the q-search still gets the benefit of having this.

I tried two versions. One accepted any move from the transposition table as a pv move. The other is more sophisticated and does not use moves from q-search nodes in the main search and also does not use moves from the table in the q-search that do not meet the normal q-search move selection criteria. The test for the 2nd version is still running but so far it does not appear to be any better.

--Jon

One bug many have had: don't let a non-capture tt best move get played in the q-search. That can cause a bit of an explosion.

[jdart]

One bug many have had: don't let a non-capture tt best move get played in the q-search. That can cause a bit of an explosion.

That is what I meant by "does not use moves from the table in the q-search that do not meet the normal q-search move selection criteria." It is a little more complex for me because I allow non-capture checking moves in the q-search.

--Jon

[bob]

One bug many have had: don't let a non-capture tt best move get played in the q-search. That can cause a bit of an explosion.

That is what I meant by "does not use moves from the table in the q-search that do not meet the normal q-search move selection criteria." It is a little more complex for me because I allow non-capture checking moves in the q-search.

--Jon

I do to at the first ply of q-search, but not beyond that. The risk for "checks in q-search" if you go beyond the first ply is that the TT might puke up a check, which typically causes an exhaustive escape-check search, and the q-search goes ape. I used to do it at the first ply and at the third, but only at the third if the first was a check. One TT experiment blew up because of that in that it was causing me to include checks at ply=3 that could not possibly result in a win of material since ply 2 could always stand pat if ply 1 was not a check...

[jdart]

This is configurable for me but the default is first ply of q-search only.

--Jon

[Tom Likens]

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.

Anyone can test the NPS of course, the source is available. In the last CCT it was hitting about 30M on a 6-core 3.2ghz i7

Don't I well remember it!

All kidding aside, I definitely have to add SMP to Djinn.

[Tom Likens]

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.

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

[hgm]

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.

[Joost Buijs]

Well, 3 others have posted in this thread that it's a noticeable win for them. How much ELO did it cost Crafty? Probably the result depends on how expensive an engine's qsearch is. Mine's slow.

I can't really tell whether my q-search is slow or not because I never compared it with other ones. I use SEE throughout for move ordering, no MVV-LVA, my SEE is highly optimized and it performs a little bit better than MVV-LVA. Maybe the q-search of Bob's program is very fast. When I see Crafty doing 30 million n/s on a 6 core (at least that's what's being told) it makes me wonder how that is possible. This can mean two things, either Crafty counts nodes differently or it does very little work at each node.

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.

Anyone can test the NPS of course, the source is available. In the last CCT it was hitting about 30M on a 6-core 3.2ghz i7

That is very fast indeed. Especially considering the clock frequency.
My program does about 11M on a 6-core 4GHz. i7. (this is with hashing in q-search). At the moment I count nodes exactly the same, each do-move is a node. And I have the feeling that my program is not slow at all, everything is pretty well optimized for speed. A few things can be done better, but I don't think I can gain more then maybe another 10%. Probably a big difference is that I removed lazy evaluation completely. With lazy evaluation it is about 20% faster, but it plays worse because of search instability. If you use the evaluation for pruning decisions, lazy evaluation is making the search very unstable.

[Tom Likens]

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.