Alfa Beta Budaması

Alfa Beta Budaması

Oyun ağacı üzerinde  gereksiz dallar var ise alfa beta budamasıyla yok edilir. Alfa beta budaması minimax algoritması üzerinde yapılan bir iyileştirmedir.

Alfa (α)–> Garantilenmiş max değerdir. Arama sonunda kökün değeri α dan küçük olamaz.

Beta (β)–> Alınabilecek min değerdir. Arama sonunda kökün değeri β dan büyük olamaz.

Başlangıçta α=-∞ β=+∞ dur.

Arama sırasında α nın β dan büyük ya da eşit çıktığı an dal ağaçtan çıkartılır. Yani o dal üzerinde budama yapılmış olur. Algoritmanın performansı O(bn/2)  ile O(bn) arasında değişir.

Algoritmanın adımları:

1- Max değer seçilir. Eğer değer α dan büyükse α=değer yapılır. Min değer seçen rakip ise değeri β ile karşılaştırır. Eğer β dan küçükse β=değer olur.

2- Eğer α>=β olursa dal kesilir. İşlemler köke uygulanıncaya kadar devam eder.

Genel olarak algoritmanın mantığı bu şekildedir. Ağacın en altından başlanarak yukarıya doğru yani köke doğru bu adımlar uygulanır.

Max değeri seçen

değer>α

α=değer

Min değeri seçen

değer<β

β=değer

IF (α>=β) ise dal budanır.

Ekran Alıntısı

Bu örnekte budanması gereken dalları belirleyelim.

Ekran Alıntısı

Görüldüğü gibi L düğümü gereksiz olduğundan budanma işlemi uygulanmıştır.

Umarım yararlı olmuştur. İyi çalışmalar..

Hakkında Ali Demirci

Ben Ali Demirci... 1991 Ankara doğumluyum. Ankara da yaşıyorum. Fırsat buldukça öğrendiklerimi burada paylaşıyorum. Java ile haşır neşirim. Android'den asla vazgeçemem. Öğrenmeye bayılırım. Yeni şeyler öğrendiğimde, geçmişteki projelerimde keşke böyle yapsaydım diye çok üzülmüşümdür. O yüzden öğrenmekten korkmayın. Takıldığınız yerleri mutlaka sorun. Biliyorsam yanıt veririm. Bilmiyorsam yol gösteririm. Teşekkürler :)

Kontrol Et

Regex Nedir? Nasıl Kullanılır?

Regex(Regular Expression) yani düzenli ifadeler, metinlerde aranan bir tümceyi kolayca bulmamızı sağlayan bir çeşit algoritmadır. Yani …