Haskell zayıf göstergelerin önbelleği ile çift eleme ile sonsuz bir ağaç nasıl oluşturulur

Question

Aşağıdaki kod sonsuz bir ağaç oluşturur, aynı zamanda tüm alt ağaçların bir önbelleğini oluşturur, böylece hiçbir yinelenen alt ağaç oluşturulmaz. Yinelenen alt ağaçların ortadan kaldırılmasının gerekçesi, satranç gibi oyunların devlet ağaçlarına uygulanmasıdır: Biri, iki hamlinin sırasını değiştirerek aynı oyun durumunda olabilir. Oyun ilerledikçe, erişilemeyen haller belleğe devam etmemelidir. Bu problemi zayıf işaretçiler kullanarak çözebileceğimi düşündüm. Ne yazık ki zayıf işaretçiler kullanmak bizi IO Monad'a getiriyor ve bu, bu kodun daha fazla sona ermeyeceği şekilde yeterli/tüm tembelliği yok etmiş görünüyor.

Sorum şu ki: Yinelenen alt simgeler (ve bellek sızıntısı olmadan) olmadan tembel (oyun durumu) ağacının verimli bir şekilde üretilmesi mümkün mü?

{-# 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

sorum böylece şudur: verimli yinelenen alt ağaçlar olmadan tembel (oyun durumu) ağacı oluşturmak mümkün mü (ve hafıza sızıntı olmadan)? Eğer yapmaya çalıştığını Esasen ne

sayılı sizin ağaç arama fonksiyonunu (örn negascout) memoize için transposition tables kullanmaktır. Sorun, oyunların bir üstel sayıya sahip olmaları ve devlet uzayının tüm transpozisyonlarını hatırlatan bir transpozisyon tablosunun sürdürülebilmesidir. Sadece fazla belleğin yok. Örneğin, satrançta bir state space compexity of 10^47 bulunmaktadır. Bu, tüm dünyada mevcut olan tüm bilgisayar belleğinden daha büyük büyüklükteki emirdir. Tabii ki, bu miktarı yansıtacak şekilde azaltamazsınız (satrançta 8 reflection symmetries vardır). Ayrıca, bu transpozisyonların birçoğu, pruning of the game tree'dan dolayı ulaşılamayacaktı. Ancak, devlet mekânı o kadar çekilmez ki, her aktarımı hala saklayamazdınız.

Çoğu program genellikle, sabit boyutta bir transpozisyon tablosu kullanırlar ve iki transpozisyon aynı değerde olduğunda, hangi girdinin saklanacağına ve hangisinin atılacağına karar vermek için replacement scheme kullanır. Bu bir tahakkümdür, çünkü diğer aktarmayı geçmek zorunda kalmanın bedeli olarak en verimli olacağını düşündüğünüz değeri (yani en çok ziyaret edilen veya kök düğüme daha yakın) tutuyorsunuz. Önemli olan, yeterince gelişmiş bir uzaylı uygarlığınız olmadıkça çift alt ağacı olmayan bir oyun ağacı oluşturmanın imkansız olmasıdır.