I am a fairly new chess engine programmer. I made a pretty simple chess engine that I am trying to figure out how to find the Principal Variation during a search. I have read many places that say this is one of the simplest ways to do it. However I just can't seem to get it right. A couple quick words, I am writing out the code and a very simple way just to understand how chess engines work. So I am currently simply using integer variables to represent the moves. I have found it necessary to use 4 variable to represent a single move:
moveType: ie, capture, quiet, promotion, short castle, etc.
moveFrom: what square the moving piece is moving from
moveTo:: square we are going to
Promotion: if there is a pawn promotion, what piece are we promoting to.
That should all be obvious, but I wrote it out for newbies who might stumble across this like me.
![Wink ;)](./images/smilies/icon_e_wink.gif)
Next I am using two seperate functions, an alpha() and beta() instead of a negamax() style function where they are combined and negated for each side. I do this for simplicity just to understand. So now that is explained my method for collecting the principal variation that I thought of is this: I read that
So am I to understand that I can simply record the PV at any node where alpha < evaluation score < beta? That seems to be what it is saying to my understanding. So I am using this idea in my search. I simply pass a pointer to a move list structure to each node, and if the node is a PV-Node (ie a<s<b) I record the move in the current node, and append the deeper moves from down the tree to the end.PV-Nodes
PV-nodes (Knuth's Type 1) are nodes that have a score that ends up being inside the window. So if the bounds passed are [a,b], with the score returned s, a<s<b. These nodes have all moves searched, and the value returned is exact (i.e., not a bound), which propagates up to the root along with a principal variation.
Root Node and the Leftmost Nodes are always PV-nodes
In Principal Variation Search, PV-nodes are defined by beta-alpha>1
All Siblings of a PV-node are expected Cut-nodes
Sounds great in theory, yet it does not appear to work. The PV I get back is not connected. Seems like just some random moves. I have been trying to think about this but just can't reason as to why this would be. So my question is, is the method I am using good? Or is there something I am missing?
Code below for the alpha() function
Code: Select all
for (int moveIndex = 0; moveIndex < moveList.count; moveIndex++)
{
// begin processing move list
MakeMove(position, moveList.moves[moveIndex].moveType, moveList.moves[moveIndex].moveFrom, moveList.moves[moveIndex].moveTo, moveList.moves[moveIndex].promotion);
val = Beta(depth - 1, position, alpha, beta, &localpV);
UndoMove(position);
if (val >= beta)
{
return beta; // fail hard beta-cutoff
}
if (val > alpha)
{
// inside here is the PV-Node (ie a<s<b) yes?
alpha = val; // alpha acts like max in minmax
// save principal variation for current pv node
pV->moves[position->currentDepth - depth - 1].score = moveList.moves[moveIndex].score;
pV->moves[position->currentDepth - depth - 1].moveType = moveList.moves[moveIndex].moveType;
pV->moves[position->currentDepth - depth - 1].moveFrom = moveList.moves[moveIndex].moveFrom;
pV->moves[position->currentDepth - depth - 1].moveTo = moveList.moves[moveIndex].moveTo;
pV->moves[position->currentDepth - depth - 1].promotion = moveList.moves[moveIndex].promotion;
// append subtree nodes to end
for (int i = position->currentDepth - depth; i < position->currentDepth; i++)
{
// save principal variation for current pv node
pV->moves[i].score = localpV.moves[i].score;
pV->moves[i].moveType = localpV.moves[i].moveType;
pV->moves[i].moveFrom = localpV.moves[i].moveFrom;
pV->moves[i].moveTo = localpV.moves[i].moveTo;
pV->moves[i].promotion = localpV.moves[i].promotion;
}
}
}
return alpha;
Code: Select all
for (int moveIndex = 0; moveIndex < moveList.count; moveIndex++)
{
// begin processing move list
MakeMove(position, moveList.moves[moveIndex].moveType, moveList.moves[moveIndex].moveFrom, moveList.moves[moveIndex].moveTo, moveList.moves[moveIndex].promotion);
val = Alpha(depth - 1, position, alpha, beta, &localpV);
UndoMove(position);
if (val <= alpha)
{
return alpha; // fail hard alpha-cutoff
}
if (val < beta)
{
// inside here is the PV-Node (ie a<s<b) yes?
beta = val; // beta acts like min in minmax
// save principal variation for current pv node, this saves the current best move
pV->moves[position->currentDepth - depth - 1].score = moveList.moves[moveIndex].score;
pV->moves[position->currentDepth - depth - 1].moveType = moveList.moves[moveIndex].moveType;
pV->moves[position->currentDepth - depth - 1].moveFrom = moveList.moves[moveIndex].moveFrom;
pV->moves[position->currentDepth - depth - 1].moveTo = moveList.moves[moveIndex].moveTo;
pV->moves[position->currentDepth - depth - 1].promotion = moveList.moves[moveIndex].promotion;
for (int i = position->currentDepth - depth; i < position->currentDepth; i++)
{
// save principal variation for current pv node, this adds the pV from down in the tree to the end
pV->moves[i].score = localpV.moves[i].score;
pV->moves[i].moveType = localpV.moves[i].moveType;
pV->moves[i].moveFrom = localpV.moves[i].moveFrom;
pV->moves[i].moveTo = localpV.moves[i].moveTo;
pV->moves[i].promotion = localpV.moves[i].promotion;
}
}
}
return beta;