triangular pv

[hgm]

Search instability will kill you. In a perfectly stable search (and TSCP probably has one), every fail high compared to a null window in a PV node will be confirmed by the re-search, and then lead to replacement of the PV.

With hash table, LMR, null move etc. a large fraction of the null-window fail highs will cause a fail low on re-search, however. This will destroy the PV that remains in effect. This seems pretty disastrous if you want to store serious information in stead of just a PV that is not used for anythng.

Better use the stack method. This does not waste any space, and is 100% reliable. Saving more data also will allow you to benefit from more data.

You could make a refinement, by not putting a PV on the stack when the PV move remains a PV move, as this would be merely a copy of the PV of the parent node. You then only have to allocate space for a new PV just before you start re-searching a non-PV move.

[Daniel Shawul]

Search instability will kill you. In a perfectly stable search (and TSCP probably has one), every fail high compared to a null window in a PV node will be confirmed by the re-search, and then lead to replacement of the PV.

With hash table, LMR, null move etc. a large fraction of the null-window fail highs will cause a fail low on re-search, however. This will destroy the PV that remains in effect. This seems pretty disastrous if you want to store serious information in stead of just a PV that is not used for anythng.

Better use the stack method. This does not waste any space, and is 100% reliable. Saving more data also will allow you to benefit from more data.

You could make a refinement, by not putting a PV on the stack when the PV move remains a PV move, as this would be merely a copy of the PV of the parent node. You then only have to allocate space for a new PV just before you start re-searching a non-PV move.

That sounds like a good explanation ,and I would be very happy if it is only search instability that causes the problem If those occasional differences differences I see towards the end of the pv are due to instability, they are not that important to ignore atleast if all we need is a PV. TSCP's author dulely mentions that the triangular-pv array method is from Levy and Newborn's book. I would have liked to read about it there.

Code: Select all

/* a "triangular" PV array; for a good explanation of why a triangular
   array is needed, see "How Computers Play Chess" by Levy and Newborn. */
move pv[MAX_PLY][MAX_PLY];
int pv_length[MAX_PLY];
BOOL follow_pv;

[Gerd Isenberg]

I see no way to replace a stack of PVs by a stack of single moves even in PVS. How do TT-probes interact with your experiments? I mean a lot of programs have abandoned the pv-array and receive the PV from TT anyway.

I am aware of those facts which is why i am cautious to make any definitive statement. I mean we have been using pv[N][N] for long so there must be some exceptions. What I want to know are how that happens exactly, even though in the end we would be still be using pv[N][N]. You can say I am playing the devil's advocate here, but so far no one seems to give adequate explanation for my satisfaction. Infact originally the though was that negascout would barely make a difference in that regard. For TSCP pv[N] seems to be as good as the pv[N][N] so far from practical point of view but I do get differences using it in scorpio even in the first move. So take a shot at explaining the situation, as i am sure there is a reason why pv[N][N] is used.

Ahh, sorry, I was not aware TCSP is that simple and has no TT
Hmm, only PV-nodes are relevant, so the left most branch produces a pv in pv[n], and if all nodes behave as expected in a minimal PVS tree, nothing changes. If a scout node at ply i needs a re-search it overwrites and corrupts the pv[n] array from that index i. However, it may propagate as new pv to the root. Your result implies, that whenever a re-search is necessary, it becomes a new PV at the root. Have you tried other positions?

[hgm]

I don't see how a basic minimax search as TSCP uses could create any instability. So with PVS you should always be OK, as you start destroying the old PV only when you are 100% sure it will be replaced.

[Gerd Isenberg]

I don't see how a basic minimax search as TSCP uses could create any instability. So with PVS you should always be OK, as you start destroying the old PV only when you are 100% sure it will be replaced.

Yep, if I think about it, you are perfectly right. Thanks to you and Daniel for the PVS lesson

[Don]

Is it really necessary to have a full pv[N][N] array (i.e pv[N] at each ply) to collect PV using triangular method ? I think that pv[N] may be enough. For alpha-beta search with open window, updating alpha does not necessarily mean the move will be part of the final PV. That is the reason why pv[N][N] is required for alpha-beta but for nega-scout search where all non-pv nodes have a zero window, every EXACT update should be part of the pv, hence pv[N] will be enough. Why I need this is not just for pv, but for updating bigger data structures such as the whole move list along with the pv. With the triangular approach, storing [N][N][NMOVES] is just too much compared to [N][NMOVES]. My first test seems to indicate that pv[N] gets correct pvs most of the time but I do get different pvs from the one collected with pv[N][N]. I forgot about this basic stuff so a reminder is appreciated.

If you use PVS search and distinguish between PV and non PV nodes you only need to worry about PV nodes for collecting a PV.

It is easy to implement a principal variation if you think recursively. I do it with copies. In C I simply pass a pointer to an array of moves, i.e.

mv_t pv[64];


search( .... pv);

At the beginning make the first move a null move (terminator) in case you return from the search without a pv. When you do recusive searches pass a new array to the child and when it returns, if it's the best move, then set pv[0] to be the new move and pv[1] and beyond are copied from the pv of the child call.

The number of PV nodes is so small that the copying is cheap - there should be no noticable overhead.

Don

[Tom Likens]

TSCP's author dulely mentions that the triangular-pv array method is from Levy and Newborn's book. I would have liked to read about it there.

Code: Select all

/* a "triangular" PV array; for a good explanation of why a triangular
   array is needed, see "How Computers Play Chess" by Levy and Newborn. */
move pv[MAX_PLY][MAX_PLY];
int pv_length[MAX_PLY];
BOOL follow_pv;

Daniel,

You can still order it from Amazon. My webpage has the link:

http://webpages.charter.net/tlikens/boo ... play_chess

regards,
--tom