Haskell递归极小化树

Question

我正在尝试使用minimax算法在Haskell中编写一个Tic Tac Toe程序。我按照以下方式构建了自己的“Rose a”数据类型:

data Rose a = a :> [Rose a]

这是我想要“存储”极小化极大树的数据类型。我了解极小极大算法的工作原理，但似乎无法在递归函数中实现它。

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"（一种能够保存井字棋棋盘的数据类型）是否有赢家，并返回Maybe P1或Maybe P2或Nothing。

我编写的"minimax"函数没有报错，但结果不正确。我的minimax实现有什么问题？

- Felix

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

- Cirdec

---

嗨Cirdec，非常感谢您的回复。您的代码似乎很合理，但是当我测试minimax函数并输入P1和一个示例Board时，我的minimax树中充满了“ 1 ”。但是示例Board实际上有P2获胜的情况，这意味着树中也应该有“-1”...我仔细检查了“hasWinner”函数是否有效，并经过一些测试后，它似乎可以正确地工作。 - Felix

如果r是由P1选择的移动，rs是可供P2选择的移动，并且P2试图使其最小化。也许P1需要考虑另一个玩家如何选择移动，而不是为了让P2做出P1最喜欢的移动。 - Cirdec

这不就是最小化P2的移动吗？我该如何在我的代码中实现你的理论？ - Felix

Answer 2

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

- Felix

---

你能分享一下你的代码库吗？ - mLstudent33