Дерево гри

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

У контексті комбінаторної теорії ігор, яка зазвичай вивчає послідовні ігри з повною інформацією, дерево гри — це графік, що представляє всі можливі стани гри в такій грі. До таких ігор належать такі відомі, як шахи, шашки, ґо та хрестики-нулики. Дерево гри можна використовувати для вимірювання складності гри[en], оскільки воно представляє всі можливі способи, якими гра може розвиватися. Через великі ігрові дерева складних ігор, таких як шахи, алгоритми, розроблені для гри в цей клас ігор, використовуватимуть часткові ігрові дерева, що робить обчислення можливими на сучасних комп'ютерах. Існують різні методи розгадування ігрових дерев. Якщо можна створити повне дерево гри, можна використати детермінований алгоритм, такий як зворотна індукція або ретроспективний аналіз. Рандомізовані алгоритми та мінімаксні алгоритми, такі як дерево пошуку Монте-Карло, можна використовувати у випадках, коли повне дерево гри неможливо.

Розуміння дерева гри[ред. | ред. код]

Перші два шари дерева гри для хрестиків-нуликів.

Щоб краще зрозуміти дерево гри, його можна розглядати як техніку для аналізу змагальних ігор, яка визначає дії, які виконує гравець, щоб виграти гру. У теорії ігор дерево гри — це орієнтований граф, вузли якого є позиціями в грі (наприклад, розташування фігур у настільній грі), а ребра — ходами (наприклад, для переміщення фігур з однієї позиції на дошці в іншу).[1]

Повне дерево гри для гри — це таке дерево гри, яке починається з початкової позиції та містить усі можливі ходи з кожної позиції; повне дерево є таким самим деревом, яке було отримано з представлення гри у розгорнутому вигляді[en]. Точніше кажучи, повна гра є нормою для гри в теорії ігор, яка може чітко висловити багато важливих аспектів. Наприклад, послідовність дій, які можуть виконувати зацікавлені сторони, їхній вибір у кожній точці прийняття рішення, інформація про дії, вжиті іншими зацікавленими сторонами, коли кожна зацікавлена сторона приймає рішення, і переваги всіх можливих результатів гри.[2]

На діаграмі показано перші два шари в дереві гри для хрестиків-нуликів. Обертання та відображення позицій еквівалентні, тому перший гравець має три варіанти ходу: у центрі, на краю або в кутку. Другий гравець має два варіанти відповіді, якщо перший гравець грав у центрі, інакше п'ять варіантів. І так далі.

Кількість листових вузлів у повному дереві гри — це кількість можливих різних способів гри. Наприклад, дерево гри для хрестиків-нуликів має 255168 листових вузлів.

Ігрові дерева важливі для штучного інтелекту, тому що один із способів вибрати найкращий хід у грі — це пошук у дереві гри за допомогою будь-якого з численних алгоритмів пошуку по дереву в поєднанні з мінімаксними правилами для скорочення дерева. У дереві гри для хрестиків-нуликів можна легко шукати, але повні дерева ігор для великих ігор, як-от шахи, завеликі для пошуку. Замість цього програма для гри в шахи здійснює пошук у частковому дереві гри: як правило, стільки ходів із поточної позиції, скільки вона може знайти за доступний час. За винятком випадків «патологічних» ігрових дерев[3] (які є досить рідкісними на практиці), збільшення глибини пошуку загалом покращує ймовірність вибору найкращого ходу.

Ігри для двох також можуть бути представлені у вигляді і-або дерев[en]. Щоб перший гравець виграв партію, має існувати виграшний хід для всіх ходів другого гравця. Це представлено в і-або дереві за допомогою диз'юнкції для представлення альтернативних ходів першого гравця та використання кон'юнкції для представлення всіх ходів другого гравця.

Вирішення ігрових дерев[ред. | ред. код]

Детермінований алгоритм[ред. | ред. код]

Повністю кольорове довільне дерево гри з детермінованим алгоритмом

Завдяки повному дереву гри можна «розв'язати» гру — тобто знайти послідовність ходів, яку може виконувати перший або другий гравець, що гарантує найкращий можливий результат для цього гравця (зазвичай виграш або нічія). Детермінований алгоритм (який зазвичай називають зворотною індукцією або ретроспективним аналіз) можна описати рекурсивно наступним чином.

  1. Розфарбуйте останній рівень дерева гри таким чином, щоб усі перемоги Гравця 1 були забарвлені одним кольором (синій на діаграмі), усі перемоги Гравця 2 — іншим (червоним на діаграмі), а всі нічиї — третім (сірим на діаграмі).
  2. Поверніться до вузлів верхнього рівня. Якщо один із синів вузла має протилежний колір поточного гравця, розфарбуйте вузол кольором цього сина. Якщо всі сини вузла того самого кольору, що й поточний гравець, пофарбуйте цей вузол у той самий колір. В іншому випадку розфарбуйте цей вузол кольором нічієї.
  3. Повторюйте крок 2, рухаючись вгору, доки всі вузли не будуть розфарбовані. Колір кореневого вузла визначатиме характер гри.

Зазвичай можна розв'язати гру (у цьому технічному сенсі «розв'язування»), використовуючи лише підмножину дерева гри, тому що в багатьох іграх хід не потрібно аналізувати, оскільки є інший хід, який є кращим для того ж гравця. Це принцип, який використовується для альфа-бета відсічення, яке можна використовувати в багатьох детермінованих іграх.

Будь-яке піддерево, яке можна використовувати для вирішення гри, відоме як дерево рішень, а розмір дерев рішень різної форми використовується як міра складності гри[en].[4]

Рандомізований алгоритм[ред. | ред. код]

Рандомізовані алгоритми можна використовувати для вирішення ігрових дерев. У такого типу реалізації дві основні переваги: швидкість і практичність. Тоді як детерміновану версію розв'язування ігрових дерев можна виконати за Ο(n), рандомізований алгоритм має очікуваний час виконання θ(n0.792), якщо кожен вузол у ігровому дереві має ступінь 2. Крім того, це практично, оскільки рандомізовані алгоритми здатні «завадити ворогу», тобто супротивник не може перемогти систему ігрових дерев, знаючи алгоритм, який використовується для вирішення ігрового дерева, оскільки порядок розв'язування є випадковим.

Нижче наведено реалізацію алгоритму вирішення рандомізованого дерева ігор:[5] 

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.[6]

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. ↑ Zuckerman, Inon; Wilson, Brandon; Nau, D. (2018). Avoiding game‐tree pathology in 2‐player adversarial search (англ.).
  2. ↑ n2:0360-5442 - Search Results. www.worldcat.org.
  3. ↑ 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.
  4. ↑ Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0.
  5. ↑ Daniel Roche (2013). SI486D: Randomness in Computing, Game Trees Unit. United States Naval Academy, Computer Science Department. Архів оригіналу за 8 травня 2021. Процитовано 28 листопада 2022.
  6. ↑ 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.

Література[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Дерево_гри&oldid=38413568