Pagtatabas na alpha-beta

Pagtatabas na alpha-beta. Ang naka-gray na mga pangilalim na puno(subtrees) ay hindi na kailangang galugarin(kapag ang mga galaw ay sinusuri mula sa kaliwa hanggang kanan) dahil alam nating ang pangkat ng mga pang-ilalim na puno bilang kabuuan ay nagbibigay ng halaga ng katumbas na pang-ilalim na puno o mas masama at sa gayon ay hindi makakaimpluwensiya sa huling resulta. Ang mga lebel na max at min ay kumakatawan sa paggalaw(turn) ng manlalaro at katunggali nito.

Ang pagtatabas na Alpha-beta (Ingles: Alpha-beta pruning) ay isang algoritmo ng paghahanap na naghahangad na bawasan ang bilang ng mga nodo na sinusuri ng algoritmong minimaks sa puno ng paghahanap (search tree) nito. Ito ay isa ring adbersaryal na algoritmo ng paghahanap na karaniwang ginagamit para sa paglalarong makina ng dalawang-manlalarong mga laro(gaya ng Tic-tac-toe, ahedres, Go, atbp.). Ito ay kompletong tumitigil sa pagsusuri ng isang galaw (move) kung ang hindi bababa sa isang posibilidad ay natagpuan na nagpapatunay na ang galaw na ito ay mas masama kesa sa nakaraang sinuring galaw. Ang mga gayong galaw ay hindi na kailangan pang karagdagang suriin. Kapag inilapat sa pamantayang punong minimaks, ito ay nagbabalik ng parehong galaw gaya ng ibabalik ng minimiks ngunit tinatabas ang mga sanga na hindi posibleng makakaimpluwensiya sa huling desisyon.

Kasaysayan

Sina Allen Newell at Herbert Simon na gumamit ng tinatawag ni John McCarthy na aproksimasyon noong 1958 ay sumulat na ang alpha-beta ay "lumilitaw na muling inimbento ng ilang mga beses". Si Arthur Samuel ay may maagang bersiyon nito at sina Richards, Hart, Levine at/o Edwards ay independiyenteng nakatuklas ng alpha-beta sa Estados Unidos. Si McCarthy ay nagmungkahi ng parehong mga ideya sa konperensiyang Dartmouth noong 1956 at sa isang pangkat ng kanyang mga estudyante kabilang si Alan Kotok sa MIT noong 1961. Independiyenteng natuklasan ni Alexander Brudno ang algoritmong alpba-beta na inilimbag ang kanyang mga resulta noong 1963. Pinino nina Donald Knuth at Ronald W. Moore ang algoritmong ito noong 1975 at napatunayan ni Judae Pearl ang optimalidad nito noong 1982.

Pagpapabuti sa walang muwang(naive) na minimaks

Ang kapakinabangan ng pagtatabas na alpha-beta ay nagkasalig sa katotohanang ang mga sanga ng hinahanap na puno(search tree) ay maaaring alisin. Sa paraang ito, ang panahong ng paghahanap ay maaaring limitihan sa 'mas kanais nais' na pang-ilalim na puno(subtree) at ang isang mas malalim na paghahanap ay maaaring isagawa sa parehong panahon. Tulad ng predesesor nito, ito ay kabilang sa sanga at hangganan(branch and bound) na klase ng mga algoritmo. Ang optimisasyong ito ay nagbabawas ng epektibong lalim sa medyo higit sa kalahati ng minimaks kung ang mga nodo ay sinuri sa isang optimal o malapit sa optimal na order o pinakamabuting pinili para sa panig na gumagalaw na iniayos muna sa bawat nodo.

Sa pagkakaroon ng aberahe o konstanteng sumasangang paktor ng b at isang hinahanap na kalalilimang d mga ply, ang maksimum o pinakamataas na bilang ng mga posisyon ng sinuring dahong nodo(kapag ang pagsasaayos ng galaw ay pessimal) ay O(b*b*...*b) = O(b^d) – na pareho sa isang simpleng paghahanap na minimaks. Kung ang pagsasaayos ng galaw para sa paghahanap ay optimal na nangangahulugang ang pinakamahusay na na mga galaw ang unang hinahanap, ang bilang ng mga sinsuring posisyon ng dahong nodo ay mga O(b*1*b*1*...*b) para sa lalim na odd at O(b*1*b*1*...*1) para sa lalim na even o $O(b^{d/2})=O({\sqrt {b^{d}}})$. Sa huling kaso, kung saan ang ply ng hinahanap ay even, ang epektong sumasangang paktor ay napaliit sa kwadradong ugat nito o sa katumbas, ang paghahanap ay maaaring tumungo ng dalawang beses na kasinglalim sa parehong halaga ng komputasyon. Ang paliwanag ng b*1*b*1*... is that all the ay ang mga galaw ng unang manlalaro ay dapat pag-aralan upang mahanapin ang pinakamahusay ngunit para sa bawat isa, ang tanging ikalawang pinakamahusay na galaw ng manlalaro ang kailangan upang pabulaanan ang lahat maliban sa una at pinakamahusay na galawa ng unang manlalaro. Ang alpha-beta ay sumisigurong walang ibang galaw ng ikalawang manlalaro ay kailangang isaalang alang. Kapag ang mga nodo ay isinaayos ng randoma, ang aberaheng bilang ng mga sinusuring nodo ay mga $O(b^{3/4})$.

Sa normal na paglalarawan, habang isinasagawa ang alpha-beta, ang mga pang-ilalim na puno(subtrees) ay temporaryong dinodominahan ng kalamangan ng unang manlalaro(kapag marami sa mga galaw ng unang manlalaro ay mahusay at sa bawat hinahanap na lalim, ang unang galaw na tiningnan ng unang manlalaro ay sapat ngunit ang lahat ng mga tugon ng ikalawang manlalaro ay kinakailangan upang makanahap ng pagpapamali) o vice versa. Ang kalamangang ito ay maaaring magpalit ng mga panig ng maraming mga beses habang isinasagawa ang paghahanap kung ang pagsasaayos ng galaw ay hindi tama na sa bawat panahon ay tumutungo sa kawalang kaigihan. Habang ang bilang mga posisyong hinahanap ay lumiliit ng eksponensiyal sa bawat galaw na mas malapit sa kasalukuyang posisyon, karapat dapat na igugol ang malaking bilang ng pagsisikap sa pagsasaayos ng mga naunang galaw. Ang pinabuting pagsasaayos sa anumang lalim ay eksponensiyal na magbabawas ng kabuuang bilang ng mga posisyong hinahanap ngunit ang pagsasaayos ng lahat ng mga posisyon sa mga lalim na. Sa kasanayan, ang pagsasaayos ng galaw ay kalimitang natutukoy ng mga resulta ng mas una at mas maliit na mga paghahanap gaya ng sa paulit ulit na pagpapalalim.

Ang algoritmong ito ay nagpapanatili ng dalawang mga halaga, ang alpha at beta na kumakatawan sa minimum na iskor na ang nag-mamaksimang(maximizing) manlalaro ay sinisiguruhan at ang maksimum na iskor ng nagminimisang(minimizing) ay sinusuguruhan. Sa simula, ang alpha ay negatibong inpinidad at ang beta ay positibong inpinidad. Habang ang rekursiyon ay nagpapatuloy, ang "bintana" ay nagiging maliit. Kapag ang beta ay naging mas maliit kesa sa alpha, ito ay nangangahulugang ang kasalukuyang posisyon ay hindi maaaring maging resulta ng pinakamahusay na laro ng parehong mga manlalaro at kaya ay hindi na kailangan pang karagdagang galugarin.

Sa karagdagan, ang algoritmong ito ay maliit na baguhin upang magbalik ng kabuuang prinsipal na bariasyon sa karagdagan sa iskor. Ang ilang mas agresibong mga algoritmo gaya ng MTD(f) ay hindi madaling pumapapayag sa gayong mga modipikasyon.

Pseudocode

function alphabeta(node, depth, α, β, Player)         
    if  depth = 0 or node is a terminal node
        return the heuristic value of node
    if  Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Beta cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Alpha cut-off *)
        return β 
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

Mga heuristikang pagpapabuti

Ang karagdagang pagpapabuti ay maaaring makamit ng hindi sinasakripisyo ang akurasyon sa pamamagitan ng paggamit ng mga heuristika upang hanapin ang mga bahagi ng puno(tree) na mas malamang na pumwersa sa mga simulang limitasyon(cutoff) na alpha-beta. Halimbawa, sa chess, ang mga galaw na na kumukuha ng mga piyesa ay maaaring suriin bago ang mga galaw na hindi kumukuha ng piyesa o ang mga galaw na naka-iskor ng mataas sa mas naunang pagdaan sa pamamagitan ng pagsusuri ng puno ng laro(game tree) ay maaaring suriin bago ang iba. Ang isa pang karaniwan at napaka murang heuristika ang mamamatay na heuristika kung saan ang huling galaw na nagsanhi ng beta cutoff sa parehong lebel sa punong hinahanap ay palaging unang sinusuri. Ang ideyang ito ay maaaring lahatin sa isang pangkat ng mga tablang nagpapamali.

Ang paghahanap na alpha-beta ay maaaring pang gawing mas mabilis sa pamamagitan ng pagsasaalang lamang ng isang makitid na bintana ng paghahanap(na sa pangkalahatan ay natutukoy ng paghuhula batay sa karanasan). Ito ay tinatawag na paghahanap na aspirasyon. Sa sukdulang kaso, ang paghahanap ay isinasagaw na ang alpha at beta ay magkatumbas sa teknikong tinatawag na zero-window search, null-window search, o scout search. Ito ay partikular na magagamit para sa paghahanap na panalo/pagkatalo malapit sa huli ng laro kung saan ang ekstrang lalim na nakamit mula sa makitid na bintana at isang simpleng punsiyon] na sumusuri ng pagkapanalo/pagkatalo ay maaaring tumungo sa isang konklusibong resulta. Kapag ang paghahanap na aspirasyon ay nabigo, tuwirang matutukoy kung ito ay nabigo na mataas(ang mataas na gilid ng bintana ay napaka baba) o mababa(ang mas mababang gilid ng bintana ay labis na mataas). Ito ay nagbibigay ng impormasyon kung anong mga halaga ng bintana ay maaaring magagamit sa muling paghahanap ng posisyon.

Iba pang mga algoritmo

Ang mas sulong na mga algoritmo ay mas mabilis habang may kakayahan pa ring kumuwenta ng halagang minimaks ay alam gaya ng SCOUT , Negascout at MTD-f.

Dahil sa ang algortimong minimaks at mga barianto nito ay likas na lalim muna, ang isang stratehiya gaya ng paulit ulit na pagpapalalim ay karaniwang ginagamit kasabay ng alpha-beta upang ang makatwirang mahusay na galaw ay maaaring ibalik kahit ang algoritmo ay naabala bago pa matapos ang eksekusyon nito. Ang isa pang kalamangan ng paggamit ng paulit ulit na pagpapalim ay ang mga paghahanap sa mas mababaw na mga lalim ay nagbibigay ng mga hiwatig na pagsasaayos ng galaw na maaaring makatulong sa paglikha ng mga cutoff para sa mas mataas na lalim na mga paghahanap nang mas maaga na kundi ay hindi magiging posible.

Ang mga algoritmong tulad ng SSS* sa kabilang dako ay gumagamit ng unang pinakamahusay na paghahanap. Ito ay potensiyal na makakagawa ng mas maigi sa panahon ngunit sa karaniwan ay sa mabigat na gastos sa kaigihan ng espasyo.