зиції, виграні згідно з правилами гри, наприклад позиції, в яких король противника отримує мат. Позиціях програними відповідають завдання, що не мають рішення. Для того, щоб вирішити ігрову задачу, необхідно побудувати вирішальне дерево, яке гарантуватиме перемогу гравця незалежно від відповідей супротивника. Таке дерево задає повну стратегію досягнення виграшу: для кожного можливого продовження, обраного противником, в дереві стратегії є відповідь хід, що приводить до перемоги. Наприклад, для гри в "тік-так-ту" може бути побудовано повне дерево ходів, яке показано на малюнку 3. Через симетрії ігрового поля тільки два відповідних ходу білих є різними.
Якщо необхідно знайти яке-небудь рішення задачі, то організовується найпростіший пошук у І - АБО дереві, який полягає в систематичному і повному перегляді дерева, не керуючись при цьому будь - якими евристиками. Для складних завдань подібні процедури неефективні через великий комбінаторної складності простору пошуку. Наприклад, для гри в шахи простір пошуку оцінюється в 10 120 позицій! Тому необхідні евристичні алгоритми управління пошуком. Основна ідея цих алгоритмів - перегляд тільки частини дерева ходів. <В В
3. Мінімаксний алгоритм
Існує стандартний метод пошуку, використовуваний в ігрових програмах, заснований на мінімаксних принципі. Дерево ходів проглядається за однією з гілок до максимальної глибини (зазвичай кілька ходів) і оцінюється позиція. Дуже багато залежить від оціночної функції, яка для більшості ігор, є наближеною евристичної оцінкою шансів на виграш одного з учасників гри. Оскільки один з учасників ігри прагне до високих оцінок, а інший - до низьких, то їм даються імена МАКС і МІН відповідно. МАКС завжди вибирає хід з максимальною оцінкою; в противагу йому МІН завжди вибирає хід з мінімальною оцінкою. Користуючись цим мінімаксних принципом і знаючи значення оцінок для всіх вершин підніжжя дерева пошуку, можна визначити оцінки всіх вище розташованих вершин дерева. Оцінки вершин підніжжя дерева робляться за допомогою деякої оціночної функції і називаються статичними. Потім, рухаючись по дереву знизу - вгору, визначається оцінка (динамічна) внутрішніх вершин.
На малюнку 4 показаний принцип оцінювання вершин і виділений жирними лініями основний варіант гри.
Основний варіант показує, яка "мінімакснооптімальная" гра для обох учасників. Необхідно відзначити, що оцінки всіх позицій, входять в основний варіант, однакові.
мінімаксних принцип дозволяє переглядати не повне дерево, а лише обмежене число рівнів в глибину. Однак, пошук в ширину не скорочується. br/>
В
Рисунок 3 - Повне дерево ходів у грі "тік-так-ту"
В
Рисунок 4 - Статичні і мінімаксні оцінки вершин
В В
4. Альфа - бета алгоритм
мінімаксних алгоритм оцінки може бути зроблений більш економним. Для цього може бути використана наступна ідея. Припустимо, що є два варіанти ходу. Як тільки стало відомо, що один хід явно гірше іншого, то можна прийняти правильне рішення, яке не з'ясовуючи, наскільки в точності він гірший. Цей принцип може бути використаний для скорочення дерева пошуку. Для дерева, представленого на малюнку 4, може бути виконана наступна послідовність дій з пошуку ходу:
- початкова позиція "а";
- перехід до "b";
- перехід до "d";
- вибір максимальної з оцінок наступників позиції "d", отримано V (d) = 4;
- повернення до "b" і перехід до "e";
- розгляд першого наступника позиції "e" з оцінкою 5. У цей момент МАКС виявляє, що йому гарантована у позиції "e" оцінка, не менша, ніж 5, незалежно від оцінок інших (можливо, більш бажаних) варіантів ходу. Цього цілком достатньо для того, щоб МІН, навіть не знаючи точної оцінки позиції "E", зрозумів, що в позиції "b" хід у "е" гірше, ніж хід у "d".
На підставі наведеного вище міркування можна знехтувати іншими наступниками позиції "е" і приписати їй наближену оцінку 5. Наближений характер цієї оцінки не надасть ніякого впливу на оцінку позиції "b", а отже і позиції "а".
На цій ідеї заснований альфа - бета алгоритм, призначений для ефективної реалізації мінімаксного принципу. На рис показаний результат застосування альфа - бета алгоритму до дерева, представленого на рисунку 5.
В
Рисунок 5 - Результат застосування альфа - бета алгоритму
Ключова ідея альфа - бета відсікання полягає в тому, щоб знайти хід не обов'язково найкращий, але "достатньо хороший "для того, щоб прийняти правильне рішення. Цю ідею можна формалізувати, ввівши два граничних значення, зазвичай позначаються Альфа і Бета , між якими повинна знаходитися робоча оцінка позиції. Альфа - Це саме маленьке значення оцінки, яке до цього моменту вже гарантовано для гравця МАКС; Бета - це найбільше значення оцінки, але яке МАКС поки ще може сподіватися. Таким чином, дійсне значен...
