Ключевая идея альфа – бета отсечения состоит в том, чтобы найти ход не обязательно лучший, но "достаточно хороший" для того, чтобы принять правильное решение. Эту идею можно формализовать, введя два граничных значения, обычно обозначаемых Альфа и Бета,между которыми должна находиться рабочая оценка позиции. Альфа – это самое маленькое значение оценки, которое к настоящему моменту уже гарантировано для игрока МАКС; Бета – это самое большое значение оценки, но которое МАКС пока еще может надеяться. Таким образом, действительное значение оценки всегда лежит между Альфа и Бета. Если же стало известно, что оценка некоторой позиции лежит вне интервала Альфа – Бета, то этого достаточно для того, чтобы сделать вывод: данная позиция не входит в основной вариант. При этом точное значение оценки такой позиции знать не обязательно, его надо знать только тогда, когда оценка лежит между Альфа и Бета.
"Достаточно хорошую" рабочую оценку V(P, Альфа, Бета) позиции Р можно определить как любое значение, удовлетворяющее следующим ограничениям:
- не более Альфа, если оценка позиции Р меньше либо равна Альфа;
- не менее Бета, если оценка позиции Р больше или равна Бета;
- точно равна оценке V(P), если оценка позиции Р находится между значениями Альфа и Бета.
Эффективность альфа – бета процедуры зависит от порядка, в котором просматриваются позиции. Всегда лучше рассматривать самые сильные ходы с каждой из сторон. В наихудшем случае альфа – бета процедура выполняет полный перебор вершин дерева.
Заключение
Минимаксный принцип и альфа – бета алгоритм лежат в основе многих удачных игровых программ, чаще всего шахматных. Общая схема подобной программы такова: произвести альфа – бета поиск из текущей позиции вплоть до некоторого предела по глубине (диктуемого временными ограничениями турнирных правил). Для оценки терминальных поисковых позиций использовать подобранную специально для данной игры оценочную функцию. Затем выполнить наилучший ход, найденный альфа – бета алгоритмом, принять ответный ход противника и запустить тот же цикл с начала.
Многое зависит от оценочной функции. Если была бы известна абсолютно точная оценочная функция, то можно было бы ограничить поиск рассмотрением только непосредственных преемников текущей позиции, фактически исключив перебор. В общем случае такая функция является эвристической.
Использованы источники
1. Уоссермен Ф., Нейрокомпьютерная техника, - М.,Мир, 1992.
2. Горбань А.Н. Обучение нейронных сетей. - М.: ПараГраф, 1990
3. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере. - Новосибирск: Наука, 1996
4. Gilev S.E., Gorban A.N., Mirkes E.M. Several methods for accelerating the training process of neural networks in pattern recognition // Adv. Modelling & Analysis, A. AMSE Press. – 1992. – Vol.12, N4. – P.29-53
5. С. Короткий. Нейронные сети: алгоритм обратного распространения.
6. С. Короткий, Нейронные сети: обучение без учителя. Artificial Neural Networks: Concepts and Theory, IEEE Computer Society Press, 1992.
7. Заенцев И. В. Нейронные сети: основные модели./Учебное пособие к курсу "Нейронные сети" для студентов 5 курса магистратуры к. электроники физического ф-та Воронежского Государственного университета – e-mail: ivz@ivz.vrn.ru
8. Лорьер Ж.Л. Системы искусственного интеллекта. – М.: Мир, 1991. – 568 с.