algorithm - Haskell 递归极小极大树

Question

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

data Rose a = a :> [Rose a]

这是我要“存储”我的极小极大树的数据类型。我了解 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”(可以容纳井字棋盘的数据类型)是否有赢家，并返回 Maybe P1 或 Maybe P2，或者 Nothing。

我写的这个“minimax”函数没有给我错误，但结果不正确。我的 minimax 实现的缺陷在哪里？

Answer 1

您没有在两个播放器之间正确切换。 minimax' p b@(r :> []) = minimax p b 是错误的。 map (minimax p) rs in 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