MTD(f): Difference between revisions
Content deleted Content added
m where is this? Tags: Mobile edit Mobile app edit iOS app edit |
add citation needed tag for a unsupported claim |
||
| (20 intermediate revisions by 10 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Zero-window Alpha-Beta game tree search algorithm}} |
{{Short description|Zero-window Alpha-Beta game tree search algorithm}} |
||
'''MTD(f)''' is an [[Alpha–beta pruning|alpha-beta]] game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory (usually a transposition table) to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for Memory-enhanced Test Driver with node ‘n’ and value ‘f’.<ref name="FürnkranzKubat2001">{{cite book|author1=Johannes Fürnkranz|author2=Miroslav Kubat|title=Machines that Learn to Play Games|url=https://books.google.com/books?id=0Q_RBtFGMc4C&pg=PA95|year=2001|publisher=Nova Publishers|isbn=978-1-59033-021-0|pages=95–}}</ref> The efficacy of this paradigm depends on a good initial guess, and the supposition that the final minimax value lies in a narrow window around the guess (which |
'''MTD(f)''' is an [[Alpha–beta pruning|alpha-beta]] game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory (usually a [[transposition table]]) to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for Memory-enhanced Test Driver with node ‘n’ and value ‘f’.<ref name="FürnkranzKubat2001">{{cite book|author1=Johannes Fürnkranz|author2=Miroslav Kubat|title=Machines that Learn to Play Games|url=https://books.google.com/books?id=0Q_RBtFGMc4C&pg=PA95|year=2001|publisher=Nova Publishers|isbn=978-1-59033-021-0|pages=95–}}</ref> The efficacy of this paradigm depends on a good initial guess, and the supposition that the final minimax value lies in a narrow window around the guess (which becomes an upper/lower bound for the search from root). The memory structure is used to save an initial guess determined elsewhere. |
||
MTD(f) was introduced in 1994 and largely supplanted [[NegaScout]] (PVS), the previously dominant search paradigm for [[chess]], [[checkers]], [[othello]] and other game automatons. |
MTD(f) was introduced in 1994 and largely supplanted [[NegaScout]] (PVS), the previously dominant search paradigm for [[chess]], [[checkers]], [[Reversi|othello]] and other game automatons.{{Citation needed|date=July 2024}} |
||
== Origin == |
== Origin == |
||
MTD(f) was first described in a University of Alberta Technical Report authored by Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin,<ref>[http://cswww.essex.ac.uk/cig/2005/papers/p1018.pdf "Adaptive Strategies of MTD-f for Actual Games"]. Tokyo University of Agriculture and Technology. K SHIBAHARA et al</ref> which would later receive the ICCA Novag Best Computer Chess Publication award for 1994/1995. The algorithm MTD(f) was created out of a research effort to understand the [[SSS*]] algorithm, a best-first search algorithm invented by [[George Stockman]] in 1979.<ref name="GonzalezDiaz-Herrera2014">{{cite book|author1=Teofilo Gonzalez|author2=Jorge Diaz-Herrera|author3=Allen Tucker|title=Computing Handbook, Third Edition: Computer Science and Software Engineering|url=https://books.google.com/books?id=wyHSBQAAQBAJ&pg=SA38-PA13|date=7 May 2014|publisher=CRC Press|isbn=978-1-4398-9853-6|pages=38–}}</ref> SSS* was found to be equivalent to a series of |
MTD(f) was first described in a [[University of Alberta]] Technical Report authored by Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin,<ref>[http://cswww.essex.ac.uk/cig/2005/papers/p1018.pdf "Adaptive Strategies of MTD-f for Actual Games"]. Tokyo University of Agriculture and Technology. K SHIBAHARA et al</ref> which would later receive the ICCA Novag Best Computer Chess Publication award for 1994/1995. The algorithm MTD(f) was created out of a research effort to understand the [[SSS*]] algorithm, a best-first search algorithm invented by [[George Stockman (computer scientist)|George Stockman]] in 1979.<ref name="GonzalezDiaz-Herrera2014">{{cite book|author1=Teofilo Gonzalez|author2=Jorge Diaz-Herrera|author3=Allen Tucker|title=Computing Handbook, Third Edition: Computer Science and Software Engineering|url=https://books.google.com/books?id=wyHSBQAAQBAJ&pg=SA38-PA13|date=7 May 2014|publisher=CRC Press|isbn=978-1-4398-9853-6|pages=38–}}</ref> SSS* was found to be equivalent to a series of Alpha-beta pruning|alpha-beta calls, provided that alpha-beta used storage, such as a transposition table. |
||
The name MTD(f) stands for Memory-enhanced Test Driver, referencing [[Judea Pearl]]'s Test algorithm,{{ |
The name MTD(f) stands for Memory-enhanced Test Driver, referencing [[Judea Pearl]]'s Test algorithm,{{citation needed|date=June 2021}} which performs Zero-Window Searches. MTD(f) is described in depth in Aske Plaat's 1996 PhD thesis.{{citation needed|date=June 2021}} |
||
== Zero-window searches == |
== Zero-window searches == |
||
A "zero-window" search is an alpha-beta search whose upper and lower bounds are identical, or differ by one unit, so that the return value is guaranteed to fall outside the bound(s) (or in an exceptionally lucky case, be equal to the bound). |
|||
| ⚫ | MTD(f) derives its efficiency by only performing zero-window alpha-beta searches, with a "good" bound (i.e. beta). In MTD(f), AlphaBeta fails high or low, returning a lower bound or an upper bound on the minimax value, respectively. Zero-window calls cause more cutoffs, but return less information - only a bound on the minimax value. To find the minimax value, MTD(f) calls AlphaBeta a number of times, converging towards it and eventually finding the exact value. A |
||
| ⚫ | MTD(f) derives its efficiency by only performing zero-window alpha-beta searches, with a previously determined "good" bound (i.e. beta). In MTD(f), AlphaBeta fails high or low, returning a lower bound or an upper bound on the minimax value, respectively. Zero-window calls cause more cutoffs, but return less information - only a bound on the minimax value. To find the minimax value, MTD(f) calls AlphaBeta a number of times, converging towards it and eventually finding the exact value. A transposition table stores and retrieves the previously searched portions of the tree in memory to reduce the overhead of re-exploring parts of the search tree.<ref name=ai>{{cite journal|last=Plaat|first=Aske|author2=Jonathan Schaeffer |author3=Wim Pijls |author4=Arie de Bruin |title=Best-first Fixed-depth Minimax Algorithms|journal=Artificial Intelligence|date=November 1996|volume=87|issue=1–2|doi=10.1016/0004-3702(95)00126-3 |pages=255–293|doi-access=free}}</ref> |
||
== Pseudocode == |
== Pseudocode == |
||
| Line 28: | Line 30: | ||
'''return''' g |
'''return''' g |
||
; {{code|f}} : First guess for best value. The better the quicker the algorithm converges. Could be 0 for first call. |
; {{code|f}} : First guess for best value. The better the quicker the algorithm converges. Could be 0 for first call. |
||
; {{code|d}} : Depth to loop for. An [[iterative deepening depth-first search]] could be done by calling {{code|MTDF()}} multiple times with incrementing {{code|d}} and providing the best previous result in {{code|f}}.<ref>https://people.csail.mit.edu/plaat/mtdf.html</ref> |
; {{code|d}} : Depth to loop for. An [[iterative deepening depth-first search]] could be done by calling {{code|MTDF()}} multiple times with incrementing {{code|d}} and providing the best previous result in {{code|f}}.<ref>{{Cite web|url=https://people.csail.mit.edu/plaat/mtdf.html|title = Aske Plaat: MTD(f), a new chess algorithm}}</ref> |
||
{{code|AlphaBetaWithMemory}} is a variation of Alpha Beta Search that caches previous results. |
{{code|AlphaBetaWithMemory}} is a variation of Alpha Beta Search that caches previous results. |
||
== |
== Description == |
||
MTD(f) calls the zero-window searches from the root of the tree. |
MTD(f) calls the zero-window searches from the root of the tree. MTD(f) depends on a transposition table to perform efficiently.<ref>When MTD(f) is used in programs suffering from a pronounced odd-even effect, where the score at the root is higher for even search depths and lower for odd search depths, it is advisable to use separate values for f to start the search as close as possible to the minimax value. Otherwise, the search would take more iterations to converge on the minimax value, especially for fine grained evaluation functions.</ref> |
||
Zero-window searches hit a cut-off sooner than wide-window searches. They are therefore more efficient, but, in some sense, also less forgiving, than wide-window searches. However, wider search windows are more forgiving for engines with large odd/even swings and fine-grained evaluation functions. For this reason some [[chess engine]]s have not switched to MTD(f). |
Zero-window searches hit a cut-off sooner than wide-window searches. They are therefore more efficient, but, in some sense, also less forgiving, than wide-window searches. However, wider search windows are more forgiving for engines with large odd/even swings and fine-grained evaluation functions. For this reason some [[chess engine]]s have not switched to MTD(f). |
||
| ⚫ | In tests with tournament-quality programs such as [[Chinook (draughts player)|Chinook]] (checkers), [[Phoenix (chess program)|Phoenix]] (chess), and [[Keyano]] (Othello), the MTD(f) algorithm outperformed all other search algorithms.<ref name=ai/ |
||
| ⚫ | |||
Recent algorithms like [[Best Node Search]] are suggested to outperform MTD(f). |
Recent algorithms like [[Best Node Search]] are suggested to outperform MTD(f). |
||
Latest revision as of 23:43, 14 July 2024
MTD(f) is an alpha-beta game tree search algorithm modified to use ‘zero-window’ initial search bounds, and memory (usually a transposition table) to reuse intermediate search results. MTD(f) is a shortened form of MTD(n,f) which stands for Memory-enhanced Test Driver with node ‘n’ and value ‘f’.[1] The efficacy of this paradigm depends on a good initial guess, and the supposition that the final minimax value lies in a narrow window around the guess (which becomes an upper/lower bound for the search from root). The memory structure is used to save an initial guess determined elsewhere.
MTD(f) was introduced in 1994 and largely supplanted NegaScout (PVS), the previously dominant search paradigm for chess, checkers, othello and other game automatons.[citation needed]
Origin
[edit]MTD(f) was first described in a University of Alberta Technical Report authored by Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin,[2] which would later receive the ICCA Novag Best Computer Chess Publication award for 1994/1995. The algorithm MTD(f) was created out of a research effort to understand the SSS* algorithm, a best-first search algorithm invented by George Stockman in 1979.[3] SSS* was found to be equivalent to a series of Alpha-beta pruning|alpha-beta calls, provided that alpha-beta used storage, such as a transposition table.
The name MTD(f) stands for Memory-enhanced Test Driver, referencing Judea Pearl's Test algorithm,[citation needed] which performs Zero-Window Searches. MTD(f) is described in depth in Aske Plaat's 1996 PhD thesis.[citation needed]
Zero-window searches
[edit]A "zero-window" search is an alpha-beta search whose upper and lower bounds are identical, or differ by one unit, so that the return value is guaranteed to fall outside the bound(s) (or in an exceptionally lucky case, be equal to the bound).
MTD(f) derives its efficiency by only performing zero-window alpha-beta searches, with a previously determined "good" bound (i.e. beta). In MTD(f), AlphaBeta fails high or low, returning a lower bound or an upper bound on the minimax value, respectively. Zero-window calls cause more cutoffs, but return less information - only a bound on the minimax value. To find the minimax value, MTD(f) calls AlphaBeta a number of times, converging towards it and eventually finding the exact value. A transposition table stores and retrieves the previously searched portions of the tree in memory to reduce the overhead of re-exploring parts of the search tree.[4]
Pseudocode
[edit]function MTDF(root, f, d) is
g := f
upperBound := +∞
lowerBound := −∞
while lowerBound < upperBound do
β := max(g, lowerBound + 1)
g := AlphaBetaWithMemory(root, β − 1, β, d)
if g < β then
upperBound := g
else
lowerBound := g
return g
f- First guess for best value. The better the quicker the algorithm converges. Could be 0 for first call.
d- Depth to loop for. An iterative deepening depth-first search could be done by calling
MTDF()multiple times with incrementingdand providing the best previous result inf.[5]
AlphaBetaWithMemory is a variation of Alpha Beta Search that caches previous results.
Description
[edit]MTD(f) calls the zero-window searches from the root of the tree. MTD(f) depends on a transposition table to perform efficiently.[6]
Zero-window searches hit a cut-off sooner than wide-window searches. They are therefore more efficient, but, in some sense, also less forgiving, than wide-window searches. However, wider search windows are more forgiving for engines with large odd/even swings and fine-grained evaluation functions. For this reason some chess engines have not switched to MTD(f).
In tests with tournament-quality programs such as Chinook (checkers), Phoenix (chess), and Keyano (Othello), the MTD(f) algorithm outperformed all other search algorithms.[4] Recent algorithms like Best Node Search are suggested to outperform MTD(f).
References
[edit]- ^ Johannes Fürnkranz; Miroslav Kubat (2001). Machines that Learn to Play Games. Nova Publishers. pp. 95–. ISBN 978-1-59033-021-0.
- ^ "Adaptive Strategies of MTD-f for Actual Games". Tokyo University of Agriculture and Technology. K SHIBAHARA et al
- ^ Teofilo Gonzalez; Jorge Diaz-Herrera; Allen Tucker (7 May 2014). Computing Handbook, Third Edition: Computer Science and Software Engineering. CRC Press. pp. 38–. ISBN 978-1-4398-9853-6.
- ^ a b Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (November 1996). "Best-first Fixed-depth Minimax Algorithms". Artificial Intelligence. 87 (1–2): 255–293. doi:10.1016/0004-3702(95)00126-3.
- ^ "Aske Plaat: MTD(f), a new chess algorithm".
- ^ When MTD(f) is used in programs suffering from a pronounced odd-even effect, where the score at the root is higher for even search depths and lower for odd search depths, it is advisable to use separate values for f to start the search as close as possible to the minimax value. Otherwise, the search would take more iterations to converge on the minimax value, especially for fine grained evaluation functions.