Alfabetabeskärning är en sökalgoritm som försöker minska antalet noder som utvärderas i ett sökträd med minimaxalgoritmen . Designad för antagonistiska spel och används för maskinspel (i datorschack , computer go och andra). Algoritmen är baserad på idén att utvärderingen av en gren av sökträdet kan avslutas i förtid (utan att beräkna alla värden för utvärderingsfunktionen) om det konstaterades att värdet på utvärderingsfunktionen för denna gren är i i vilket fall som helst sämre än vad som beräknats för föregående gren. Alfabetabeskärning är en optimering eftersom den inte påverkar algoritmens korrekthet.
Allen Newell och Herbert Simon , med hjälp av vad John McCarthy kallade en "approximation" [1] 1958, skrev att alfa-beta-beskärning " tycks ha uppfunnits upprepade gånger " [2] . Arthur Samuel , Richards, Hart, Levin, Edwards föreslog oberoende tidiga versioner av denna algoritm [3] . McCarthy lade också fram liknande idéer vid Dartmouth-seminariet 1956 och föreslog sedan, 1961, till en grupp av sina studenter vid MIT , inklusive Alan Kotok [4] för forskning . Alexander Brudno upptäckte självständigt algoritmen och publicerade sina resultat 1963 [5] . 1975 förbättrade Donald Knuth och Ronald Moore algoritmen genom att lägga till "beta"-beskärning [6] [7] .
Fördelen med alfa-beta-beskärning är i själva verket att några av sökträdets undernivågrenar kan uteslutas efter att minst en av nivågrenarna har beaktats i sin helhet. Eftersom klippning sker på alla häckningsnivåer (förutom den sista), kan effekten vara ganska betydande. Metodens effektivitet påverkas avsevärt av den preliminära sorteringen av alternativ (utan uppräkning eller med uppräkning till ett mindre djup) - vid sortering, ju fler "bra" alternativ som beaktas i början, desto fler "dåliga" grenar kan kapas av utan en uttömmande analys.
| Algoritmer för grafsökning | ||
|---|---|---|
| Oinformerade metoder | ||
| Informerade metoder | ||
| Genvägar | ||
| Minsta spännträd | ||
| Övrig | ||