Кіріспе
Zero window Alpha Beta game tree search algorithm
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’. 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) – бұл ‘zero window’ бастапқы іздеу шектерін және аралық іздеу нәтижелерін қайта пайдалану үшін жадыны (әдетте транспозиция кестесі) пайдалануға бейімделген альфа-бета ойын ағашын іздеу алгоритмі. MTD(f) – түйін ‘n’ және ‘f’ мәні бар жадыға күшейтілген сынақ жүргізушісін білдіретін MTD(n,f) қысқартылған түрі. Бұл парадигманың тиімділігі жақсы бастапқы болжамға және соңғы минимакс мәнінің болжамның айналасындағы тар терезеде екендігіне байланысты (ол тамырдан іздеу үшін жоғарғы/төменгі шекараға айналады). Жад құрылымы басқа жерде анықталған бастапқы болжамды сақтау үшін қолданылады. MTD(f) 1994 жылы ұсынылған және бұрын шахмат, шашка, Othello және басқа ойын автоматтары үшін басым іздеу парадигмасы болған NegaScout (PVS) алгоритмін ығыстырды.
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’. 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) алғаш рет Альберта университетінің Aske Plaat, Jonathan Schaeffer, Wim Pijls және Arie de Bruin авторлық техникалық есебінде сипатталды, кейіннен ол 1994/1995 жылдардағы ICCA Novag ең жақсы компьютерлік шахмат жарияланымы сыйлығына ие болды. MTD(f) алгоритмі 1979 жылы Джордж Стокман ойлап тапқан SSS* алгоритмін түсіну мақсатындағы зерттеу жұмысының нәтижесінде құрылды, SSS* – жақсырақ іздеу алгоритмі. SSS* альфа-бета кесу шақыруларының тізбесімен теңестірілді, егер альфа-бета деректерді сақтауды қолданса, мысалы, транспозициялық кесте сияқты. MTD(f) атауы Memory enhanced Test Driver дегенді білдіреді, бұл Judea Pearl-дің Test алгоритміне сілтеме жасайды, ол Zero Window Searches-ті жүзеге асырады. MTD(f) Аске Платтың 1996 жылғы докторлық диссертациясында толыққанды сипатталған.
Нөлдік терезенің іздеулері
"Нөлдік терезе" іздеуі – альфа-бета іздеуі, оның жоғарғы және төменгі шектері бірдей немесе бірлікке дейін ғана ерекшеленеді, сондықтан қайтарылатын мән міндетті түрде шектен тыс болады (немесе өте жақсы жағдайда, шекке тең болады). MTD(f) өзінің тиімділігін тек нөлдік терезелі альфа-бета іздеуін орындау арқылы қамтамасыз етеді, бұл ретте бұрын анықталған "жақсы" шек (яғни, бета) қолданылады. MTD(f) кезінде AlphaBeta жоғары немесе төмен сәтсіздікке ұшырап, сәйкесінше минимакс мәнінің төменгі немесе жоғарғы шегін қайтарады. Нөлдік терезеге шақырулар көбірек тоқтатуларға (cutoffs) әкеледі, бірақ минимакс мәнінің шегін ғана қамтитын ақпаратты аз қайтарады. Минимакс мәнін табу үшін MTD(f) AlphaBeta-ны бірнеше рет шақырып, оған жақындасып, ақырында нақты мәнді анықтайды. Транспозициялық кесте іздеу ағашының бұрын ізделген бөліктерін жадыда сақтап, оларды қайтару арқылы іздеу ағашының бір бөлігін қайта зерттеуге кеткен қосымша шығындарды азайтады.
Сипаттама
MTD(f) ағаштың түбірінен нөлдік тереземен іздеуді шақырады. MTD(f) тиімді жұмыс істеу үшін транспозиция кестесіне тәуелді. Нөлдік тереземен іздеулер кең тереземен іздеулерге қарағанда ертерек тоқтатылады. Сондықтан олар тиімдірек, бірақ, белгілі бір жағдайда, кең тереземен іздеуге қарағанда кем кешірімді. Дегенмен, кең тереземен іздеулер үлкен тақ/жұп өзгерістері және ұсақ грануляциялы бағалау функциялары бар қозғалтқыштар үшін кешірімдірек. Осы себепті кейбір шахмат қозғалтқыштары MTD(f) алгоритміне көшпеді. Chinook (шахматы), Phoenix (шахматы) және Keyano (Othello) сияқты турнирлік деңгейдегі бағдарламалармен жүргізілген сынақтарда MTD(f) алгоритмі басқа барлық іздеу алгоритмдерінен артық нәтижелер көрсетті. Жақындағы Best Node Search сияқты алгоритмдер MTD(f) алгоритмінен жоғары нәтижелер бере алады деп болжануда.