1

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:

// 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.

I've also tried a debugging idea I saw, 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.

1
  • Have you tried only pruning at pre-horizon nodes? Depth 4 is pretty far from the leaf nodes Apr 27, 2023 at 20:43

1 Answer 1

1

As I see if you don't do any depth checking. Also if I am reading your code correctly, you do not check to see if the move is a capture. I could be wrong as you might already be checking this. But, according to chessprogramming wiki, you should not do futility pruning when the side to move is in check. Which I see you only check if a move gives check. I have a four player chess teams engine, heres how I do futility pruning.

if (moveIsPrunable && curTeamIsNotInCheck && lmrDepth <= 8 && evalScore <= alpha - 125 - 90 * lmrDepth) {
    continue;
}

I hope this helps, If you have any problems feel free to reply to this post.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.