我正在为一个两人棋盘游戏编写一个基本的极小化极大算法。到目前为止，我有一个函数可以评估棋盘并返回一个分数。我还有一个函数可以返回所有可能移动的玫瑰树（以及这些移动的移动等）到给定的深度。我可以找到这棵树的叶子，并根据我的启发式方法给它们赋值，我的疑问是接下来该做什么？
我是否应该以某种方式编辑叶子的父节点，并根据子节点的值为父节点赋予一个新值，然后继续直到到达根节点？
我是否应该从叶子开始创建一个新的树，选择最小/最大值直到到达根节点？如果是的话，新的树如何记住到达叶子所需的所有移动？
我只想使用标准库的导入（不想下载任何包）。任何建议都会很棒，我已经为此挣扎了几天。谢谢
我试图挑选出我代码的一些部分来给出例子，但有很多函数纠缠在一起。如果有帮助的话，这里是主要函数的类型签名以及它们做什么的解释：
这个函数接受一个 Int（表示树的 Depth），一个 Game（当前棋盘状态），一个即时可能移动的列表，并返回一个玫瑰树，其中包含每个可能的移动（以及这些移动的移动）和与该移动相关联的分数。如果玩家是暗色，其分数为正，如果玩家是暗色，其分数为负 – 玫瑰树中的每个深度是下一个玩家的移动。
roseTreeAtDepthN :: Int-> Game -> [Position] -> [Rose (Position,score)]例如：treeAtDepthN 2 initialGame [(2,3),(3,2),(4,5),(5,4)] 返回：
[Rose ((2,3),4) [Rose ((2,2),-3) [],Rose ((2,4),-3) [],Rose ((4,2),-3) []], Rose ((3,2),4) [Rose ((2,2),-3) [],Rose ((2,4),-3) [],Rose ((4,2),-3) []], Rose ((4,5),4) [Rose ((3,5),-3) [],Rose ((5,3),-3) [],Rose ((5,5),-3) []], Rose ((5,4),4) [Rose ((3,5),-3) [],Rose ((5,3),-3) [],Rose ((5,5),-3) []]]我还有另一个函数可以让我获取树的叶子。我在 treeAtDepthN 中对每个移动使用评估游戏状态的函数，但我意识到这可能不是必要的，应该只在树的叶子上使用。我不确定这是否有帮助。
后续编辑：
不确定我的极小化极大算法接下来该做什么。我有一个函数可以打印到某个深度的所有可能移动，我有一个启发式方法来评估每个移动，我只是不确定如何将其变成一个返回最佳移动的函数。我只想使用 Haskell 库中给出的函数（不想下载任何包等）。
data Rose a = Rose a [Rose a] deriving Show我认为如果我画一张图来解释我拥有的函数，可能会更容易理解。我有两个可以想到的解决方案，在图中概述了，我不确定应该选择哪种方法，如果有的话：
我想我想要一个函数，可以将图顶部的 [Rose a] 转换为图底部的 rose a。
谢谢。
回答：
实际上，你不需要构建一个带有更新分数的树。你只需要计算最佳移动（即最大化最小、最坏情况分数的移动）。
所以，先从一些初步工作开始：
import Data.Listimport Data.Ordtype Position = (Int,Int)type Score = Intdata Rose a = Rose a [Rose a]我们可以编写一个函数，接受一个移动树列表，并选择移动（即 Position），该移动导致最小分数的最大值：
maximin :: [Rose (Position, Score)] -> (Position, Score)maximin = maximumBy (comparing snd) . map minscore辅助函数 minscore 计算移动树的最小分数，假设有最佳的反击策略。
minscore :: Rose (Position, Score) -> (Position, Score)如果我们在一个叶子节点，我们对分数的最佳估计是当前棋盘的直接启发式评估，所以我们只返回那个位置和分数：
minscore (Rose x []) = x否则，我们使用 maximin 的相反，即 minimax，来计算最佳反击策略的分数：
minscore (Rose (pos,_) moves) = let (_,score) = minimax moves in (pos,score)请注意，minscore 总是返回从树根开始的下一个移动（pos），但分数将从根节点（对于叶子）或通过进一步的递归计算（对于节点）获取。
maximin 和其镜像 minimax 的完整定义是：
maximin :: [Rose (Position, Score)] -> (Position, Score)maximin = maximumBy (comparing snd) . map minscore where minscore (Rose x []) = x minscore (Rose (pos,_) moves) = let (_,score) = minimax moves in (pos,score)minimax :: [Rose (Position, Score)] -> (Position, Score)minimax = minimumBy (comparing snd) . map maxscore where maxscore (Rose x []) = x maxscore (Rose (pos,_) moves) = let (_,score) = maximin moves in (pos,score)应用到你的图示示例：
example = maximin [Rose ((1,1),2) [Rose ((1,2),3) [], Rose ((1,3),-2) [], Rose ((1,4),4) []], Rose ((2,2),3) [Rose ((2,3),-7) [], Rose ((2,4),-1) []], Rose ((3,3),1) [Rose ((3,4),2) []]]你会得到：
> example((3,3),2)这看起来是你想要的。
关于性能的一些注意事项：
- 极小化极大算法实际上不使用内部节点的启发式分数，只在叶子节点使用，所以你可能最好处理一个
[Rose Position]，并且只在需要时计算启发式分数（当你在minscore或maxscore中检测到叶子时）。 - Alpha-beta 剪枝 是极小化极大算法的一个众所周知的优化，应该在任何严肃的实现中使用。
无论如何，完整的代码是：
import Data.Listimport Data.Ordtype Position = (Int,Int)type Score = Intdata Rose a = Rose a [Rose a]maximin :: [Rose (Position, Score)] -> (Position, Score)maximin = maximumBy (comparing snd) . map minscore where minscore (Rose x []) = x minscore (Rose (pos,_) moves) = let (_,score) = minimax moves in (pos,score)minimax :: [Rose (Position, Score)] -> (Position, Score)minimax = minimumBy (comparing snd) . map maxscore where maxscore (Rose x []) = x maxscore (Rose (pos,_) moves) = let (_,score) = maximin moves in (pos,score)example = maximin [Rose ((1,1),2) [Rose ((1,2),3) [], Rose ((1,3),-2) [], Rose ((1,4),4) []], Rose ((2,2),3) [Rose ((2,3),-7) [], Rose ((2,4),-1) []], Rose ((3,3),1) [Rose ((3,4),2) []]]