Transposition table usage in quiescent 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.
bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table usage in quiescent search?

Post by bob » Wed Mar 06, 2013 8:19 pm

Chan Rasjid wrote:
bob wrote:
pkappler wrote: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.
I don't quite understand.

A 'replace-always' scheme does not always replace unless we really want to implement it that way without checking if the position has already been hashed in an earlier search of a greater draft.

My implementation does not replace a same position where the entry has a greater or equal draft - it is the same position!

Rasjid.
Same position, different information. When you did the probe, and got the hit, the info did not terminate the search. So why not store info that WILL terminate the search the next time around?

"replace always" means exactly that.

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table usage in quiescent search?

Post by bob » Wed Mar 06, 2013 8:21 pm

Joost Buijs wrote:
pkappler wrote: 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

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table usage in quiescent search?

Post by bob » Wed Mar 06, 2013 8:23 pm

jdart wrote: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
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Transposition table usage in quiescent search?

Post by jdart » Wed Mar 06, 2013 8:45 pm

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
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table usage in quiescent search?

Post by bob » Wed Mar 06, 2013 9:35 pm

jdart wrote:
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
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Transposition table usage in quiescent search?

Post by jdart » Thu Mar 07, 2013 12:51 am

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

--Jon

Tom Likens
Posts: 303
Joined: Sat Apr 28, 2012 4:18 pm
Location: Austin, TX
Contact:

Re: Transposition table usage in quiescent search?

Post by Tom Likens » Thu Mar 07, 2013 1:49 am

bob wrote: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! :smile:

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

Tom Likens
Posts: 303
Joined: Sat Apr 28, 2012 4:18 pm
Location: Austin, TX
Contact:

Re: Transposition table usage in quiescent search?

Post by Tom Likens » Thu Mar 07, 2013 3:06 am

bob wrote:
Tom Likens wrote:
bob wrote: 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
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table usage in quiescent search?

Post by bob » Thu Mar 07, 2013 4:17 am

Tom Likens wrote:
bob wrote:
Tom Likens wrote:
bob wrote: 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.

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition table usage in quiescent search?

Post by hgm » Thu Mar 07, 2013 7:43 am

bob wrote: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.

Post Reply