4. Мінімаксні ігрові програми: удосконалення і обмеження

Мінімаксний принцип і альфа-бета алгоритм лежать в основі багатьох вдалих ігрових програм; найвідоміші з них - шахові. Загальна схема подібної програми така:

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

2. для оцінки термінальних пошукових позицій використати спеціальну оцінюючу функцію;

3. потім виконати найкращий хід, знайдений альфа-бета алгоритмом;

4. прийняти відповідь і розпочати той же цикл.

Тому, двома основними складовими ігрової програми є:

• альфа-бета алгоритм і

• евристична оцінна функція.

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

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

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

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

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

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

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

• враховує контроль часу: по досягненню часової межі завжди є хід, кращий із знайдених на цей момент;

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

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

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

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

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

Знання в мінімаксних ігрових програмах приймають наступні три основні форми:

• Функція оцінки.

• Евристики для відсікання піддерев дерев.

• Евристики для розпізнавання спокійних позицій.

Функція оцінки зводить всі різноманітні аспекти ігрової ситуації до одного числа, і таке спрощення може завдати шкоди.

На противагу цьому розуміння гравцем ігрової позиції є багатовимірним.

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