It is not as bad as you think. It must fail to get correct pvs sometimes. With the regular alpha-beta it fails much more frequently. Here is tscp triangular pv modified with alpha beta first and then negascout. The two pvs are for pv[n][n] and pv[n] resp.
With alpha-beta the two pvs are almost always different.
Note that the best move at the root changed from d2d4 to e2e4 which still worked. However I agree there must be cases where it fails to get the correct pv when doing researches.
What is PV[n][m] in your terminology? Normally it would be a single move, not an entire PV. PV[n] is a PV.
In Fairy-Max I don't even use a tri-diagonal array. Just a stack of moves in a 1d array. Each new node puts its PV on top of the stack. It de-allocates the space when returning (by setting the stack pointer back to the start of its own PV), but the data stays there, accessible for the parent, to copy it back to to its own PV.
N is the number of plies (MAXPLY). Since I use iterative search , i have to declare the pv as pv[MAXPLY][MAXPLY] and for saving move list it would be pv[MAXPLY][MAXPLY][NMOVES] which i thought is too much.
Precisely the same method could be used for storing not just the move of a (potential) PV node, but any information about it. You could even store the entire move list in this node on such a PV stack, so that on a re-visit you can benefit from the move ordering in the previous iteration (e.g. sorted by node count).
Yes that is what i wanted to try out first. Move sorting based on node counts can also be used elsewhere (not only on PVs) where you use IID. I use IID for CUT nodes too so once the IID search is finished the move list would be immediately available with its node counts. We have a best move from IID in any case so the benefit might not be much, but sorting the moves may help in less important moves LMRed more.
Daniel Shawul wrote: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.
You are at depth 7, and a search produces a backed-up score. But at depth 5, after searching everything, that backed-up score did not stand. But you overwrote the PV.
The PV has to be backed up just like the score is backed up... And unless a score is backed up to the root, the root PV should not be changed...
I have played 5 games with tscp now and it seems that the pv[n] and pv[n][n] method give the same result. I do get different results when using it to scorpio though. For the curious the tscp code is here https://dl.dropbox.com/u/55295461/tscp-negascout.zip
You can turn on alpha-beta inside search() and you would see mismatche indicated by [****] immediately. But after five games i can't seem to get a mismatch with negascout. PV[n] may be correct under specific circumstances with negascout search. Howver scorpio does get different pvs so there must be exceptions. Anyway it seems to be a good alternative to getting some kind of pv without using memcpy(), even though that doesn't matter much.
Test run
Daniel Shawul wrote:I have played 5 games with tscp now and it seems that the pv[n] and pv[n][n] method give the same result. I do get different results when using it to scorpio though. For the curious the tscp code is here https://dl.dropbox.com/u/55295461/tscp-negascout.zip
You can turn on alpha-beta inside search() and you would see mismatche indicated by [****] immediately. But after five games i can't seem to get a mismatch with negascout. PV[n] may be correct under specific circumstances with negascout search. Howver scorpio does get different pvs so there must be exceptions. Anyway it seems to be a good alternative to getting some kind of pv without using memcpy(), even though that doesn't matter much.
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 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.
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.
hgm wrote: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.
/* 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;
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?
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.
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.
