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

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

Альфа-бета-отсечение (англ. 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 года.

Read other articles:

Okuma Shigenobu

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Okuma Shigenobu – berita · surat kabar · buku · cendekiawan · JSTOR Ōkuma Shigenobu大隈 重信 Perdana Menteri JepangMasa jabatan16 April 1914 – 9 Oktober 1916Penguasa monarkiTaishō Pendah...

 

Fadhilah Budiono

Kombes. Pol. (Purn.) H.Fadhilah Budiono Bupati Sampang ke-10Masa jabatan5 Juli 2017 – 26 Februari 2018PresidenJoko WidodoGubernurSoekarwo PendahuluFannan HasibPenggantiJonathan Judianto (Pj.)Slamet JunaidiMasa jabatan1995 – 2006PresidenSoehartoBJ HabibieAbdurrahman WahidMegawati SoekarnoputriSusilo Bambang YudhoyonoGubernurBasofi SudirmanImam UtomoWakilSaid Hidayat (2001-2006) PendahuluR. Bagus HinayanaPenggantiNoer TjahjaWakil Bupati Sampang ke-2Masa jabatan2013...

 

The Trench (novel)

Not to be confused with a 1991 novel by Abdul Rahman Munif. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: The Trench novel – news · newspapers · books · scholar · JSTOR (January 2021) (Learn how and when to remove this template message) 1999 science fiction novel by Steve Alten This article is about t...

LEP Pre-Injector

The LEP Pre-Injector (LPI) was the initial source that provided electrons and positrons to CERN's accelerator complex for the Large Electron–Positron Collider (LEP) from 1989 until 2000. LPI comprised the LEP Injector Linac (LIL) and the Electron Positron Accumulator (EPA). LEP Injector Linac LIL-W with electron-positron converter Electron Positron Accumulator History Building of the former LEP Injector Linac (LIL) at CERN, afterwards housing the CLIC test facility. The green LIL sign is st...

 

عمو بابا

عمو بابا عمو بابا أثناء تدريبه للمنتخب العراقي العسكري سنة 1979 معلومات شخصية الميلاد 27 نوفمبر 1934(1934-11-27)بغداد الوفاة 27 مايو 2009 (عن عمر ناهز 74 عاماً)دهوك سبب الوفاة السكري  مركز اللعب مهاجم الجنسية العراق  المسيرة الاحترافية1 سنوات فريق م. (هـ.) 1951–1954 RAF Employees' (Assyrian) Club 195...

 

Brazilian Constituent Assembly (1988)

National Constitutional Assembly Assembleia Nacional ConstituinteTypeTypeUnicameral constituent assembly HistoryFoundedFebruary 1, 1987 (1987-02-01)DisbandedJuly 22, 1988 (1988-07-22)LeadershipPresidentUlysses Guimarães, PMDB 1st Vice PresidentMauro Benevides, PMDB 2nd Vice PresidentJorge Arbage, PDS StructureSeats559 constituentsPolitical groupsMajority   PMDB (303)   PFL (135)   PDS (38)   PTB (18)   PL (7)   PDC (6) &...

Mount Sorell

Mountain in Western Tasmania, Australia Not to be confused with Mount Sorrel. Mount SorellMount Sorell viewed from the Macquarie Harbour fjordHighest pointElevation1,144 m (3,753 ft)[1]Prominence673 m (2,208 ft)[1]Isolation11.49 km (7.14 mi)[1]Coordinates42°16′12″S 145°32′24″E / 42.27000°S 145.54000°E / -42.27000; 145.54000 (Mount Sorell)[2]GeographyMount SorellLocation in Tasmania L...

 

Jennie Bond

English journalist and television presenter Jennie BondBond (left) in 2012BornJennifer Bond (1950-08-19) 19 August 1950 (age 73)Hitchin, Hertfordshire, EnglandOccupation(s)Journalist, presenterNotable credit(s)BBC News royal correspondent (1989–2003)The Great British MenuCash in the AtticSpouse James Keltz ​(m. 1982)​Children1 Jennifer Bond (born 19 August 1950) is an English journalist and television presenter. Bond worked for fourteen years as the BBC's r...

 

Blue Ridge National Wildlife Refuge

Nature preserve in California, United States Blue Ridge National Wildlife RefugeIUCN category IV (habitat/species management area)Map of the United StatesLocationTulare County, California, United StatesNearest citySpringville, CaliforniaCoordinates36°16′47″N 118°50′41″W / 36.2798°N 118.8446°W / 36.2798; -118.8446[1]Area897 acres (3.63 km2)Established1982Governing bodyU.S. Fish and Wildlife ServiceWebsiteBlue Ridge National Wildlife Re...

Ubisoft Leamington

British video game developer Ubisoft LeamingtonFormerlyFreeStyleGames Limited (2002–2017)Company typeSubsidiaryIndustryVideo gamesFounded29 November 2002; 21 years ago (2002-11-29) in Warwick, EnglandFounderAlex DarbyAlex ZoroDavid OsbournJamie JacksonJonny AmbrosePhil HindleHeadquartersLeamington Spa, EnglandKey peopleLisa Opie (managing director)ProductsDJ Hero seriesGuitar Hero seriesNumber of employees50 (2016)ParentActivision (2008–2017)Ubisoft (2017–present)...

 

Peter D. Fuller

American auto dealer, racehorse owner, and boxer (1923–2012) Peter D. FullerBorn(1923-03-22)March 22, 1923Boston, Massachusetts, U.S.DiedMay 14, 2012(2012-05-14) (aged 89)Portsmouth, New Hampshire, U.S.Alma materDartmouth, HarvardOccupation(s)Auto dealer, racehorse ownerKnown forOwner of Dancer's Image and Mom's CommandSpouse Joan Beth Marcotte ​(m. 1951)​Children8, including Abigail FullerParent(s)Viola T. and Alvan T. Fuller Peter Davenport Ful...

 

Trisquel

Linux distribution based on Ubuntu Linux distribution Trisquel GNU/LinuxTrisquel 11.0 desktopDeveloperThe Trisquel Project[1] and Sognus, S.L.U.OS familyLinux (Unix-like)Working stateCurrent[2]Initial releaseJanuary 30, 2007; 17 years ago (2007-01-30)[3]Latest release11.0[4] / March 19, 2023; 14 months ago (2023-03-19)Repositorygitlab.trisquel.org/trisquel/ Marketing targetHome users, small enterprises and educational centers...

Edward Virginius Valentine

American sculptor (1838–1930) Edward Virginius ValentineValentine in a 1906 publicationBorn(1838-11-12)November 12, 1838DiedOctober 19, 1930(1930-10-19) (aged 91)Richmond, Virginia, U.S.Resting placeHollywood CemeteryOccupationSculptorSpouses Alice Churchill Robinson ​ ​(m. 1872; died 1883)​ Katherine Cole Friend Mayo ​ ​(m. 1892; died 1927)​ Edward Virginius Valentine (November 12, 1838 - O...

 

خط طول 72° شرق

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) 72° خط طول 72 شرق خريطة لجميع الإحداثيات من جوجل خريطة لجميع الإحداثيات من بينغ تصدير جميع الإحداثيات من كي...

 

Asus Eee PC

ASUS Eee PC adalah model komputer jinjing berukuran kecil yang dirancang dan diproduksi oleh perusahaan ASUS. Perbedaan utama ASUS Eee PC dengan kebanyakan komputer jinjing lain terletak pada ukuran fisik yang lebih kecil, bobot yang lebih ringan, serta spesifikasi teknis yang dimilikinya. Pada awal peluncuran produknya, Eee PC menggunakan sistem operasi Linux dan perangkat penyimpan data berupa memori solid-state drive (SSD). Pada model-model Eee PC berikutnya, sistem operasi Windows XP dise...

Meaning (philosophy)

Philosophical conception of meaning This article is about the philosophical treatment of meaning. For the linguistic treatment of meaning, see Semantics. For the non-linguistic treatment of meaning, see Meaning (non-linguistic). For other uses, see Meaning. Part of a series onEpistemology Outline Category Index Schools Coherentism Contextualism Dogmatism Empiricism Fallibilism Foundationalism Infallibilism Infinitism Naturalism Perspectivism Pragmatism Rationalism Relativism Skepticism Solips...

 

Le Blanc-Mesnil

Le Blanc-MesnilNegaraPrancisArondisemenLe RaincyAntarkomunebelum ada pada 2005Kode INSEE/pos93007 /  Le Blanc-Mesnil merupakan sebuah komune di pinggiran timurlaut Paris, Prancis. Terletak 12.6 km (7.8 mil) dari pusat kota Paris, antara Bandar Udara Internasional Charles de Gaulle dan Bandar Udara Le Bourget. Nama Nama Le Blanc-Mesnil tercatat untuk pertama kalinya pada abad ke-11 sebagai Mansionile Blaun. Nama ini adalah gabungan dari Mansionile Latin Pertengahan, berarti rumah kec...

 

Coppa UEFA 1974-1975

Coppa UEFA 1974-1975 Competizione Coppa UEFA Sport Calcio Edizione 4ª Organizzatore UEFA Date dal 17 settembre 1974al 21 maggio 1975 Partecipanti 64 Nazioni 31 Risultati Vincitore Borussia M'gladbach(1º titolo) Finalista Twente Semi-finalisti ColoniaJuventus Statistiche Miglior marcatore Jupp Heynckes (11) Incontri disputati 124 Gol segnati 379 (3,06 per incontro) I giocatori del Borussia M'gladbach sollevano il trofeo Cronologia della competizione 1973-1974 1975-1976 Man...

Malikismo

Questa voce sull'argomento islam è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Distribuzione delle scuole giuridico-religiose islamiche nel mondo. Distribuzione delle scuole giuridico-religiose islamiche nel mondo. I malikiti o malichiti sono quei musulmani sunniti che seguono il madhhab (scuola giuridico-religiosa) fondato sulla scia dell'insegnamento di Mālik ibn Anas di Medina (m. 796). Indice 1 ...

 

Google Play

Google Play Store Información generalTipo de programa Distribución digital, Tienda en líneaDesarrollador GoogleModelo de desarrollo Software propietarioLanzamiento inicial 28 de agosto de 2008 (16 años)Estado actual Con soporteIdiomas MultilingüeInformación técnicaProgramado en SiPlataformas admitidas Android, Android TV, Wear OS, Chrome OS, WebVersionesÚltima versión estable 37.7.22-21 (info) ( 28 de septiembre de 2023 (1 año y 3 días))Enlaces Sitio web oficial Blog...