坚持 minimax 算法 - 下一步是什么？ Haskell

Question

我正在为 2 人棋盘游戏编写基本的 MiniMax 算法。到目前为止，我有一个评估板和 returns 分数的函数。我有一个函数 returns 所有可能的移动（以及这些移动的移动）等的玫瑰树......到给定的深度。我可以找到那棵树的叶子，并根据我的启发式给它们一个值，我的问题是在那之后我该做什么？

我是否以某种方式编辑叶子的父节点并根据子节点的值为父节点分配一个新值并继续前进直到到达根节点？

我是否打算从叶子向上创建一棵新树，选择最小/最大值直到到达根节点？如果是这样，新树如何记住到达叶子所需的所有移动？

我只想使用标准库中的导入（我不想下载包）。任何建议都会很棒，几天来一直在努力解决这个问题。谢谢

我试图从我的代码中挑选出一些部分来举例说明，但是有很多函数纠缠在一起。如果有帮助的话，这里是主要函数的类型签名和它们所做的解释：

这个函数接收一个Int（代表树的Depth），一个Game（棋盘的当前状态），立即可能的移动列表和returns一棵玫瑰树，包含每个可能的移动（以及移动到这些移动）以及与该移动相关的分数。如果玩家是黑暗的，它的分数是正的，如果玩家是黑暗的，它的分数是负的——玫瑰树的每个深度都是玩家的下一个动作。

roseTreeAtDepthN :: Int-> Game -> [Position] -> [Rose (Position,score)]

例如：treeAtDepthN 2 initialGame [(2,3),(3,2),(4,5),(5,4)] returns :

[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 中为每一步都使用了评估游戏状态的函数，但我意识到这可能不是必需的，应该只在树的叶子上使用。我不确定这是否有帮助。

稍后编辑：

不确定我的极小极大算法接下来要做什么。我有一个函数可以将所有可能的动作打印到一定深度，我有一个启发式方法可以评估每个动作，我只是不确定如何将它变成一个 returns 最佳动作的函数。我只想使用 Haskell 库中提供的函数（不想下载任何包等）。

data Rose a = Rose a [Rose a]
    deriving Show

我想如果我画一张图来解释我所拥有的功能，我可能会更容易理解。我有两个我能想到的解决方案，图片中概述了这两个解决方案，我不确定应该采用哪种方法（如果有的话）。 :

我猜我想要一个功能，将图片顶部的[玫瑰a]变成图片底部的玫瑰a。

谢谢。

Answer 1

好吧，您实际上不需要构建具有更新分数的树。您只需要计算出最佳着法（使最小、最坏情况得分最大化的着法）。

所以，从一些准备开始：

import Data.List
import Data.Ord

type Position = (Int,Int)
type Score = Int
data 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)

如果我们在叶子上，我们对分数的最佳估计是对当前棋盘的直接启发式评估，所以我们只是 return 那个位置和分数：

minscore (Rose x []) = x

否则，我们使用maximin的反面计算最佳反击得分，即minimax:

minscore (Rose (pos,_) moves)
  = let (_,score) = minimax moves in (pos,score)

请注意，minscore 总是 return 从树的根部开始下一步 (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)

这看起来像你想要的。

一些关于性能的说明：

minimax 算法实际上并不使用内部节点的启发式分数，仅在叶子上使用，因此您最好处理 [Rose Position] 并仅在需要的地方计算启发式分数（当您在 minscore 或 maxscore) 中检测到一片叶子。
Alpha-beta pruning 是 minimax 算法的著名优化，应该在任何严肃的实现中使用。

总之，完整代码为：

import Data.List
import Data.Ord

type Position = (Int,Int)
type Score = Int
data 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) []]]

坚持 minimax 算法 - 下一步是什么？ Haskell

stuck with minimax algorithm - what next? Haskell

haskell

tree

artificial-intelligence

minimax