Ігри двох осіб із повною інформацією

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

Такі ігри можна подавати у вигляді дерева гри (або ігрового дерева). Вершини цього дерева відповідають ситуаціям, а дуги – ходам. Початкова ситуація гри – це коренева вершина; листки дерева – термінальні позиції.

У більшості ігор цього типу можливі такі результати: виграш, програш і нічия. Розглянемо ігри, які мають тільки два результати – виграш і програш. Ігри, у яких можлива нічия, можна спрощено вважати іграми з двома результатами – виграш і не-виграш. Двох учасників гри будемо називати гравцем і противником. Гравець може виграти в деякій нетермінальній позиції з ходом гравця (позиції гравця), якщо в ній існує який-небудь дозволений хід, який приводить до виграшу. Водночас деяка нетермінальна позиція з ходом противника (позиція противника) є виграна для гравця, якщо всі дозволені ходи з цієї позиції приводять до позицій, у яких можливий виграш. Ці правила повністю відповідають зображенню задач у вигляді І/АБО-дерева. Між поняттями, стосовними І/АБО-дерева, і поняттями, використовуваними в іграх, можна встановити взаємну відповідність таким чином.

Позиція гри – вершини, задачі.

Термінальні позиції виграшу – цільові вершини, тривіальні задачі.

Термінальні позиції програшу – задачі, які не мають розв'язку.

Виграні позиції – задачі, які мають розв'язок.

Позиції гравця – АБО-вершини.

Позиції противника – І-вершини.

Очевидно, що аналогічно поняття, стосовні пошуку в І/АБО-деревах, можна переосмислити в термінах пошуку в ігрових деревах.

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

database

turn(symbol, symbol)

term_v(symbol)

term_p(symbol)

predicates

nondeterm vikt(symbol)

nondeterm turn_not_vikt(symbol, symbol)

clauses

vikt(P):-

term_v(P).

vikt(P):-

not(term_p(P)),

turn(P,P1),

not(term_p(P1)),

not(turn_not_vikt(P1,_)).

turn_not_vikt(P1,P2):-

turn(P1,P2), not(vikt(P2)).

turn(a, b).

turn(a, c).

turn(b, d).

turn(b, e).

turn(c, f).

turn(c, g).

term_v(d).

term_v(e).

term_p(f).

term_p(g).

goal

vikt(a).

Програма перевіряє, чи виграна позиція а. У цьому випадку система дасть відповідь yes, тобто позиція а виграна (як видно з рис. 10, існують ходи з позиції а, які приводять до виграних термінальних позицій d та c). Якщо зробити запит щодо того, чи виграна позиція с, – vikt(c), система дасть відповідь no (не існує жодного ходу з позиції с, який приводить до виграшу).

Рис. 10. Просте дерево гри

У розглядуваному випадку правила гри вбудовані в предикат turn , який породжує всі дозволені ходи, а також у предикати term_v і term_p, що розпізнають термінальні позиції, які згідно з правилами гри є виграні або програні. Вираз not(term_p(P)) означає, що Р – нетермінальна позиція програшу, а вираз not(term_p(P1)) означає, що і наступна після Р позиція теж є нетермінальною позицією програшу. Вираз not(turn_not_vikt(P1,_)) говорить: не існує ходу противника, який приводить до невиграної позиції, іншими словами, усі ходи противника приводять до позицій, виграних із погляду гравця.

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

Вищенаведена програма демонструє основні принципи програмування ігор. Але для практично прийнятної реалізації таких складних ігор, як шахи або го, потрібно застосовувати значно більш потужні методи. Надзвичайна комбінаторна складність таких ігор робить простий алгоритм, який проглядає дерево аж до термінальних ігрових позицій, абсолютно неприйнятним. Наприклад, якщо в кожній шаховій позиції існує приблизно 30 дозволених ходів і термінальні позиції розміщені на глибині 40 ходів, то простір пошуку шахової партії має астрономічні розміри – близько 10¹²⁰ позицій (один хід (два напівходи) – 30301 000 позицій, 40 ходів – 1 000⁴⁰ позицій).