UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваАльфа-бета відсіканя (Alpha-Beta Pruning) при програмуванні комп’ютерних ігор (реферат)
Автор
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось1802
Скачало179
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

(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), маємо

 

 

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

 

У більшості роботи з теорії ігор використовується ледве інше

формулювання; у ній гравці називаються Max і Min і виклад ведеться з

"точки зору" гравця Max. Таким чином, якщо p є термінальна позиція з

ходом Max, його виграш дорівнює, як і раніш f(p), якщо ж у термінальній

позиції p ходити повинен Min, те його виграш дорівнює

 

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

 

Max намагається максимізувати свій кінцевий виграш, а Min намагається

мінімізувати його. Співвідношенню (1) при цьому відповідають дві

-----> Page:

0 [1] [2] [3] [4] [5] [6]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ