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

Серая часть ветки не вычисляется, т.к. по результатам расчётов вся ветка уже «хуже» наилучшего ранее вычисленного значения и дальнейшие вычисления могут изменить прогноз только в сторону ухудшения

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

История

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

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

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

На примере приведённого графика, как только получено значение 5, то если ниже по дереву будет получено значения выше 5, например 8, как в серой ветке , то они будут больше минимального и не выбраны. Если бы итогом вычислений в серой ветке было бы значение меньше минимального, например 2 , то это бы стало значением и родительской ветки вместо 5. И в том и другом случае это было бы хуже максимального значения 6, поэтому игнорирование серой ветки не повлияло на результат.

Примечания

  1. ↑ McCarthy J. Human Level AI Is Harder Than It Seemed in 1955 (27 ноября 2006). Дата обращения: 20 декабря 2006. Архивировано 8 апреля 2012 года.
  2. ↑ Newell A., Simon H. A. Computer Science as Empirical Inquiry: Symbols and Search (англ.) // Communications of the ACM, Vol. 19, No. 3 : journal. — 1976. — March. Архивировано 28 июня 2007 года.
  3. ↑ Richards D. J., Hart T. P. The Alpha-Beta Heuristic (AIM-030). Massachusetts Institute of Technology (4 декабря 1961). Дата обращения: 21 декабря 2006. Архивировано 8 апреля 2012 года.
  4. ↑ Kotok A. MIT Artificial Intelligence Memo 41 (3 декабря 2004). Дата обращения: 1 июля 2006. Архивировано 8 апреля 2012 года.
  5. ↑ Marsland T. A. Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence / S. Shapiro (editor) (PDF) 159-171. J. Wiley & Sons (May 1987). Дата обращения: 21 декабря 2006. Архивировано 8 апреля 2012 года.
  6. ↑ Knuth D. E., Moore R. W. An Analysis of Alpha-Beta Pruning (неопр.) // Artificial Intelligence Vol. 6, No. 4. — 1975. — С. 293—326., перепечатано как «часть 9» книги: Knuth D. 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. Архивировано 1 декабря 2010 года.
  7. ↑ Abramson B. Control Strategies for Two-Player Games (неопр.) // ACM Computing Surveys, Vol. 21, No. 2. — 1989. — June (т. 21). — С. 137. — doi:10.1145/66443.66444. Архивировано 20 августа 2008 года. Архивированная копия. Дата обращения: 25 октября 2009. Архивировано из оригинала 20 августа 2008 года.