Альфа-бета-отсечение: различия между версиями
(удалена ссылка на не правильного Р. Мура) |
Patarakin (обсуждение | вклад) м (1 версия импортирована) |
Версия 20:54, 19 октября 2022
Альфа-бета-отсечение (Шаблон:Lang-en) — алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакса. Предназначен для антагонистических игр и используется для машинной игры (в компьютерных шахматах, компьютерном го и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета-отсечение является оптимизацией, так как не влияет на корректность работы алгоритма.
История
Аллен Ньюэлл и Герберт Саймон, использовавшие то, что Джон Маккарти назвал «аппроксимацией»<ref name="JMC">Шаблон:Cite web</ref> в 1958 году, написали, что альфа-бета-отсечение, «кажется, изобреталось неоднократно»<ref name=NS>Шаблон:Статья</ref>. Артур Самуэль, Ричардс, Харт, Левин, Эдвардс независимо предлагали ранние версии этого алгоритма<ref name="Richard-Hart">Шаблон:Cite web</ref>. Маккарти также выдвигал подобные идеи на Дартмутском семинаре в 1956 году, а затем, в 1961 году, предложил для исследования группе своих студентов в MIT, включая Алана Котока<ref name="AIM41">Шаблон:Cite web</ref>. Александр Брудно независимо открыл алгоритм и опубликовал свои результаты в 1963 году<ref name=Marsland>Шаблон:Cite web</ref>. В 1975 году Дональд Кнут и Рональд Мур усовершенствовали алгоритм, добавив «бета»-отсечения<ref name=Knuth-Moore>Шаблон:Статья, перепечатано как «часть 9» книги: Шаблон:Книга</ref><ref name=Abramson>Шаблон:Статья Шаблон:Cite web</ref>.
Оптимизация минимакса
Преимущество альфа-бета-отсечения фактически заключается в том, что некоторые из ветвей подуровней дерева поиска могут быть исключены после того, как хотя бы одна из ветвей уровня рассмотрена полностью. Так как отсечения происходят на каждом уровне вложенности (кроме последнего), эффект может быть весьма значительным. На эффективность метода существенно влияет предварительная сортировка вариантов (без перебора или с перебором на меньшую глубину) — при сортировке чем больше в начале рассмотрено «хороших» вариантов, тем больше «плохих» ветвей может быть отсечено без исчерпывающего анализа.
