Dec 27, 2006

[Programming] Extracting the principal variation

This is a somewhat complicated matter. I try to explain it the best I can. Have my code ready, since it is spread through the entire Engine-class and trying to show examples of it would be futile.

When alphaBeta() is first called we submit a pointer to a global vector. This is where the principal variation will be stored when the search is done.

Inside the method a vector called localpv is created. Every time the alphaBeta() is called recursively we submit the localpv.

If we get a move between alpha and beta we have found a new best move, so we want to add this to the principal variation.

Now, since there will most likely be a number of lines that look good at first but then is discovered to not be the best line afterall, we can not just save the line. That is why we have a localpv passed around.

When calculating down in the trees, we are using the localpv of the last instance that called alphaBeta and add the move to it, along with the rest of moves in the current localpv.

So let's say we have returned to ply 3 in a 6 ply search and find the evaluation is between alpha and beta, we add the move that resulted in the line (a move on ply 3) to ply 2's localpv. And then add the rest of ply 3's moves to it.

When we reach the root we are once again working with the actual global pv, and if the evaluation is still between alpha and beta we add the move and the rest of the line to it.

Basically we are working with hundreds of localpv, created at each new call to alphaBeta(). This takes quite some memory but does not slow the engine down, and compared to the number of moves generated it is not much.

This is one tricky bit of code to comprehend. Just remember that even though the code says we are adding moves to pv it is not the global pv unless we are at the root, down in the search trees we are adding it to the last instance' localpv.

No comments: