Beskjæring av alfa -beta - Alpha–beta pruning

Beskjæring av alfa -beta
Klasse	Søkealgoritme
Ytelse i verste fall
Beste ytelse

Beskæring av alfa -beta er en søkealgoritme som søker å redusere antall noder som evalueres av minimax -algoritmen i søketreet . Det er en adversarial søkealgoritme som vanligvis brukes for maskinspill av to-spillerspill ( Tic-tac-toe , Chess , Go , etc.). Det slutter å evaluere et trekk når det er funnet minst en mulighet som viser at trekket er verre enn et tidligere undersøkt trekk. Slike trekk trenger ikke evalueres ytterligere. Når det brukes på et standard minimax -tre, returnerer det samme trekk som minimax ville, men beskjærer bort grener som umulig kan påvirke den endelige avgjørelsen.

Historie

Allen Newell og Herbert A. Simon som brukte det John McCarthy kaller en "tilnærming" i 1958 skrev at alfa -beta "ser ut til å ha blitt oppfunnet flere ganger". Arthur Samuel hadde en tidlig versjon for en brikkesimulering. Richards, Timothy Hart, Michael Levin og/eller Daniel Edwards oppfant også alfa -beta uavhengig i USA . McCarthy foreslo lignende ideer under Dartmouth -verkstedet i 1956 og foreslo det for en gruppe av studentene hans, inkludert Alan Kotok ved MIT i 1961. Alexander Brudno unnfanget uavhengig alfa -beta -algoritmen og publiserte resultatene hans i 1963. Donald Knuth og Ronald W. Moore raffinerte algoritmen i 1975. Judea Pearl beviste at det var optimalt når det gjelder forventet kjøretid for trær med tilfeldig tildelte bladverdier i to artikler. Optimaliteten til den randomiserte versjonen av alfa -beta ble vist av Michael Saks og Avi Wigderson i 1986.

Kjerneidé

Et spiltre kan representere mange to-spiller nullsumspill , for eksempel sjakk, brikker og reversi. Hver node i treet representerer en mulig situasjon i spillet. Hver terminalnode (utfall) i en gren tildeles en numerisk poengsum som bestemmer verdien av utfallet til spilleren med neste trekk.

Algoritmen opprettholder to verdier, alfa og beta, som henholdsvis representerer minimumsscoren som den maksimerende spilleren er sikret og maksimal score som den minimerende spilleren er sikret. I utgangspunktet er alfa negativ uendelig og beta er positiv uendelig, det vil si at begge spillerne starter med sin verste mulige poengsum. Når den maksimale poengsummen som den minimerende spilleren (dvs. "beta" -spilleren) er sikret, blir mindre enn minimumspoenget som den maksimerende spilleren (dvs. "alfa" -spilleren) er sikret (dvs. beta <alfa), blir maksimaliseringen spilleren trenger ikke å vurdere flere etterkommere av denne noden, da de aldri vil nås i selve spillet.

For å illustrere dette med et eksempel fra det virkelige liv, anta at noen spiller sjakk, og det er deres tur. Flytt "A" vil forbedre spillerens posisjon. Spilleren fortsetter å lete etter trekk for å sikre at en bedre ikke har blitt savnet. Bevegelse "B" er også et godt trekk, men spilleren innser da at det vil tillate motstanderen å tvinge sjakkmat i to trekk. Dermed trenger du ikke lenger å vurdere andre utfall fra å spille trekk B siden motstanderen kan tvinge en seier. Den maksimale poengsummen som motstanderen kan tvinge etter trekk "B" er negativ uendelig: et tap for spilleren. Dette er mindre enn minimumsposisjonen som tidligere ble funnet; trekk "A" resulterer ikke i et tvunget tap i to trekk.

Forbedringer over naiv minimaks

En illustrasjon av beskjæring av alfa -beta. De nedtonede undertrærne trenger ikke å utforskes (når trekk evalueres fra venstre til høyre), siden det er kjent at gruppen av undertrær som helhet gir verdien av et tilsvarende undertre eller verre, og som sådan ikke kan påvirke det endelige resultatet. Maks- og min -nivåene representerer henholdsvis spillerens og motstanderens tur.

Fordelen med alfa -beta beskjæring ligger i det faktum at grener av søketreet kan elimineres. På denne måten kan søketiden begrenses til det 'mer lovende' undertreet, og et dypere søk kan utføres samtidig. Som forgjengeren tilhører den grenen og den bundne klassen av algoritmer. Optimaliseringen reduserer den effektive dybden til litt mer enn halvparten av den enkle minimaks hvis nodene evalueres i en optimal eller nær optimal rekkefølge (beste valg for side i bevegelse bestilt først ved hver node).

Med en (gjennomsnittlig eller konstant) forgreningsfaktor på b , og en søkedybde på d -lag , er det maksimale antallet bladnodeposisjoner evaluert (når bevegelsesrekkefølgen er pessimal ) er O ( b × b × ... × b ) = O ( b ^d ) - det samme som et enkelt minimax -søk. Hvis bevegelsesrekkefølgen for søket er optimal (det vil si at de beste trekkene alltid blir søkt først), er antallet bladnodeposisjoner som er evaluert omtrent O ( b × 1 × b × 1 × ... × b ) for oddetall og O ( b × 1 × b × 1 × ... × 1) for jevn dybde, eller . I sistnevnte tilfelle, hvor et søkes lag er jevnt, reduseres den effektive forgreningsfaktoren til kvadratroten , eller tilsvarende kan søket gå dobbelt så dypt med samme beregningsmengde. Forklaringen på b × 1 × b × 1 × ... er at alle den første spillers trekk må studeres for å finne den beste, men for hver er det bare den andre spillerens beste trekk som trengs for å tilbakevise alle unntatt den første (og best) first player move — alfa – beta sikrer at ingen andre spilleres trekk trenger å bli vurdert. Når noder blir vurdert i en tilfeldig rekkefølge (dvs. algoritmen randomiserer), asymptotisk, er det forventede antallet noder evaluert i ensartede trær med binære bladverdier . For de samme trærne, når verdiene er tilordnet bladverdiene uavhengig av hverandre og sier null og en er like sannsynlig, er det forventede antallet noder som er evaluert , som er mye mindre enn arbeidet utført av den randomiserte algoritmen, nevnt ovenfor, og er igjen optimal for slike tilfeldige trær. Når bladverdiene velges uavhengig av hverandre, men fra intervallet jevnt og tilfeldig, øker det forventede antallet evaluerte noder til i grensen, som igjen er optimal for disse tilfeldige trærne. Vær oppmerksom på at det faktiske arbeidet for "små" verdier av er bedre tilnærmet ved bruk . ${\ displaystyle O (b^{d/2}) = O ({\ sqrt {b^{d}}})}}$ ${\ displaystyle \ Theta (((b-1+{\ sqrt {b^{2}+14b+1}})/4)^{d})}$ ${\ displaystyle \ Theta ((b/2)^{d})}$ ${\ displaystyle [0,1]}$ ${\ displaystyle \ Theta (b^{d/log (d)})}$ ${\ displaystyle d \ to \ infty}$ ${\ displaystyle d}$ ${\ displaystyle 0.925d^{0.747}}$

Et sjakkprogram som søker i fire lag med et gjennomsnitt på 36 grener per node, vurderer mer enn en million terminalnoder. En optimal alfa-beta sviske ville eliminere alle bortsett fra omtrent 2000 terminalnoder, en reduksjon på 99,8%.

Et animert pedagogisk eksempel som prøver å være menneskevennlig ved å erstatte uendelige (eller vilkårlig store) verdier for tomhet og ved å unngå å bruke negamax- kodingsforenklingene.

Vanligvis under alfa -beta domineres undertrær midlertidig av enten en førstespillers fordel (når mange førstespillers trekk er gode, og ved hver søketybde er det første trekket som kontrolleres av den første spilleren tilstrekkelig, men alle andre spillers svar er nødvendig for å prøv å finne en tilbakevisning), eller omvendt. Denne fordelen kan bytte side mange ganger i løpet av søket hvis bevegelsesrekkefølgen er feil, noe som hver gang fører til ineffektivitet. Ettersom antall søkte stillinger eksponentielt avtar hvert trekk nærmere den nåværende posisjonen, er det verdt å bruke mye innsats på å sortere tidlige trekk. En forbedret sortering på hvilken som helst dybde vil eksponentielt redusere det totale antallet posisjoner som er søkt, men sortering av alle posisjoner på dybder nær rotnoden er relativt billig ettersom det er så få av dem. I praksis bestemmes bevegelsesrekkefølgen ofte av resultatene av tidligere, mindre søk, for eksempel gjennom iterativ utdypning .

I tillegg kan denne algoritmen endres trivielt for å returnere en hel hovedvariasjon i tillegg til poengsummen. Noen mer aggressive algoritmer som MTD (f) tillater ikke lett en slik modifikasjon.

Pseudokode

Pseudokoden for dybdebegrenset minimaks med alfa-beta beskjæring er som følger:

Implementeringer av alfa-beta beskjæring kan ofte avgrenses med om de er "fail-soft" eller "fail-hard". Med fail-soft alfa – beta kan alfabetfunksjonen returnere verdier (v) som overskrider (v <α eller v> β) α- og β-grensene som er satt av funksjonskallargumentene. Til sammenligning begrenser fail-hard alfa-beta funksjonens returverdi til det inkluderende området α og β. Hovedforskjellen mellom fail-soft og fail-hard implementeringer er om α og β oppdateres før eller etter cutoff-kontrollen. Hvis de oppdateres før kontrollen, kan de overskride de første grensene, og algoritmen er mislykket.

Den følgende pseudokoden illustrerer den mislykkede variasjonen.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Følgende pseudokode illustrerer fail-soft alfa-beta.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if value ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if value ≤ α then
                break (* α cutoff *)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Heuristiske forbedringer

Ytterligere forbedring kan oppnås uten å ofre nøyaktigheten ved å bruke ordreheuristikk for å søke i tidligere deler av treet som sannsynligvis vil tvinge til alfa -beta -avbrudd. For eksempel i sjakk kan trekk som fanger brikker bli undersøkt før trekk som ikke gjør det, og trekk som har scoret høyt i tidligere pasninger gjennom spilletre-analysen, kan bli evaluert før andre. En annen vanlig, og veldig billig, heurist er dreperheuristen , der det siste trekket som forårsaket en beta-cutoff på samme trenivå i tresøket alltid blir undersøkt først. Denne ideen kan også generaliseres til et sett med tilbakevisningstabeller .

Alpha -beta -søk kan gjøres enda raskere ved bare å vurdere et smalt søkevindu (vanligvis bestemt av gjetninger basert på erfaring). Dette er kjent som aspirasjonssøk . I ekstreme tilfelle utføres søket med alfa og beta lik; en teknikk kjent som nullvindussøk , nullvindussøk eller speider søk . Dette er spesielt nyttig for vinn/tap -søk nær slutten av et spill der den ekstra dybden fra det smale vinduet og en enkel seier/tap -evalueringsfunksjon kan føre til et avgjørende resultat. Hvis et aspirasjonssøk mislykkes, er det enkelt å oppdage om det mislyktes høyt (høy kant på vinduet var for lav) eller lav (nedre kant av vinduet var for høy). Dette gir informasjon om hvilke vindusverdier som kan være nyttige i et nytt søk av stillingen.

Over tid har andre forbedringer blitt foreslått, og Falphabeta (fail-soft alfa-beta) ideen om John Fishburn er nesten universell og er allerede innarbeidet ovenfor i en litt modifisert form. Fishburn foreslo også en kombinasjon av det drepende heuristiske og nullvindus-søket under navnet Lalphabeta ("siste trekk med minimalt vindu alfa-beta-søk").

Andre algoritmer

Siden minimax- algoritmen og dens varianter iboende er dybde-først , brukes vanligvis en strategi som iterativ utdypning i forbindelse med alfa-beta, slik at et rimelig godt trekk kan returneres selv om algoritmen blir avbrutt før den er ferdig med utførelsen. En annen fordel ved å bruke iterativ utdypning er at søk på grunnere dybder gir tips om bevegelsesordre, samt grunne alfa- og betaestimater, som begge kan bidra til å produsere avbrudd for søk på høyere dybde mye tidligere enn det som ellers ville vært mulig.

Algoritmer som SSS* , derimot, bruker den best-first- strategien. Dette kan potensielt gjøre dem mer tidseffektive, men vanligvis til en stor kostnad i arealeffektivitet.

Se også

Referanser

Bibliografi

George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Kapittel 7: Stifinning i AI". Algoritmer i et nøtteskall . Oreilly Media . s. 217–223. ISBN 978-0-596-51624-6.
Judea Pearl , Heuristics , Addison-Wesley, 1984
John P. Fishburn (1984). "Vedlegg A: Noen optimaliseringer av α-β-søk". Analyse av Speedup i distribuerte algoritmer (revisjon av doktorgradsoppgave fra 1981) . UMI Research Press. s. 107–111. ISBN 0-8357-1527-2.

Languages

In other projects