MTD(f), A Minimax Algorithm Faster Than NegaScout
This provides a faster algorithm for game-playing AI, particularly in chess, checkers, and Othello, though it appears incremental as it builds on existing minimax methods.
The authors tackled the problem of improving minimax search efficiency in game-playing programs, resulting in MTD(f), which outperformed NegaScout/PVS in tests with chess, checkers, and Othello programs, as evidenced by its adoption in Cilkchess.
MTD(f) is a new minimax search algorithm, simpler and more efficient than previous algorithms. In tests with a number of tournament game playing programs for chess, checkers and Othello it performed better, on average, than NegaScout/PVS (the AlphaBeta variant used in practically all good chess, checkers, and Othello programs). One of the strongest chess programs of the moment, MIT's parallel chess program Cilkchess uses MTD(f) as its search algorithm, replacing NegaScout, which was used in StarSocrates, the previous version of the program.