Альфа-бета отсечение

Альфа-бета отсечение (англ. Alpha-beta pruning) — это алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакс. Этот алгоритм предназначен для антагонистических игр и используется для машинной игры (в шахматах, го и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета отсечение является оптимизацией, так как результаты работы оптимизируемого алгоритма не изменяются.

История

Аллен Ньюэлл и Герберт Саймон, использовавшие то, что Джон Маккарти назвал «аппроксимацией»^[1] в 1958 году, написали, что альфа-бета отсечение «кажется, изобреталось неоднократно»^[2]. Артур Самуэль, Ричардс, Харт, Левин, Эдвардс независимо предлагали ранние версии этого алгоритма^[3]. Маккарти также выдвигал подобные идеи на Дартмутском семинаре в 1956 году, а затем, в 1961 году, предложил для исследования группе своих студентов в MIT, включая Алана Котока^[4]. Александр Брудно независимо открыл алгоритм и опубликовал свои результаты в 1963 году^[5]. В 1975 году Дональд Кнут и Рональд У. Мур усовершенствовали алгоритм (добавив «бета» отсечения).^[6][7]

Оптимизация Минимакс

Преимущество альфа-бета отсечения фактически заключается в том, что некоторые из ветвей подуровней дерева поиска могут быть исключены после того, как хотя бы одна из ветвей уровня рассмотрена полностью. Так как отсечения происходят на каждом уровне вложенности (кроме последнего), эффект может быть весьма значительным. На эффективность метода существенно влияет предварительная сортировка вариантов (без перебора или с перебором на меньшую глубину) — при сортировке чем больше в начале рассмотрено «хороших» вариантов, тем больше «плохих» ветвей может быть отсечено без исчерпывающего анализа.

См. также

• Компьютерные шахматы
• Стратегия слепого поиска

Примечания

1. ↑ McCarthy, John Human Level AI Is Harder Than It Seemed in 1955 (LaTeX2HTML 27 November 2006). Архивировано из первоисточника 9 апреля 2012. Проверено 20 декабря 2006.
2. ↑ Newell, Allen and Herbert A. Simon (March 1976). «Computer Science as Empirical Inquiry: Symbols and Search» (PDF). Communications of the ACM, Vol. 19, No. 3. Проверено 2006-12-21.
3. ↑ Richards, D.J. and Hart, T.P. The Alpha-Beta Heuristic (AIM-030). Massachusetts Institute of Technology (4 December 1961 to 28 October 1963). Архивировано из первоисточника 9 апреля 2012. Проверено 21 декабря 2006.
4. ↑ Kotok, Alan MIT Artificial Intelligence Memo 41 (XHTML 3 December 2004). Архивировано из первоисточника 9 апреля 2012. Проверено 1 июля 2006.
5. ↑ Marsland, T.A. Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor) (PDF) 159-171. J. Wiley & Sons (May 1987). Архивировано из первоисточника 9 апреля 2012. Проверено 21 декабря 2006.
6. ↑ * Knuth, D. E., and Moore, R. W. (1975). «An Analysis of Alpha-Beta Pruning». Artificial Intelligence Vol. 6, No. 4: 293–326.

   • Reprinted as Chapter 9 in Knuth Donald E. Selected Papers on Analysis of Algorithms. — Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102, 2000. — ISBN 1-57586-212-3

7. ↑ Abramson, Bruce (June 1989). «Control Strategies for Two-Player Games». ACM Computing Surveys, Vol. 21, No. 2 21: 137. DOI:10.1145/66443.66444. Проверено 2008-08-20.

Ссылки

• Knuth D. E., Moor R. W. Анализ альфа-бета отсечений // Artificial Intelligence, 1975. Пер. с англ. П. Н. Дубер.

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.