MTD(f)
MTD(f) to algorytm przeszukiwania drzewa gier alfa-beta zmodyfikowany tak, aby używał początkowych granic wyszukiwania „zerowego okna” oraz pamięci (zwykle tabeli transpozycji ) do ponownego wykorzystania pośrednich wyników wyszukiwania. MTD(f) to skrócona forma MTD(n,f), która oznacza sterownik testowy o zwiększonej pamięci z węzłem „n” i wartością „f”. Skuteczność tego paradygmatu zależy od dobrego wstępnego przypuszczenia i założenia, że ostateczna wartość minimaksu leży w wąskim oknie wokół przypuszczenia (które staje się górną/dolną granicą wyszukiwania od korzenia). Struktura pamięci służy do zapisywania wstępnego przypuszczenia określonego w innym miejscu.
MTD(f) został wprowadzony w 1994 roku iw dużej mierze wyparł NegaScout (PVS), wcześniej dominujący paradygmat wyszukiwania szachów , warcabów , othello i innych automatów do gier.
Pochodzenie
MTD(f) został po raz pierwszy opisany w Raporcie Technicznym Uniwersytetu Alberty autorstwa Aske Plaata, Jonathana Schaeffera, Wima Pijlsa i Arie de Bruina, który później otrzymał nagrodę ICCA Novag Best Computer Chess Publication za rok 1994/1995. Algorytm MTD(f) został stworzony w wyniku wysiłków badawczych mających na celu zrozumienie algorytmu SSS* , algorytmu wyszukiwania najlepszego pierwszego wynalezionego przez George'a Stockmana w 1979 r. SSS* okazał się równoważny z serią przycinania alfa-beta|alpha wywołania -beta, pod warunkiem, że alfa-beta używała pamięci, takiej jak tablica transpozycji.
Nazwa MTD(f) oznacza Memory-enhanced Test Driver, odnosząc się do algorytmu testowego Judea Pearl , [ potrzebne źródło ] , który przeprowadza wyszukiwanie w zerowym oknie. MTD(f) jest szczegółowo opisane w rozprawie doktorskiej Aske Plaat z 1996 roku. [ potrzebne źródło ]
Wyszukiwanie w zerowym oknie
Wyszukiwanie w „oknie zerowym” to wyszukiwanie alfabetyczne, którego górne i dolne granice są identyczne lub różnią się o jedną jednostkę, dzięki czemu gwarantowana jest wartość zwracana poza granicami (lub w wyjątkowo szczęśliwym przypadku jest równa do wiązania).
MTD(f) czerpie swoją skuteczność, przeprowadzając tylko przeszukiwania alfa-beta w zerowym oknie, z wcześniej określoną „dobrą” granicą (tj. beta). W MTD(f), AlphaBeta kończy się niepowodzeniem na wysokim lub niskim poziomie, zwracając odpowiednio dolną lub górną granicę wartości minimax. Wywołania w zerowym oknie powodują więcej odcięć, ale zwracają mniej informacji — tylko ograniczenie wartości minimax. Aby znaleźć wartość minimax, MTD(f) wywołuje AlphaBeta kilka razy, zbiegając się w jej kierunku i ostatecznie znajdując dokładną wartość. Tablica transpozycji przechowuje i odzyskuje wcześniej przeszukane części drzewa w pamięci, aby zmniejszyć obciążenie związane z ponowną eksploracją części drzewa wyszukiwania.
Pseudo kod
funkcja MTDF(pierwiastek, f, d) to g := f górna granica := +∞ dolna granica := −∞ podczas gdy niższa granica < górna granica do β := max(g, dolna granica + 1) g := AlphaBetaWithMemory(root, β − 1 , β, d) jeśli g < β then upperBound := g else lowerBound := g return g
f- Najpierw zgadnij najlepszą wartość. Im lepiej, tym szybciej algorytm osiąga zbieżność. Może być 0 dla pierwszego połączenia.
d- Głębokość pętli. Jakiś iteracyjne pogłębianie przeszukiwania w głąb można wykonać przez wielokrotne wywołanie
MTDF() z inkrementacjądi podaniem najlepszego poprzedniego wyniku wf.
AlphaBetaWithMemory to odmiana Alpha Beta Search, która zapisuje poprzednie wyniki w pamięci podręcznej.
Opis
MTD(f) wywołuje wyszukiwanie w zerowym oknie z korzenia drzewa. Efektywne działanie MTD(f) zależy od tablicy transpozycji.
Wyszukiwania w zerowym oknie osiągają punkt odcięcia wcześniej niż wyszukiwania w szerokim oknie. Są zatem bardziej wydajne, ale w pewnym sensie mniej wyrozumiałe niż wyszukiwania w szerokim oknie. Jednak szersze okna wyszukiwania są bardziej wyrozumiałe dla silników z dużymi wahaniami nieparzystymi/parzystymi i precyzyjnymi funkcjami oceny. Z tego powodu niektóre silniki szachowe nie przeszły na MTD(f).
W testach z programami o jakości turniejowej, takimi jak Chinook (warcaby), Phoenix (szachy) i Keyano (Othello), algorytm MTD(f) przewyższał wszystkie inne algorytmy wyszukiwania. Sugeruje się, że najnowsze algorytmy, takie jak Best Node Search, przewyższają MTD (f).