Alpha-beta budama
- Algoritmalar kursu
- Uzman seviye
- Ders 32/41
- 4 dk
Alpha-beta budama ile aramayı hızlandırmayı öğrenirsin.
Alpha-beta budama
Alpha-beta budama, minimax'ın hızlandırılmış halidir. Oyun ağacında kesin değerlendirilmeyecek dalları budar; sonuç aynı kalır.
Alpha, max oyuncunun güvence altına aldığı en düşük değer; beta, min oyuncunun güvence altına aldığı en yüksek değerdir.
Bir düğümde alpha >= beta olduğunda, geri kalan çocuklar incelenmeden budama yapılır. İyi sıralama ile karmaşıklık O(b^(d/2))'ye iner.
Budama koşulu
Max dalında her çocuk değerlendirildikten sonra alpha = max(alpha, value) ile alpha güncellenir. Eğer alpha >= beta ise, geri kalan çocuklar incelenmeden döngüden çıkılır.
Min dalında ise beta = min(beta, value) ile beta güncellenir ve beta <= alpha koşulu sağlanırsa budama yapılır.
Budama, hiçbir zaman nihai minimax değerini değiştirmez; yalnızca gereksiz hesabı önler.
Uygulama alphabeta fonksiyonu
alphabeta(node, alpha, beta, is_max) yaz. Minimax değerini budamayla döndür. print(alphabeta([[3, 5], [2, 9]], float('-inf'), float('inf'), True)) ile 3 yazdır.
Başlangıç kodu
def alphabeta(node, alpha, beta, is_max):
# Alpha-beta budamalı minimaxÖrnek çözüm
def alphabeta(node, alpha, beta, is_max):
# Alpha-beta budamalı minimax
if not isinstance(node, list):
return node
if is_max:
value = float('-inf')
for child in node:
value = max(value, alphabeta(child, alpha, beta, False))
alpha = max(alpha, value)
if alpha >= beta:
break
return value
value = float('inf')
for child in node:
value = min(value, alphabeta(child, alpha, beta, True))
beta = min(beta, value)
if beta <= alpha:
break
return value
print(alphabeta([[3, 5], [2, 9]], float('-inf'), float('inf'), True))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 alpha güncelleme
alpha = max(alpha, ____)alpha = max(alpha, value)Açıklama: alpha, value ile karşılaştırılır.
2 Max dalında budama ne zaman yapılır?
if alpha >= beta:
break- Alpha, beta'dan büyükse Doğru cevap
- Alpha sıfırsa
- Beta sıfırsa
- Tüm çocuklar tarandığında
Açıklama: Alpha >= beta olduğunda geri kalan çocuklar buda nır.
3 Alpha-beta kavramları
| Kavram | Anlamı |
|---|---|
alpha |
Max alt sınır |
beta |
Min üst sınır |
budama |
Gereksiz dal kesme |
O(b^(d/2)) |
İyi sıralama |