• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Генетичний алгоритм

Цей пошук часто показує хорошу продуктивність, але і заходить у глухий кут з наступних причин (рис.2.6):

Рисунок 13.9 – Локальний максимум та плато

1. Локальні максимуми. Подолати їх локальний пошук не в змозі.

2. Плато. Область, в якій евристика не змінюється від ходу до ходу.

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

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

1. Вибираються позиції з кращими значеннями евристик (відбір).

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

3. В отримані нові комбінації вносяться випадкові зміни (мутації).

4. Якщо отримана позиція гірше попередніх, вона відкидається, якщо краще, запам'ятовується (відбір).

5. З наявних кращих позицій все повторюється з п.2.

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

13.4 Пошук в умовах протидії

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

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

Так, показана на ланцюжку: 5 - 3 - 0 сірників нас влаштовує (вузли відображають число сірників, яке залишається після зробленого ходу), але противник так ніколи не буде ходити, а візьме замість трьох сірників дві, що призведе до нашого програшу. Щоб оцінити доцільність того чи іншого ходу, привласнимо нашій перемозі значення 1, а перемогу супротивника - значення 0. У такому випадку наша стратегія полягає в тому, щоб максимізувати результат, а стратегія супротивника - його мінімізувати. Назвемо для ясності супротивника - МІН, а себе - МАКС. Спускаючись по дереву рішень, ми можемо дати оцінку кожному вузлу на самому нижньому рівні (показаний фрагмент дерева).

Рисунок 13.10 – Дерево рішень

Виграш Макс (1) показаний світлої заливкою, виграш МІНА (0) - темною. Припускаючи, що обидва гравці діють у своїх інтересах розумно, ми можемо дати оцінку кожному ходу гравців на кожен рівень вище, а саме: з усіх варіантів ходів МІН віддасть перевагу ті, які дадуть оцінку 0, а МАКС - ходи, що дають оцінку 1. Таким чином, оцінка кожного ходу Максим буде дорівнює мінімуму оцінок ходів у відповідь МІНА і навпаки, оцінка кожного ходу МІНА буде дорівнює максимуму оцінок ходів у відповідь Максим.

Рисунок 13.11 – Дерево рішень

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

У загальному випадку мінімаксний алгоритм складається з наступних кроків:

1. Вибір шкали оцінок результатів гри.

2. Спуск по дереву і привласнення оцінок кінцевим станам.

3. Послідовне привласнення оцінок батьківським вузлам: для МІНА - максимальної з дочірніх, для Максим - мінімальної.

4. Після присвоєння значення початкової позиції можна починати робити ходи.

Очевидним недоліком мінімаксного алгоритму є його трудомісткість, оскільки необхідно виконати обхід усього дерева.

13.5 Шахові програми

Алгоритм минимакса навіть при використанні альфа-бета відсікання все ж вимагає спуску до термінального стану по багатьом галузям, отже, його застосовність сильно обмежена. Іншими словами, на практиці він не використовується, за винятком зовсім простих випадків. Більш практичним є застосування евристичних оцінок кожної позиції без спуску до нижніх листів дерева. Такий підхід використовується, наприклад, в шахових програмах, де шахістами давно відпрацьована методика оцінки як окремих фігур, так і позицій в цілому. Так, пішак має вартість 1, кінь чи слон - 3, тура - 5, ферзь - 9. Оцінюються також такі характеристики, як безпека короля, хороша пешечная структура і т.д. Таким чином, кожен хід може бути відразу оцінений. Це не означає, що можна обмежитися глибиною пошуку в один хід. Хороша позиція може бути досягнута через 5 або 8 ходів.

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

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

Перша шахова програма була розроблена в 1951 році Аланом Тьюрінгом. Ця програма практично не експлуатувалася, а її алгоритм перевірявся шляхом моделювання вручну.

Першою успішною вітчизняної програмою стала Kaissa, розроблена в 1974 році в Інституті теоретичної та експериментальної фізики під керівництвом екс-чемпіона світу М.Ботвінніка. Це програма перемогла на першому чемпіонаті світу з комп'ютерних шахів в Стокгольмі.

Найкращою шаховою програмою, яка перемогла Гаррі Каспарова в 1997 році, є Deep Blue, створена в компанії IBM. Програма працювала на паралельному комп'ютері з 30 процесорами IBM RS/6000. На цьому комп'ютері експлуатувалися кошти «програмного пошуку» і 480 спеціалізованих НВІС шахових процесорів, що виробляють ходи. На цьому комп'ютері програма Deep Blue в середньому здійснювала пошук 126000000 вузлів в секунду, а пікова швидкість складала 330 мільйонів. На кожен хід програма формувала до 30 мільярдів позицій, досягаючи глибини пошуку 14. Основою програми є звичайний альфа-бета пошук з ітеративним поглибленням, але ключовою особливістю програми є здатність поглиблювати пошук у цікавих позиціях до 40 ходів. Крім звичайного пошуку програма використовувала довідник дебютів з 4000 позицій, велику базу ендшпіль і базу з 700 000 ігор гросмейстерів. Тільки така добавка до програми дозволила зрівняти її з чемпіоном світу, який також володіє такими знаннями і використовує шаблонні рішення.

Група розробників Deep Blue відмовилася від запропонованого Каспаровим реваншу. Замість цього на змаганнях в 2002 році проти Володимира Крамника виступила програма Deep Fritz, вже на звичайному персональному комп'ютері. Deep Fritz - це розробка Франса Морхен (Голландія) і Матіаса Фієста (Німеччина). У цій програмі застосована техніка нульового ходу (null move), що полягає в тому, що в ході пошуку гравцеві дозволяється зробити два ходи підряд (інший гравець пропускає хід). Завдяки цьому легше виявляються слабкі ходи. Матч з восьми ігор проти Deep Fritz закінчився нічиєю, що дозволило Крамнику заявити: «Тепер очевидно, що ця найкраща шахова програма і чемпіон світу грають на рівних».

Читайте також:

1. Rete-алгоритм
2. Алгоритм
3. Алгоритм
4. Алгоритм 1.
5. Алгоритм RLE
6. Алгоритм безпосередньої заміни
7. Алгоритм Берлекемпа-Мессі
8. Алгоритм відшукання оптимального плану.
9. Алгоритм Дейкстри.
10. Алгоритм Деккера.
11. Алгоритм Деккера.
12. Алгоритм діагностики при травмах живота.

Переглядів: 1434