MTD(f), A Minimax Algorithm Faster Than NegaScout
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A New Paradigm for Minimax Search
This paper introduces a new paradigm for minimax game-tree search algo- rithms. MT is a memory-enhanced version of Pearls Test procedure. By changing the way MT is called, a number of best-first game-tree search algorith…
Best-First and Depth-First Minimax Search in Practice
Most practitioners use a variant of the Alpha-Beta algorithm, a simple depth-first pro- cedure, for searching minimax trees. SSS*, with its best-first search strategy, reportedly offers the potential for more efficient s…
A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization
Gradient descent-ascent (GDA) is a widely used algorithm for minimax optimization. However, GDA has been proved to converge to stationary points for nonconvex minimax optimization, which are suboptimal compared with loca…
Minimax Strikes Back
Deep Reinforcement Learning reaches a superhuman level of play in many complete information games. The state of the art algorithm for learning with zero knowledge is AlphaZero. We take another approach, Ath\'enan, which …
Deep Reinforcement LearningGPUreinforcement-learningReinforcement Learning (RL)Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
Smooth minimax games often proceed by simultaneous or alternating gradient updates. Although algorithms with alternating updates are commonly used in practice, the majority of existing theoretical analyses focus on simul…