我必须在 Haskell 中实现蒙特卡洛树搜索。我定义了这样的数据类型:
data Tree s a = TreeNode {
rGame :: s, -- state
rPlayed :: a, -- action
visit :: Int, -- number of visits
score :: Float,
left :: Tree s a,
right :: Tree s a} | TreeNil deriving Show
我还实现了一个带有随机数生成器的 Zipper(听说我需要一个):
data Crumb s a = LeftCrumb s a (Tree s a) | RightCrumb s a (Tree s a) deriving Show
type Treecrumbs s a = [Crumb s a]
data Zipper s a = Zipper (Tree s a) (Treecrumbs s a) (StdGen)
我的问题是如何实现这个 MCTS 的扩展功能。因为是惰性评估,我也认为我可以生成整棵树。在我看来,函数应该是这样的:
expand :: (s -> [(a, s)]) -- The generator
-> s -- first state
-> Tree s a -- The result tree
expand gen t =