Howdy - I hope you're all having a wonderful day
Today is a special day - my engine has finally beaten me in a game of chess!
Anyway, I am currently working on scoring the principal variation move (which is stored in a table called pv_table) and noticed that a few other developers (such as in Code Monkey King's video) had a more complex approach to doing this than the one I propose. They (and Tom Kerrigan's TSCP) use an approach with two flags follow_pv and score_pv, but I don't understand why they are necessary. My approach simply checks whether the current move is the PV move, and if so it receives the highest score:
Principal Variation Search and Principal Variation move scoring are two distinct things.
First, a PV node is a node that has alpha > beta - 1, that is, the search window is not zero-width.
When the search is called at the root it is called with a full-width search window, making the root a PV node. PVS assumes the first move in a PV node is part of the PV, and all subsequent nodes will fail low (score less than alpha), and it detects this by setting a flag whenever a move raises alpha (since raising alpha in a zero-width search results in a fail-high). It makes the search for fail-lows as cheap as possible by calling them with a zero-width window, while searching with a full-width window if the move does not fail low for correctness. That's what the follow_pv flag is doing.
Your algorithm does not work since a move anywhere in the search tree can be the same move
as in pv_table[0][N]. You would rate too many moves too high, not just the PV.
The PV moves moveM to moveN are only valid if the moves move0 to moveM-1 are in the PV.
The PV is the best variation known so far and also the leftmost branch in the next
deeper search tree of the next iteration in an iterative deepening search scheme.
During the search you fill the triangular PV table pv_table[MAX_PLY][MAX_PLY]
and have the PV in the first row when you have finished the search in the root.
move0 in pv_table[0][0], move1 in pv_table[0][1], ..., moveN in pv_table[0][N], pv_table[0][N+1] == 0.
I assume you know how to do this.
I f you enter a new ply set pv_table[N][N] to 0 and if a move is the new best move
combine the current pv_table with the move and its successors from deeper plies.
Since you wil use, change and update this table in the next search you have at least two possibilities.
(1) Push these moves into the transposition table (hash table) and use the moves in that table first
in any position of the search. Either with extra specialised code or with the biggest move sort score.
You should do a quick consistency check if the move is possible because you do that with all moves from that table.
or
(2) After the last search iteration or before the next deeper search iteration make a global copy
of the first row of the last pv_table that contains the PV. Let's say do_pv_table[MAX_PLY].
Fill the remaining entries in this table with 0.
Use a global boolean flag doing_pv and set that to true. In your undo_move() function set this flag to false.
No conditions, just do it.
In the search in every position in ply N check if the flag doing_pv is true and if the table do_pv_table[N] is != 0.
In that case use that move first explicitely or give it the biggest move sort score.
Instead of global variables you could also make them reference parameters.
(2) may be more complicated to do right in multithreaded programs.
