A very quick clarification question on sorting PV moves

[maksimKorzh]

Hi guys

I'm trying to clarify the the exact conditions to score PV moves.

So my current understanding is:
If we have a PV move stored at CURRENT ply in PV table (assuming triangular PV)
and the move that has just been done on chess board EQUALS to the PREVIOUS ply's move of the PV table,
e.g assuming position:
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
and PV line e2a6 e6d5 c3d5 b6d5 e4d5


I assume that we need to have this exact position:
[d]r3k2r/p1ppqpb1/Bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPB1PPP/R3K2R b KQkq - 0 1
to assing highest score to move e6d5 hence search it first in the next iteration of iterative deepeneing.

Is that correct?
If so what kind of techniques are available to MATCH the exact position to make sure WE ARE actually FOLLOWING PV?

I saw in VICE when move is stored into pv corresponding position's hash key is stored into pv/hash table and later retrieved by hash key.
On the other hand TSCP uses global variable follow_pv seemingly for the same purpose (I still can't figure out how it works)

Now what I'm trying to do is to check if CURRENT board position actually HAS piece extracted from the previous PV table ply's at square extracted from previous ply's move target square:

Code: Select all

   if (
        get_bit( bitboards[get_move_piece(pv_table[0][ply - 1])], get_move_target(pv_table[0][ply - 1])) 
       )
    {    
        // in this case we're looking if CURRENT PV move is available in the move list
        // and if so then order it highest
        if (pv_table[0][ply] == move)
        {
            printf("curr PV "); print_move(pv_table[0][ply]); printf(" ply %d\n", ply);
            printf("prev PV "); print_move(pv_table[0][ply-1]); printf(" ply %d\n", ply);
            print_board();
            //getchar();
            return 20000;
        }
    }

Even though it works and saves nodes still I have a feeling that this approach is wrong at least due to the reason it would fail in case of promotions because on promotions piece is changing.

Last question:
How to answer the question WHETHER SEARCH IS FOLLOWING PV or not without involving position keys?
Is that possible?

THANKS IN ADVANCE!

[Sven]

It is as simple as that:
1) A node belongs to the root PV (i.e., follows the root PV) if its parent node belongs to it and the move leading to the current node is the parent's PV move.
2) The root node always belongs to the root PV.

In an older private engine I developed years ago I implemented that "node follows PV" approach. But today I think it is useless once you are using a TT. The purpose of "node follows PV" can only be to try the PV of iteration N as first variation in iteration N+1. A lot of effort is put into ordering of very few nodes, actually N-1 nodes for a depth N search - all other nodes do not follow the root PV. In contrast to that, using the TT for move ordering already solves it for you.

Now some words on "triangular PV". I think it is very important to see this two-dimensional array as one of at least two possible implementations that serve the same abstract goal: to store the PV of each node from the root to the current node. Let me explain why I think this is true.

a) "Triangular" approach
In my view, a clean way of using the triangular approach follows this scheme (example for a maximum search depth of 6, "X" is a move and "-" an entry that is never used):

Code: Select all

node at depth 0: X X X X X X
node at depth 1: - X X X X X
node at depth 2: - - X X X X
node at depth 3: - - - X X X
node at depth 4: - - - - X X
node at depth 5: - - - - - X

So the root PV is stored in pv[0][0] ... pv[0][5]. Its length can be up to 6 plies.
The PV of the node at depth 3 is stored in pv[3][3] ... pv[3][5]. Its length can be up to 3 plies.

When entering a new node you clear its PV, i.e. at depth 3 you set pv[3][3] to "null" which serves as an end-of-variation indicator like a null byte in a string.

If you have found a PV at depth 3 (and stored it) but then search another move M which turns out to be even better, you overwrite pv[3][3] ... pv[3][5] as follows: you replace pv[3][3] by M and overwrite pv[3][4] ... pv[3][5] with the PV of M's subtree which has been stored in pv[4][4] ... pv[4][5].

Slightly less than half of the entries of the two-dimensional array are unused.

b) "PV parameter" approach
You store the PV of each node in a PV structure which is allocated on the stack right before search() is called, and passed as "out" parameter (through a non-const pointer or C++ reference) to search(). You perfom the same operations as with "triangular", they just look slightly different. The storage overhead is exactly the same for both approaches. The "PV parameter" approach might be a tiny bit slower than "triangular" due to the additional parameter of the search function and due to also maintaining the PV size but it is less error prone, more flexible and much easier to read, and the speed penalty is not critical.

Code: Select all

struct PV {
    Move move[MAX_MOVES];
    int size;
    void clear() {
        size = 0;
    }
    void concat(Move const * m, PV const * pv) { // could also be done with C++ references: void concat(Move const & m, PV const & m)
        move[0] = *m;
        int i;
        for (i = 0; i < std::min<int>(MAX_MOVES - 1, pv->size); i++) {
            move[i+1] = pv->move[i];
        }
        size = i+1;
    }
    PV() : size(0) {}
};
int search(..., PV * pv) {
    pv->clear();
    ....
    for (all moves) {
        ...
        PV subtreePV;
        int score = -search(..., &subtreePV);
        ...
        if (move M is new PV) {
            pv->concat(M, &subtreePV);
        }
    }
}

[maksimKorzh]

It is as simple as that:
1) A node belongs to the root PV (i.e., follows the root PV) if its parent node belongs to it and the move leading to the current node is the parent's PV move.
2) The root node always belongs to the root PV.

In an older private engine I developed years ago I implemented that "node follows PV" approach. But today I think it is useless once you are using a TT. The purpose of "node follows PV" can only be to try the PV of iteration N as first variation in iteration N+1. A lot of effort is put into ordering of very few nodes, actually N-1 nodes for a depth N search - all other nodes do not follow the root PV. In contrast to that, using the TT for move ordering already solves it for you.

Now some words on "triangular PV". I think it is very important to see this two-dimensional array as one of at least two possible implementations that serve the same abstract goal: to store the PV of each node from the root to the current node. Let me explain why I think this is true.

a) "Triangular" approach
In my view, a clean way of using the triangular approach follows this scheme (example for a maximum search depth of 6, "X" is a move and "-" an entry that is never used):

Code: Select all

node at depth 0: X X X X X X
node at depth 1: - X X X X X
node at depth 2: - - X X X X
node at depth 3: - - - X X X
node at depth 4: - - - - X X
node at depth 5: - - - - - X

So the root PV is stored in pv[0][0] ... pv[0][5]. Its length can be up to 6 plies.
The PV of the node at depth 3 is stored in pv[3][3] ... pv[3][5]. Its length can be up to 3 plies.

When entering a new node you clear its PV, i.e. at depth 3 you set pv[3][3] to "null" which serves as an end-of-variation indicator like a null byte in a string.

If you have found a PV at depth 3 (and stored it) but then search another move M which turns out to be even better, you overwrite pv[3][3] ... pv[3][5] as follows: you replace pv[3][3] by M and overwrite pv[3][4] ... pv[3][5] with the PV of M's subtree which has been stored in pv[4][4] ... pv[4][5].

Slightly less than half of the entries of the two-dimensional array are unused.

b) "PV parameter" approach
You store the PV of each node in a PV structure which is allocated on the stack right before search() is called, and passed as "out" parameter (through a non-const pointer or C++ reference) to search(). You perfom the same operations as with "triangular", they just look slightly different. The storage overhead is exactly the same for both approaches. The "PV parameter" approach might be a tiny bit slower than "triangular" due to the additional parameter of the search function and due to also maintaining the PV size but it is less error prone, more flexible and much easier to read, and the speed penalty is not critical.

Code: Select all

struct PV {
    Move move[MAX_MOVES];
    int size;
    void clear() {
        size = 0;
    }
    void concat(Move const * m, PV const * pv) { // could also be done with C++ references: void concat(Move const & m, PV const & m)
        move[0] = *m;
        int i;
        for (i = 0; i < std::min<int>(MAX_MOVES - 1, pv->size); i++) {
            move[i+1] = pv->move[i];
        }
        size = i+1;
    }
    PV() : size(0) {}
};
int search(..., PV * pv) {
    pv->clear();
    ....
    for (all moves) {
        ...
        PV subtreePV;
        int score = -search(..., &subtreePV);
        ...
        if (move M is new PV) {
            pv->concat(M, &subtreePV);
        }
    }
}

Thank you so much Swen.

1) A node belongs to the root PV (i.e., follows the root PV) if its parent node belongs to it and the move leading to the current node is the parent's PV move.

Exactly ensures my understanding is correct:

So my current understanding is:
If we have a PV move stored at CURRENT ply in PV table (assuming triangular PV)
and the move that has just been done on chess board EQUALS to the PREVIOUS ply's move of the PV table,

assuming that what you call parent node is what I called previous ply's move (it's literally the same right? say: e2e4 e7e5 - here if we are at e7e5 then e2e4 would be parent root node or how I call it previous ply's move) IS actually "leading to the current node" or how I call it - is the move is currently made on board.

re: explanation of how triangular PV works
- thanks. This is clear.

re: PV parameter
- cool, but triangular approach seems more straightforward to me.

[hgm]

It is like Sven says: following the PV is just a poor-mans alternative for having a TT. With a good replacement scheme the PV (or a line that is as good) should always be in the TT. You are on the PV if all nodes you did from the root followed the PV.

If you insist on following the PV you can use a Boolean global that you set to TRUE before the search, and you search the PV move at the current depth first as long as that variable is set, and clear it as soon as you return from searching a move.

[Sven]

[...]
assuming that what you call parent node is what I called previous ply's move (it's literally the same right? say: e2e4 e7e5 - here if we are at e7e5 then e2e4 would be parent root node or how I call it previous ply's move) IS actually "leading to the current node" or how I call it - is the move is currently made on board.

Terminology: The search walks through a tree consisting of nodes (positions) and edges (moves). The parent node of a given node is the node in which the previous move was made and led to the current position. The set of positions that can be reached from a given position by making one of the legal moves is the set of children (child nodes). The position from which you start the search is the root position, or root node.

[maksimKorzh]

[...]
assuming that what you call parent node is what I called previous ply's move (it's literally the same right? say: e2e4 e7e5 - here if we are at e7e5 then e2e4 would be parent root node or how I call it previous ply's move) IS actually "leading to the current node" or how I call it - is the move is currently made on board.

Terminology: The search walks through a tree consisting of nodes (positions) and edges (moves). The parent node of a given node is the node in which the previous move was made and led to the current position. The set of positions that can be reached from a given position by making one of the legal moves is the set of children (child nodes). The position from which you start the search is the root position, or root node.

Thanks for this brilliancy. DEEPLY APPRECIATE.