Реферат Альфа-бета відсіканя (Alpha-Beta Pruning) при програмуванні комп'ютерних ігор (реферат)


СкачатиСкачать (DOC|ZIP):
Альфа-бета відсіканя (Alpha-Beta Pruning) при програмуванні

Альфа-бета відсіканя

(Alpha-Beta Pruning) при програмуванні

компютерних ігор

ВСТУП

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

Визначені основні поняття, зв'язані з деревом гри, описується процедура, називана альфа-бета відсіканнями (alpha-beta pruning), і тісно зв'язаний з нею метод, однак, не настільки ефективний, оскільки він не робить "нижніх відсікань"; тут же доведена коректність обох методів.

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

1. Ігри й оцінки позицій

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

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

Якщо з позиції p є d дозволених ходів p1,...,pd, виникає проблема вибору кращого з них. Будемо називати хід найкращим, якщо по закінченні гри він приносить найбільший можливий виграш за умови, що супротивник вибирає ходи, найкращі для нього (у тім же змісті). Нехай F(p) є найбільший виграш, досяжний у позиції p гравцем, якому належить черга ходу, проти оптимального захисту. Т.к. після ходу в позицію pi виграш цього гравця дорівнює -F(pi), маємо

(1)

Ця формула дозволяє индуктивно визначити F(p) для кожної позиції p.

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

(2) g(p) = -f(p).

Max намагається максимізувати свій кінцевий виграш, а Min намагається мінімізувати його. Співвідношенню (1) при цьому відповідають дві функції, саме

(1') ,

що задає максимальний гарантований виграш гравця Max у позиції p, і

,

що дорівнює оптимуму, досяжному для гравця Min. Як і раніш, тут передбачається, що p1,...,pd є дозволені в позиції p ходи. Індукцією по числу ходів легко показати, що функції, обумовлені співвідношеннями (1) і (3), збігаються і що для всіх p

(5) G(p) = -F(p).

Таким чином, обидва підходи еквівалентні.

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

Функція F(p) дорівнює тому максимуму, що гарантований, якщо обоє гравця діють оптимально. Випливає, однак, видно, що вона відбиває результати дуже обережної стратегії, що не обов'язково гарна проти поганих чи гравців гравців, що діють відповідно до іншого принципу оптимальності. Нехай, наприклад, є два ходи в позиції p1 і p2, причому p1 гарантує нічию (виграш 0) і не дає можливості виграти, у той час, як p2 дає можливість виграти, якщо супротивник перегляне дуже тонкий хід, що виграє. У такій ситуації ми можемо віддати перевагу ризикованому ходу в p2, якщо тільки ми не упевнені в тім, що наш супротивник всемогутній. Дуже можливо, що люди виграють у шахових програм у такий саме спосіб.

2. Розробка алгоритму

Нижченаведений алгоритм (на спеціально придуманій алголоподібній мові), мабуть, обчислює F(p) відповідно до визначення (1):

integer procedure F(position p):

begin integer m,i,t,d;

Визначити позиції p1,...,pd, підлеглі p;

if d = 0 then F := f(p) else

begin

m := -;

for i:= 1 step 1 until d do

begin

t := -F(pi);

if t > m then m:= t;

end;

F := m;

end;

end.


СкачатиСкачати:Альфа-бета відсіканя (Alpha-Beta Pruning) при програмуванні


Схожі реферати:
  • РЕФЕРАТ на тему: Закон вартості та його роль в транзитній та сучасній економіці ПЛАН ВСТУП 1. ЗМІСТ ЗАКОНУ ВАРТОСТІ 2. ФУНКЦІЇ ЗАКОНУ ВА
  • Загартування шкіри (реферат)
  • Центральні банки, їх походження, призначення (реферат)
  • Облік реалізації товарів. Основна діяльність підприємства торгівлі операції купівлі-продажу товарів, оскільки вони є головною метою його створення і
  • Центральний підприємницький ремесловий реєстр (реферат)
  • Оповідання Володимира Винниченка для дітей та методика їх вивчення на уроках позакласного читання та в позаурочний час (дипломна)
  • План Історія виникнення адвокатури та поняття адвокатська таємниця . Адвокатська таємниця. Охорона адвокатської таємниц: етика, деонтологія, право. Начерк історії адв
  • ј ЅВЇАЙё№ДЅЇИЙЖ№ "ЭmЫ/puЦаЭsЬЭnЫ/1229642/ЭmХЫЩ001.ЮpЫ" Р* Б№Ж"№єГЖБAИЅВ№И јј Остапенко С.С. - керівник уряду УНР у 1919р.  (1881 1937) (керув
  • РЕФЕРАТ на тему: Фондові біржі Поняття фондової біржі. Короткий світовий огляд фондової діяльності. Фондова біржа являє собою певним чином
  • Інвестиції і інвестиційна діяльність. Економічна суть інвестицій (реферат)




  • Скористайтеся пошуком:
    Loading

    Пошук :

    0.032976