An Improved MTD(f)?

[JoAnnP38]

I have been experimenting with the MTD(f) enhancement to search. For reference here is the simplified code as I understand it. (Please interject with a correction if my understanding is flawed.)

Code: Select all

int MTD(int guess, int depth)
{
    int lowerBound = -short.MaxValue;
    int upperBound = short.MaxValue;
    do
    {
        int beta = guess != lowerBound ? guess : guess + 1;
        guess = AlphaBetaWithMemory(beta - 1, beta, depth);
        if (guess < beta)
        {
            upperBound = guess;
        }
        else
        {
            lowerBound = guess;
        }
    } while (lowerBound < upperBound);
    return guess;
}

In my testing the convergence of MTD was horrible because the guess was only being adjusted +/- 1 at a time. I found this code change improved the convergence time significantly.

Code: Select all

// Improved???
int ImprovedMTD(int guess, int depth)
{
    int lowerBound = -short.MaxValue;
    int upperBound = short.MaxValue;
    do
    {
        int beta = guess != lowerBound ? guess : guess + 1;
        guess = AlphaBetaWithMemory(beta - 1, beta, depth);
        if (guess < beta)
        {
            upperBound = guess;
        }
        else
        {
            lowerBound = guess;
        }
        // !!! TADAAAA !!!
        guess = (lowerBound + upperBound) / 2;
    } while (lowerBound < upperBound);
    return guess;
}

Does this binary search inspired change make sense? Is it an obvious change to an example of instructive-only MTD(f)? Or am I fooling myself because something must be seriously wrong with my implementation?

[alvinypeng]

This change makes sense. This type of search has already been used in sunfish.

Code: Select all

    def search(self, history):
        """Iterative deepening MTD-bi search"""
        self.nodes = 0
        self.history = set(history)
        self.tp_score.clear()

        gamma = 0
        # In finished games, we could potentially go far enough to cause a recursion
        # limit exception. Hence we bound the ply. We also can't start at 0, since
        # that's quiscent search, and we don't always play legal moves there.
        for depth in range(1, 1000):
            # The inner loop is a binary search on the score of the position.
            # Inv: lower <= score <= upper
            # 'while lower != upper' would work, but it's too much effort to spend
            # on what's probably not going to change the move played.
            lower, upper = -MATE_LOWER, MATE_LOWER
            while lower < upper - EVAL_ROUGHNESS:
                score = self.bound(history[-1], gamma, depth, can_null=False)
                if score >= gamma:
                    lower = score
                if score < gamma:
                    upper = score
                yield depth, gamma, score, self.tp_move.get(history[-1])
                gamma = (lower + upper + 1) // 2

[JoAnnP38]

This change makes sense. This type of search has already been used in sunfish.

Thank you! Now I don't feel so crazy. Thanks for the link btw!

[abulmo2]

You just reinvent the wheel:
https://www.chessprogramming.org/NegaC*

[JoAnnP38]

You just reinvent the wheel:
https://www.chessprogramming.org/NegaC*

The story of my life...