4

我正在尝试创建一个函数，该函数使用遗传算法递归地玩所有可能的井字游戏，然后返回一个 (wins,losses,ties) 的元组。但是，下面的函数在这样调用时总是会溢出堆栈：

scoreOne :: UnscoredPlayer -> [String] -> ScoredPlayer
scoreOne player boards = ScoredPlayer (token player) (chromosome player) (evaluateG $!             testPlayer player boards)
...
let results = map (\x->scoreOne x boards) players
print (maximum results)

哪里players是染色体列表。溢出不会发生在只有 1 名玩家的情况下，但会发生在 2 名玩家身上。

编辑：如果函数以下列方式调用，它不会溢出堆栈。

let results = map (\player -> evaluateG (testPlayer player boards)) players
print (maximum results)

但是，以下方式确实会溢出堆栈。

let results = map (\player -> ScoredPlayer (token player) (chromosome player) (evaluateG $! testPlayer player boards)) players

作为参考，ScoredPlayer定义为（字符串为玩家标记，[Int] 为染色体，Float 为分数）：

data ScoredPlayer = ScoredPlayer String ![Int] !Float deriving (Eq)

根据我对 Haskell 的了解，该playAll'函数不是尾递归的，因为foldl'我正在使用的调用正在对函数结果执行进一步处理。但是，我不知道如何消除foldl'呼叫，因为需要确保玩所有可能的游戏。有什么方法可以重构函数，使它是尾递归的（或者至少不会溢出堆栈）？

在此先感谢，并为大量代码清单感到抱歉。

playAll' :: (Num a) => UnscoredPlayer -> Bool -> String -> [String] -> (a,a,a) ->    (a,a,a)
playAll' player playerTurn board boards (w,ls,t)= 
    if won == self then (w+1,ls,t) -- I won this game
    else
        if won == enemy then (w,ls+1,t) -- My enemy won this game
        else
            if '_' `notElem` board then (w,ls,t+1) -- It's a tie
            else
                if playerTurn then --My turn; make a move and try all possible combinations for the enemy
                    playAll' player False (makeMove ...) boards (w,ls,t)
                else --Try each possible move against myself
                    (foldl' (\(x,y,z) (s1,s2,s3) -> (x+s1,y+s2,z+s3)) (w,ls,t)
                        [playAll' player True newBoard boards (w,ls,t)| newBoard <- (permute enemy board)])
    where
        won = winning board --if someone has one, who is it?
        enemy = (opposite.token) player --what player is my enemy?
        self = token player --what player am I?
4

1 回答 1

6

该foldl'函数是尾递归的，问题是它不够严格。这是唐斯图尔特在评论中提到的问题。

将 Haskell 数据结构视为惰性盒子，每个新的构造函数都会创建一个新盒子。当你有一个像这样的弃牌时

foldl' (\(x,y,z) (s1,s2,s3) -> (x+s1,y+s2,z+s3))

元组是一个盒子，其中的每个元素都是另一个盒子。严格从foldl'只删除最外面的盒子。元组中的每个元素仍然在一个惰性盒子中。

为了解决这个问题，您需要更严格地删除多余的框。唐的建议是

data R = R !Int !Int !Int

foldl' (\(R x y z) (s1,s2,s3) -> R (x+s1) (y+s2) (z+s3))

现在 的严格性foldl'就足够了。R 的各个元素是严格的，所以当最外面的盒子（R 构造函数）被移除时，里面的三个值也会被计算。

没有看到更多我能提供的代码。我无法运行此列表，所以我不知道这是否解决了问题，或者整个程序中是否存在其他问题。

作为一种风格，if您可能更喜欢以下内容，而不是嵌套的：

playAll' player playerTurn board boards (w,ls,t)=
  case () of
    _ | won == self -> (w+1,ls,t) -- I won this game
    _ | won == enemy -> (w,ls+1,t) -- My enemy won this game
    _ | '_' `notElem` board -> (w,ls,t+1) -- It's a tie 
    _ -> ... --code omitted
于 2010-10-06T23:44:44.073 回答