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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

Цей пошук часто показує хорошу продуктивність, але і заходить у глухий кут з наступних причин (рис.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. Алгоритм діагностики при травмах живота.

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