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(b^n/2)  ile O(bⁿ) 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.

Bu örnekte budanması gereken dalları belirleyelim.

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

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