Alfa-beta budama - Alpha–beta pruning

Alfa-beta budama
Sınıf	Arama algoritması
En kötü durum performansı
En iyi durum performansı

Alfa-beta budama bir olan arama algoritması tarafından değerlendirilir düğümlerin sayısını azaltmak istiyor minimaks algoritma onun içinde arama ağacının . İki oyunculu oyunların ( Tic-tac-toe , Chess , Go , vb.) makinelerde oynanması için yaygın olarak kullanılan bir çekişmeli arama algoritmasıdır . Hareketin daha önce incelenen bir hamleden daha kötü olduğunu kanıtlayan en az bir olasılık bulunduğunda bir hamleyi değerlendirmeyi durdurur. Bu tür hareketlerin daha fazla değerlendirilmesine gerek yoktur. Standart bir minimax ağacına uygulandığında, minimax ile aynı hareketi döndürür, ancak nihai kararı etkilemesi mümkün olmayan dalları budayarak uzaklaştırır.

Tarih

1958'de John McCarthy'nin "yaklaşım" dediği şeyi kullanan Allen Newell ve Herbert A. Simon , alfa-beta'nın "birkaç kez yeniden icat edilmiş gibi göründüğünü" yazdı. Arthur Samuel , dama simülasyonu için erken bir versiyona sahipti. Richards, Timothy Hart, Michael Levin ve/veya Daniel Edwards da Amerika Birleşik Devletleri'nde bağımsız olarak alfa-beta'yı icat etti . McCarthy , 1956'daki Dartmouth atölyesi sırasında benzer fikirler önerdi ve 1961'de MIT'den Alan Kotok da dahil olmak üzere bir grup öğrencisine önerdi . Alexander Brudno , alfa-beta algoritmasını bağımsız olarak tasarladı ve sonuçlarını 1963'te yayınladı. Donald Knuth ve Ronald W. Moore Algoritmayı 1975'te geliştirdi. Judea Pearl , iki makalede rastgele atanan yaprak değerlerine sahip ağaçlar için beklenen çalışma süresi açısından optimalliğini kanıtladı. Alfa-beta'nın randomize versiyonunun optimalliği, 1986'da Michael Saks ve Avi Wigderson tarafından gösterildi.

Ana düşünce

Bir oyun ağacı , satranç, dama ve ters çevirme gibi birçok iki oyunculu sıfır toplamlı oyunu temsil edebilir . Ağaçtaki her düğüm, oyundaki olası bir durumu temsil eder. Bir dalın her bir uç düğümüne (sonucuna), bir sonraki hamlede oyuncuya sonucun değerini belirleyen sayısal bir puan atanır.

Algoritma, sırasıyla maksimize eden oyuncunun garanti ettiği minimum puanı ve minimize eden oyuncunun garanti ettiği maksimum puanı temsil eden iki değer, alfa ve beta tutar. Başlangıçta, alfa negatif sonsuzdur ve beta pozitif sonsuzdur, yani her iki oyuncu da olabilecek en kötü skorla başlar. Küçültücü oyuncunun (yani "beta" oyuncusunun) garanti edildiği maksimum puan, maksimum yapan oyuncunun (yani, "alfa" oyuncusunun) garanti ettiği minimum puandan (yani beta <alfa) daha az olduğunda, maksimuma çıkaran oyuncu Gerçek oyunda asla ulaşılmayacaklarından, oyuncunun bu düğümün sonraki torunlarını düşünmesine gerek yoktur.

Bunu gerçek hayattan bir örnekle açıklamak gerekirse, birinin satranç oynadığını ve sıranın onlara geldiğini varsayalım. "A" hamlesi oyuncunun konumunu iyileştirecektir. Oyuncu, daha iyisinin kaçırılmadığından emin olmak için hamle aramaya devam eder. "B" hamlesi de iyi bir hamledir, ancak oyuncu daha sonra rakibinin iki hamlede matı zorlamasına izin vereceğini fark eder. Bu nedenle, rakip kazanmaya zorlayabileceğinden, B hamlesi oynamanın diğer sonuçlarının artık dikkate alınmasına gerek yoktur. Rakibin "B" hamlesinden sonra zorlayabileceği maksimum puan negatif sonsuzluktur: oyuncu için bir kayıp. Bu, daha önce bulunan minimum konumdan daha azdır; "A" hamlesi, iki hamlede zorunlu bir kayba neden olmaz.

Saf minimax üzerinde iyileştirmeler

Alfa-beta budama örneği. Gri renkli alt ağaçların keşfedilmesine gerek yoktur (hareketler soldan sağa değerlendirildiğinde), çünkü alt ağaç grubunun bir bütün olarak eşdeğer bir alt ağacın değerini veya daha kötüsünü verdiği ve bu nedenle etkileyemeyeceği bilinmektedir. nihai sonuç. Maksimum ve minimum seviyeler sırasıyla oyuncunun ve rakibin sırasını temsil eder.

Alfa-beta budamanın faydası, arama ağacının dallarının elimine edilebilmesi gerçeğinde yatmaktadır. Bu şekilde, arama süresi 'daha umut verici' alt ağaçla sınırlandırılabilir ve aynı zamanda daha derin bir arama yapılabilir. Selefi gibi, dal ve sınır algoritmaları sınıfına aittir . Düğümler optimal veya optimale yakın bir sırada değerlendirilirse, optimizasyon efektif derinliği basit minimax'ın yarısından biraz fazlasına düşürür (her düğümde ilk sırada sıralanan yan hareket için en iyi seçim).

Bir (ortalama veya sabit) ile dallanma faktörü ve b ve bir ara derinliğine d katların (hareket sipariş olduğunda, yaprak düğümü pozisyonların sayısı değerlendirilir pessimal ) olan O ( b x b x ... x b ) = O ( b ^d ) – basit bir minimax arama ile aynı. Arama için hareket sıralaması optimal ise (yani en iyi hamleler her zaman önce aranır), değerlendirilen yaprak düğüm konumlarının sayısı tek derinlik ve O için yaklaşık O ( b ×1× b ×1×...× b ) olur. ( b ×1× b ×1×...×1) çift derinlik için veya . İkinci durumda, bir aramanın katının çift olduğu durumlarda, etkin dallanma faktörü kareköküne indirgenir veya eşdeğer olarak, arama aynı miktarda hesaplama ile iki kat daha derine gidebilir. Açıklaması b × 1 × b × 1 × ... tüm birinci oyuncunun hamle en uygun olanı bulmak için çalışılması gereken bir konudur ama her biri için, sadece ikinci oyuncunun en iyi hareket çürütmek için gerekli olmasıdır tüm ama ilk (ve en iyi) ilk oyuncu hamlesi—alfa-beta, başka hiçbir ikinci oyuncu hamlesinin dikkate alınmamasını sağlar. Düğümler rasgele bir sırada (yani, algoritma rasgele olduğunda) asimptotik olarak ele alındığında, ikili yaprak değerlerine sahip tek tip ağaçlarda değerlendirilen beklenen düğüm sayısı . Aynı ağaçlar için, yaprak değerlerine birbirinden bağımsız olarak değerler atandığında ve sıfır ve birin her ikisi de eşit olası olduğunda , değerlendirilen beklenen düğüm sayısı , rastgele algoritma tarafından yapılan işten çok daha küçük olan, bahsedilen yukarıda ve yine bu tür rastgele ağaçlar için en uygunudur. Yaprak değerler, birbirinin fakat bağımsız bir şekilde, seçilmiş zaman rastgele eşit aralıklarla düğümler beklenen sayı artar değerlendirildi olarak , bu tür bir rastgele ağaçları için daha uygun olan limit. "küçük" değerleri için asıl çalışmanın, kullanılarak daha iyi tahmin edildiğini unutmayın . $O(b^{d/2})=O({\sqrt {b^{d}}})$ $\Theta (((b-1+{\sqrt {b^{2}+14b+1}})/4)^{d})$ ${\görüntüleme stili \Teta ((b/2)^{d})}$ ${\görüntüleme stili [0,1]}$ $\Teta (b^{d/log(d)})$ $d\to \infty$ ${\görüntüleme stili d}$ ${\ Displaystyle 0.925d^{0.747}}$

Düğüm başına ortalama 36 dala sahip dört katı arayan bir satranç programı, bir milyondan fazla terminal düğümünü değerlendirir. Optimum bir alfa-beta kuru erik, yaklaşık 2.000 terminal düğümü hariç hepsini ortadan kaldırarak %99,8'lik bir azalma sağlar.

Boşluk için başlangıçtaki sonsuz (veya keyfi olarak büyük) değerleri değiştirerek ve negamax kodlama basitleştirmelerini kullanmaktan kaçınarak insan dostu olmaya çalışan animasyonlu bir pedagojik örnek .

Normalde alfa-beta sırasında, alt ağaçlara geçici olarak ilk oyuncu avantajı hakimdir (birçok ilk oyuncu hamlesi iyi olduğunda ve her arama derinliğinde ilk oyuncu tarafından kontrol edilen ilk hamle yeterlidir, ancak tüm ikinci oyuncu yanıtları gereklidir). bir çürütme bulmaya çalışın) veya tam tersi. Bu avantaj, arama sırasında hareket sırası yanlışsa, her seferinde verimsizliğe yol açan birçok kez taraf değiştirebilir. Mevcut pozisyona yaklaştıkça aranan pozisyon sayısı katlanarak azaldığından, erken hamleleri sıralamak için büyük çaba harcamaya değer. Herhangi bir derinlikte geliştirilmiş bir sıralama, aranan toplam konum sayısını katlanarak azaltacaktır, ancak kök düğümün yakınındaki derinliklerdeki tüm konumları sıralamak, çok az sayıda olduğu için nispeten ucuzdur. Uygulamada, hareket sıralaması genellikle daha önceki, daha küçük aramaların sonuçlarıyla belirlenir, örneğin yinelemeli derinleştirme yoluyla .

Ek olarak, bu algoritma , puana ek olarak tüm bir ana varyasyonu döndürmek için önemsiz bir şekilde değiştirilebilir . MTD(f) gibi bazı daha agresif algoritmalar böyle bir değişikliğe kolayca izin vermez.

sözde kod

Alfa-beta budama ile derinlik sınırlı minimax için sözde kod aşağıdaki gibidir:

Alfa-beta budama uygulamaları, genellikle "başarısız-yumuşak" veya "başarısız-sert" olmalarına göre tanımlanabilir. Fail-soft alfa-beta ile, alfabe işlevi, işlev çağrısı bağımsız değişkenleri tarafından ayarlanan α ve β sınırlarını aşan (v < α veya v > β) değerler (v) döndürebilir. Karşılaştırıldığında, başarısız olan alfa-beta, işlev dönüş değerini α ve β'nın kapsayıcı aralığıyla sınırlar. Fail-soft ve fail-hard uygulamaları arasındaki temel fark, α ve β'nın cutoff kontrolünden önce mi sonra mı güncellenmesidir. Kontrolden önce güncellenirlerse, başlangıç sınırlarını aşabilirler ve algoritma başarısız olur.

Aşağıdaki sözde kod, fail-hard varyasyonunu gösterir.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Aşağıdaki sözde kod, fail-soft alfa-beta'yı gösterir.

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if value ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if value ≤ α then
                break (* α cutoff *)
        return value

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)

Sezgisel iyileştirmeler

Ağacın alfa-beta kesintilerini zorlaması muhtemel daha önceki kısımlarını aramak için sıralama buluşsal yöntemlerini kullanarak doğruluktan ödün vermeden daha fazla iyileştirme elde edilebilir . Örneğin, satrançta, taşları tutan hamleler, tutmayan hamlelerden önce incelenebilir ve oyun ağacı analizi yoluyla daha önceki geçişlerde yüksek puan almış hamleler diğerlerinden önce değerlendirilebilir. Bir başka yaygın ve çok ucuz buluşsal yöntem , ağaç aramada aynı ağaç düzeyinde bir beta kesmesine neden olan son hareketin her zaman ilk olarak incelendiği öldürücü buluşsal yöntemdir . Bu fikir aynı zamanda bir dizi çürütme tablosuna da genelleştirilebilir .

Alfa-beta araması, yalnızca dar bir arama penceresi (genellikle deneyime dayalı tahminlerle belirlenir) dikkate alınarak daha da hızlı yapılabilir. Bu, aspirasyon araması olarak bilinir . Aşırı durumda, arama alfa ve beta eşit olacak şekilde gerçekleştirilir; sıfır pencereli arama , boş pencereli arama veya keşif araması olarak bilinen bir teknik . Bu, dar pencereden kazanılan ekstra derinliğin ve basit bir kazanç/kayıp değerlendirme fonksiyonunun kesin bir sonuca yol açabileceği bir oyunun sonuna yakın kazanma/kaybetme aramaları için özellikle yararlıdır. Bir aspirasyon araması başarısız olursa, yüksek (pencerenin yüksek kenarı çok düşük) veya düşük (pencerenin alt kenarı çok yüksek) başarısız olup olmadığını saptamak kolaydır . Bu, konumun yeniden aranmasında hangi pencere değerlerinin yararlı olabileceği hakkında bilgi verir.

Zamanla, başka iyileştirmeler önerildi ve gerçekten de John Fishburn'ün Falphabeta (başarısız-yumuşak alfa-beta) fikri neredeyse evrenseldir ve zaten yukarıda biraz değiştirilmiş bir biçimde dahil edilmiştir. Fishburn ayrıca Lalphabeta ("minimum pencereli alfa-beta araması ile son hareket") adı altında öldürücü buluşsal ve sıfır pencereli aramanın bir kombinasyonunu önerdi.

Diğer algoritmalar

Yana minimaks algoritma ve türevleri doğal olan derinliği ilk gibi bir strateji yinelemeli derinleşen genellikle oldukça iyi bir hareket bitmiş çalıştırdığında önce algoritma kesilse bile döndürülebilir, böylece, alfa-beta ile bağlantılı olarak kullanılır. Yinelemeli derinleştirmeyi kullanmanın bir başka avantajı, daha sığ derinliklerdeki aramaların, hareket sıralama ipuçlarının yanı sıra sığ alfa ve beta tahminleri vermesidir; bu, her ikisinin de, aksi takdirde mümkün olandan çok daha erken bir zamanda daha yüksek derinlikli aramalar için eşikler üretmeye yardımcı olabilir.

SSS* gibi algoritmalar ise en iyi ilk stratejisini kullanır. Bu, potansiyel olarak onları zaman açısından daha verimli hale getirebilir, ancak tipik olarak alan verimliliğinde ağır bir maliyetle.

Ayrıca bakınız

Referanslar

bibliyografya

George T. Heineman; Gary Pollice; Stanley Selkov (2008). "Bölüm 7: Yapay Zekada Yol Bulma". Özetle Algoritmalar . Oreilly Medya . s. 217–223. ISBN'si 978-0-596-51624-6.
Judea Pearl , Sezgisel Yöntem , Addison-Wesley, 1984
John P. Fishburn (1984). "Ek A: α-β Aramasının Bazı Optimizasyonları". Dağıtılmış Algoritmalarda Hızlanma Analizi (1981 doktora tezinin revizyonu) . UMI Araştırma Basın. s. 107–111. ISBN'si 0-8357-1527-2.

Languages

In other projects