Now, I understand this is because I'm likely pruning too many good lines, so the Elo gain from the increased search depth is being offset by missing winning tactical lines. Where I'm stuck is figuring out what I'm missing (or including) in my futility pruning code that's causing this "over-pruning". Over the past week or so, I've done quite a bit of research and have tried many different configurations and ideas, and none of them seem to be working for me.
I've also taken a look at the code of other engines, and it doesn't seem like I'm doing anything weird. Here are the relevant parts of my search code:
Code: Select all
// The primary negamax function, which only returns a score and no best move.
func (search *Search) negamax(depth, ply uint8, alpha, beta int16, doNull bool) int16 {
...
// Check if futility pruning can be done.
canFutilityPrune := false
futilityMargin := int16(200 * depth)
if depth <= 4 &&
!inCheck &&
alpha < Checkmate {
canFutilityPrune = staticScore+futilityMargin <= alpha
}
...
// Set a flag to record if any pruning was done. If pruning was done, then
// we can't declare a mate, since we didn't test every move.
noPruning := true
for index := 0; index < int(moves.Count); index++ {
...
givesCheck := sqIsAttacked(
&search.Pos,
search.Pos.SideToMove,
search.Pos.PieceBB[search.Pos.SideToMove][King].Msb())
tactical := givesCheck || move.MoveType() == Attack || move.MoveType() == Promotion
important := move.Equal(hashMove)
if canFutilityPrune && legalMoves > 0 && !tactical && !important {
search.Pos.UnmakeMove(move)
noPruning = false
continue
}
...
}
// If we don't have any legal moves, and we haven't pruned moves, it's either checkmate, or a stalemate.
if legalMoves == 0 && noPruning {
if inCheck {
// If its checkmate, return a checkmate score of negative infinity,
// with the current ply added to it. That way, the engine will be
// rewarded for finding mate quicker, or avoiding mate longer.
return -Inf + int16(ply)
} else {
// If it's a draw, return the draw value.
return search.contempt()
}
}
// Return the best score, which is alpha.
return alpha
}
I've also tried a debugging idea I saw in another thread, where at pre-horizon nodes (depth=1) if a move was pruned, I perform a normal full-search and make sure that the move failed-low and my futility margin was high enough and my pruning seemed to pass this test, so I must admit, at this point, I'm pretty stumped. Any ideas as to where I'm going wrong with my pruning would be appreciated.