Повна версія

Головна arrow Інформатика arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ШАХОВІ ПРОГРАМИ

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

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

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

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

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

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

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

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

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

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

 
<<   ЗМІСТ   >>