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

План

1. Ведення ігор   

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

2. 1. Процедура мінімакса на графах, що допускають повний перебір   

2. 2. Мінімакс при фіксованій глибині пошуку   

2. 3. Процедура альфа–бета-усікання       

3. Стратегії пошуку в просторі станів на основі даних і від цілі   

 

1. Ведення ігор

Багато ранніх досліджень в області пошуку в просторі станів здійснювалися на основі таких поширених настільних ігор, як шашки, шахи і квачі. Додатково до властивого їм "інтелектуального" характеру такі ігри мають деякі властивості, що роблять їх ідеальним об'єктом для експериментів. Більшість ігор ведуться з використанням чіткого певного набору правил: це дозволяє легко будувати простір пошуку і позбавляє дослідника від неясності і плутанини, властивих менш структурованим проблемам. Позиції фігур легко представлені в комп'ютерній програмі, вони не вимагають створення складних формалізмів, необхідних для передачі семантичних тонкощів складніших наочних областей. Тестування ігрових програм не породжує жодних фінансових або етичних проблем. Пошук в просторі станів — принцип, лежачий в основі більшості досліджень в області ведення ігор.

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

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

Оскільки у більшості з нас є досвід в цих простих іграх, можна спробувати розробити свої евристики і випробувати їх ефективність. Для цього нам не потрібні консультації експертів в якихось темних для необізнаних областях, на зразок медицини або математики. Тому ігри є хорошою основою для вивчення евристичного пошуку. Програми ведення ігор, не дивлячись на їх простоту, ставлять перед дослідниками нові питання, включаючи варіант, при якому ходи супротивника неможливо детерміновано передбачити. Наявність супротивника ускладнює структуру програми, додаючи в неї елемент непередбачуваності і потребу приділяти увагу психологічним і тактичним чинникам ігрової стратегії.

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

У той час дві протилежні концепції викликали численні спори. Кращі гравці розрізняли два принципові типи Гри — формальний і психологічний.

— Герман Гессе (Hermann Hesse), Магістр Луди (Гра в бісер)

2. 1. Процедура мінімакса на графах, що допускають повний перебір

Ігри завжди були важливою прикладною областю для евристичних алгоритмів. Ігри для двох чоловік складніші, ніж прості головоломки із-за існування "ворожого" і, по суті, непередбачуваного супротивника. Такі ігри не тільки забезпечують деякі цікаві можливості для розвитку евристик, але і створюють великі труднощі в розробці алгоритмів пошуку.

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

1 2 3 4 5 6 7 8

Схожі роботи

Реферати

Курсові

Дипломні