Vyhledávání hlavních variant - Principal variation search

Vyhledávání hlavních variací (někdy srovnávané s prakticky identickým NegaScoutem ) je negamaxový algoritmus, který může být rychlejší než prořezávání alfa-beta . Stejně jako prořezávání alfa-beta je NegaScout algoritmus směrového vyhledávání pro výpočet hodnoty minimax uzlu ve stromu . Dominuje prořezávání alfa-beta v tom smyslu, že nikdy nebude zkoumat uzel, který lze prořezat alfa-beta; spoléhá se však na přesné uspořádání uzlů, aby tuto výhodu využilo.

NegaScout funguje nejlépe, když je dobré objednávání tahů. V praxi je pořadí přesunů často určováno předchozími mělčími vyhledáváními. Produkuje více mezních hodnot než alfa-beta za předpokladu, že první prozkoumaný uzel je nejlepší. Jinými slovy předpokládá, že první uzel je v hlavní variantě . Poté může zkontrolovat, zda je to pravda, prohledáním zbývajících uzlů s nulovým oknem (také známým jako skautské okno; když jsou alfa a beta stejné), což je rychlejší než hledání s běžným oknem alfa-beta. Pokud se důkaz nezdaří, první uzel nebyl v hlavní variantě a hledání pokračuje jako normální alfa-beta. NegaScout proto funguje nejlépe, když je pořadí tahů dobré. Při náhodném objednávání tahů bude NegaScout trvat déle než běžná alfa-beta; ačkoli nebude zkoumat žádné uzly, které alfa-beta neudělala, bude muset znovu prohledat mnoho uzlů.

Alexander Reinefeld vynalezl NegaScout několik desetiletí po vynálezu prořezávání alfa-beta. Ve své knize podává důkaz správnosti NegaScout.

Jiný vyhledávací algoritmus zvaný SSS * může teoreticky vyústit v méně prohledávaných uzlů. Její původní formulace však má praktické problémy (zejména se při ukládání spoléhá na seznam OPEN) a dnes většina šachových strojů při hledání stále používá formu NegaScout. Většina šachových strojů používá transpoziční tabulku, ve které je uložena příslušná část vyhledávacího stromu. Tato část stromu má stejnou velikost, jakou by měl OPEN seznam SSS *. Přeformulování s názvem MT-SSS * umožnilo jeho implementaci jako řadu volání nulového okna na Alpha-Beta (nebo NegaScout), které používají tabulku pro provedení, a bylo možné provést přímé srovnání pomocí programů pro hraní her. V praxi nepřekonal NegaScout. Ještě dalším vyhledávacím algoritmem, který má v praxi lepší výsledky než NegaScout, je první algoritmus s názvem MTD (f) , ačkoli žádný z těchto algoritmů dominuje tomu druhému. Existují stromy, ve kterých NegaScout prohledává méně uzlů než SSS * nebo MTD (f) a naopak.

NegaScout přejde po SCOUT, který vynalezla Judea Pearl v roce 1980, což byl první algoritmus, který překonal alfa-beta a byl prokázán asymptoticky optimální. Nulová okna s β = α + 1 v prostředí negamax byla vynalezena nezávisle JP Fishburnem a použita v algoritmu podobném SCOUT v příloze jeho Ph.D. práce, v paralelním algoritmu alfa-beta, a na posledním podstromu kořenového uzlu vyhledávacího stromu.

Idea

Většina tahů není přijatelná pro oba hráče, takže abychom získali přesné skóre, nemusíme úplně prohledávat každý uzel. Přesné skóre je zapotřebí pouze v hlavní variantě (sled tahů přijatelný pro oba hráče), u níž se očekává, že se rozšíří až na kořen. V iterativním prohlubování hledání předchozí iterace již vytvořila takovou sekvenci. V uzlu, který má skóre, které končí uvnitř okna, které se nazývá PV-uzel, prohledáme první tah, který je považován za nejlepší, v celém okně, abychom vytvořili vazbu. To je nutné k prokázání, že další kroky jsou nepřijatelné. Provedli jsme vyhledávání nulového okna, abychom otestovali, zda může být tah lepší. Vzhledem k tomu, že vyhledávání v nulovém okně je mnohem levnější, může ušetřit spoustu úsilí. Pokud zjistíme, že tah může zvýšit alfa, provedeme re-search s celým oknem, abychom získali přesné skóre.

Pseudo kód

function pvs(node, depth, α, β, color) is
    if depth = 0 or node is a terminal node then
        return color × the heuristic value of node
    for each child of node do
        if child is first child then
            score := −pvs(child, depth − 1, −β, −α, −color)
        else
            score := −pvs(child, depth − 1, −α − 1, −α, −color) (* search with a null window *)
            if α < score < β then
                score := −pvs(child, depth − 1, −β, −score, −color) (* if it failed high, do a full re-search *)
        α := max(α, score)
        if α ≥ β then
            break (* beta cut-off *)
    return α

Viz také

Reference

  1. ^ A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Berlin (1989), ISBN  3-540-50742-6
  2. ^ Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (listopad 1996). "Nejlepší první algoritmy s minimální pevnou hloubkou" . Umělá inteligence . 87 (1–2): 255–293. doi : 10.1016 / 0004-3702 (95) 00126-3 .
  3. ^ Pearl, J., „SCOUT: Jednoduchý algoritmus pro vyhledávání her s osvědčenými optimálními vlastnostmi“, Sborník z první výroční národní konference o umělé inteligenci, Stanford University, 18. – 21. Srpna 1980, str. 143–145.
  4. ^ Pearl, J., „Asymptotické vlastnosti stromů Minimax a postupy při hledání her“, Artificial Intelligence, sv. 14, č. 2, str. 113-138, září 1980.
  5. ^ Fishburn, JP, „Analýza zrychlení v distribuovaných algoritmech“, UMI Research Press ISBN  0-8357-1527-2 , 1981, 1984.
  6. ^ Fishburn, JP, Finkel, RA a Lawless, SA, „Parallel Alpha-Beta Search on Arachne“ Proceedings 1980 Int. Konf. Parallel Processing, IEEE, 26. – 29. Srpna 1980, str. 235–243.
  7. ^ Fishburn, JP, „Optimalizace vyhledávání alfa-beta“, Bulletin ACM SIGART , číslo 72, červenec 1980, str. 29-31.
  8. ^ Judea Pearl (1980). Asymptotické vlastnosti stromů Minimax a postupy při hledání her. Artificial Intelligence, sv. 14, č. 2
  9. ^ Murray Campbell, Tony Marsland (1983). Porovnání algoritmů pro vyhledávání stromů Minimax. Artificial Intelligence, sv. 20, č. 4, str. 347-367. ISSN 0004-3702.

externí odkazy