Home  Up

MTD(f) Experiments

1. Introduction

This page contains MTD(f) experiments referenced in the Note for ICGA Journal: On implementing MTD(f) (in preparation). See also my earlier online paper Handling Search Inconsistencies in MTD(f) and the discussion on the World Draughts Forum.

Our implementation of the MTD(f) algorithm is given in Algorithm 1 (MT) and Algorithm 2 (MTD) below. MTD is called from within an iterative deepening framework, starting with f = 0 for d = 1. The returned value g is input f to the next depth. MTD replaces AlphaBetaTT for the root node in an existing program.

Algorithm 1. Memory-enhanced Test with move selection code (Fail-Soft Negamax version):

int MT(Board board, int gamma, int depth) {
    if (depth == 0 || terminal(board)) return negaEval(board);          // negaEval returns the evaluation relative to the color to move
    ttMove = NO_MOVE;
    entry = tt.lookup(board);
    if (entry != null) {
        if (entry.depth >= depth) {
            if (entry.bound == LOWER && entry.value >= gamma) return entry.value;
            if (entry.bound == UPPER  && entry.value  <  gamma) return entry.value;
        }
        ttMove = entry.move;
    }
    generateMoves(board, moves);            // at least one move (else terminal)
    orderMoves(moves, ttMove);                // apply move ordering, ttMove (if any) first
    g = −INFINITY;
    for (i = 0; i < moves.size; i++) {
        value = −MT(board.makeMove(moves[i]), −gamma + 1, depth − 1);
        if (value > g) {
            g = value;
            move = moves[i];
            if (g >= gamma) break;
        }
    }
    tt.store(board, g, g < gamma ? UPPER : LOWER, depth, <NEW_TT_MOVE>);
    return g;
}

Algorithm 2. MTD(f) with move selection code (marked with an asterisk):

    int, Move MTD(Board root, int f, int d) {
        g = f;
        low = −INFINITY; upp = + INFINITY;
*      bestMove = NO_MOVE;
        do {
            gamma = g == low ? g + 1 : g;
            g = MT(root, gamma, d);
*          bestMove = <NEW_BEST_MOVE>;
            if (g < gamma) upp = g; else low = g;
        } while (low < upp);                                          // not: while (low != upp)
*      return g, bestMove;
    }

There are three viable options for the new TT move in function MT:

A.     <NEW_TT_MOVE> := move

B.     <NEW_TT_MOVE> := g >= gamma ? move : NO_MOVE

C.     <NEW_TT_MOVE> := g >= gamma ? move : ttMove

There are two considered options for the new best move in MTD:

X.      <NEW_BEST_MOVE> := tt.lookup(root).move

Y.      <NEW_BEST_MOVE> := g >= gamma ? tt.lookup(root).move : bestMove

In the Note it is shown that option Y is the safe way to select the best move in MTD(f) in the presence of search inconsistencies, regard­less of how we implemented the new TT move (option A, B or C). Using option X, in combination with option A, the algorithm is capable of blundering in the presence of search inconsistencies. The experiments in Handling Search Inconsistencies in MTD(f) tentatively confirm this.

2. Experiments

AlphaBetaTT and all options for MTD(f) were implemented in the developing 10x10 draughts engine Max, successor to Maximus (Van Horssen 2012). It has a machine-learned evaluation function (Buro 1997, Letouzey Online a) and a 6-piece endgame database. The search is still sequential and other than extending forced moves and leaf captures (quiescence), no search extensions and forward pruning are used yet. Move ordering consists of using the TT move and the History Heuristic (Schaeffer 1983) for the remainder of the moves (except for shallow depths). In this engine, which uses centipawns as evaluation unit, MTD(f) makes on average 5 calls to MT.

2.1. Performance of the TT move options

We investigated the performance of the options A, B and C (i.e., their effect on move ordering). A tournament was played between versions of Max using different options, see Table 1. The search was interrupted after 0.1 second per move, returning the best move of the last completed iteration. No pondering was used.

 

A

B

C

games

score

MTD(f) option A

 

+106 104 =778, 50.1%

+92 89 =807, 50.2%

1976

50.1%

MTD(f) option B

+104 106 =778, 49.9%

 

+90 102 =796, 49.4%

1976

49.6%

MTD(f) option C

+89 92 =807, 49.8%

+102 90 =796, 50.6%

 

1976

50.2%

Table 1. 10x10 draughts tournament of 988-game matches (the 3-move ballots: 494 3-ply openings, played with both colors) at 0.1 sec/move. We use '+' for wins, '−' for losses and '=' for draws.

We found no significant difference between the three options, or it should be that option B is slightly worse than the others, which would indicate that having some TT move is slightly better than having no TT move in case the search failed low.

2.2. Ponder move and TT move options

We also investigated the effectiveness of options A and C for providing a ponder move, retrieved from the TT. (Option B often provides no ponder move.) This was done by using the ponder move to predict the next move in self-play. The TT was cleared in between moves to make sure no TT entries from a previous search by the opponent were used. Of course, the percentage of ponder hits is biased in self-play, that is why we compare the results to those of AlphaBetaTT, which always provides a good ponder move. We only examine positions where a ponder move should be available and the move to play is not forced. This gives an average branching factor of about 10.0 for 10x10 draughts. Table 2 shows the results. AlphaBetaTT also returns the best move of the last completed iteration. We performed three series of experiments: (1) with a fixed search depth per move (10 ply), (2) 988 games (3-move ballots) with 0.1 sec/move, and (3) 158 games (2-move ballots) with 1 sec/move.

10 ply/move

0.1 sec/move

1 sec/move

988 games, > 82,000 moves

988 games, > 83,000 moves

158 games, > 13,000 moves

ponder hit %

no ponder %

ponder hit %

no ponder %

ponder hit %

no ponder %

AlphaBetaTT

71.3

0.000

74.6

0.000

77.3

0.000

MTD(f) option A

69.7

0.025

71.9

0.031

74.4

0.030

MTD(f) option C

69.1

0.023

71.9

0.043

74.4

0.008

Table 2. Percentages of ponder hits and no ponder move in 10x10 draughts self-play.

No significant difference was found between the two options, but a significant difference with AlphaBetaTT was found. If we take the AlphaBetaTT ponder hit percentage as a baseline of 100%, MTD(f) achieves about 96% of that. So, in MTD(f) we have to settle for a somewhat less reliable ponder move and in rare cases no ponder move at all.

3. Conclusions

Concluding, we can say that

1.      To select the best move (the move to play) we should always use option Y. It is the safe way to select a move in the presence of search inconsistencies, which are a fact of life if we use a TT efficiently.

2.      For selecting the move to store in the TT there are three viable options: A, B and C. We found no significant difference in performance between these options.

3.      MTD(f) cannot provide the real principal variation, but for practical purposes a semi-PV can be efficiently retrieved from the TT.

4.      To select the ponder move we can retrieve the position after the best move from the TT. This way, the options A and C (not B) almost always provide a ponder move. However, the quality of this ponder move cannot quite match that of the ponder move provided by alpha-beta based algorithms.

References

Buro, M. (1997). Experiments with Multi-ProbCut and a new high-quality evaluation function for Othello. Games in AI Research, 77-96.

Van Horssen, J. J. (2012). Schwarzman vs. MAXIMUS: A Man-Machine Match in International Draughts. ICGA Journal, 35(2), 106-119.

Letouzey, F. (Online a). Scan. World Draughts Forum. http://laatste.info/bb3/viewtopic.php?t=6786.

Schaeffer, J. (1983). The history heuristic. ICCA Journal, 6(3), 16-19.