Pagtatabas na alpha-beta

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^[1] noong 1958 ay sumulat na ang alpha-beta ay "lumilitaw na muling inimbento ng ilang mga beses". ^[2] 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.^[3] 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.^[4] Independiyenteng natuklasan ni Alexander Brudno ang algoritmong alpba-beta na inilimbag ang kanyang mga resulta noong 1963. ^[5] Pinino nina Donald Knuth at Ronald W. Moore ang algoritmong ito noong 1975^[6]^[7] at napatunayan ni Judae Pearl ang optimalidad nito noong 1982.^[8]

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. ^[9] 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})$ ^[1].

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 ^[10], 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.

Sanggunian

↑ ^1.0 ^1.1 McCarthy, John (LaTeX2HTML 27 November 2006). "Human Level AI Is Harder Than It Seemed in 1955". Nakuha noong 2006-12-20. {{cite web}}: Check date values in: |date= (tulong)
↑ Newell, Allen and Herbert A. Simon (1976). "Computer Science as Empirical Inquiry: Symbols and Search" (PDF). Communications of the ACM. 19 (3). Nakuha noong 2006-12-21. {{cite journal}}: Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link)
↑ Edwards, D.J. and Hart, T.P. (4 December 1961 to 28 October 1963). "The Alpha-Beta Heuristic (AIM-030)". Massachusetts Institute of Technology. Nakuha noong 2006-12-21. {{cite web}}: Check date values in: |date= (tulong)CS1 maint: multiple names: mga may-akda (link)
↑ Kotok, Alan (XHTML 3 December 2004). "MIT Artificial Intelligence Memo 41". Inarkibo mula sa orihinal noong 2020-11-06. Nakuha noong 2006-07-01. {{cite web}}: Check date values in: |date= (tulong)
↑ Marsland, T.A. (1987). "Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)" (PDF). J. Wiley & Sons. pp. 159–171. Inarkibo (PDF) mula sa orihinal noong 2003-09-06. Nakuha noong 2006-12-21. {{cite web}}: External link in |author= (tulong); Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link) Naka-arkibo 2003-09-06 sa Wayback Machine.
↑
* Knuth, D. E., and Moore, R. W. (1975). "An Analysis of Alpha-Beta Pruning" (PDF). Artificial Intelligence. 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3.{{cite journal}}: CS1 maint: date auto-translated (link) CS1 maint: multiple names: mga may-akda (link)^{[patay na link]}
- Reprinted as Chapter 9 in Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. ISBN 1-57586-212-3. OCLC 222512366. Inarkibo mula sa orihinal noong 2010-12-01. Nakuha noong 2012-02-07.{{cite book}}: CS1 maint: date auto-translated (link)
↑ Abramson, Bruce (1989). "Control Strategies for Two-Player Games". ACM Computing Surveys. 21 (2): 137. doi:10.1145/66443.66444. Inarkibo mula sa orihinal noong 2008-08-20. Nakuha noong 2008-08-20. {{cite journal}}: Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link) Naka-arkibo 2008-08-20 sa Wayback Machine.
↑ Pearl, Judea (1982). "The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality". Communications of the ACM. 25 (8): 559–564. {{cite journal}}: Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link)
↑ Padron:Russell Norvig 2003
↑ Pearl, J., "SCOUT: A Simple Game-Searching Algorithm With Proven Optimal Properties," Proceedings of the First Annual National Conference on Artificial Intelligence, Stanford University, August 18-21, 1980, pp. 143-145.

[JMC-1] 1.0 ^1.1 McCarthy, John (LaTeX2HTML 27 November 2006). "Human Level AI Is Harder Than It Seemed in 1955". Nakuha noong 2006-12-20. {{cite web}}: Check date values in: |date= (tulong)

[NS-2] Newell, Allen and Herbert A. Simon (1976). "Computer Science as Empirical Inquiry: Symbols and Search" (PDF). Communications of the ACM. 19 (3). Nakuha noong 2006-12-21. {{cite journal}}: Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link)

[AIM30-3] Edwards, D.J. and Hart, T.P. (4 December 1961 to 28 October 1963). "The Alpha-Beta Heuristic (AIM-030)". Massachusetts Institute of Technology. Nakuha noong 2006-12-21. {{cite web}}: Check date values in: |date= (tulong)CS1 maint: multiple names: mga may-akda (link)

[AIM41-4] Kotok, Alan (XHTML 3 December 2004). "MIT Artificial Intelligence Memo 41". Inarkibo mula sa orihinal noong 2020-11-06. Nakuha noong 2006-07-01. {{cite web}}: Check date values in: |date= (tulong)

[Marsland-5] Marsland, T.A. (1987). "Computer Chess Methods (PDF) from Encyclopedia of Artificial Intelligence. S. Shapiro (editor)" (PDF). J. Wiley & Sons. pp. 159–171. Inarkibo (PDF) mula sa orihinal noong 2003-09-06. Nakuha noong 2006-12-21. {{cite web}}: External link in |author= (tulong); Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link) Naka-arkibo 2003-09-06 sa Wayback Machine.

[Knuth-Moore-6] * Knuth, D. E., and Moore, R. W. (1975). "An Analysis of Alpha-Beta Pruning" (PDF). Artificial Intelligence. 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3.{{cite journal}}: CS1 maint: date auto-translated (link) CS1 maint: multiple names: mga may-akda (link)^{[patay na link]}
Reprinted as Chapter 9 in Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. ISBN 1-57586-212-3. OCLC 222512366. Inarkibo mula sa orihinal noong 2010-12-01. Nakuha noong 2012-02-07.{{cite book}}: CS1 maint: date auto-translated (link)

[7] Reprinted as Chapter 9 in Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. ISBN 1-57586-212-3. OCLC 222512366. Inarkibo mula sa orihinal noong 2010-12-01. Nakuha noong 2012-02-07.{{cite book}}: CS1 maint: date auto-translated (link)

[Abramson-7] Abramson, Bruce (1989). "Control Strategies for Two-Player Games". ACM Computing Surveys. 21 (2): 137. doi:10.1145/66443.66444. Inarkibo mula sa orihinal noong 2008-08-20. Nakuha noong 2008-08-20. {{cite journal}}: Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link) Naka-arkibo 2008-08-20 sa Wayback Machine.

[8] Pearl, Judea (1982). "The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality". Communications of the ACM. 25 (8): 559–564. {{cite journal}}: Unknown parameter |month= ignored (tulong)CS1 maint: date auto-translated (link)

[9] Padron:Russell Norvig 2003

[10] Pearl, J., "SCOUT: A Simple Game-Searching Algorithm With Proven Optimal Properties," Proceedings of the First Annual National Conference on Artificial Intelligence, Stanford University, August 18-21, 1980, pp. 143-145.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]