Використання евристик в іграх

вирішується систематичним перебором всіх можливих ходів і контрзаходів супротивника. Потім розглянемо ігри, в яких повний перебір або неможливий, або небажаний. Оскільки в таких іграх можна проглянути тільки обмежену частину простору станів, гравець вимушений використовувати евристику, щоб прийти до перемоги.

Гра "нім" (nim) — це одна з ігор, простір станів якої допускає вичерпний пошук. У цій грі на стіл між двома супротивниками викладається деяке число фішок. При кожному ході гравець повинен розділити "купку" фішок на два непорожні набори різних розмірів. Наприклад, 6 фішок можна розділити на групи 5 і 1 або 4 і 2, але не 3 і 3. Перший гравець, який не зможе більше зробити хід, програє. Для розумного числа фішок в просторі станів цієї гри можна реалізувати повний перебір. На мал. 1 показаний простір станів для 7 фішок.

У іграх, що не допускають вичерпного опису простору станів, основна трудність полягає в прогнозі дій супротивника. Простій спосіб врахувати такі дії — припустити, що ваш супротивник використовує ті ж самі знання про простір станів, що і ви, і застосовує ці знання для своєї перемоги. Хоча це припущення має свої обмеження, воно дає розумну основу для прогнозу поведінки супротивника. Метод мінімакса реалізує пошук в ігровому просторі з урахуванням цього припущення.

Назвемо супротивників в грі MIN і МАХ. Ці імена вибрані з наступних причин: МАХ представляє гравця, що намагається виграти, або максимізувати свою перевагу, а MIN — супротивника, який намагається мінімізувати рахунок свого опонента. Передбачається, що MIN використовує ту ж саму інформацію і завжди намагається досягти найгіршого МАХ стану

При реалізації стратегії мінімакса помітимо кожен рівень в області пошуку ім'ям гравця, що виконує черговий хід: MIN або МАХ. У прикладі на мал. 2 перший хід робить MIN. Кожному листовому вузлу привласнимо значення 1 або 0, залежно від переможця: МАХ або MIN. В процесі реалізації процедури мінімакса ці значення передаються вгору по графові згідно наступному правилу.

• Якщо батьківський стан є вузлом МАХ, то йому привласнюють максимальне значення.

• Якщо батьківський стан — вузол MIN, то йому привласнюють мінімальне значення.

Значення, що пов'язується таким чином з кожним станом, відображає якнайкращий стан, якого цей гравець може досягти (зважаючи на дії супротивника відповідно до алгоритму мінімакса). Таким чином, набутих значень використовуються для того, щоб вибрати якнайкращий серед можливих кроків. Результат застосування алгоритму мінімакса до графа простору станів для гри "нім" показаний на мал. 2.

Значення вершинам привласнюються від низу до верху на основі принципу мінімакса. Оскільки будь-який з можливих перших кроків MIN веде до вершин із значенням 1, другий гравець, МАХ, завжди може перемогти, незалежно від першого ходу MIN. MIN може перемогти тільки в тому випадку, якщо МАХ допустить помилку. На мал. 2 видно, що MIN може вибрати будь-який з можливих варіантів першого ходу — всі вони відкривають можливі шляхи перемоги МАХ, відмічені на малюнку напівжирними лініями із стрілками.

Хоча існують ігри, де можливий повний перебір, все ж таки найцікавішими є випадки, в яких він непридатний.

1 2 3 4 5 6 7 8

Схожі роботи

Реферати

Курсові

Дипломні