Haskell 递归极小极大树

Question

我正在尝试使用 minimax 算法在 Haskell 中编写 Tic Tac Toe 程序。我构造了自己的 "Rose a" 数据类型如下：

data Rose a = a :> [Rose a]

这是我想要 'store' 我的 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

"Player"也是自建数据类型，可以取值P1或P2。 "hasWinner" 函数检查给定的 "Board"（可以容纳井字棋盘的数据类型）是否有赢家，并且 returns 可能是 P1 或可能是 P2，或者没有。

我写的这个"minimax"函数没有报错，但是结果不正确。我的 minimax 实现的缺陷在哪里？

Answer 1

您没有在两个播放器之间正确切换。 minimax' p b@(r :> []) = minimax p b 是错误的。在 minimax' 中的 map (minimax p) rs 不会切换到另一位玩家以获得最大化的一半。

我建议为 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

Answer 2

经过大量测试和困惑，我发现创建游戏树的函数存在一些缺陷。经过调试，Cirdec推荐的算法正确运行！

Haskell 递归极小极大树

Haskell Recursive Minimax Tree

algorithm

recursion

haskell

minimax