Jak zbudować nieskończone drzewo z podwójną eliminacją poprzez pamięć podręczną słabych wskaźników w Haskell

Question

Poniższy kod tworzy nieskończone drzewo, jednocześnie tworząc pamięć podręczną wszystkich poddrzew, tak aby nie tworzyć duplikatów poddrzew. Uzasadnieniem dla eliminacji zduplikowanych poddrzew jest zastosowanie do drzew stanów gier szachowych: często można skończyć w tym samym stanie gry, zmieniając kolejność dwóch ruchów. W trakcie gry stany, które stają się niedostępne, nie powinny nadal zajmować pamięci. Pomyślałem, że mogę rozwiązać ten problem poprzez użycie słabych wskaźników. Niestety używanie słabych wskaźników prowadzi nas do IO Monad i wydaje się, że zniszczyło to wystarczająco/wszystkie lenistwo, tak że ten kod już się nie kończy.

Moje pytanie brzmi: Czy możliwe jest wydajne generowanie drzewa leniwego (stanu gry) bez duplikatów poddrzew (i bez przecieków pamięci)?

{-# LANGUAGE RecursiveDo #-} 

import Prelude hiding (lookup) 
import Data.Map.Lazy (Map, empty, lookup, insert) 
import Data.List (transpose) 

import Control.Monad.State.Lazy (StateT(..)) 
import System.Mem.Weak 
import System.Environment 

type TreeCache = Map Integer (Weak NTree) 

data Tree a = Tree a [Tree a] 
type Node = (Integer, [Integer]) 
type NTree = Tree Node 

getNode (Tree a _) = a 
getVals = snd . getNode 

makeTree :: Integer -> IO NTree 
makeTree n = fst <$> runStateT (makeCachedTree n) empty 

makeCachedTree :: Integer -> StateT TreeCache IO NTree 
makeCachedTree n = StateT $ \s -> case lookup n s of 
    Nothing -> runStateT (makeNewTree n) s -- makeNewTree n s                                 
    Just wt -> deRefWeak wt >>= \mt -> case mt of 
    Nothing -> runStateT (makeNewTree n) s 
    Just t -> return (t,s) 

makeNewTree :: Integer -> StateT TreeCache IO NTree 
makeNewTree n = StateT $ \s -> mdo 
    wt <- mkWeak n t Nothing 
    (ts, s') <- runStateT 
       (mapM makeCachedTree $ children n) 
       (insert n wt s) 
    let t = Tree (n, values n $ map getVals ts) ts 
    return (t, s') 

children n = let bf = 10 in let hit = 2 in [bf*n..bf*n+bf+hit-1] 

values n [] = repeat n 
values n nss = n:maximum (transpose nss) 

main = do 
    args <- getArgs 
    let n = read $ head args in 
    do t <- makeTree n 
     if length args == 1 then putStr $ show $ take (fromInteger n) $ getVals t else putStr "One argument only!!!" 

Answer 1

Moje pytanie brzmi następująco: Czy jest możliwe, aby skutecznie generować leniwe (stan gry) Drzewo bez duplikatów poddrzew (bez przecieki pamięci)?

nr Zasadniczo co starasz się zrobić to użyć transposition tables do memoize swoją funkcję przeszukiwania drzewa (np negascout). Problem polega na tym, że gry mają wykładniczą liczbę stanów i utrzymują tabelę transpozycji, która pamięta, że ​​wszystkie transpozycje przestrzeni stanu są nieosiągalne. Po prostu nie masz tyle pamięci.

Na przykład, Chess ma numer state space compexity of 10^47. To o kilka rzędów wielkości większe niż cała pamięć komputera dostępna na całym świecie. Oczywiście możesz zmniejszyć tę kwotę, nie przechowując odbić (Chess ma 8 reflection symmetries). Ponadto wiele z tych transpozycji będzie niedostępnych z powodu pruning of the game tree. Jednak przestrzeń stanu jest tak trudna, że ​​nigdy nie byłaby w stanie przechowywać każdej transpozycji.

Zwykle używa się tabeli transpozycji o stałym rozmiarze, a gdy dwie transpozycje mieszają się z tą samą wartością, używają one replacement scheme, aby zdecydować, który wpis zostanie zachowany, a który odrzucony. Jest to kompromis, ponieważ utrzymujesz wartość, która Twoim zdaniem będzie najbardziej wydajna (tj. Najczęściej odwiedzana lub bliżej węzła głównego) kosztem konieczności przejścia przez drugą transpozycję. Chodzi o to, że nie można wygenerować drzewa gry, które nie ma zduplikowanych poddrzew, chyba że jesteś z wystarczająco zaawansowanej, obcej cywilizacji.