Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
У контексті комбінаторної теорії ігор, яка зазвичай вивчає послідовні ігри з повною інформацією, дерево гри — це графік, що представляє всі можливі стани гри в такій грі. До таких ігор належать такі відомі, як шахи, шашки, ґо та хрестики-нулики. Дерево гри можна використовувати для вимірювання [en], оскільки воно представляє всі можливі способи, якими гра може розвиватися. Через великі ігрові дерева складних ігор, таких як шахи, алгоритми, розроблені для гри в цей клас ігор, використовуватимуть часткові ігрові дерева, що робить обчислення можливими на сучасних комп'ютерах. Існують різні методи розгадування ігрових дерев. Якщо можна створити повне дерево гри, можна використати детермінований алгоритм, такий як зворотна індукція або ретроспективний аналіз. Рандомізовані алгоритми та мінімаксні алгоритми, такі як дерево пошуку Монте-Карло, можна використовувати у випадках, коли повне дерево гри неможливо.
Розуміння дерева гри
Щоб краще зрозуміти дерево гри, його можна розглядати як техніку для аналізу змагальних ігор, яка визначає дії, які виконує гравець, щоб виграти гру. У теорії ігор дерево гри — це орієнтований граф, вузли якого є позиціями в грі (наприклад, розташування фігур у настільній грі), а ребра — ходами (наприклад, для переміщення фігур з однієї позиції на дошці в іншу).
Повне дерево гри для гри — це таке дерево гри, яке починається з початкової позиції та містить усі можливі ходи з кожної позиції; повне дерево є таким самим деревом, яке було отримано з представлення гри у [en]. Точніше кажучи, повна гра є нормою для гри в теорії ігор, яка може чітко висловити багато важливих аспектів. Наприклад, послідовність дій, які можуть виконувати зацікавлені сторони, їхній вибір у кожній точці прийняття рішення, інформація про дії, вжиті іншими зацікавленими сторонами, коли кожна зацікавлена сторона приймає рішення, і переваги всіх можливих результатів гри.
На діаграмі показано перші два шари в дереві гри для хрестиків-нуликів. Обертання та відображення позицій еквівалентні, тому перший гравець має три варіанти ходу: у центрі, на краю або в кутку. Другий гравець має два варіанти відповіді, якщо перший гравець грав у центрі, інакше п'ять варіантів. І так далі.
Кількість листових вузлів у повному дереві гри — це кількість можливих різних способів гри. Наприклад, дерево гри для хрестиків-нуликів має 255168 листових вузлів.
Ігрові дерева важливі для штучного інтелекту, тому що один із способів вибрати найкращий хід у грі — це пошук у дереві гри за допомогою будь-якого з численних алгоритмів пошуку по дереву в поєднанні з мінімаксними правилами для скорочення дерева. У дереві гри для хрестиків-нуликів можна легко шукати, але повні дерева ігор для великих ігор, як-от шахи, завеликі для пошуку. Замість цього програма для гри в шахи здійснює пошук у частковому дереві гри: як правило, стільки ходів із поточної позиції, скільки вона може знайти за доступний час. За винятком випадків «патологічних» ігрових дерев (які є досить рідкісними на практиці), збільшення глибини пошуку загалом покращує ймовірність вибору найкращого ходу.
Ігри для двох також можуть бути представлені у вигляді [en]. Щоб перший гравець виграв партію, має існувати виграшний хід для всіх ходів другого гравця. Це представлено в і-або дереві за допомогою диз'юнкції для представлення альтернативних ходів першого гравця та використання кон'юнкції для представлення всіх ходів другого гравця.
Вирішення ігрових дерев
Детермінований алгоритм
Завдяки повному дереву гри можна «розв'язати» гру — тобто знайти послідовність ходів, яку може виконувати перший або другий гравець, що гарантує найкращий можливий результат для цього гравця (зазвичай виграш або нічія). Детермінований алгоритм (який зазвичай називають зворотною індукцією або ретроспективним аналіз) можна описати рекурсивно наступним чином.
- Розфарбуйте останній рівень дерева гри таким чином, щоб усі перемоги Гравця 1 були забарвлені одним кольором (синій на діаграмі), усі перемоги Гравця 2 — іншим (червоним на діаграмі), а всі нічиї — третім (сірим на діаграмі).
- Поверніться до вузлів верхнього рівня. Якщо один із синів вузла має протилежний колір поточного гравця, розфарбуйте вузол кольором цього сина. Якщо всі сини вузла того самого кольору, що й поточний гравець, пофарбуйте цей вузол у той самий колір. В іншому випадку розфарбуйте цей вузол кольором нічієї.
- Повторюйте крок 2, рухаючись вгору, доки всі вузли не будуть розфарбовані. Колір кореневого вузла визначатиме характер гри.
Зазвичай можна розв'язати гру (у цьому технічному сенсі «розв'язування»), використовуючи лише підмножину дерева гри, тому що в багатьох іграх хід не потрібно аналізувати, оскільки є інший хід, який є кращим для того ж гравця. Це принцип, який використовується для альфа-бета відсічення, яке можна використовувати в багатьох детермінованих іграх.
Будь-яке піддерево, яке можна використовувати для вирішення гри, відоме як дерево рішень, а розмір дерев рішень різної форми використовується як міра [en].
Рандомізований алгоритм
Рандомізовані алгоритми можна використовувати для вирішення ігрових дерев. У такого типу реалізації дві основні переваги: швидкість і практичність. Тоді як детерміновану версію розв'язування ігрових дерев можна виконати за Ο(n), рандомізований алгоритм має очікуваний час виконання θ(n0.792), якщо кожен вузол у ігровому дереві має ступінь 2. Крім того, це практично, оскільки рандомізовані алгоритми здатні «завадити ворогу», тобто супротивник не може перемогти систему ігрових дерев, знаючи алгоритм, який використовується для вирішення ігрового дерева, оскільки порядок розв'язування є випадковим.
Нижче наведено реалізацію алгоритму вирішення рандомізованого дерева ігор:
def gt_eval_rand(u) -> bool: """Returns True if this node evaluates to a win, otherwise False""" if u.leaf: return u.win else: random_children = (gt_eval_rand(child) for child in random_order(u.children)) if u.op == "OR": return any(random_children) if u.op == "AND": return all(random_children) Алгоритм використовує ідею «короткого замикання»: якщо кореневий вузол вважається оператором «АБО», то як тільки знайдено один True, корінь класифікується як True; і навпаки, якщо кореневий вузол вважається оператором «І», тоді як тільки знайдено один False, корінь класифікується як False.
Див. також
Примітки
- Zuckerman, Inon; Wilson, Brandon; Nau, D. (2018). Avoiding game‐tree pathology in 2‐player adversarial search (англ.).
- n2:0360-5442 - Search Results. www.worldcat.org.
- Nau, Dana S. (1 листопада 1982). An investigation of the causes of pathology in games. Artificial Intelligence (англ.). Т. 19, № 3. с. 257—278. doi:10.1016/0004-3702(82)90002-9. ISSN 0004-3702.
- (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN .
- (2013). SI486D: Randomness in Computing, Game Trees Unit. United States Naval Academy, Computer Science Department. Архів оригіналу за 8 травня 2021. Процитовано 28 листопада 2022.
- Pekař, Libor; Matušů, Radek; Andrla, Jiří; Litschmannová, Martina (September 2020). Review of Kalah Game Research and the Proposition of a Novel Heuristic–Deterministic Algorithm Compared to Tree-Search Solutions and Human Decision-Making. Informatics (англ.). 7 (3): 34. doi:10.3390/informatics7030034.
Література
- Hu, Te Chiang; Shing, Man-tak (2002). Combinatorial Algorithms. Courier Dover Publications. ISBN . Процитовано 2 квітня 2007.
- , Heuristics, Addison-Wesley, 1984
- Aske Plaat, Jonathan Schaeffer, Wim Pijls, and Arie de Bruin. Exploiting Graph Properties of Game Trees
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U konteksti kombinatornoyi teoriyi igor yaka zazvichaj vivchaye poslidovni igri z povnoyu informaciyeyu derevo gri ce grafik sho predstavlyaye vsi mozhlivi stani gri v takij gri Do takih igor nalezhat taki vidomi yak shahi shashki go ta hrestiki nuliki Derevo gri mozhna vikoristovuvati dlya vimiryuvannya en oskilki vono predstavlyaye vsi mozhlivi sposobi yakimi gra mozhe rozvivatisya Cherez veliki igrovi dereva skladnih igor takih yak shahi algoritmi rozrobleni dlya gri v cej klas igor vikoristovuvatimut chastkovi igrovi dereva sho robit obchislennya mozhlivimi na suchasnih komp yuterah Isnuyut rizni metodi rozgaduvannya igrovih derev Yaksho mozhna stvoriti povne derevo gri mozhna vikoristati determinovanij algoritm takij yak zvorotna indukciya abo retrospektivnij analiz Randomizovani algoritmi ta minimaksni algoritmi taki yak derevo poshuku Monte Karlo mozhna vikoristovuvati u vipadkah koli povne derevo gri nemozhlivo Rozuminnya dereva griPershi dva shari dereva gri dlya hrestikiv nulikiv Shob krashe zrozumiti derevo gri jogo mozhna rozglyadati yak tehniku dlya analizu zmagalnih igor yaka viznachaye diyi yaki vikonuye gravec shob vigrati gru U teoriyi igor derevo gri ce oriyentovanij graf vuzli yakogo ye poziciyami v gri napriklad roztashuvannya figur u nastilnij gri a rebra hodami napriklad dlya peremishennya figur z odniyeyi poziciyi na doshci v inshu Povne derevo gri dlya gri ce take derevo gri yake pochinayetsya z pochatkovoyi poziciyi ta mistit usi mozhlivi hodi z kozhnoyi poziciyi povne derevo ye takim samim derevom yake bulo otrimano z predstavlennya gri u en Tochnishe kazhuchi povna gra ye normoyu dlya gri v teoriyi igor yaka mozhe chitko visloviti bagato vazhlivih aspektiv Napriklad poslidovnist dij yaki mozhut vikonuvati zacikavleni storoni yihnij vibir u kozhnij tochci prijnyattya rishennya informaciya pro diyi vzhiti inshimi zacikavlenimi storonami koli kozhna zacikavlena storona prijmaye rishennya i perevagi vsih mozhlivih rezultativ gri Na diagrami pokazano pershi dva shari v derevi gri dlya hrestikiv nulikiv Obertannya ta vidobrazhennya pozicij ekvivalentni tomu pershij gravec maye tri varianti hodu u centri na krayu abo v kutku Drugij gravec maye dva varianti vidpovidi yaksho pershij gravec grav u centri inakshe p yat variantiv I tak dali Kilkist listovih vuzliv u povnomu derevi gri ce kilkist mozhlivih riznih sposobiv gri Napriklad derevo gri dlya hrestikiv nulikiv maye 255168 listovih vuzliv Igrovi dereva vazhlivi dlya shtuchnogo intelektu tomu sho odin iz sposobiv vibrati najkrashij hid u gri ce poshuk u derevi gri za dopomogoyu bud yakogo z chislennih algoritmiv poshuku po derevu v poyednanni z minimaksnimi pravilami dlya skorochennya dereva U derevi gri dlya hrestikiv nulikiv mozhna legko shukati ale povni dereva igor dlya velikih igor yak ot shahi zaveliki dlya poshuku Zamist cogo programa dlya gri v shahi zdijsnyuye poshuk u chastkovomu derevi gri yak pravilo stilki hodiv iz potochnoyi poziciyi skilki vona mozhe znajti za dostupnij chas Za vinyatkom vipadkiv patologichnih igrovih derev yaki ye dosit ridkisnimi na praktici zbilshennya glibini poshuku zagalom pokrashuye jmovirnist viboru najkrashogo hodu Igri dlya dvoh takozh mozhut buti predstavleni u viglyadi en Shob pershij gravec vigrav partiyu maye isnuvati vigrashnij hid dlya vsih hodiv drugogo gravcya Ce predstavleno v i abo derevi za dopomogoyu diz yunkciyi dlya predstavlennya alternativnih hodiv pershogo gravcya ta vikoristannya kon yunkciyi dlya predstavlennya vsih hodiv drugogo gravcya Virishennya igrovih derevDeterminovanij algoritm Povnistyu kolorove dovilne derevo gri z determinovanim algoritmom Zavdyaki povnomu derevu gri mozhna rozv yazati gru tobto znajti poslidovnist hodiv yaku mozhe vikonuvati pershij abo drugij gravec sho garantuye najkrashij mozhlivij rezultat dlya cogo gravcya zazvichaj vigrash abo nichiya Determinovanij algoritm yakij zazvichaj nazivayut zvorotnoyu indukciyeyu abo retrospektivnim analiz mozhna opisati rekursivno nastupnim chinom Rozfarbujte ostannij riven dereva gri takim chinom shob usi peremogi Gravcya 1 buli zabarvleni odnim kolorom sinij na diagrami usi peremogi Gravcya 2 inshim chervonim na diagrami a vsi nichiyi tretim sirim na diagrami Povernitsya do vuzliv verhnogo rivnya Yaksho odin iz siniv vuzla maye protilezhnij kolir potochnogo gravcya rozfarbujte vuzol kolorom cogo sina Yaksho vsi sini vuzla togo samogo koloru sho j potochnij gravec pofarbujte cej vuzol u toj samij kolir V inshomu vipadku rozfarbujte cej vuzol kolorom nichiyeyi Povtoryujte krok 2 ruhayuchis vgoru doki vsi vuzli ne budut rozfarbovani Kolir korenevogo vuzla viznachatime harakter gri Zazvichaj mozhna rozv yazati gru u comu tehnichnomu sensi rozv yazuvannya vikoristovuyuchi lishe pidmnozhinu dereva gri tomu sho v bagatoh igrah hid ne potribno analizuvati oskilki ye inshij hid yakij ye krashim dlya togo zh gravcya Ce princip yakij vikoristovuyetsya dlya alfa beta vidsichennya yake mozhna vikoristovuvati v bagatoh determinovanih igrah Bud yake pidderevo yake mozhna vikoristovuvati dlya virishennya gri vidome yak derevo rishen a rozmir derev rishen riznoyi formi vikoristovuyetsya yak mira en Randomizovanij algoritm Randomizovani algoritmi mozhna vikoristovuvati dlya virishennya igrovih derev U takogo tipu realizaciyi dvi osnovni perevagi shvidkist i praktichnist Todi yak determinovanu versiyu rozv yazuvannya igrovih derev mozhna vikonati za O n randomizovanij algoritm maye ochikuvanij chas vikonannya 8 n0 792 yaksho kozhen vuzol u igrovomu derevi maye stupin 2 Krim togo ce praktichno oskilki randomizovani algoritmi zdatni zavaditi vorogu tobto suprotivnik ne mozhe peremogti sistemu igrovih derev znayuchi algoritm yakij vikoristovuyetsya dlya virishennya igrovogo dereva oskilki poryadok rozv yazuvannya ye vipadkovim Nizhche navedeno realizaciyu algoritmu virishennya randomizovanogo dereva igor def gt eval rand u gt bool Returns True if this node evaluates to a win otherwise False if u leaf return u win else random children gt eval rand child for child in random order u children if u op OR return any random children if u op AND return all random children Algoritm vikoristovuye ideyu korotkogo zamikannya yaksho korenevij vuzol vvazhayetsya operatorom ABO to yak tilki znajdeno odin True korin klasifikuyetsya yak True i navpaki yaksho korenevij vuzol vvazhayetsya operatorom I todi yak tilki znajdeno odin False korin klasifikuyetsya yak False Div takozhVidsichennya alfa beta Nekooperativna gra Chislo Shennona en PrimitkiZuckerman Inon Wilson Brandon Nau D 2018 Avoiding game tree pathology in 2 player adversarial search angl n2 0360 5442 Search Results www worldcat org Nau Dana S 1 listopada 1982 An investigation of the causes of pathology in games Artificial Intelligence angl T 19 3 s 257 278 doi 10 1016 0004 3702 82 90002 9 ISSN 0004 3702 1994 Searching for Solutions in Games and Artificial Intelligence PDF Ph D Thesis University of Limburg Maastricht The Netherlands ISBN 90 900748 8 0 2013 SI486D Randomness in Computing Game Trees Unit United States Naval Academy Computer Science Department Arhiv originalu za 8 travnya 2021 Procitovano 28 listopada 2022 Pekar Libor Matusu Radek Andrla Jiri Litschmannova Martina September 2020 Review of Kalah Game Research and the Proposition of a Novel Heuristic Deterministic Algorithm Compared to Tree Search Solutions and Human Decision Making Informatics angl 7 3 34 doi 10 3390 informatics7030034 LiteraturaHu Te Chiang Shing Man tak 2002 Combinatorial Algorithms Courier Dover Publications ISBN 0 486 41962 2 Procitovano 2 kvitnya 2007 Heuristics Addison Wesley 1984 Aske Plaat Jonathan Schaeffer Wim Pijls and Arie de Bruin Exploiting Graph Properties of Game Trees