|
|
| Строка 1: |
Строка 1: |
| [[Файл:AB pruning.svg|thumb|400px]]
| | '''Альфа-бета-отсечение''' — алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом [[минимакс]]а. Предназначен для [[Антагонистическая игра|антагонистических игр]] и используется для машинной игры (в [[Компьютерные шахматы|компьютерных шахматах]], компьютерном [[го]] и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета-отсечение является [[Оптимизация (математика)|оптимизацией]], так как не влияет на корректность работы алгоритма. |
| | |
| '''Альфа-бета-отсечение''' ({{lang-en|alpha-beta pruning}}) — алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом [[минимакс]]а. Предназначен для [[Антагонистическая игра|антагонистических игр]] и используется для машинной игры (в [[Компьютерные шахматы|компьютерных шахматах]], компьютерном [[го]] и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета-отсечение является [[Оптимизация (математика)|оптимизацией]], так как не влияет на корректность работы алгоритма. | |
| | |
| == История ==
| |
| [[Аллен Ньюэлл]] и [[Герберт Саймон]], использовавшие то, что [[Джон Маккарти]] назвал «аппроксимацией»<ref name="JMC">{{cite web
| |
| |author = McCarthy J.
| |
| |title = Human Level AI Is Harder Than It Seemed in 1955
| |
| |date =LaTeX2HTML 27 November 2006
| |
| |url = http://www-formal.stanford.edu/jmc/slides/wrong/wrong-sli/wrong-sli.html
| |
| |accessdate = 2006-12-20
| |
| |archiveurl = https://www.webcitation.org/66mXcqCVV?url=http://www-formal.stanford.edu/jmc/slides/wrong/wrong-sli/wrong-sli.html
| |
| |archivedate = 2012-04-08
| |
| }}</ref> в 1958 году, написали, что альфа-бета-отсечение, «''кажется, изобреталось неоднократно''»<ref name=NS>{{статья
| |
| |заглавие=Computer Science as Empirical Inquiry: Symbols and Search
| |
| |издание=Communications of the ACM, Vol. 19, No. 3
| |
| |ссылка=http://archive.computerhistory.org/projects/chess/related_materials/text/2-3.Computer_science_as_empirical_inquiry/2-3.Computer_science_as_empirical_inquiry.newell_simon.1975.ACM.062303007.pdf
| |
| |accessdate=2006-12-21
| |
| |язык=en
| |
| |тип=journal
| |
| |автор=[[Ньюэлл, Аллен|Newell A.]], [[Саймон, Герберт|Simon H. A.]]
| |
| |месяц=3
| |
| |год=1976
| |
| |archiveurl=https://www.webcitation.org/5PwLLXQSN?url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-3.Computer_science_as_empirical_inquiry/2-3.Computer_science_as_empirical_inquiry.newell_simon.1975.ACM.062303007.pdf
| |
| |archivedate=2007-06-28
| |
| }}</ref>. [[Самуэль, Артур|Артур Самуэль]], Ричардс, Харт, Левин, Эдвардс независимо предлагали ранние версии этого алгоритма<ref name="Richard-Hart">{{cite web
| |
| |author = Richards D. J., Hart T. P.
| |
| |title = The Alpha-Beta Heuristic (AIM-030)
| |
| |publisher = Massachusetts Institute of Technology
| |
| |date =4 December 1961 to 28 October 1963
| |
| |url = http://hdl.handle.net/1721.1/6098
| |
| |accessdate = 2006-12-21
| |
| |archiveurl = https://www.webcitation.org/66mXdL4XI?url=http://dspace.mit.edu/handle/1721.1/6098
| |
| |archivedate = 2012-04-08
| |
| }}</ref>. [[Джон Маккарти|Маккарти]] также выдвигал подобные идеи на [[Дартмутский семинар|Дартмутском семинаре]] в 1956 году, а затем, в 1961 году, предложил для исследования группе своих студентов в [[Массачусетский технологический институт|MIT]], включая [[Коток, Алан|Алана Котока]]<ref name="AIM41">{{cite web |author=[[:en:Alan Kotok|Kotok A.]] |title=MIT Artificial Intelligence Memo 41 |date=XHTML 3 December 2004 |url=http://www.kotok.org/AI_Memo_41.html |accessdate=2006-07-01 |archiveurl=https://www.webcitation.org/66mXdpr6i?url=http://www.kotok.org/AI_Memo_41.html |archivedate=2012-04-08 }}</ref>. [[Брудно, Александр Львович|Александр Брудно]] независимо открыл алгоритм и опубликовал свои результаты в [[1963 год]]у<ref name=Marsland>{{cite web
| |
| |author = [http://www.cs.ualberta.ca/~tony/ Marsland T. A.]
| |
| |title = Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence / S. Shapiro (editor)
| |
| |publisher = J. Wiley & Sons
| |
| |month = May
| |
| |year = 1987
| |
| |pages = 159-171
| |
| |url = http://www.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf
| |
| |format = PDF
| |
| |accessdate = 2006-12-21
| |
| |archiveurl = https://www.webcitation.org/66mXeIbK3?url=http://webdocs.cs.ualberta.ca/~tony/OldPapers/encyc.mac.pdf
| |
| |archivedate = 2012-04-08
| |
| }}</ref>. В [[1975 год]]у [[Дональд Кнут]] и Рональд Мур усовершенствовали алгоритм, добавив «бета»-отсечения<ref name=Knuth-Moore>{{статья
| |
| |заглавие=An Analysis of Alpha-Beta Pruning
| |
| |издание=Artificial Intelligence Vol. 6, No. 4
| |
| |страницы=293—326
| |
| |язык=und
| |
| |автор=Knuth D. E., Moore R. W.
| |
| |год=1975}}, перепечатано как «часть 9» книги: {{книга
| |
| |заглавие=Selected Papers on Analysis of Algorithms
| |
| |год=2000
| |
| |издательство=Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102
| |
| |ссылка=http://www-cs-faculty.stanford.edu/~knuth/aa.html
| |
| |isbn=1-57586-212-3
| |
| |oclc=222512366
| |
| |язык=en
| |
| |автор=Knuth D. E.
| |
| }}</ref><ref name=Abramson>{{статья
| |
| |заглавие=Control Strategies for Two-Player Games
| |
| |издание=ACM Computing Surveys, Vol. 21, No. 2
| |
| |ссылка=http://www.theinformationist.com/pdf/constrat.pdf/
| |
| |accessdate=2008-08-20
| |
| |doi=10.1145/66443.66444
| |
| |том=21
| |
| |страницы=137
| |
| |archiveurl=https://web.archive.org/web/20080820030859/http://www.theinformationist.com/pdf/constrat.pdf/
| |
| |archivedate=2008-08-20
| |
| |язык=und
| |
| |автор=Abramson B.
| |
| |месяц=6
| |
| |год=1989}} {{Cite web |url=http://www.theinformationist.com/pdf/constrat.pdf/ |title=Архивированная копия |access-date=2009-10-25 |archive-date=2008-08-20 |archive-url=https://web.archive.org/web/20080820030859/http://www.theinformationist.com/pdf/constrat.pdf/ |deadlink=yes }}</ref>.
| |
|
| |
|
| == Оптимизация минимакса == | | == Оптимизация минимакса == |
| Преимущество альфа-бета-отсечения фактически заключается в том, что некоторые из ветвей подуровней дерева поиска могут быть исключены после того, как хотя бы одна из ветвей уровня рассмотрена полностью. Так как отсечения происходят на каждом уровне вложенности (кроме последнего), эффект может быть весьма значительным. На эффективность метода существенно влияет предварительная сортировка вариантов (без перебора или с перебором на меньшую глубину) — при сортировке чем больше в начале рассмотрено «хороших» вариантов, тем больше «плохих» ветвей может быть отсечено без исчерпывающего анализа. | | Преимущество альфа-бета-отсечения фактически заключается в том, что некоторые из ветвей подуровней дерева поиска могут быть исключены после того, как хотя бы одна из ветвей уровня рассмотрена полностью. Так как отсечения происходят на каждом уровне вложенности (кроме последнего), эффект может быть весьма значительным. На эффективность метода существенно влияет предварительная сортировка вариантов (без перебора или с перебором на меньшую глубину) — при сортировке чем больше в начале рассмотрено «хороших» вариантов, тем больше «плохих» ветвей может быть отсечено без исчерпывающего анализа. |
|
| |
|
| == Примечания ==
| | |
| {{примечания}}
| |
| {{Алгоритмы поиска на графах}}
| |
|
| |
|
| [[Категория:Алгоритмы поиска]] | | [[Категория:Алгоритмы поиска]] |
| [[Категория:Компьютерные шахматы]]
| |
| [[Категория:Программирование логических игр]]
| |
