TT buckets

[stevemulligan]

I turned my TT back on and realized I'm going to get shortened PV's because I use a simple depth-replacement right now. I want the full PV (getting it 99% of the time is good enough for me)

From what I can see, 4 slots using age-replacement will fix my PV problem and reduce type-2 collisions. Am I understanding that right? (I'm addressing using the method described by HGM here

Also for powerOf2 is that 2^n or n^2 (I'm assuming the former, using 131072 entries)

[Zlaire]

I assume you talk about PV as a cosmetic thing.

I'd say don't adjust your TT based on that, adjust that for strength instead.

Read this http://chessprogramming.wikispaces.com/ ... +variation for some alternative ideas.

[hgm]

What has shortened PVs got to do with the replacement? Are you taking the PV from the hash after the search?

[stevemulligan]

Are you taking the PV from the hash after the search?

Yes. I was storing the PV in a separate table for a while but I realized I was doing it wrong. I was storing it in a c# dictionary indexed by zob hash. This doesn't work because it grows forever, if I clear it out then I get shortened PV's again. So I'm trying to decide on a method that a) I can understand and b) is proven to work.

I think using a 4 slot bucket will solve the PV problem (in 99% of cases) and give a small performance increase but I wanted to make sure before I started. The last time I got stuck I spent weeks trying to debug something on my own because I didn't grasp the basic concept of standing pat.

edit: (I know separate PV table is proven to work but I don't understand how to implement it properly)

[hgm]

Taking the PV from the hash is an unreliable method: you often don't get the PV that the engine did actually calculate. E.g. the PV can end in a checkmate, while the engine did not report a mating score (because the mate was beyond its horizon).

The 'triangular array' method should not be that hard to understand. For every ply level you keep one PV, which is the best PV so far for the current node at that level. When you enter the node you clear its PV. If you find a PV move in that node, (i.e. score between alpha and beta), you make it the first move of the PV for that level, and put the PV of the daughter node (from which you just returned, at the next level) behind it.

That is all.

[Evert]

edit: (I know separate PV table is proven to work but I don't understand how to implement it properly)

Then you should break out pen&paper and sit down to work though the algorithm until you do understand it and can implement it correctly.
Of course, you can then still decide to retrieve the PV from the transposition table if you want to.

[stevemulligan]

The 'triangular array' method should not be that hard to understand.

I was using a triangular array at one point. I can't find the exact page where I got the code from but it was almost identical to the code at the bottom of this page (The page I learned from had a black background and I can't find it now) I did manage to get it working but I took it out because I didn't think it was compatible with hash tables.

How do I make this work with the hash table? If I get a exact hit halfway down a branch then I'm going to missing part of the PV right?


edit:

Then you should break out pen&paper and sit down to work though the algorithm until you do understand it and can implement it correctly.

The part I got stuck on with that method is how to remove entries in the PV table once they are no longer applicable. Looping through every entry in my TT at the start of search to remove unused entries is the only way I can think of to make sure the PV table only contains valid entries.

[hgm]

Indeed, hash cuts will be PV cuts. If you care about that, just don'tdoany hash cuts in PV nodes (this is how Fruit solves it). This is the easiest solution, coding-wise, but there are alternatives:

*) at the moment of a hash cut in a PV node you could fetch the remaining part of the PV out of the hash table, just like you are doingnow after the search, and copy it into the triangular array. This gives you back the inaccuray problem, but less severely, because there has beenless time for the PV tail to be over written.
*) you could use the search to do that, but then use the score of the hash entry in stead of that returned by the search. This is sightly less efficient than using a dedicated routine to retreive the hash (but not very, because every side branch is likely to be a hash hit too, and not being PV nodes, these will be cut). But it saves some coding work. And you won't have the problem of the Fruit method that you ignore the hash score, which is potentially better. It does still suffer from the accuracy problem, though.
*) Every time you store a PV node in the hash table, you could save the full PV with it (in stead of just the first move). And then restore this saved PV whenever you take a hash cut. There are severalplaces you could store the PV. You don't want to reserve space for it in every hash entry, as it would almost never be used. Crafty uses a separate (comparatively small) hash table for storing these PVs. I would store them in a neighboring entry of the same bucket.

[bob]

I turned my TT back on and realized I'm going to get shortened PV's because I use a simple depth-replacement right now. I want the full PV (getting it 99% of the time is good enough for me)

From what I can see, 4 slots using age-replacement will fix my PV problem and reduce type-2 collisions. Am I understanding that right? (I'm addressing using the method described by HGM here

Also for powerOf2 is that 2^n or n^2 (I'm assuming the former, using 131072 entries)

Nope, it will make it worse. If you get more EXACT hits, you get more short PVs. You can look at Crafty to see an alternative. An extra TT that stores just paths. When I store an EXACT entry (not very often) I use the alternate TT to store the complete path from the terminal position back to that TT position. When I get an EXACT hit, I graft that stored PV onto the normal PV and I get to see everything. You can make this TT quite large to avoid overwrites, and since it is rarely accessed, the TLB issues won't hurt at all...

[Evert]

I was using a triangular array at one point. I can't find the exact page where I got the code from but it was almost identical to the code at the bottom of this page (The page I learned from had a black background and I can't find it now)

Probably Bruce Moreland's pages. Sadly, they have disappeared and seem to not have been completed...

I did manage to get it working but I took it out because I didn't think it was compatible with hash tables.

How do I make this work with the hash table? If I get a exact hit halfway down a branch then I'm going to missing part of the PV right?

They work fine with hash tables, but yes: you do get a shorter PV if you terminate the search on a hash hit. There are ways around that (don't accept exact cut-offs in PV nodes, for instance, or keep around separate table for PV nodes so you can reconstruct the path later if needed, or just try to extend the PV using entries from th TT), but whether it's worth it is not so clear (from the point of view of playing strength it almost certainly isn't because the collected PV is mainly for output; you do get to stuff it back into the TT though).

The part I got stuck on with that method is how to remove entries in the PV table once they are no longer applicable. Looping through every entry in my TT at the start of search to remove unused entries is the only way I can think of to make sure the PV table only contains valid entries.

Not sure what you mean, but when you enter a node, the first thing you do is terminate the current line at that node. Then when you find a best move, store it along with whatever variation goes with it. Do that consistently and you end up with the full PV at the root.