如何通过Haskell中的弱指针缓存构建一个具有重复消除的无限树

Question

以下代码构建无限树,同时创建所有子树的缓存,以便不创建重复的子树.消除重复子树的基本原理来自对类似国际象棋游戏的状态树的应用:通过改变两个移动的顺序,人们通常可以最终处于相同的游戏状态.随着游戏的进行,无法访问的状态不应继续占用内存.我以为我可以通过使用弱指针来解决这个问题.不幸的是,使用弱指针将我们带入了IO Monad,这似乎已经破坏了足够/所有的懒惰,使得此代码不再终止.

因此我的问题是:是否有可能有效地生成一个没有重复子树的懒惰(游戏状态)树(并且没有泄漏内存)？

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

因此，我的问题是：是否可以有效地生成一个没有重复子树（并且不会泄漏内存）的惰性（游戏状态）树？

不。本质上，您想要做的是使用换位表来记忆您的树搜索功能（例如negascout）。问题在于，游戏具有指数数量的状态，维护一个记住状态空间所有换位的换位表是不可行的。你只是没有那么多记忆力。

例如，国际象棋的状态空间复杂度为 10^47。这比全世界可用的所有计算机内存大几个数量级。当然，您可以通过不存储反射来减少这个量（国际象棋有8 种反射对称性）。此外，由于博弈树的修剪，许多转置将无法实现。然而，状态空间非常棘手，您仍然无法存储每个转置。

大多数程序通常做的是使用固定大小的转置表，当两个转置散列到相同的值时，它们使用替换方案来决定哪个条目将被保留以及哪个条目将被丢弃。这是一种权衡，因为您保留了您认为最有效的值（即访问次数最多或更接近根节点），但代价是必须遍历其他转置。关键是，除非你来自足够先进的外星文明，否则不可能生成没有重复子树的游戏树。