un

guest
1 / ?
back to lessons

Dal Faktörü ve Düğüm Sayısı

Bir oyun ağacı, başlangıç pozisyonundan her olası hareket serisini modeller. Her düğüm bir masa durumunu temsil eder. Her kenar bir yasal hamleyi temsil eder. Arşının yapısı, aramanın sürdürülebilir olup olmayacağını belirler.

Ana Parametreler

Dal faktörü b: tipik bir konumda mevcut yasal hamle sayısı.

Derinlik d: önden arama yapmak için gereken yarı-hareket sayısı.

Derinlik d'deki düğüm sayısı: b^d

Tüm derinliklerdeki toplam düğüm sayısı: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)

Büyük b ve d için, toplam ≈ b^d (son düzey tarafından yönetilir).

4×4×4 Tic-Tac-Toe

Tam oyun ağacı: b ≈ 64 (yasal kareler), d = 64 (toplam hamleler). Tam düğüm sayımı ≈ 64^64 ≈ 10^115. Gözlemlenebilir evren, yaklaşık olarak 10^80 atom içerir. Brute-force arama fiziksel olarak imkansızdır.

Oyun Ağacı ve Alfa-Beta Budama

Ağ Boyutunu Hesapla

Satranç daha gerçekçi sayılar sağlar. Ortalama dal faktörü b ≈ 35. 3 hamle her taraftan (6 pli arama) yaklaşık olarak 35^6 düğüm gerektirir.

Bir satranç araması için düğüm sayısını hesapla: derinlik d = 6 yarı-hareket ile dal faktörü b = 35. Ardından, aynı hesaplamayı d = 10 yarı-hareket için yapın. Her iki hesaplamayı açıkça gösterin.

Alfa-Beta Budama: Eksponanseli Büyüklüğü Azaltma

Alpha-beta keskinliği, sonuçta minimax etkisi yapmayan dalları ortadan kaldırır. Ana fikir: eğer bir dalın değeri V'yi biliyorsanız, maximizing oyuncu için V'nin altında düşen veya minimizing oyuncu için V'nin üzerinde düşen herhangi bir kardinal dalı kestirebilirsiniz.

En İyi Geometri

En iyi hamle sıralaması altında (en iyi hamleler ilk olarak aranır), alpha-beta etkin etkileşen faktörünü b'ye √b'ye düşürür. Arama derinliği aynı düğüm bütçesinde aynı düğüm için etkili olarak çiftlenir:

Tam arama: b^d düğüm

Alpha-beta en iyi durumda: b^(d/2) düğüm

Örnek: b=35, d=6. Tam: 35^6 ≈ 1,84 × 10^9. Alpha-beta: 35^3 = 42,875. Düzenleme faktörü: ~43,000.

Uygulamada, hamle sıralaması kusurludur. Ortalama düzenleme: b^(d×0.75) — eşdeğer etkileşen faktörü ≈ b^0.75.

Bir satranç motoru için b = 35 ve d = 8 kademeli, (1) tam minimax araması altında düğüm sayısını hesaplayın, (2) mükemmel alpha-beta keskinliği (en iyi durumda). Düzenleme faktörünü gösterin ve tüm hesaplamaları gösterin.

Merkez-Angıç Duality

Hamming, geometrik bir ikiliğe işaret eder: 4×4×4 kübde, 8 köşe pozisyonunun 8 merkez pozisyonuna (iç 2×2×2 küp) ve bunun tersine, tüm 76 kazanan çizgiyi koruyarak bir ters çevrim vardır.

Bir Pozisyonu Geçiren Hat Sayısı

4×4×4 kübde, kazanan hatları geçiren şekilde farklıdır:

Köşe pozisyonları: her biri için 7 hat (4 yüz diyagonali, 2 kenar hattı, 1 uzaktaki diyagonal)

Merkez-kenar pozisyonları: her biri için 4 hat

Yüz-merkez pozisyonları: her biri için 6 hat

Gövde-merkez pozisyonları (iç 2×2×2): her biri için 7 hat

Düalizm, köşeleri (7 hat) body-centerlara (7 hat) harcar. Her iki set 'sıcak noktalardan' oluşur.

Neden Sıcak Noktalar Geometrik Olarak Önemli?

Oynucu daha fazla yüksek-hat-sayısı pozisyonu kontrol eder, daha fazla olası kazanan hat kontrol eder. Bu, herhangi bir arama olmadan hareket seçimi yönlendiren doğrudan bir geometrik argümandır: hat kaplama maksimizasyonu.

4×4×4 kare, toplam 76 kazanan çizgi ve 64 pozisyon sahiptir. 8 köşe her birini 7 çizgi üzerinde tutar, 8 gövde merkezi pozisyonu her birini 7 çizgi üzerinde tutar, 24 yüz merkezi pozisyonu her birini 6 çizgi üzerinde tutar ve 24 kenar pozisyonu her birini 4 çizgi üzerinde tutar. Doğrula: bu sayılar tutarlı bir şekilde mi eklenir? Her iki taraftan (pozisyon, çizgi) olayları sayısını doğrula: pozisyonları toplarken ve ayrı olarak, her çizgi üzerinde 4 uç sayarak. İki toplam uyuşur mu?

Değerlendirme Fonksiyonları

Her oyun oynayan program bir değerlendirme fonksiyonuna ihtiyaç duyar: bir tablo durumlarını sayısal değerlere (maximizing oyuncu için iyi = pozitif, minimizing oyuncu için iyi = negatif) eşleyen bir fonksiyon. Değerlendirme fonksiyonu, arama ağacının dallarında sınır koşullarını sağlar.

Lineer Değerlendirme Fonksiyonları

Bir lineer değerlendirme fonksiyonu, pozisyonun özelliklerine (f_i) her birine bir ağırlık (w_i) atar:

E(pozisyon) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n

4×4×4 taşlı taht için: açık hatlar kontrolü, yüksek hat sayısı karelerdeki pozisyonlar, tehdit edilen forklar gibi özellikler olabilir. Satranç için: malzeme sayımı, merkez kontrolü, kral güvenliği, siper yapısı.

Bu, özellikteki bir doğrusal fonksiyondur - ℝ^n'deki bir hipersayı. Aynı özelliklere sahip iki pozisyon, diğer tüm farklılıklardan bağımsız olarak aynı değerlendirme alır. Değerlendirme fonksiyonunun geometrisi, programın ne görür olduğunu belirler.

Samuel'in taş programı, ağırlık vektörünü (w) ayarlayarak gelişti - lineer değerlendirme fonksiyonları uzayında gradient asansı.

Bir basit 4×4×4 taşlı taht oyunu değerlendirme fonksiyonu iki özelliktan oluşur: (1) f_1 = sizin açık hattlarınız (sizin parçalarınız var ve rakip hiçbiri yok), (2) f_2 = rakip açık hattları. Değerlendirme: E = w_1 × f_1 - w_2 × f_2. Eğer w_1 = 2 ve w_2 = 3, bir pozisyon için hesapla (sizin 12 açık hattınız ve rakip 8). Sonra: eğer E > 0, pozisyon sizin lehineyse ne anlama gelir?

Geometri & Formalizasyonun Sınırı

Oyun ağının temiz bir geometrik yapısı vardır: derinlik d'ye göre eksponansiyel büyüme, alpha-beta ile b^(d/2)'ye indirgenir, yüksek-değer pozisyonlara (sıcak noktalar etkili b'yi azaltır) sınırlı olduğunda daha da indirgenir. Değerlendirme fonksiyonu, özellik alanı içinde bir hiperyüklemeyi tanımlar.

Bütün bunlar temiz, kesin, formel olarak tamamlanmış. Oyun oynamakla ilgili merkezî sorunu tanımlar — matematiksel yapı, açık bir rehberlik sağlar bölge.

Sınır — kural uygulamasından keşfe geçiş zamanı, pozisyon avantajını taktik fırsatlar için değiştirmek, değerlendirme fonksiyonunun ötesine geçen emürgent örüntüleri tanıma — bu formalizasyona karşı direnç gösterir. Hamming'in zımni bilgisinin sınırda yaşadığı yer.

Geometri, arama yapabileceğiniz kadarı hesaplamayı sağlar. Aramanın ne için olduğunu söylemez.

Bu dersin geometrisini düşünün. Oyun ağının formalizmi (b^d düğüm, alpha-beta indirgeme b^(d/2), lineer değerlendirme fonksiyonları) oyun oynamakta kullanılabilir kısımların kesin bir açıklamasını sağlar. Geometri nerede bozuluyor ve oyun oynamakta zeka ögesi, geometrik modele ne zaman geçer? Belirli bir yanıt verin, genel bir gözlem yapmayın.