You could use a different scheme to collect the PV. The approach I use is probably suboptimal, but in practice, it's worked pretty well for me. At the beginning of the iterative deepening loop, I declare a dynamic array (although it doesn't need to be dynamic, it just needs to be set to a length long enough to accompany the longest possible PV your search could return), and pass it into the first call to the negamax search routine by reference. I've just wrapped the PV in a struct to tack on some convenience functions:
Code: Select all
func (search *Search) RunSearch() uint32 {
pv := PVLine{}
bestMove := NullMove
...
for depth := int8(1); depth <= MaxPly && depth <= search.Timer.MaxDepth; depth++ {
pv.Clear()
...
score := search.negamax(depth, 0, -Infinity, Infinity, &pv, false)
...
if search.Timer.IsStopped() {
if bestMove == NullMove && depth == 1 {
bestMove = pv.GetBestMove()
}
break
}
...
bestMove = pv.GetBestMove()
Then each recursive call to the negamax search routine has it's own child PV array created and then reused so that the child node can record and store its PV. Whenever we find a new best move (alpha is raised), I call a method to take the PV array of the current node, clear its first move, and re-build the array by tacking on the new best move found, and then the new PV from the child associated with it at the end:
Code: Select all
func (search *Search) negamax(depth int8, ply uint8, alpha, beta int16, pv *PVLine, doNMP bool) int16 {
...
childPV := PVLine{}
...
for move := moveGen.Next(); !equals(move, NullMove); move = moveGen.Next() {
...
score = -search.negamax(depth-1, ply+1, -beta, -alpha, &childPV, false)
...
if bestScore > alpha {
alpha = bestScore
nodeType = PVNode
pv.Update(move, childPV)
}
childPV.Clear()
}
...
}
The important part is at the end of searching a move in the move loop, is for me to clear the childPV, so the child node gets a fresh PV to start building from.
As I said, I recognize this method is not the most efficient, and at some point, I plan on revisiting things to speed them up. But as I said, it's worked well so far and from testing it's not a significant speed penalty. Although if you're curious I can run a short match with two versions of Blunder, one having the PV code one without, and see if there's a statistically significant Elo loss like you mentioned encountering for your orginal solution.
