How to collect PV?

[Joerg Oster]

https://web.archive.org/web/20040620092 ... ing/pv.htm
An alternative data representation of triangular array idea.
Disadvantages:
- Harder to debug.
- Spreads code snippets in several places of the most complex chess code: in the body of search function;
- Needs more stack memory (important only if code portability is an issue);
- Less efficient in garbage collecting languages (minor issue);

I tried this first, because it seemed to be easier, and it does correctly print the first few moves of the pv but it will sometimes include illegal moves. I must've written a bug somewhere, but I'm not quite sure how to debug it. It seems that the triangular table would be potentially more efficient anyway, at least in regard to stack memory usage ¯\_(ツ)_/¯

If anyone cares to take a quick look at my implementation attempt, it's here: https://github.com/benthevining/BenBot/ ... Search.cpp

I get output such as this from fastchess when running an SPRT:

Code: Select all

Started game 9 of 100 (Refactor vs Baseline)
Warning; Illegal pv move h6h5 from Refactor
Info; info depth 3 score mate -2 time 6 hashfull 0 nodes 3714 nps 619000 tbhits 0 pv b6b1 e4b1 h5h4 c7h7 h6h5
Position; startpos
Moves; d2d4 d7d6 c2c4 e7e5 d4d5 f7f5 e2e4 f5e4 b1c3 g8f6 g1e2 c8f5 e2g3 f5g6 c1g5 b8d7 d1a4 e8f7 g3e4 f7g8 f1d3 g6e4 c3e4 d7b6 g5f6 b6a4 f6d8 a4b2 d3f1 a8d8 a1b1 b2c4 f1c4 d8b8 c4a6 b7b6 b1c1 c7c5 d5c6 d6d5 c6c7 b8e8 c7c8q e8c8 c1c8 h7h6 e4c3 d5d4 c3d5 g8f7 a6c4 b6b5 c4b3 f7g6 e1g1 g6h7 f1e1 f8d6 b3c2 g7g6 c2g6 h7g7 g6e8 h8f8 e1c1 d4d3 c1c3 e5e4 e8b5 d3d2 d5e3 d6h2 g1h2 f8f2 b5c6 f2f4 h2g1 d2d1q e3d1 a7a6 d1e3 h6h5 c3c4 f4f6 c6e4 f6b6 c4c7 g7h6 c8g8 

Make sure, you always clear the pv line when entering a new node.
In the moves loop, when you get a new best move, clear the pv for this ply level, add this new best move, and append the child pv.
If you distinguish between PV nodes and NonPV nodes, you can limit this to PV nodes only.

Maybe this https://github.com/joergoster/Stockfish ... e24fe8e0e9 is of some help?!

[hgm]

In my engines I use a separate stack for the PV, which basically packs the used part of each row of the triangular array in a linear array. This can be done because rows never change unless all later rows (except the one you copy) have become invalid and can be discarded.

I wanted to implement the same but it was difficult and dismissed the idea. I enjoy such kind of clever optimisations.

The code is actually very simple:

Code: Select all

MOVE pv[10000], *pvSP = pv; // global declaration of PV storage as stack

Search()
{
  MOVE *startPV = pvSP; // allocate space for new PV at top of PV stack
  *pvSP++ = 0; // initialize empty PV
  ...
  if(score > alpha) {
    if(score >= beta) goto cutoff;
    // move scores between alpha and beta, and thus becomes new PV
    MOVE *p = startPV;
    *p++ = move; // starts with move we just searched
    while((*p++ = *pvSP++)) {} // copy daughter PV behind it
    pvSP = p; // new top of PV stack
  }
  ...
  pvSP = startPV; // mak pvSP point to the returned PV
}

[Aleks Peshkov]

In my engines I use a separate stack for the PV, which basically packs the used part of each row of the triangular array in a linear array. This can be done because rows never change unless all later rows (except the one you copy) have become invalid and can be discarded.

I wanted to implement the same but it was difficult and dismissed the idea. I enjoy such kind of clever optimisations.

The code is actually very simple:

Code: Select all

MOVE pv[10000], *pvSP = pv; // global declaration of PV storage as stack

Search()
{
  MOVE *startPV = pvSP; // allocate space for new PV at top of PV stack
  *pvSP++ = 0; // initialize empty PV
  ...
  if(score > alpha) {
    if(score >= beta) goto cutoff;
    // move scores between alpha and beta, and thus becomes new PV
    MOVE *p = startPV;
    *p++ = move; // starts with move we just searched
    while((*p++ = *pvSP++)) {} // copy daughter PV behind it
    pvSP = p; // new top of PV stack
  }
  ...
  pvSP = startPV; // mak pvSP point to the returned PV
}

It seems the most cache friendly implementation. Definitely needed mention in the Wiki.

[abulmo2]

In my engines I use a separate stack for the PV, which basically packs the used part of each row of the triangular array in a linear array. This can be done because rows never change unless all later rows (except the one you copy) have become invalid and can be discarded.

I wanted to implement the same but it was difficult and dismissed the idea. I enjoy such kind of clever optimisations.

The code is actually very simple:

Code: Select all

MOVE pv[10000], *pvSP = pv; // global declaration of PV storage as stack

Search()
{
  MOVE *startPV = pvSP; // allocate space for new PV at top of PV stack
  *pvSP++ = 0; // initialize empty PV
  ...
  if(score > alpha) {
    if(score >= beta) goto cutoff;
    // move scores between alpha and beta, and thus becomes new PV
    MOVE *p = startPV;
    *p++ = move; // starts with move we just searched
    while((*p++ = *pvSP++)) {} // copy daughter PV behind it
    pvSP = p; // new top of PV stack
  }
  ...
  pvSP = startPV; // mak pvSP point to the returned PV
}

I wonder if this code is a troll... with at least 5 anti-patterns in 11 lines of code.

https://wiki.c2.com/?GlobalVariablesConsideredHarmful
https://en.wikipedia.org/wiki/Magic_num ... ogramming)
https://wiki.c2.com/?GotoConsideredHarmful
https://critical.eschertech.com/2010/03 ... rithmetic/
]https://www.codingrules.dev/rule-2

[hgm]

From one of your references: "I don't think there's anything wrong with using goto to do, for example, a double break.".

And, like it or not, array indexing is pointer arithmetic. a[ i] is defined as *(a+i).

[tttony]

I do it like this in C:

Code: Select all

void update_pv(move_t *dst, move_t *src, move_t move){
    *dst++ = move;
    while ((*dst++ = *src++));
}
score_t search(board_s *board, score_t alpha, score_t beta, depth_t depth, bool in_check, move_t *pv){
   // .....
   *pv = 0;
   move_t new_pv[64];
   score_t score;
   // .....
   while (move == next_move(board)) {
       bool gives_check = move_gives_check(move);
       score = -search(board, alpha, -beta, -alpha, gives_check, new_pv){
       if (score > alpha) {
           update_pv(pv, new_pv, move);
       }
       // .....
   }
   // .....
}

In start search:

Code: Select all

move_t best_move = NO_MOVE;
move_t pv[64];
pv[0] = NO_MOVE;

for (depth_t depth = 1; depth <= params->depth_limit; ++depth) {
    score = search(board, params, -INF, +INF, depth, in_check, pv);
    uci_print_info(params, depth, score, pv);
    best_move = pv[0];
}

[Aleks Peshkov]

I do it like this in C:

Code: Select all

   // .....
   move_t new_pv[64];
   // .....

This is a reason why HGM's solution better than Bruce Moreland's. When you start search each ply deeper, you create a hole of unused memory in stack (or in heap for less effecient languages).

[abulmo2]

From one of your references: "I don't think there's anything wrong with using goto to do, for example, a double break.".

And, like it or not, array indexing is pointer arithmetic. a[ i] is defined as *(a+i).

a[ i] is a better abstraction than *(a + i), ie easier to read or understand than *(a + i)
All the controversial usage of the C language you wrote can be summarized as a lack of abstraction.

Here is, IMHO, a version of your code with better abstraction:

Code: Select all

#define PLY_MAX 128 

// a Move
typedef unsigned short Move;

// struct Line: a succession of moves.
typedef struct Line {
  Move move[PLY_MAX];
  int n;
} Line;

// set an empty line 
void line_clear(Line *line) {
  line->n = 0;
}

// add a move to the line
void line_push(Line *line, const Move move) {
	assert(line->n < PLY_MAX); // check for array bound overflow 
	line->move[line->n++] = move;
}

// set a line by appending the next line to the current move
void line_set(Line *destination, const Move move, const Line* source) {
  line_clear(destination);
  line_push(destination, move);
  for (int i = 0; i < source->n; ++i) {
    line_push(destination, source->move[i]);
  }
}

// struct search
typedef struct Search {
  ....
  Line pv[PLY_MAX];
  int ply; // distance from the root
  ...
} Search;

void alphabeta(Search *search, const int alpha, const int beta, const  int depth) {
  Line *pv = search->pv + search->ply;
  ...
  line_clear(pv);
  ...
  if(score > alpha) {
    if(score >= beta) return score;
    // move scores between alpha and beta, and thus becomes new PV
   line_set(pv, move, pv + 1);
  }
  
  // no need to reset the pv back to its initial location

Maybe it's just of matter of taste, but better abstractions make the code easier to read & understand; and so to make it better and stronger.
And as modern compilers will inlined everything the final code will be as fast in both cases.

[Aleks Peshkov]

Here is, IMHO, a version of your code with better abstraction:

Original code was working sample with ALL important details to refactor it to any abstraction. You suggested a pile of not working lines of code.

[hgm]

Here is, IMHO, a version of your code with better abstraction:

Code: Select all

#define PLY_MAX 128 

// a Move
typedef unsigned short Move;

// struct Line: a succession of moves.
typedef struct Line {
  Move move[PLY_MAX];
  int n;
} Line;

// set an empty line 
void line_clear(Line *line) {
  line->n = 0;
}

// add a move to the line
void line_push(Line *line, const Move move) {
	assert(line->n < PLY_MAX); // check for array bound overflow 
	line->move[line->n++] = move;
}

// set a line by appending the next line to the current move
void line_set(Line *destination, const Move move, const Line* source) {
  line_clear(destination);
  line_push(destination, move);
  for (int i = 0; i < source->n; ++i) {
    line_push(destination, source->move[i]);
  }
}

// struct search
typedef struct Search {
  ....
  Line pv[PLY_MAX];
  int ply; // distance from the root
  ...
} Search;

void alphabeta(Search *search, const int alpha, const int beta, const  int depth) {
  Line *pv = search->pv + search->ply;
  ...
  line_clear(pv);
  ...
  if(score > alpha) {
    if(score >= beta) return score;
    // move scores between alpha and beta, and thus becomes new PV
   line_set(pv, move, pv + 1);
  }
  
  // no need to reset the pv back to its initial location

Maybe it's just of matter of taste, but better abstractions make the code easier to read & understand; and so to make it better and stronger.
And as modern compilers will inlined everything the final code will be as fast in both cases.

The problem is of course that this code is no good at all; it doesn't do what should be done. When a real engine gets a beta cutoff, it cannot simply return the bestScore (or beta). For one, a beta cutoff doesn't terminate the current node; it oinly terminates the current IID iteration in the node. If this was not the final iteration of that IID, you would have to continue with the next one. Even in the last iteration, some cleanup is usually necessary, such as removing the move list from the move stack. You would also want to store the result (score and move) in the hash table, which would normally be done after the loop over moves completes.

Of course you could be tempted to replace the 'return' by a 'break', but this would break only out of a single level of nested loops, not out of all of them. And the 'loop over moves' could easily be nested. (E.g. first looping over generation stages, and within each stage over the moves in that stage. Or, in the case of micro-Max, first over from-squares, then over directions, and finally over distances.

JavaScript has a nice solution for this, b.t.w. (allowing you to attach a name to a loop body, and using that name in a break statement to break out of that and all loops inside that body). But not C.