Alfa Beta Budaması (Alpha Beta Prunning)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde özellikle yapay zeka ve karar mekanizmalarının uygulanmasında çok kullanılan bir ağaç dolaşma algoritmasıdır. İsmindeki budama da bu ağaç üzerindeki bazı dalları kesmesinden gelmektedir.

Yazının konusu olan alfa beta budaması (alpha beta prunning) minimax ağaçlarında (minimax trees) kullanılır. Bu ağaçları anlattığımız yazıdan aşağıdaki şekli alıp hatırlayacak olursak:

Şekildeki ağacın kökünde olan mevcut durumda yapılabilecek bütün ihtimaller gösterilmiştir. Bu ağaç bir tictactoe oyunu için tasarlandığından ve oyundaki hamle sayısı sınırlı olduğundan bilgisayarın hesaplaması açısından sorun oluşturmaz. Ancak hamle sayısının çok fazla olduğu satranç veya GO gibi oyunlar düşünülürse bütün hamlelerin hesaplanması bilgisayarlar için (günümüz teknolojisinde hâlâ ) imkansızdır. Bu durumda hesaplamayı kolaylaştırmak için bu ağaç üzerinde bir iyileştirilmeye gidilmesi gerekir.

İşte tam bu noktada alfa beta budaması devreye girer. Ağacın bazı dallarının işlenmesi ve hamlelerinin sonucunun hesaplanması gereksizdir. Alfa beta budaması bu dalları tespit ederek budar. Yani bu dalları ve altlarını hesaplamayarak performans artışı hedeflenir.

Klasik minimax ağacı işlenirken iki adımlı arama yapılır. Birinci adıma ağaçtaki düğümlere (nodes) sezgisel (heuristic) değerler atanır. İkinci adımda ise en derinden başlanarak bu değerler yukarı doğru işletilir. En sonunda mevcut konumda yapılacak hamleye karar verilir.

Bu anlamda alfa beta araması olarak isimlendirebileceğimiz yeni arama algoritmamız derin öncelikli aramadır (depth first search). Öncelikle alfa ve beta isminde iki değer belirlenir. Burada alfa ile anlatılan o ana kadar ulaşılan azami değerdir. Yani alfa değeri hiçbir zaman azalamaz hep artar, buna mukabil beta değeri ise anlık asgari değerdir. Beta değeri de hiçbir zaman artamaz hep azalır.

İşte tam bu noktada elimizde alfa ve beta değerlerini bulunduruyorsak artık budama yapabiliriz. Örneğin ağacın herhangi bir düğümündeyken elimizde alfa değeri olarak 16 bulunsun. Bu değerden büyük olan düğümlere bakılmasına gerek yoktur çünkü o ana kadar olan en büyük değer zaten elimizdedir, bu değerden büyük olan değerleri taşıyan alt ağaçlar sonucu etkilemeyecektir. Öyleyse elimizdeki alfa değerinden büyük olan dalları budayabiliriz. Bunun ismi alfa budamasıdır.

Benzer şekilde beta değeri elimizdeki en küçük anlık değeri tutacaktır. Bu değerden küçük olan dalların dolaşılması da anlamsızdır ve budanabilir. Bunun ismi de beta budamasıdır. Yani budanan dal, beta’nın altına kalması veya alfa’nın üstünde olmasına göre beta veya alfa budaması ismini alır.

Bu durumu bir örnek üzerinden anlamaya çalışalım. Örneğin aşağıdaki ağacı ele alalım:

Yukarıdaki şekil üzerinde, A kök düğümünden başlanarak minimax dolaşmamızı gerçekleştirelim. Öncelikle alfa ve beta değerlerini atayalım. Örneğin alfa değeri olarak –¥ ve beta değeri olarak ¥ aldığımızı düşünelim. Bu durumda yukarıdaki ağacın dolaşılması sırasında alfa ve beta değerleri güncellenerek dolaşılacaktır.

Bu yazı şadi evren şeker tarafından yazılmış ve bilgisayarkavramlari.com sitesinde yayınlanmıştır. Bu içeriğin kopyalanması veya farklı bir sitede yayınlanması hırsızlıktır ve telif hakları yasası gereği suçtur.

İlk olarak kök A’dan B -> E -> L şeklinde en derine indiğimizi düşünelim (depth first search). Bulduğumuz değer 7 olacak ve dolayısıyla asgari değerin arandığı bu seviyede L ve M düğümleri (nodes) için en küçük değer 6 olacaktır (6 < 7) dolayısıyla bu iki düğümün taranmasından sonra E düğümü için 6 bulunacaktır. (bir üst seviyeye asgari değer çıkarılıyor)

Benzer şekilde normal bir minimax ağaç dolaşması sırasında F için 5 ve G için 2 bulunacaktır. Ancak E düğümünün altındaki düğümler taranırken alfa ve beta değerleri güncellenir. Alfa değeri olarak 6 ve beta değeri olarak 7 bulunacaktır.

Şimdi ağacın yukarı doğru bütün düğümlerinde bu durumu düşünebiliriz. Yani E düğümü için en küçük 6 en büyük 7 olurken B düğümü için en büyük 7 ve en küçük 6 ve A düğümü için en küçük 6 en büyük 7 olacaktır.

Burada dikkat edilecek husus, yukarı doğru her seviyede alfa ve betanın yer değiştirmesidir. Çünkü her seviyede aranan değer değişmektedir, örneğin en alt seviyede asgari değer aranırken bir üstünde azami bir üstünde asgari … şeklinde gitmektedir.

E-F-G düğümleri arasından en büyük değeri alacağımızı biliyoruz. Ayrıca L-M-N-O-P-Q düğümlerinden de en küçüğünü alacağımızı biliyoruz. O halde ağaç dolaşılırken LMNOPQ düğümlerinin asgarisi, bir önceki daldakinden daha büyükse o düğümden geri kalanlar budanabilir.

Ağaçta kaldığımız noktadan devam ederek budama işleminin nasıl yapıldığına bakalım. F düğümünün altında 8 ve 5 değerlerine bakılacak, küçük olan 5 dönecek ve alfa ve beta değerlerinde bir değişiklik olmayacaktır. Çünkü 5 değeri bir üst seviyede önemsizdir. Bir üst seviyede azami değeri alacağımız için ve E düğümünde zaten 6 olduğu için bu seviyede 5 anlamsızdır.

Dolaşmaya G düğümü ile devam edelim. P düğümüne ulaştığımızda 2 değerini göreceğiz.

İşte tam bu noktada artık geri kalan düğümleri budayabiliriz. Çünkü 2 değeri elimizdeki alfa değerinden küçüktür. Diğer düğümlerin budanmasının (yani Q düğümüne hiç bakılmamasının) anlamını berber inceleyelim.

G düğümünün altındaki en küçük değer 2 (veya daha küçük de olabilir) ancak biz 2 bulunca geri kalanları buduyoruz çünkü her halükarda yukarı (yani G düğümü seviyesine) 2 veya daha küçük bir sayı çıkacaktır. Çıkan bu sayı ise G düğümü seviyesinde anlamsız olacaktır çünkü bu seviyede en büyük değer aranacaktır. En büyük değer zaten 6 olarak E düğümünde bulunmuştu. Dolayısıyla E düğümünde 6 olduğu bir durumda diğer düğümlerin altındaki en küçük düğümün önemi yoktur.

Dolaşmaya H düğümü ile devam edelim. Altındaki düğümlerden en küçüğünü alalım (0 ve -2’den küçük olanı) -2, H değeri olarak alınır.

Benzer şekilde I değeri T ve U düğümlerinden küçük olanı olarak alınır yani I değeri olarak da 2 bulunur. Ardından C Değeri olarak H ve I düğümlerinden büyük olan yani 2 alınır.

Bu seviyede yani BCD seviyesinde B değerini 6 ve C değerini 2 olarak bulduk şimdi sıra D düğümünde.

D düğümünün altındaki J ve J’nin de altındaki V düğümüne derin öncelikli arama gereği bakıldığı anda D düğümü artık kökten budanabilir. Sebebi ise şayet V değeri olan 5 yukarıdaki J düğümüne atanırsa (ki bu seviyedeki en küçük değer olarak kabul edelim, daha küçük bir değer olursa daha da kesin olarak budama yaparız) ve J düğümünün değeri olarak da K düğümünden büyük olduğunu kabul edersek (K’nın daha büyük olması halinde budama yine daha kesin olur) K’nın üstündeki D düğümüne değer olarak 5 gelir ve 5 değeri, daha önce C düğümünün değeri olarak hesapladığımız 2’den büyük olduğu için zaten bir üst seviye olan A düğümüne çıkamaz. Dolayısıyla D düğümü ve altındakilerin hesaplanması gereksizdir.

Yukarıdaki örnekte Q ve W düğümleri budanırken alfa budaması (alpha pruning) ve K düğümü budanırken de beta budaması (beta prunning) kullanılmış olunur. Kısaca alfa > beta olduğu durumlarda budama yapılır.