Двох осіб з повною інформацією

Ігри

Лекція 4.20.

1. Приклади: шахи, шашки тощо.

2. Участь двох гравців, що ходять по черзі та мають повну інформацію про поточну ігрову ситуацію.

3. Гра є кінченою по досягненні позиції, яка згідно до правил гри є "термінальною" (кінцевою) з фіксацією результату гри, наприклад матова позиція в шахах.

4. Можливе подання у формі дерева гри (або ігрового дерева), чиї вершини фіксують ситуації (коренева вершина - початкова ситуація, листи - термінальні позиції), а дуги - ходи.

5. Обмежуються лише двома типами результатів - виграш і програш.

6. Два учасники гри "гравець" і "супротивник":

§ гравець може виграти в деякій нетермінальній позиції з ходом гравця ("позиції гравця"), якщо в нійіснує дозволений хід, що веде до виграшу;

§ з іншого боку, деяка нетермінальна позиція з ходом супротивника ("позиція супротивника") є виграною для гравця, якщо всі дозволені ходи із цієї позиції ведуть до позицій, у яких можливий виграш.

Ці правила повністю відповідають поданню задач у формі І/Або-дерева. Між поняттями щодо І/Або-дерева і поняттями ігор існує взаємно однозначна відповідність:

позиції гри вузли, вершини, задачі

термінальні позиції цільові вузли,

виграшу тривіально розв'язувані задачі

термінальні позиції задачі, що не мають

програшу рішення

виграні позиції задачі, що мають рішення

позиції гравця Або-вузли

позиції супротивника І-вузли

Вочевидь, що й поняття щодо пошуку в І/Або-деревах можна визначити в термінах пошуку в ігрових деревах.

Нижче наведено просту програму, що визначає, чи є деяка позиція виграною для гравця.

вигр(Поз) :-

терм_вигр( Поз). % Термінальна виграна позиція

вигр(Поз) :- not терм_прогр(Поз),

хід(Поз, Поз1), % Дозволений хід в Поз1

not (хід(Поз1, Поз2),

not вигр( Поз2) ).% Жоден з ходів супротивника

не веде до не-виграшу

Тут правила гри вбудовані в предикат хід(Поз, Поз1), що породжує всі дозволені ходи, а також у предикати терм_вигр(Поз) і терм_прогр(Поз), які розпізнають термінальні позиції, що є, відповідно до правил гри, виграними або програними.

1. Ця програма використає стратегію вглиб та демонструє основні принципи програмування ігор.

2. Але практично прийнятна реалізація таких складних ігор, як шахи або го, вимагала б залучення значно могутніших методів.

3. Величезна комбінаторна складність цих ігор робить наївний перебірний алгоритм, що переглядає дерево аж до термінальних позицій, абсолютно непридатним.

4. Цей висновок ілюструє (на прикладі шахів) рис. 1: простір пошуку має астрономічні розміри - близько 10¹²⁰ позицій, що перебуває далеко за межами можливостей комп’ютерів.

Рис. 1. Складність ігрових дерев у шахах. Оцінки згідно тому, що: а) в кожній шаховій позиції існує приблизно 30 дозволених ходів; б) термінальні позиції розташовані на глибині у 40 ходів. Один хід включає два напівходи - по одному на кожного гравця.

2. Мінімаксний принцип єстандартним у пошуку в ігрових (особливо в шахових) програмах:

§ Дерево гри проглядається лише до деякої глибини (звичайно на кілька ходів), а потім для всіх його кінцевих вершин обчислюються оцінки згідно до деякої оцінюючої функції.

§ Далі оцінки кінцевих вершин поширюються нагору по дереву пошуку згідно до мінімаксного принципу. У результаті всі вершини дерева пошуку одержують оцінки.

§ І нарешті, ігрова програма, що бере участь у деякій грі, робить свій хід - той, що веде з початкової позиції в найперспективнішого (за оцінкою) її спадкоємця.

Тут використано два різних об’єкти - "дерево гри" і "дерево пошуку": дерево пошуку - це лише частина дерева гри (його верхня частина), тобто та його частина, що була явно породжена в процесі пошуку.

§ Дуже багато залежить від оцінюючої функції шансів на виграш одного з учасників гри.

§ Чим вища оцінка, тим більше шансів на виграш у гравця, і чим вона нижча, тим більше шансів на виграш у супротивника.

§ Оскільки один з учасників гри завжди прагне до високих оцінок, а інший - до низьких, їх іменують МАКС і МІН відповідно. МАКС завжди обирає хід з максимальною оцінкою, а МІН - хід з мінімальною оцінкою.

Керуючись мінімаксним принципом і знаючи значення оцінок для всіх вершин "підніжжя" дерева пошуку, можна визначити оцінки всіх інших вершин дерева. На рис. 2 показано, як це робиться крізь пари рівнів позицій з ходом Макс'а та з ходом Мін'а:

§ Оцінки вершин найнижчого рівня визначаються за допомогою оцінюючої функції.

§ Оцінки внутрішніх вершин визначаються, рухаючись знизу нагору від рівня до рівня, аж до кореня дерева.

Рис. 2. Статичні (нижній рівень) і мінімаксні оцінки вершин дерева пошуку. Виділені ходи фіксують основний варіант, тобто мінімаксно-оптимальну гру по обидва боки.

У результаті, згідно прикладу (рис. 2), оцінка кореня стає рівною 4, і, відповідно, з позиції а кращим ходом Макс'а буде a-b. Краща відповідь Мін'а на цей хід - b-d, і т.д. Цю послідовність ходів називають основним варіантом, який показує "мінімаксно-оптимальну" гру для обох учасників.

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

Правила поширення оцінок формулюють в такий спосіб. Статичну оцінку позиції Р позначають через v(P), а її робочу оцінку - через V(Р). Нехай Р₁, ..., Р_n - дозволені спадкоємці позиції Р. Тоді співвідношення між статичними й робочими оцінками можна записати так:

V( Р) = v( P),

якщо Р - термінальна позиція дерева пошуку (n=0).

V(Р) = max V(Р_і ),