algerbrex wrote: ↑Sun Sep 05, 2021 4:18 am
I'm getting weird results when introducing futility pruning into Blunder. On the one hand, I'm getting a pretty sizeable reduction in nodes, and I'm searching a full ply deeper for some positions (e.g. kiwipete), but I'm getting no, or negative Elo gain when I'm testing.
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
}
As I mentioned, I've fiddled in various ways with tuning the futility margin, what counts as a "tactical" move, and what counts as an "important" move. And nothing I've tried so far so shows any positive gain. And the other threads I've visited on TalkChess where futility pruning wasn't working didn't help much either.
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.
There are two futility pruning schemes that you can use.
1. Position futility pruning
2. Move futility pruning
In (1) if current position is already bad then there is no need to search further, the best move of this position may no longer improve your root position, you can return alpha or qsearch() score in this case.
Code: Select all
// Check if futility pruning can be done.
canFutilityPrune := false
futilityMargin := int16(200 * depth)
if depth <= 4 &&
!inCheck &&
alpha < Checkmate {
canFutilityPrune = staticScore+futilityMargin <= alpha
}
if canFutilityPrune
return alpha or qsearch()
For example from startpos and into the position below which is already bad, you can now prune this branch.
[fen]rnbqkbnr/p1pp1ppp/p7/4p3/4P3/8/PPPP1PPP/RNBQK1NR w KQkq - 0 3[/fen]
In (2) when you are looping through your move list finding bad moves.
Code: Select all
if not tactical_move and other conditions
continue checking other moves
This one is effective if the position is not yet bad. If position is not bad, there might be bad and good moves. You try to find the bad ones here and prune it. Example the position below is not bad for white but there are good and bad moves. Bxf7, Ba6 and Ng5 moves are bad here for example. These are the moves that you need to prune without searching or searching at shallow depth.
[fen]r1bqk1nr/pppp1ppp/2n5/2b1p3/2B1P3/5N2/PPPP1PPP/RNBQK2R w KQkq - 4 4[/fen]
In your current method, you prune moves from the already bad positions, so this is not effective and might lose strength.
