Comment créer une arborescence infinie avec élimination des doublons via le cache des pointeurs faibles dans Haskell

Question

Le code suivant crée une arborescence infinie, tout en créant simultanément un cache de tous les sous-arborescences, de sorte qu'aucun sous-arborescence en double ne soit créé. La raison d'être de l'élimination des sous-arbres en double provient de l'application aux arbres d'états des jeux de type échecs: on peut souvent se retrouver dans le même état de jeu en changeant simplement l'ordre de deux coups. Au fur et à mesure que le jeu progresse, les états qui deviennent inaccessibles ne devraient pas continuer à occuper la mémoire. Je pensais pouvoir résoudre ce problème en utilisant des pointeurs faibles. Malheureusement, l'utilisation de pointeurs faibles nous amène dans la Mono IO et cela semble avoir détruit assez/toute paresse de sorte que ce code ne se termine plus.

Ma question est la suivante: est-il possible de générer efficacement un arbre paresseux (état de jeu) sans sous-arborescence en double (et sans fuites de mémoire)?

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

Ma question est donc: Est-il possible de générer efficacement un arbre paresseux (état de jeu) sans double sous-arbres (et sans fuite de mémoire)?

Non Essentiellement ce que vous essayez de faire est d'utiliser transposition tables pour memoize votre fonction de recherche d'arbre (par exemple negascout). Le problème est que les jeux ont un nombre exponentiel d'états et le maintien d'une table de transposition qui se souvient de toutes les transpositions de l'espace d'état est infaisable. Vous n'avez simplement pas beaucoup de mémoire. Par exemple, Chess a un state space compexity of 10^47. C'est plusieurs ordres de grandeur supérieurs à toute la mémoire de l'ordinateur disponible dans le monde entier. Bien sûr, vous pouvez réduire cette quantité en ne stockant pas les réflexions (Echecs a 8 reflection symmetries). En outre, beaucoup de ces transpositions seraient inaccessibles en raison de pruning of the game tree. Cependant, l'espace d'état est si intraitable que vous ne pourrez toujours pas stocker toutes les transpositions. Ce que la plupart des programmes font habituellement est d'utiliser une table de transposition de taille fixe et lorsque deux transpositions ont la même valeur, ils utilisent un replacement scheme pour décider quelle entrée sera conservée et quelle sera supprimée. C'est un compromis parce que vous gardez la valeur que vous pensez être la plus efficace (c'est-à-dire la plus visitée ou la plus proche du nœud racine) au prix d'avoir à traverser l'autre transposition. Le fait est qu'il est impossible de générer un arbre de jeu qui n'a pas de sous-arbres dupliqués, sauf si vous êtes issu d'une civilisation extraterrestre suffisamment avancée.