Alfa-Beta Budaması (Alpha-Beta Pruning)

alfa-beta budaması nedir?

Alfa-beta budaması, minimax algoritmasını hızlandıran bir optimizasyon. İki oyunculu oyunlarda (satranç, go, tic-tac-toe) bir motor, olası hamleleri bir ağaç gibi açar ve minimax ile "ben en iyisini, rakip en kötümü seçerse sonuç ne olur?" diye hesaplar. Ama bu ağaç çok hızlı büyür. Alfa-beta, sonucu değiştiremeyecek dalları hiç açmadan atlayarak çok daha az düğüm değerlendirir — ve böylece aynı sürede daha derine bakar.

Önemli ayrım: bu "üret sonra at" değil. Budanan düğümler hiç oluşturulmaz bile.

nasıl çalışır?

Arama boyunca iki değer taşınır:

• alfa: MAX oyuncusunun şu ana kadar garantileyebildiği en iyi skor (başta −∞).
• beta: MIN oyuncusunun garantileyebildiği en iyi skor (başta +∞).

İlerledikçe bu sınırlar güncellenir. Bir noktada alfa ≥ beta olursa, o dalın geri kalanı budanır — çünkü oradan gelecek hiçbir değer kök kararı değiştiremez. Örnek: MAX bir koldan en az 2 garantilemişse ve diğer kolda MIN en fazla 0 verebiliyorsa, MIN''in o kolundaki kalan hamlelere bakmaya gerek yok; MAX zaten 2''yi seçecek.

neden önemli?

Çünkü minimax ile birebir aynı sonucu verir, ama çok daha ucuza. Budama yalnızca kararı etkileyemeyecek dalları siler, hiçbir doğruluk kaybı yok.

Hız farkı hamle sırasına bağlı:

• İdeal sıralama (iyi hamleler önce): maliyet yaklaşık O(b^(d/2)) — yani budamasız minimax''in yarı derinliğinin maliyeti. Pratikte aynı çabayla yaklaşık iki kat derine bakabilirsin.
• En kötü sıralama: hiç budama olmaz, maliyet O(b^d) — düz minimax ile aynı.

Gerçek motorlar bu ikisinin arasında bir yerde. Ek yük küçük olduğu için alfa-beta kullanmak neredeyse her zaman kazançlı.

kullanım alanları

• Oyun yapay zekâsı: satranç ve dama motorlarının klasik beyni; derin arama bu sayede mümkün.
• Çekişmeli karar aramaları: rakibin en iyi oynadığı varsayılan her senaryo.
• İteratif derinleştirme, sezgisel sıralama, hash tabloları gibi tekniklerle birleşince çok daha güçlü.

Not: hamleleri baştan "en iyiden" sıralayamazsın — en iyiyi bilsen zaten minimax''e gerek kalmazdı. Bu yüzden sezgisel sıralama devreye girer.