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

Вибір(_,_,Поз1,Оц1,Поз1,Оц1).

Прибл_кращ(СписПоз,НовАльфа,НовБета,Поз1,Оц1), вибір(Поз,Оц,Поз1,Оц1,ХорПоз,ХорОц).

Дост_хор(СписПоз,Альфа,Бета,Поз,Оц,ХорПоз,ХорОц).

Стат_оц(Поз,Оц).

прибл_кращ([Поз|СписПоз],Альфа,Бета,ХорПоз,ХорОц):-

альфабета(Поз,Альфа,Бета,_,Оц),

дост_хор([ ],_,_,Поз,Оц,Поз,Оц):-!. %Больш нема кандидатів

дост_хор(_,Альфа,Бета,Поз,Оц,Поз,Оц):-

хід_міна(Поз),Оц>Бета,!; %Перехід через верхню гран

хід_макса(Поз),Оц<Альфа,!. %Перехід через нижню гран

дост_хор(СписПоз,Альфа,Бета,Поз,Оц,ХорПоз,ХорОц):-

нов_границі(Альфа,Бета,Поз,Оц,НовАльфа,НовБета),
% Уточнює границі

нов_границі(Альфа,Бета,Поз,Оц,Оц,Бета):-

хід_міна(Поз),Оц>Альфа,!. %Збільшує нижню границю

нов_границі(Альфа,Бета,Поз,Оц,Альфа,Оц):-

хід_макса(Поз),Оц<Бета,!. % Зменшує верхню границю

нов_границі(Альфа,Бета,_,_,Альфа,Бета).

вибір(Поз,Оц,Поз1,Оц1,Поз,Оц):-

хід_міна(Поз),Оц>Оц1,!;

хід_макса(Поз),Оц<Оц1,!.

Відомо, що в найгіршому випадку альфа-бета алгоритм не має ніяких переваг відносно мінімаксного алгоритму повного перебору.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Типові знання й механізм "порад"

Дата добавления: 2014-01-04