Dallanma Faktörü & Düğüm Sayısı
Bir oyun ağacı, başlangıç konumundan mümkün olan her hamle dizisini modeller. Her düğüm, bir tahta durumunu temsil eder. Her kenar, bir yasal hamleyi temsil eder. Ağacın yapısı, aramanın uygulanabilir kalıp kalmadığını belirler.
Temel Parametreler
Dallanma faktörü b: tipik bir konumda mevcut yasal hamle sayısı.
Derinlik d: ileri doğru arama yapılacak hamle sayısı (yarım hamleler).
Derinlik d'de düğüm sayısı: b^d
Tüm derinliklerde toplam düğüm: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Büyük b ve d için, toplam ≈ b^d (yaprak seviyesi tarafından baskındır).
4×4×4 Tic-Tac-Toe
Tam oyun ağacı: b ≈ 64 (yasal kareler), d = 64 (toplam hamleler). Tam düğüm sayısı ≈ 64^64 ≈ 10^115. Gözlemlenebilir evren kabaca 10^80 atom içerir. Kaba kuvvet araması fiziksel olarak imkansızdır.
Ağaç Boyutunu Hesaplama
Satranç daha gerçekçi sayılar sağlar. Ortalama dallanma faktörü b ≈ 35. 6 hamle derinliğindeki bir arama (her taraf 3 hamle) yaklaşık 35^6 düğüm gerektirir.
Alfa-Beta Budaması: Üssü Azaltma
Alfa-beta budaması, minimax sonucunu etkileyemeyen alt ağaçları ortadan kaldırır. Temel fikir: bir dalın V değerini zaten biliyorsanız, değeri kanıtlanabilir şekilde V'nin altına (maksimize eden oyuncu için) veya V'nin üstüne (minimize eden oyuncu için) düşen herhangi bir kardeş dalını budayabilirsiniz.
En İyi Durum Geometrisi
Optimal hamle sıralaması altında (en iyi hamleler önce aranır), alfa-beta etkili dallanma faktörünü b'den √b'ye düşürür. Arama derinliği aynı düğüm bütçesi için etkin bir şekilde iki katına çıkar:
Tam arama: b^d düğüm
Alfa-beta en iyi durum: b^(d/2) düğüm
Örnek: b=35, d=6. Tam: 35^6 ≈ 1,84 × 10^9. Alfa-beta: 35^3 = 42.875. Azaltma faktörü: ~43.000.
Uygulamada, hamle sıralaması mükemmel değildir. Tipik azaltma: b^(d×0,75) — eşdeğer dallanma faktörü ≈ b^0,75.
Merkez-Köşe Dualitesi
Hamming, 4×4×4 küpte geometrik bir dualiteyi not eder: 8 köşe konumunu 8 merkez konumuna (iç 2×2×2 küp) & tersini gönderen bir inversiyon vardır, tüm 76 kazanma çizgisini korurken.
Bir Konum Aracılığıyla Çizgileri Sayma
4×4×4 küpte, konumlar, içlerinden kaç kazanma çizgisinin geçtiğine göre farklılık gösterir:
Köşe konumları: her biri 7 çizgi (4 yüz köşegeni, 2 kenar çizgisi, 1 uzay köşegeni)
Kenar-merkez konumları: her biri 4 çizgi
Yüz-merkez konumları: her biri 6 çizgi
Gövde-merkez konumları (iç 2×2×2): her biri 7 çizgi
Dualite, köşeleri (7 çizgi) gövde-merkezlerine (7 çizgi) eşler. Her iki küme de 'sıcak noktalar' oluşturur.
Sıcak Noktalar Neden Geometrik Olarak Önemlidir
Daha fazla yüksek-çizgi sayılı konumları kontrol eden bir oyuncu daha fazla olası kazanma çizgisini kontrol eder. Bu, doğrudan bir geometrik argümandır: çizgi kapsamı maksimizasyonu, herhangi bir arama olmadan hamle seçimini yönlendirir.
Değerlendirme İşlevleri
Her oyun oynayan program bir değerlendirme işlevine ihtiyaç duyar: tahta durumlarını sayısal değerlere eşleyen bir işlev (pozitif = maksimize eden oyuncu için iyi, negatif = minimize eden oyuncu için iyi). Değerlendirme işlevi, arama ağacının yapraklarındaki sınır koşulunu sağlar.
Doğrusal Değerlendirme İşlevleri
Doğrusal bir değerlendirme işlevi, konumun her özelliğine w_i ağırlığı atar:
E(konum) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
4×4×4 tic-tac-toe için: özellikler, kontrol edilen açık çizgileri, yüksek-çizgi sayılı karelerdeki konumları, tehdit edilen çatalları içerebilir. Satranç için: materyal sayısı, merkez kontrolü, kral güvenliği, piyade yapısı.
Bu, özellik uzayında doğrusal bir işlevdir — ℝ^n'de bir hiper düzlem. Aynı özellik değerlerine sahip iki konum, diğer tüm farklar ne olursa olsun aynı değerlendirmeyi alır. Değerlendirme işlevinin geometrisi, programın 'ne gördüğünü' belirler.
Samuel'ın kontrol programı, ağırlık vektörü w'yi ayarlayarak geliştirildi — doğrusal değerlendirme işlevleri uzayında gradyan iniş.
Geometri & Formalizasyonun Sınırı
Oyun ağacı temiz bir geometrik yapıya sahiptir: d derinliğinde üssel büyüme, alfa-beta tarafından b^(d/2)'ye indirgenebilir, yüksek değerli konumlara kısıtlanarak daha da indirgenebilir (sıcak noktalar etkili b'yi azaltır). Değerlendirme işlevi, özellik uzayında bir hiper düzlem tanımlar.
Bütün bunlar temiz, kesin, resmi olarak tam. Oyun oynama probleminin merkezini açıklar — matematiksel yapının net rehberlik sağladığı bölge.
Sınır — kural uygulamasından keşfetmeye ne zaman geçeceği, konumsal avantajı taktik fırsatla ne zaman değiştireceği, değerlendirme işlevinin ötesindeki ortaya çıkan desenleri nasıl tanıyacağı — bu formalizasyona direnir. Hamming'in örtük bilgisi o sınırda yaşar.
Geometri, ne kadar arama yapabileceğinizi hesaplamanıza izin verir. Neye bakacağınızı söylemez.