Hashed PVs

[sje]

Chances are, no matter what you set max ply to, you will get a PV that is longer. You have to have a cutoff point where you realize "I can't copy all of this hash-recovered pv on to the end of the current one, because it simply is too long.

That bit me as soon as I wrote this code a few years ago.

I still get some PVs that end with <HT> as a result. I could change MAXPLY to 128 or 256, but I am not sure I want to really display PVs that long, I am not sure they are sensible.

If the PV can be extended by appending tablebase moves, it can be come a couple hundred of ply in length. That's one of the reasons I dropped MAXPLY from the program. The only absolutely way to handle a fixed length limit is to set MAXPLY to 12,000 or so, the theoretic maximum ply length of a game.

Using variable length move lists works. Moves are never copied; only the end links of lists are adjusted and this is always an O(1) time operation regardless of the lengths of the lists. Using a private move node recycler makes the node allocation time also an O(1) operation; this is more important than the append time because allocation happens more often. A private allocator is a good idea anyway, as hitting malloc() or new in a multithreaded application invites the possibility of a block due to a mutex in the library code.

If there is a downside to using lists, then it's the implementation time for installing the code into an already written program.

[hgm]

How can you avoid having to copy the entire lists? Just manipulating the pointers would lead to the tail cells being shared by many TT entries, and it would be impossible to know when you can free them because they are no longer in use. E.g. if you overwrite a TT entry with a PV, that PV might still be part of the PV of the TT entry for the parent position.

[sje]

And in C++ template library we have the std::list template:

http://www.cplusplus.com/reference/list/list/

This works, but has a drawback in that the default instantiation uses the new/delete library calls which entails some slowdown because of their generality. That's why Symbolic uses a a private allocator which is just another move list which holds recycled nodes. The new/delete routes are called only for this free list, and only when absolutely necessary.

It is possible to use the std::list template with a custom allocator, but this was extra complexity which I didn't need.

Obviously, each thread should have its own private allocator object.

Once I tried a pre-flight approach where the program primed the private allocator with several thousand move node allocations at program start time. This had no measurable benefit, so it was dropped.

The use of the alternative std::vector template should be reserved for those cases where O(1) random access time for elements is needed.

[sje]

How can you avoid having to copy the entire lists? Just manipulating the pointers would lead to the tail cells being shared by many TT entries, and it would be impossible to know when you can free them because they are no longer in use. E.g. if you overwrite a TT entry with a PV, that PV might still be part of the PV of the TT entry for the parent position.

The program doesn't use a transposition table for storing PV data. Only single moves are stored in a transposition table, and this is entirely orthogonal to PV data storage.

When list B is appended to list A, only a few pointers are adjusted regardless of list lengths. List B becomes empty as a result. No move data is ever copied or duplicated in PV operations.

A PV is not extended via probes of the main transposition table as I've found this unnecessary in my approach. However, a PV can be extended via tablebase probes.

[sje]

To help others to save some time, I'm sharing my C++ templates for two-way linked Node, List, and Pool formation.

See: https://dl.dropboxusercontent.com/u/316 ... lTemplates

Sample method, this one gets used for appending PV data:

Code: Select all

  void Merge(TWList<T> * const listptr)
  {
    T * const headptr = listptr->head;

    if (headptr)
    {
      if (tail)
      {
        tail->PutNext(headptr);
        headptr->PutPrev(tail);
      }
      else
        head = headptr;

      tail = listptr->tail;
      count += listptr->count;
      listptr->head = listptr->tail = 0;
      listptr->count = 0;
    };
  }

Note that the lengths of the lists in play are not important.

The code could be made even faster by having a version which dropped the count member variable, but I doubt this would have much effect. It's plenty fast enough as it is.

[sje]

Sample template instantiation:

In Symbolic, a Move class instance contains a 32 bit representation of a move. However, the actual implementation is independent of the TWNode and TWList template usage.

Code: Select all

class MoveNode: public Move, public TWNode<MoveNode> {};
class MoveList: public TWList<MoveNode> {};

Actually, there are a few more methods defined for each template instantiation, like copy constructors and assignment operators. In particular, the MoveList class has calls for locating a move node by its SAN encoding, encoding an entire move list, and flipping an entire move list. There is even a Decode method which gets used when an user supplies a whole list of moves to be executed sequentially.

[xmas79]

Chances are, no matter what you set max ply to, you will get a PV that is longer. You have to have a cutoff point where you realize "I can't copy all of this hash-recovered pv on to the end of the current one, because it simply is too long.

That bit me as soon as I wrote this code a few years ago.

I still get some PVs that end with <HT> as a result. I could change MAXPLY to 128 or 256, but I am not sure I want to really display PVs that long, I am not sure they are sensible.

If a PV is sensible at depth D, why should not be sensible at depth D+1? I really don't know, and I have to play with it a bit more. Adding a table base hit can be very sensible... Maybe grafting is the real problem that makes those very long PVs useless...

And another thing that is happening now is that when I store PV into the vector, I save the associated score. And when I retrieve PVs in exact hash hits, I discovered that sometimes (don't really know if it's *often* instead of *sometimes*) there is a difference between the score just probed in TT and the one retrieved from PV. Still didn't have time to analyze this.

Natale.

[hgm]

Very often the first mate you see beyond the horizon (through TT grafting) is at a ridiculously large distance, while the best mate is twice as close (but still beyond the horizon). The PV to that distant mate then has very many detours, and I think this is what Bob means if he says that they are not sensible.

[bob]

Chances are, no matter what you set max ply to, you will get a PV that is longer. You have to have a cutoff point where you realize "I can't copy all of this hash-recovered pv on to the end of the current one, because it simply is too long.

That bit me as soon as I wrote this code a few years ago.

I still get some PVs that end with <HT> as a result. I could change MAXPLY to 128 or 256, but I am not sure I want to really display PVs that long, I am not sure they are sensible.

If a PV is sensible at depth D, why should not be sensible at depth D+1? I really don't know, and I have to play with it a bit more. Adding a table base hit can be very sensible... Maybe grafting is the real problem that makes those very long PVs useless...

And another thing that is happening now is that when I store PV into the vector, I save the associated score. And when I retrieve PVs in exact hash hits, I discovered that sometimes (don't really know if it's *often* instead of *sometimes*) there is a difference between the score just probed in TT and the one retrieved from PV. Still didn't have time to analyze this.

Natale.

This is a pretty simple to answer question. Would you agree that the best move at ply=1 in the PV will be played in the actual game with 100% probability? It IS the best move the search returns. But what about the second move? Does your program predict correctly 100% of the time? No. But if your program is strong enough, the second move in the PV IS the best move some probability P of the time, where P < 1.0. What about the third? A little less likely? By the time you get out into those rather ridiculous PVs that can easily stretch beyond 64 plies, do the moves mean anything, or is the PV just "interesting" because it is so long?

Only case I can make for long PVs might be endgame tablebase hits where you can walk the table and show the PV all the way out to that mate in 211 or whatever you found. Otherwise, those moves at the end of that PV are just "legal moves" with no real probability that they will show up in the actual game...