TT buckets

[stevemulligan]

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

The advice given by everyone was very helpful. I went back to triangular array and it looks ok when I have the TT disabled.

Watching the output with the cache turned on makes me think I implemented the TT incorrectly and I'm pretty sure I don't understand the concept properly because I can't figure out a solution.

Without TT:

Code: Select all

 2 -23 0 111 f6f7 f3g2
 3 127 0 1397 f6f7 f3g2 b3b2

3 ply search with TT (qsearch off):

Code: Select all

 2 -23 0 111 f6f7 f3g2
 3 -23 0 16 f6f7 f3g2

The 3rd ply stops after f3g2 because there is a cache hit (same position was found in previous iteration) and it returns the cached score before enumerating any moves.

Code: Select all

TransTableEntry tte = Cache.GetEntry(examineBoard.PieceZob);
if (&#40;tte.type != &#40;byte&#41;TransTableType.Empty&#41; && &#40;tte.depth <= realDepth&#41;)
&#123;
  if &#40;tte.zob == examineBoard.PieceZob&#41;
  &#123;
      if &#40;CacheOn&#41;
      &#123;
          
          if (&#40;tte.type == &#40;byte&#41;TransTableType.Exact&#41;) 
          &#123;
               PVTableEntry pv = Cache.PVTable&#91;examineBoard.PieceZob&#93;;
               triangularLength&#91;realDepth&#93; = pv.moveLength;
               triangularArray&#91;realDepth&#93; = pv.moves;

               // F3G2 gets returned here, no more moves searched??
               return tte.score;
          &#125;

          if (&#40;tte.type == &#40;byte&#41;TransTableType.Alpha&#41; && &#40;tte.score <= alpha&#41;)
           return tte.score;

           if (&#40;tte.type == &#40;byte&#41;TransTableType.Beta&#41; && &#40;tte.score >= beta&#41;)
           return tte.score;
      &#125;
   &#125;
&#125;

// The rest of search is below this point.

In my case, depth 3 is the leaf nodes, depth 0 is root.


So my question is, how do I get it to keep searching to ply 3 when the cache is enabled?

[bob]

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

The advice given by everyone was very helpful. I went back to triangular array and it looks ok when I have the TT disabled.

Watching the output with the cache turned on makes me think I implemented the TT incorrectly and I'm pretty sure I don't understand the concept properly because I can't figure out a solution.

Without TT:

Code: Select all

 2 -23 0 111 f6f7 f3g2
 3 127 0 1397 f6f7 f3g2 b3b2

3 ply search with TT (qsearch off):

Code: Select all

 2 -23 0 111 f6f7 f3g2
 3 -23 0 16 f6f7 f3g2

The 3rd ply stops after f3g2 because there is a cache hit (same position was found in previous iteration) and it returns the cached score before enumerating any moves.

Code: Select all

TransTableEntry tte = Cache.GetEntry(examineBoard.PieceZob);
if (&#40;tte.type != &#40;byte&#41;TransTableType.Empty&#41; && &#40;tte.depth <= realDepth&#41;)
&#123;
  if &#40;tte.zob == examineBoard.PieceZob&#41;
  &#123;
      if &#40;CacheOn&#41;
      &#123;
          
          if (&#40;tte.type == &#40;byte&#41;TransTableType.Exact&#41;) 
          &#123;
               PVTableEntry pv = Cache.PVTable&#91;examineBoard.PieceZob&#93;;
               triangularLength&#91;realDepth&#93; = pv.moveLength;
               triangularArray&#91;realDepth&#93; = pv.moves;

               // F3G2 gets returned here, no more moves searched??
               return tte.score;
          &#125;

          if (&#40;tte.type == &#40;byte&#41;TransTableType.Alpha&#41; && &#40;tte.score <= alpha&#41;)
           return tte.score;

           if (&#40;tte.type == &#40;byte&#41;TransTableType.Beta&#41; && &#40;tte.score >= beta&#41;)
           return tte.score;
      &#125;
   &#125;
&#125;

// The rest of search is below this point.

In my case, depth 3 is the leaf nodes, depth 0 is root.


So my question is, how do I get it to keep searching to ply 3 when the cache is enabled?

You have a serious implementation problem. That 3 ply search should NOT use the score from the TT. You are supposedly doing a 3 ply search, but the TT entry was stored for a 2 ply search. That's where the "draft" value is used. When you store a TT entry, you also store the remaining depth (draft). When you get a hit, you verify that the table draft is >= remaining real depth or else you treat this as a miss...

[Sven]

Code: Select all

TransTableEntry tte = Cache.GetEntry(examineBoard.PieceZob);
if (&#40;tte.type != &#40;byte&#41;TransTableType.Empty&#41; && &#40;tte.depth <= realDepth&#41;)
&#123;
  if &#40;tte.zob == examineBoard.PieceZob&#41;
  &#123;
      if &#40;CacheOn&#41;
      &#123;
          
          if (&#40;tte.type == &#40;byte&#41;TransTableType.Exact&#41;) 
          &#123;
               PVTableEntry pv = Cache.PVTable&#91;examineBoard.PieceZob&#93;;
               triangularLength&#91;realDepth&#93; = pv.moveLength;
               triangularArray&#91;realDepth&#93; = pv.moves;

               // F3G2 gets returned here, no more moves searched??
               return tte.score;
          &#125;

          if (&#40;tte.type == &#40;byte&#41;TransTableType.Alpha&#41; && &#40;tte.score <= alpha&#41;)
           return tte.score;

           if (&#40;tte.type == &#40;byte&#41;TransTableType.Beta&#41; && &#40;tte.score >= beta&#41;)
           return tte.score;
      &#125;
   &#125;
&#125;

// The rest of search is below this point.

In my case, depth 3 is the leaf nodes, depth 0 is root.


So my question is, how do I get it to keep searching to ply 3 when the cache is enabled?

You have a serious implementation problem. That 3 ply search should NOT use the score from the TT. You are supposedly doing a 3 ply search, but the TT entry was stored for a 2 ply search. That's where the "draft" value is used. When you store a TT entry, you also store the remaining depth (draft). When you get a hit, you verify that the table draft is >= remaining real depth or else you treat this as a miss...

Which means that in the code above, "tte.depth <= realDepth" should in fact read "tte.depth >= realDepth", otherwise the TT entry is "not deep enough" to allow pruning the current node.

Sven

[bob]

Code: Select all

TransTableEntry tte = Cache.GetEntry(examineBoard.PieceZob);
if (&#40;tte.type != &#40;byte&#41;TransTableType.Empty&#41; && &#40;tte.depth <= realDepth&#41;)
&#123;
  if &#40;tte.zob == examineBoard.PieceZob&#41;
  &#123;
      if &#40;CacheOn&#41;
      &#123;
          
          if (&#40;tte.type == &#40;byte&#41;TransTableType.Exact&#41;) 
          &#123;
               PVTableEntry pv = Cache.PVTable&#91;examineBoard.PieceZob&#93;;
               triangularLength&#91;realDepth&#93; = pv.moveLength;
               triangularArray&#91;realDepth&#93; = pv.moves;

               // F3G2 gets returned here, no more moves searched??
               return tte.score;
          &#125;

          if (&#40;tte.type == &#40;byte&#41;TransTableType.Alpha&#41; && &#40;tte.score <= alpha&#41;)
           return tte.score;

           if (&#40;tte.type == &#40;byte&#41;TransTableType.Beta&#41; && &#40;tte.score >= beta&#41;)
           return tte.score;
      &#125;
   &#125;
&#125;

// The rest of search is below this point.

In my case, depth 3 is the leaf nodes, depth 0 is root.


So my question is, how do I get it to keep searching to ply 3 when the cache is enabled?

You have a serious implementation problem. That 3 ply search should NOT use the score from the TT. You are supposedly doing a 3 ply search, but the TT entry was stored for a 2 ply search. That's where the "draft" value is used. When you store a TT entry, you also store the remaining depth (draft). When you get a hit, you verify that the table draft is >= remaining real depth or else you treat this as a miss...

Which means that in the code above, "tte.depth <= realDepth" should in fact read "tte.depth >= realDepth", otherwise the TT entry is "not deep enough" to allow pruning the current node.

Sven

Good one. I didn't see the code. It's backward and would REALLY kill chess skill. You'd actually want that entry to get overwritten so you could do a deeper than 2 ply search.

[stevemulligan]

Good one. I didn't see the code. It's backward and would REALLY kill chess skill. You'd actually want that entry to get overwritten so you could do a deeper than 2 ply search.

Thx for the clarifications Robert & Sven. I figured I could use depth from root instead of draft and would only need to change to comparison operation but I guess I missed something. I should be able to get it working now, thx again!!

[wgarvin]

Good one. I didn't see the code. It's backward and would REALLY kill chess skill. You'd actually want that entry to get overwritten so you could do a deeper than 2 ply search.

Thx for the clarifications Robert & Sven. I figured I could use depth from root instead of draft and would only need to change to comparison operation but I guess I missed something. I should be able to get it working now, thx again!!

"Depth from root" wouldn't work unless you clear the hash table every time you search a new root (or at least decrease all of the "depth from root" values stored in the TT). Anyways, the distance between the root and the current node would seem to be path-dependent. A TT node is a result about searching from that particular position, so whatever "depth" you store and compare, should be a measure of "how deep" you searched that specific position only. Just go with draft

[stevemulligan]

When you store a TT entry, you also store the remaining depth (draft).

What happens in a TT for qsearch then? I don't know how to get the draft there until qsearch is done. Do I only store the board score for each ply?

[kbhearn]

a) you don't have to store qnodes necessarily
b) if your qsearch is just a simple test all captures (or all 'potentially good' captures where 'potentially good' is deterministic), it doesn't matter how many plies into it you are, it can all be treated as draft 0. (if you do something like also including checks but only for the first N plies of quiescence in order to avoid a potential explosion then it would sometimes make a difference)

[Mincho Georgiev]

When you store a TT entry, you also store the remaining depth (draft).

What happens in a TT for qsearch then? I don't know how to get the draft there until qsearch is done. Do I only store the board score for each ply?

I was never able to measure any gain from storing the qnodes. The only benefit of that IMO is if you're trying to recover full pv line. Otherwise, it just don't pay-off at least to me.

[Evert]

When you store a TT entry, you also store the remaining depth (draft).

What happens in a TT for qsearch then? I don't know how to get the draft there until qsearch is done. Do I only store the board score for each ply?

With reductions and extensions, you never know the draft until the search is done. I may say that I have X plies to go to the horizon, but extensions and reductions may change that down the line.
What I store is the nominal draft, which is the only thing I know when comparing the draft stored in the TT. I have no idea whether it would help or hurt to store the actual draft in the TT (anyone know?)
For Jazz (and Sjaak) qsearch nodes have negative draft: they are "on the other side" of the search horizon. I don't use the TT there, however.