triangular pv

[Daniel Shawul]

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.

[hgm]

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.

Code: Select all

MOVE pv[], pvEnd;

Search()
{
  int myPV = pvEnd;
  *pvEnd++ = 0; // initialize empty PV by writing sentinel

  ...

    if(score > alpha) { // alpha-beta stuff
      ...
      if(score >= beta) goto cutoff;
      // We have new PV move; backup PV
     MOVE *p = pvEnd; // points to 'returned' PV that is in de-allocated space above stack top
     pvEnd = myPV+1;  // leave room to prepend own move
     while(*pvEnd++ = *p++); // leaves pvEnd directly after new own PV
     *myPV = move;    // prefix with current move
    }

  ...

  pvEnd = myPV; // deallocate own PV
  return bestScore;
}

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

[hgm]

Err.. That should have been

Code: Select all

MOVE pv[100000];
MOVE *endPV = pv;

...

Note that Fairy-Max uses vanilla alpha-beta, not PVS. I don't think this makes much difference, however. Perhaps in the number of times you have to execute it, but not in the code.

Null-window nodes would never trigger the code that copies the daughter PV, so their PV would remain the empty one they initialize at node entry. That doesn't take up much space on the stack. But when you are in a re-search of a move failing high in a PV node you will have a well-filled PV in every node along the currently active branch. Of course these get progressively shorted when you approach the leaves. They are all maximally packed on the pv[] stack.

[Sven]

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.

I don't see how a one-dimensional array of moves, i.e. pv[N], should be sufficient with any common search strategy, regardless whether you use "open window", "nega-scout" or anything else. What these all have in common is that at some node X deep down the tree you obtain a PV that is local to X but only gets copied to the parent of X if the parent move leading to X becomes the new best move (and is within alpha/beta bounds). Each node on the current move path has its own PV, and you need to maintain them all at the same time since you always need both the current node's PV and the one of its parent, otherwise you can't update the PV correctly when finding a new best move at a node.

What I do is a bit more flexible, and perhaps easier to use: I have a "PV" data type (in my case a C++ class but it can be a simple struct together with some small functions as well) holding an array of moves (fixed size). The array is "zero-terminated" like a character string using a "null" move as terminator. Each search function has a "PV" result parameter that has to be filled. It is cleared on entering a node by setting "pv[0] = NULL_MOVE". Within the move loop each subtree search call gets a "localPV" argument as well which it has to fill (here you can see the analogy to the "triangular" approach: one PV per depth). Whenever backing up after returning from a subtree delivers a new best move with a value within alpha/beta, the node's PV is changed into "bestMove concatenated with localPV". Like in the "triangular" case, array dimensions must be checked each time (dynamic memory allocation would be horrible, of course).

Sven

[Daniel Shawul]

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.

Code: Select all

ply      nodes  score  pv
  1         21     48  d2d4
 d2d4
  2         84      0  d2d4 d7d5
 d2d4 g8f6
  3        800     35  d2d4 d7d5 b1c3
 d2d4 g8f6 d2d4
  4       4219      5  e2e4 d7d5 f1b5 c8d7 b5d3
 e2e4 d7d5 c2c3 c8h3 g1h3
  5      22461     35  e2e4 e7e5 d2d4 d7d5 g1f3
 e2e4 e7e5 d2d4 c8h3 g1h3
  6     138420     13  e2e4 e7e5 d2d4 e5d4 d1d4 g8f6
 e2e4 e7e5 b2b3 c8h3 g1h3 c8h3
  7    1174526     30  e2e4 d7d5 e4d5 d8d5 d2d4 d5e4 g1e2 e7e5
 e2e4 d7d5 b2b3 f6e4 d2d3 e4f2 e1f2 d5e4
  8    7070387     18  e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 d2d4 d7d6
 e2e4 e7e5 b2b3 c6a5 a1a5 c6a5 a1a5 c8h3

With negascout they are the same in every case

Code: Select all

ply      nodes  score  pv
  1         27     48  d2d4
 d2d4
  2        134      0  d2d4 d7d5
 d2d4 d7d5
  3       1374     35  d2d4 d7d5 b1c3
 d2d4 d7d5 b1c3
  4      10602      5  e2e4 d7d5 f1b5 c8d7 b5d3
 e2e4 d7d5 f1b5 c8d7 b5d3
  5      74547     35  e2e4 e7e5 b1c3 b8c6 g1f3
 e2e4 e7e5 b1c3 b8c6 g1f3
  6     628009     13  e2e4 e7e5 d2d4 e5d4 d1d4 g8f6
 e2e4 e7e5 d2d4 e5d4 d1d4 g8f6
  7    4458081     30  e2e4 d7d5 e4d5 d8d5 b1c3 d5e6 g1e2 g8f6
 e2e4 d7d5 e4d5 d8d5 b1c3 d5e6 g1e2 g8f6
  8   39738134     18  e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 d2d4 d7d6
 e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 d2d4 d7d6
Computer's move: e2e4

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.

[Daniel Shawul]

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.

[bob]

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

[Daniel Shawul]

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

Code: Select all

tscp> sd 6
tscp> on
ply      nodes  score  pv
  1         26     48  d2d4[tri]
  1         26     48  d2d4[pvn]
  2         90      0  d2d4 d7d5[tri]
  2         90      0  d2d4 d7d5[pvn]
  3        685     35  d2d4 d7d5 b1c3[tri]
  3        685     35  d2d4 d7d5 b1c3[pvn]
  4       4031      5  e2e4 d7d5 f1b5 c8d7 b5d3[tri]
  4       4031      5  e2e4 d7d5 f1b5 c8d7 b5d3[pvn]
  5      22113     35  e2e4 b8c6 b1c3 e7e5 g1f3[tri]
  5      22113     35  e2e4 b8c6 b1c3 e7e5 g1f3[pvn]
  6     100149     13  e2e4 b8c6 d2d4 d7d5 e4d5 d8d5[tri]
  6     100149     13  e2e4 b8c6 d2d4 d7d5 e4d5 d8d5[pvn]
Computer's move: e2e4
tscp> on
ply      nodes  score  pv
  1         26      0  d7d5[tri]
  1         26      0  d7d5[pvn]
  2        126    -35  d7d5 b1c3[tri]
  2        126    -35  d7d5 b1c3[pvn]
  3       1211     -5  d7d5 f1b5 c8d7 b5d3[tri]
  3       1211     -5  d7d5 f1b5 c8d7 b5d3[pvn]
  4       8013    -35  e7e5 b1c3 b8c6 g1f3[tri]
  4       8013    -35  e7e5 b1c3 b8c6 g1f3[pvn]
  5      31853    -13  e7e5 d2d4 e5d4 d1d4 g8f6[tri]
  5      31853    -13  e7e5 d2d4 e5d4 d1d4 g8f6[pvn]
  6     244729    -30  d7d5 e4d5 d8d5 b1c3 d5e6 g1e2 g8f6[tri]
  6     244729    -30  d7d5 e4d5 d8d5 b1c3 d5e6 g1e2 g8f6[pvn]
Computer's move: d7d5
tscp> on
ply      nodes  score  pv
  1         53     35  b1c3[tri]
  1         53     35  b1c3[pvn]
  2        480      5  f1b5 c8d7 b5d3[tri]
  2        480      5  f1b5 c8d7 b5d3[pvn]
  3       2340     48  e4d5 d8d5 d2d4[tri]
  3       2340     48  e4d5 d8d5 d2d4[pvn]
  4       9619     35  e4d5 d8d5 b1c3 d5c6[tri]
  4       9619     35  e4d5 d8d5 b1c3 d5c6[pvn]
  5      60934     30  e4d5 d8d5 b1c3 d5e6 g1e2 g8f6[tri]
  5      60934     30  e4d5 d8d5 b1c3 d5e6 g1e2 g8f6[pvn]
  6     309791     40  e4d5 d8d5 b1c3 d5a5 f1b5 c8d7 b5d3[tri]
  6     309791     40  e4d5 d8d5 b1c3 d5a5 f1b5 c8d7 b5d3[pvn]
Computer's move: e4d5
tscp> on
ply      nodes  score  pv
  1         29      0  d8d5[tri]
  1         29      0  d8d5[pvn]
  2        262    -48  d8d5 d2d4[tri]
  2        262    -48  d8d5 d2d4[pvn]
  3       1597    -35  d8d5 b1c3 d5c6[tri]
  3       1597    -35  d8d5 b1c3 d5c6[pvn]
  4       7710    -30  d8d5 b1c3 d5e6 g1e2 g8f6[tri]
  4       7710    -30  d8d5 b1c3 d5e6 g1e2 g8f6[pvn]
  5      41577    -40  d8d5 b1c3 d5a5 f1b5 c8d7 b5c4[tri]
  5      41577    -40  d8d5 b1c3 d5a5 f1b5 c8d7 b5c4[pvn]
  6     349319    -55  g8f6 f1b5 c8d7 b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[tri]
  6     349319    -55  g8f6 f1b5 c8d7 b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[pvn]
Computer's move: g8f6
tscp> on
ply      nodes  score  pv
  1         75     87  f1b5[tri]
  1         75     87  f1b5[pvn]
  2        291     72  f1b5 c8d7 b5c4[tri]
  2        291     72  f1b5 c8d7 b5c4[pvn]
  3       1826     65  f1b5 c8d7 b5d7 d8d7 c2c4[tri]
  3       1826     65  f1b5 c8d7 b5d7 d8d7 c2c4[pvn]
  4       9003     70  f1b5 c8d7 b5c4 e7e6 b1c3 e6d5 c3d5[tri]
  4       9003     70  f1b5 c8d7 b5c4 e7e6 b1c3 e6d5 c3d5[pvn]
  5      51083     55  f1b5 c8d7 b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[tri]
  5      51083     55  f1b5 c8d7 b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[pvn]
  6     283284     65  f1b5 c8d7 b5c4 d7f5 b1c3 c7c6 d5c6 b8c6[tri]
  6     283284     65  f1b5 c8d7 b5c4 d7f5 b1c3 c7c6 d5c6 b8c6[pvn]
Computer's move: f1b5
tscp> on
ply      nodes  score  pv
  1        121    -72  c8d7 b5c4[tri]
  1        121    -72  c8d7 b5c4[pvn]
  2        662    -65  c8d7 b5d7 d8d7 c2c4[tri]
  2        662    -65  c8d7 b5d7 d8d7 c2c4[pvn]
  3       3280    -70  c8d7 b5c4 e7e6 b1c3 e6d5 c3d5[tri]
  3       3280    -70  c8d7 b5c4 e7e6 b1c3 e6d5 c3d5[pvn]
  4      13362    -55  c8d7 b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[tri]
  4      13362    -55  c8d7 b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[pvn]
  5      78583    -65  c8d7 b5c4 d7f5 b1c3 c7c6 d5c6 b8c6[tri]
  5      78583    -65  c8d7 b5c4 d7f5 b1c3 c7c6 d5c6 b8c6[pvn]
  6     406279    -57  c8d7 b5c4 e7e5 d2d4 e5d4 d1d4 f8d6[tri]
  6     406279    -57  c8d7 b5c4 e7e5 d2d4 e5d4 d1d4 f8d6[pvn]
Computer's move: c8d7
tscp> on
ply      nodes  score  pv
  1         63     72  b5c4[tri]
  1         63     72  b5c4[pvn]
  2        443     65  b5d7 d8d7 c2c4[tri]
  2        443     65  b5d7 d8d7 c2c4[pvn]
  3       2345     70  b5c4 e7e6 b1c3 e6d5 c3d5[tri]
  3       2345     70  b5c4 e7e6 b1c3 e6d5 c3d5[pvn]
  4       8557     55  b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[tri]
  4       8557     55  b5c4 e7e5 d5e6 d7e6 c4e6 f7e6[pvn]
  5      51405     65  b5c4 d7f5 b1c3 c7c6 d5c6 b8c6[tri]
  5      51405     65  b5c4 d7f5 b1c3 c7c6 d5c6 b8c6[pvn]
  6     253838     57  b5c4 e7e5 d2d4 e5d4 d1d4 f8d6[tri]
  6     253838     57  b5c4 e7e5 d2d4 e5d4 d1d4 f8d6[pvn]
Computer's move: b5c4
tscp> on
ply      nodes  score  pv
  1         93    -55  e7e6 d5e6 d7e6 c4e6 f7e6[tri]
  1         93    -55  e7e6 d5e6 d7e6 c4e6 f7e6[pvn]
  2        434    -70  e7e6 b1c3 e6d5 c3d5[tri]
  2        434    -70  e7e6 b1c3 e6d5 c3d5[pvn]
  3       2406    -55  e7e5 d5e6 d7e6 c4e6 f7e6[tri]
  3       2406    -55  e7e5 d5e6 d7e6 c4e6 f7e6[pvn]
  4      17599    -65  d7f5 b1c3 c7c6 d5c6 b8c6[tri]
  4      17599    -65  d7f5 b1c3 c7c6 d5c6 b8c6[pvn]
  5     101479    -57  e7e5 d2d4 e5d4 d1d4 f8d6[tri]
  5     101479    -57  e7e5 d2d4 e5d4 d1d4 f8d6[pvn]
  6     461920    -59  b7b5 c4b3 a7a5 a2a3 a5a4 b3a2[tri]
  6     461920    -59  b7b5 c4b3 a7a5 a2a3 a5a4 b3a2[pvn]
Computer's move: b7b5
tscp> on
ply      nodes  score  pv
  1         87     79  c4b3[tri]
  1         87     79  c4b3[pvn]
  2        226     59  c4b3 b8a6[tri]
  2        226     59  c4b3 b8a6[pvn]
  3       1596     79  c4b3 e7e5 d2d4[tri]
  3       1596     79  c4b3 e7e5 d2d4[pvn]
  4       5477     67  c4b3 e7e5 d5e6 f7e6[tri]
  4       5477     67  c4b3 e7e5 d5e6 f7e6[pvn]
  5      40639     59  c4b3 a7a5 a2a3 a5a4 b3a2[tri]
  5      40639     59  c4b3 a7a5 a2a3 a5a4 b3a2[pvn]
  6     171221     39  c4b3 a7a5 a2a3 a5a4 b3a2 b8a6[tri]
  6     171221     39  c4b3 a7a5 a2a3 a5a4 b3a2 b8a6[pvn]
Computer's move: c4b3
tscp>

[Gerd Isenberg]

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.

[Daniel Shawul]

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.