Potatura alfa-beta

Potatura alfa-beta

Potatura alfa-beta. Si può ignorare il sottoalbero destro, perché sappiamo già che ha valore 1 o meno, e quindi non contiene la soluzione migliore
ClasseAlgoritmo di ricerca
Caso peggiore temporalmente
Caso ottimo temporalmente

La potatura alfa-beta è un algoritmo di ricerca che può ridurre drasticamente il numero di nodi da valutare nell'albero di ricerca dell'algoritmo minimax. Viene comunemente usata nei programmi di gioco automatico per computer, per giochi a turni a due o più giocatori (Tris, Go, Scacchi ecc.), e consiste nel terminare la valutazione di una possibile mossa non appena viene dimostrato che è comunque peggiore di una già valutata in precedenza: è una ottimizzazione sicura, che non modifica il risultato finale dell'algoritmo a cui viene applicata.

Funzionamento dell'algoritmo

La potatura alfa-beta si basa su due valori, detti appunto alfa e beta che rappresentano, in ogni punto dell'albero, la posizione migliore e peggiore che è possibile raggiungere. Più precisamente, se A è il giocatore massimizzante e B il giocatore minimizzante:

  • α è il punteggio minimo che A può raggiungere, a partire dalla posizione in esame; all'inizio dell'algoritmo viene posto a -∞. Durante il calcolo, α coincide con il valore della migliore mossa possibile attualmente calcolata per A.
  • β è il punteggio massimo che B può raggiungere a partire dalla stessa posizione; all'inizio dell'algoritmo viene posto a +∞. Durante il calcolo, β coincide con il valore della migliore mossa possibile attualmente calcolata per B.

La ricerca procede come una normale ricerca minimax, in cui però i valori di α e β per ogni nodo vengono aggiornati man mano che la ricerca si approfondisce. Se durante la ricerca, per un dato nodo α diventa maggiore di β, la ricerca al di sotto di quel nodo cessa e il programma passa ad un altro sottoalbero, perché la posizione di quel nodo non può essere raggiunta durante il gioco normale (cioè da quella posizione in poi, A perderebbe inevitabilmente anche se giocasse per vincere, il che in un gioco competitivo è assurdo, e certamente non è il risultato che vogliamo). Si dice che il sottoalbero corrispondente al nodo con α e β "invertiti" viene potato, da cui il nome dell'algoritmo stesso.

Miglioramenti rispetto al semplice minimax

Il beneficio fondamentale della potatura alfa-beta è l'eliminazione di interi rami dell'albero di ricerca; questo permette di limitare la ricerca alle mosse più promettenti, approfondendo ulteriormente la loro valutazione nel tempo dato. Come i suoi predecessori, anche la potatura alfa-beta è un algoritmo di tipo branch and bound.

Dato un fattore di diramazione (medio o costante) b e una profondità di ricerca di d mosse, il numero massimo di mosse valutate (quando l'ordinamento dell'albero è pessimo) è O(b*b*...*b) = O(bd) – lo stesso di una semplice ricerca minimax. Se invece l'ordinamento è perfetto (le mosse migliori sono sempre valutate per prime), il numero di posizioni ricercate diventa O(b*1*b*1*...*b) per profondità d pari e O(b*1*b*1*...*1) per d dispari, cioè

.

Quindi, nel caso migliore il fattore di diramazione efficace è ridotto alla sua radice quadrata, ovvero la ricerca può raggiungere una profondità doppia con lo stesso numero di calcoli[1]. Il motivo di b*1*b*1*... è che per il giocatore A devono essere valutate tutte le mosse possibili per trovare la migliore, mentre basta conoscere la miglior mossa di B per scartare tutte le mosse di A meno la migliore; il principio alfa-beta garantisce che non è necessario considerare nessun'altra mossa di B. Nel caso degli scacchi, dove il fattore di diramazione è circa 40, e considerando una profondità di ricerca di 12 turni, il rapporto fra caso migliore e caso peggiore è circa 406, cioè una ricerca alfa-beta ottimale per gli scacchi è 4 miliardi di volte più rapida del semplice minimax.

Perciò, poiché il numero di posizioni da valutare diminuisce esponenzialmente col diminuire della profondità, vale la pena compiere sforzi anche grandi per tenere quanto più possibile ordinato l'albero di ricerca: un ordinamento anche solo parziale può migliorare le prestazioni di milioni di volte. Nella pratica quindi, prima della ricerca vera e propria si effettua una prima "pre-ricerca" molto superficiale per ottenere un primo albero già parzialmente ordinato, che la ricerca vera e propria si occuperà di approfondire e completare fino alla profondità stabilita.

Nei programmi di gioco per i computer questa pre-ricerca non è, generalmente, necessaria: viene infatti adottata una procedura di raffinamento successivo, per cui ad ogni nuova mossa il calcolo riparte approfondendo il sottoalbero scelto dal giocatore di turno, già parzialmente ordinato dalle ricerche precedenti

Normalmente, nel corso dell'algoritmo, i sottoalberi sono temporaneamente dominati dal vantaggio di uno dei due giocatori; questo accade tipicamente quando un giocatore può fare molte buone mosse e ad ogni iterazione le prime mosse controllate sono già buone, mentre tutte le mosse dell'altro richiedono una analisi più approfondita per poter essere giudicate). Può anche accadere che questo vantaggio apparente passi spesso dall'uno all'altro giocatore, nel caso l'albero di ricerca del gioco sia poco ordinato.

Miglioramenti euristici

Si possono migliorare le prestazioni senza sacrificare l'accuratezza dei risultati usando euristiche di ordinamento per ricercare subito le parti dell'albero che più probabilmente forzeranno subito dei tagli alfa-beta: per esempio negli scacchi si esaminano per prime le mosse che prendono dei pezzi, o che hanno raggiunto dei punteggi molto alti nella prima ricerca superficiale. Un'altra ottimizzazione euristica molto comune ed economica è l'euristica killer, per cui l'ultima mossa che ha provocato un taglio beta allo stesso livello nell'albero viene sempre ricercata per prima; questa ottimizzazione si può generalizzare in un insieme di tabelle di confutazione.

La ricerca alfa-beta può essere ulteriormente accelerata considerando una finestra di ricerca (la differenza α - β) molto stretta, di solito con un valore ipotizzato in base all'esperienza; questa tecnica è nota come aspiration search. Nel caso estremo, si compie la ricerca con α = β, ottenendo la tecnica nota come zero-window search, null-window search, o scout search. Questa tecnica è particolarmente efficace nei finali di partita, quando si cerca lo scaccomatto. Se una aspiration search fallisce, è immediato sapere se l'intervallo scelto era troppo alto o troppo basso, ottenendo una nuova ipotesi di intervallo alfa-beta per una eventuale nuova ricerca sulla stessa posizione.

Altri algoritmi di ricerca

Sono noti in letteratura algoritmi di ricerca simili più veloci e avanzati, altrettanto capaci di calcolare il valore minimo esatto, come il Negascout e l'MTD-f. Poiché l'algoritmo minimax e le sue varianti sono intrinsecamente a ricerca di profondità, insieme alla potatura alfa-beta viene di solito adottata una strategia ad approfondimento iterativo, che permette alla ricerca di fornire una mossa ragionevolmente buona anche se la ricerca viene interrotta prima del termine. Un altro vantaggio dell'approfondimento iterativo è che permette di ordinare parzialmente l'albero di ricerca, il che permette di potare più in fretta i rami inutili, risparmiando tempo.

D'altra parte esistono anche algoritmi come l'SSS*, che invece analizzano l'albero delle mosse possibili a partire dalle migliori. Questo può renderli computazionalmente più efficienti, ma ha un costo molto pesante in termini di spazio di memoria occupato.

Pseudocodice

Ecco una forma in Pseudocodice dell'algoritmo di potatura alfa-beta. Viene chiamato dalla funzione "minimax" come esempio.

01 FUNZIONE alfa_beta(nodo, profondità, α, β, chi_gioca)
02      SE profondità = 0 O nodo è terminale
03          RESTITUISCI valore euristico del nodo
04      SE chi_gioca = MAX
05          v := -∞
06          PER OGNI figlio del nodo
07              v := max(v, alfa_beta(figlio, profondità - 1, α, β, MIN))
08              α := max(α, v)
09              SE β ≤ α
10                  INTERROMPI IL CICLO (* taglio secondo β *)
11          RESTITUISCI v
12      ALTRIMENTI SE chi_gioca = MIN
13          v := +∞
14          PER OGNI figlio del nodo
15              v := min(v, alfa_beta(figlio, profondità - 1, α, β, MAX))
16              β := min(β, v)
17              SE β ≤ α
18                  INTERROMPI IL CICLO (* taglio secondo α *)
19          RESTITUISCI v
(* richiamo iniziale *)
alfa_beta(origine, profondità, -, +∞, MAX)

Note

  1. ^ S.J. Russell and P. Norvig (2003). Artificial Intelligence: A Modern Approach. Second Edition, Prentice Hall.

Voci correlate

Collegamenti esterni

Read other articles:

French TwistSutradara Josiane Balasko Produser Pierre Grunstein Claude Berri Ditulis oleh Josiane Balasko Patrick Aubrée Telsche Boorman PemeranVictoria Abril Josiane Balasko Alain ChabatPenata musikManuel MalouSinematograferGérard de BattistaPenyuntingClaudine MerlinKako Kelber (co-penyunting)DistributorAMLF (Prancis) Miramax Zoë (AS)Tanggal rilis 8 Februari 1995 (1995-02-08) Durasi104 menitNegara Prancis Bahasa Prancis Anggaran$7 jutaPendapatankotor$75.2 juta[1] French...

Company headquarters in Karaköy, Istanbul. Turkish Maritime Organization (Turkish: Türkiye Denizcilik İşletmeleri A.Ş., TDİ) is a state-owned company responsible for the operation of certain harbor and shipyards in Turkey. Its headquarters is located in Karaköy quarter of Beyoğlu district, Istanbul. The precursor of the company was founded in 1843 during the Ottoman Empire era. The company was responsible only for the ports around İstanbul. In 1933, following the establishment of the...

Fictional character in 2012-14 Spider-Man film series Fictional character Gwen StacyMarc Webb's The Amazing Spider-Man characterPromotional picture of Emma Stone as Gwen Stacy in The Amazing Spider-ManFirst appearanceThe Amazing Spider-Man (2012)Last appearanceThe Amazing Spider-Man 2 (2014)Based onGwen Stacyby Stan LeeSteve DitkoAdapted by Marc Webb James Vanderbilt Portrayed byEmma StoneVoiced byKari WahlgrenIn-universe informationFull nameGwendolyne Maxine StacySpeciesHumanGenderFemaleOccu...

Telhado Freguesia extinguida Iglesia de Santa María TelhadoLocalización de Telhado en PortugalCoordenadas 41°27′03″N 8°27′12″O / 41.45092, -8.45328Entidad Freguesia extinguida • País  Portugal • Distrito Braga • Municipio Vila Nova de Famalicão • Freguesia actual Vale (São Cosme), Telhado e PortelaPoblación (2011)   • Total 1784 hab.[editar datos en Wikidata] Telhado era una freguesia portuguesa d...

La época pre-code de la industria cinematográfica estadounidense hace referencia al breve periodo comprendido entre la introducción del sonido, finales de los años veinte,[1]​ y la aplicación del Código de Producción de Películas (Motion Picture Production Code) que recogía las directrices de censura. Desde 1934, el Código de Producción de Películas pasó a denominarse, de forma incorrecta, «código Hays». Aunque el código fue adoptado en 1930, el proceso de supervisión ...

Pour les articles homonymes, voir Tadić. Boris Tadić Борис Тадић Boris Tadić en 2004. Fonctions Président de la république de Serbie (indépendante) 5 juin 2006 – 5 avril 2012(7 ans, 8 mois et 25 jours) Réélection 3 février 2008 Président du gouvernement Vojislav KoštunicaMirko Cvetković Prédécesseur Lui-même (au sein de la Communauté d'États de Serbie-et-Monténégro) Successeur Slavica Đukić Dejanović (intérim) Tomislav Nikolić Président de l...

Maurice Strong (2010) Maurice Frederick Strong, PC, CC, OM, FRSC (* 29. April 1929 in Oak Lake, Manitoba; † 27. November 2015 in Ottawa, Ontario[1]) war ein kanadischer Unternehmer und UNO-Funktionär. Inhaltsverzeichnis 1 Leben 2 Auszeichnungen 3 Literatur 4 Einzelnachweise Leben Anfang der 1970er Jahre war er Generalsekretär der Konferenz der Vereinten Nationen über die Umwelt des Menschen, bevor er 1972 erster Generaldirektor des Umweltprogramms der Vereinten Nationen wurde. An...

Піноккіоангл. Pinocchio Жанр драматичний фільм, музичний фільм, дитячий фільм, пригодницький фільм і фентезійний фільмРежисер Роберт ЗемекісПродюсер Кріс ВайцdСценарист Кріс Вайцd і Роберт ЗемекісНа основі Пригоди Піноккіо і ПіноккіоУ головних ролях Том...

Ngo Bao Chau Ngo Bao Chau (lahir 28 Juni 1972) adalah seorang matematikawan Vietnam. Dia memiliki kewarganegaraan Prancis dan Vietnam. Ia lahir di Hanoi, ia lulus di universitas Hanoi. Dia tinggal di Paris, Prancis sekarang. Dia bekerja untuk Institute for Advanced Study dalam Princeton, New Jersey, dan akan bergabung dengan fakultas matematika di University of Chicago pada tanggal 1 September 2010. Dia memberikan Medali Fields 2010. Lihat pula Ilmuwan Peneliti Matematika Pengawasan otoritas ...

John L. Meisenheimer Sr. (June, 1933) is a Professor Emeritus of Chemistry (1963–1999) and EKU Foundation Professor (1994–1996) at Eastern Kentucky University.[1] On October 31, 1957, he was the Launch and Flight Weather Officer for the first U.S., intercontinental missile (Snark). In 1958, as the Launch Weather Officer for Explorer 1, the first U.S. satellite, he delayed America's entry into the space race for two days with his correct forecasts of extreme upper air wind shear.&#...

Sawah di pinggiran Namwon Produksi beras di Korea Selatan penting untuk pasokan makanan di negara tersebut, dengan beras menjadi bagian umum dari makanan orang Korea. Pada tahun 2009, Korea Selatan memproduksi 3.899.036 metrik ton (4.297.951 ton) beras.[1] Padi adalah tanaman paling berharga di Korea Selatan.[2] Namun, seperti dicatat oleh Donald S. Macdonald, kenaikan tingkat upah dan nilai tanah membuat biaya produksi menjadi mahal. Beras mewakili sekitar 90 persen dari tota...

The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.Find sources: Piranha compositing software – news · newspapers · books · scholar · J...

Aventura discographyStudio albums6Live albums3Video albums3Music videos15Singles18 American bachata band Aventura has released six studio albums, three live albums, two video albums, 15 music videos and 26 singles. Albums Studio albums Title Details Peak chart positions Sales Certifications US USLatin USTrop. SWI MEX Generation Next Released: November 9, 1999 Label: Premium Latin Formats: CD, digital download — — 19 74 — US: 13,000[1] We Broke the Rules Released: July 2, 2002 La...

Directas Ya!Diretas Já! Paseo por el centro de São Paulo, 16 de abril de 1984. Foto: Jorge H. Singh.Campaña para Revindicar el derecho a elegir al presidente del país por voto directo de los electoresSede Brasil BrasilPersonas clave Tancredo Neves, Franco Montoro, Orestes Quércia, Fernando Henrique Cardoso, Mario Covas, Lula da Silva y Pedro Simon.[editar datos en Wikidata] Este artículo es parte de una serieDictadura militar en Brasil1964–1985 Perspectiva cronológica ...

Fictional character from Skins Fictional character Nick LevanSkins characterSean Teale as Nick LevanFirst appearanceFranky (episode 5.01)Last appearanceFinale (episode 6.10)Created byBryan Elsley and Jamie BrittainPortrayed bySean TealeSeasons5-6Centric episode(s)Nick (series 5) (episode 5.05)Nick (series 6) (episode (6.06)In-universe informationOccupationStudentFamilyLeon Levan (father)Siobhan Jane (mother)Matty Levan (brother) Nicholas Laurence Nick Levan is a fictional character from the t...

Ne pas confondre la Villa Vassilieff – anciennement Musée du Montparnasse – avec la villa Marie-Vassilieff, la voie privée dans laquelle se trouve le musée. Musée du MontparnasseLe musée dans l'ancien atelier de Marie Vassilieff.Informations généralesType Musée d'artOuverture 28 mai 1998Fermeture 2015Site web web.archive.org/web/20140725082939/www.museedumontparnasse.netLocalisationPays  FranceCommune ParisAdresse 21 avenue du MaineCoordonnées 48° 50′ 36,3″...

American film producer Maurice Buddy AdlerAdler in 1958BornE. Maurice Adler(1906-06-22)June 22, 1906New York City, New York, U.S.DiedJuly 12, 1960(1960-07-12) (aged 54)Los Angeles, California, U.S.Resting placeForest Lawn Memorial Park Cemetery, Glendale, CaliforniaYears active1939–1960SpouseAnita Louise (1940–1960) E. Maurice Buddy Adler (June 22, 1906 – July 12, 1960) was an American film producer and production head for 20th Century Fox studios. In 1954, his production of F...

Sports stadium in Oyonnax, France Stade Charles-MathonLocationOyonnax, FranceCoordinates46°15′13″N 5°38′41″E / 46.25361°N 5.64472°E / 46.25361; 5.64472OwnerCity of OyonnaxCapacity11,500Surfacesynthetic grassConstructionOpened1939Renovated1983Expanded2005TenantsOyonnax Rugby Stade Charles-Mathon is a sports stadium located in Oyonnax, France. It is the home of rugby union side Oyonnax Rugby who play in the Top 14. It was first opened in 1939,[1] and ...

Eurovision Song Contest 1999Country AustriaNational selectionSelection processInternal selectionSelection date(s)Artist: 12 February 1999Song: 25 February 1999Selected entrantBobbie SingerSelected songReflectionSelected songwriter(s)Dave MoskinFinals performanceFinal result10th, 65 pointsAustria in the Eurovision Song Contest ◄1997 • 1999 • 2000► Austria participated in the Eurovision Song Contest 1999 with the song Reflection written by Dave Moskin....

Mechanism for central bank lending to eligible depository institutions The discount window is an instrument of monetary policy (usually controlled by central banks) that allows eligible institutions to borrow money from the central bank, usually on a short-term basis, to meet temporary shortages of liquidity caused by internal or external disruptions. The interest rate charged on such loans by a central bank is called the bank rate, discount rate, policy rate, base rate, or repo rate, and is ...