Alpha-beta budama

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.

Örnek çözümü göster

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))

Kendini test et

alpha güncelleme

alpha = max(alpha, ____)

Cevabı göster

alpha = max(alpha, value)

Max dalında budama ne zaman yapılır?
```
if alpha >= beta:
    break
```
- Alpha, beta'dan büyükse
- Alpha sıfırsa
- Beta sıfırsa
- Tüm çocuklar tarandığında
Cevabı göster

Alpha, beta'dan büyükse — Alpha >= beta olduğunda geri kalan çocuklar buda nır.
Alpha-beta kavramları

alpha

Max alt sınır
beta

Min üst sınır
budama

Gereksiz dal kesme
O(b^(d/2))

İyi sıralama

Sıradaki ders: Nash dengesi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler