MTD-f - MTD-f

MTD (f) Бұл минимакс іздеу алгоритмі 1994 жылы жасалған Aske Plaat, Джонатан Шеффер, Wim Pijls, және Ари де Брюин. Турнир сапасымен эксперименттер шахмат, дойбы, және Отелло бағдарламалар оны ең тиімді минимакс алгоритмі ретінде көрсетеді. MTD (f) атауы MTD (n, f) аббревиатурасы (түйіні бар жадпен жақсартылған тест драйвері) n және құндылық f). Бұл балама альфа-бета кесу алгоритм.[1]

Шығу тегі

MTD (f) алғаш рет Альберта Университетінде Аске Плат, Джонатан Шеффер, Вим Пайлс және Арие де Брюин авторлығымен жазылған техникалық есепте сипатталған,[2] кейінірек ICCA Novag 1994/1995 жылдарға арналған компьютерлік шахматтың үздік жарияланымы сыйлығын алады. MTD (f) алгоритмі түсіну үшін ғылыми-зерттеу жұмыстарының нәтижесінде құрылды SSS * алгоритм, ойлап тапқан іздеу алгоритмі Джордж Стокман 1979 жылы.[3] SSS * қатарына эквивалентті болып табылды альфа-бета альфа-бета жақсы жұмыс істейтін сияқты сақтауды пайдаланған жағдайда, қоңыраулар транспозиция кестесі.

MTD (f) атауы сілтеме арқылы жадты жақсартылған тест драйвері дегенді білдіреді Иудея інжу-маржаны Нөлдік терезе іздеуін орындайтын тест алгоритмі. MTD (f) Аске Платтың 1996 жылғы кандидаттық диссертациясында терең сипатталған.

Нөлдік терезені іздеу

MTD (f) өзінің тиімділігін тек нөлдік терезедегі альфа-бета іздеуді жүзеге асырады, «жақсы» шекара бар (айнымалы бета). Жылы NegaScout, іздеу AlphaBeta-дағы сияқты кең іздеу терезесімен шақырылады (түбір, −INFINITY, + INFINITY, тереңдік), сондықтан қайтару мәні бір қоңыраудағы альфа мен бета мәні арасында болады. MTD (f) -де AlphaBeta минимакс мәніне сәйкесінше төменгі шекараны немесе жоғарғы шекті қайтара отырып, жоғары немесе төмен деңгейде орындалмайды. Нөлдік терезедегі қоңыраулар көп үзілістерге әкеліп соқтырады, бірақ аз ақпарат қайтарады - тек минимакс мәніне байланысты. Минималды мәнді табу үшін MTD (f) AlphaBeta-ға бірнеше рет қоңырау шалып, оған жақындасып, ақырында дәл мәнін табады. A транспозиция кестесі іздеу ағашының бөліктерін қайта зерттеуге жұмсалатын шығындарды азайту үшін жадқа ағаштың бұрын ізделген бөліктерін сақтайды және алады.[4]

Псевдокод

функциясы MTDF (түбір, f, d) болып табылады    g: = f жоғарғыBound: = + ∞ төменгіBound: = −∞ уақыт lowerBound істеу        β: = max (g, lowerBound + 1) g: = AlphaBetaWithMemory (түбір, β - 1, β, d) егер g <β содан кейін            upperBound: = ж басқа            lowerBound: = ж қайту ж
f
Ең жақсы құндылық туралы алғашқы болжам. Алгоритм соғұрлым тезірек жақындайды. Бірінші қоңырау үшін 0 болуы мүмкін.
г.
Ілмекке дейінгі тереңдік. Ан тереңдетуді тереңдету - бірінші іздеу қоңырау арқылы жасалуы мүмкін MTDF () ұлғайту арқылы бірнеше рет г. және алдыңғы ең жақсы нәтижені қамтамасыз ету f.[5]

Өнімділік

NegaScout нөлдік терезені іздейді рекурсивті. MTD (f) нөлдік терезені ағаштың тамырынан іздейді. MTD (f) алгоритмін жүзеге асыру басқа іздеу алгоритмдеріне (мысалы, NegaScout) қарағанда шахмат сияқты ойындарға қарағанда іс жүзінде тиімдірек болды (аз түйіндерді іздеу). [1], дойбы және Отелло. NegaScout немесе MTD (f) сияқты іздеу алгоритмдерін тиімді орындау үшін транспозиция кестесі жақсы жұмыс істеуі керек. Әйтпесе, мысалы, хэш-коллизия болған кезде, кіші ағаш қайтадан кеңейтіледі. MTD (f) айқын жұп эффектімен зардап шегетін бағдарламаларда қолданылған кезде, іздеу тереңдігі үшін түбірлік ұпай жоғары, тақ тереңдікке төмен болатын кезде іздеуді бастау үшін f үшін бөлек мәндерді қолданған жөн. минимум мәніне мүмкіндігінше жақын. Әйтпесе, іздеу минимакс мәніне жақындау үшін көп қайталануларды қажет етеді, әсіресе ұсақ түйіршікті бағалау функциялары үшін.

Нөлдік терезелерді іздеу кең терезедегі іздеулерге қарағанда тезірек тоқтатылады. Сондықтан олар терезедегі іздеулерге қарағанда тиімдірек, бірақ белгілі бір мағынада кешірімді. MTD (f) нөлдік терезеде іздеуді ғана қолданады, өйткені Альфа-бета және NegaScout кең терезелерді іздеуді қолданады, MTD (f) тиімдірек. Алайда кең іздеу терезелері тақ / жұп өзгермелі және ұсақ түйіршікті бағалау функциялары бар қозғалтқыштар үшін кешірімді. Осы себепті кейбір шахмат қозғалтқыштары сияқты турнирдің сапалы бағдарламалары бар сынақтарда MTD (f) -ге ауысқан жоқ Чинук (дойбы), Феникс (шахмат), және Кейано (Отелло), MTD (f) алгоритмі барлық іздеу алгоритмдерінен асып түсті.[4][6]

Соңғы алгоритмдер сияқты Үздік іздеу MTD (f) -дан асып түсу ұсынылады.

Әдебиеттер тізімі

  1. ^ Йоханнес Фюрнкранц; Мирослав Кубат (2001). Ойын ойнауды үйренетін машиналар. Нова баспалары. 95–13 бб. ISBN  978-1-59033-021-0.
  2. ^ «Нақты ойындарға арналған MTD-f адаптивті стратегиялары». Токио ауыл шаруашылығы және технологиялар университеті. К ШИБАХАРА және т.б.
  3. ^ Теофило Гонсалес; Хорхе Диас-Эррера; Аллен Такер (2014 ж. 7 мамыр). Есептеу бойынша анықтамалық, үшінші басылым: Информатика және бағдарламалық қамтамасыз ету. CRC Press. 38–3 бет. ISBN  978-1-4398-9853-6.
  4. ^ а б Плат, Аске; Джонатан Шеффер; Wim Pijls; Ари де Брюин (қараша 1996). «Үздік минимакс алгоритмдері бойынша тіркелген тереңдік». Жасанды интеллект. 87 (1–2): 255–293. дои:10.1016/0004-3702(95)00126-3.
  5. ^ https://people.csail.mit.edu/plaat/mtdf.html
  6. ^ Плат, Аске; Джонатан Шеффер; Wim Pijls; Ари де Брюин (қараша 1996). «Үздік минимакс алгоритмдері бойынша тіркелген тереңдік». Жасанды интеллект. 87 (1–2): 255–293. дои:10.1016/0004-3702(95)00126-3.

Сыртқы сілтемелер