A very quick clarification question on sorting PV moves

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

A very quick clarification question on sorting PV moves

Post by maksimKorzh » Sun Sep 13, 2020 7:10 pm

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:

and PV line e2a6 e6d5 c3d5 b6d5 e4d5


I assume that we need to have this exact position:

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!
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

Sven
Posts: 3877
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: A very quick clarification question on sorting PV moves

Post by Sven » Sun Sep 13, 2020 10:03 pm

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);
        }
    }
}
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: A very quick clarification question on sorting PV moves

Post by maksimKorzh » Mon Sep 14, 2020 9:41 am

Sven wrote:
Sun Sep 13, 2020 10:03 pm
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.
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

User avatar
hgm
Posts: 24730
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: A very quick clarification question on sorting PV moves

Post by hgm » Mon Sep 14, 2020 5:59 pm

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
Posts: 3877
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: A very quick clarification question on sorting PV moves

Post by Sven » Mon Sep 14, 2020 9:13 pm

maksimKorzh wrote:
Mon Sep 14, 2020 9:41 am
[...]
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: A very quick clarification question on sorting PV moves

Post by maksimKorzh » Tue Sep 15, 2020 1:43 pm

Sven wrote:
Mon Sep 14, 2020 9:13 pm
maksimKorzh wrote:
Mon Sep 14, 2020 9:41 am
[...]
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.
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

Post Reply