Haskell递归Minimax树

Question

我正在尝试使用minimax算法在Haskell中编写一个Tic Tac Toe程序.我构建了自己的"Rose a"数据类型,如下所示:

data Rose a = a :> [Rose a]

这是我想要"存储"我的minimax树的数据类型.我理解minimax算法是如何工作的,但似乎无法在递归函数中实现它.

minimax :: Player -> Rose Board -> Rose Int
minimax p (r :> [])   | hasWinner r == Just p              = 1  :> []
                      | hasWinner r == Just (nextPlayer p) = (-1) :> []
                      | otherwise                          = 0  :> []
minimax p (r :> rs)   = maximum(map root xs) :> xs
    where xs = map (minimax' (nextPlayer p)) rs

minimax' :: Player -> Rose Board -> Rose Int
minimax' p b@(r :> []) = minimax p b
minimax' p   (r :> rs) = minimum(map root xs) :> xs
    where xs = map (minimax p) rs

"播放器"也是一种自构造的数据类型,其值可以是P1或P2."hasWinner"函数检查给定的"Board"(可以容纳Tic Tac Toe板的数据类型)是否有赢家,并返回Maybe P1或Maybe P2,或Nothing.

我写的这个"minimax"函数并没有给我错误,但结果不正确.我的minimax实现中的缺陷在哪里？

Answer 1

你没有正确地在两个玩家之间切换.minimax' p b@(r :> []) = minimax p b是错的.map (minimax p) rsin minimax'不会切换到另一个玩家最大化的一半.

我建议明确写出来P1(试图最大化)和P2(试图最小化).

最后阶段可以指定获胜者而不关心当前正在玩哪个玩家

minimax :: Player -> Rose Board -> Rose Int
minimax p (r :> [])   | hasWinner r == Just P1 = 1    :> []
                      | hasWinner r == Just P2 = (-1) :> []
                      | otherwise              = 0    :> []

玩家P1正试图最大化

minimax P1 (r :> rs) = maximum (map root xs) :> xs
    where xs = map (minimax (nextPlayer p)) rs

玩家P2正在努力减少

minimax P2 (r :> rs) = minimum (map root xs) :> xs
    where xs = map (minimax (nextPlayer p)) rs