使用递归方案进行 Alpha Beta 剪枝

Question

我正在尝试更加熟练地使用递归方案，因为到目前为止，它们对于将粗糙的显式递归代码转变为不那么尖峰的东西确实很有帮助。在实现可能与显式递归真正混淆的算法时，我倾向于使用的其他工具之一是 monad 转换器/可变性。理想情况下，我希望对递归方案足够熟悉，这样我就可以完全放弃状态性。我仍然会使用 Transformer 的算法的一个例子是带有 alpha beta 剪枝的极小极大算法。我用变形和极小极大 f 代数 ( data MinimaxF a f = MMResult a | MMState [f] Bool) 做了正常的极小极大，但我不确定如何扩展它来进行 alpha beta 剪枝。我想也许我可以使用组织同态，或者也许有一些带有comonads的自定义解决方案，但我不知道如何尝试使用这两种技术的解决方案。

除了使用递归方案的 alpha beta 修剪版本之外，我们将非常感谢您提供有关解决类似问题的任何一般建议。例如，我在将递归方案应用于 Dijkstra 等通常以命令式方式实现的算法时遇到了麻烦。

Answer 1

Alpha-beta 可以被视为极小极大的一个实例，其中min和max是使用精心选择的格子来实例化的。完整要点。

我们将游戏表示为一棵树，其中每个内部节点都是游戏中的一个位置，等待指定的玩家选择到子节点的移动，并且每个叶子都是带有其分数或值的最终位置。

-- | At every step, either the game ended with a value/score,
-- or one of the players is to play.
data GameF a r = Value a | Play Player (NonEmpty r)
 deriving Functor
type Game a = Fix (GameF a)

-- | One player wants to maximize the score,
-- the other wants to minimize the score.
data Player = Mini | Maxi

minimax将适用于由以下类定义的任何晶格：

class Lattice l where
  inf, sup :: l -> l -> l

类比Lattice: 更通用Ord，而Ord实例是Lattice具有可判定的相等性 ( Eq) 的。如果我们可以重新定义，那么将其添加为超类Ord是合适的。Lattice但这里需要一个新类型：

-- The Lattice induced by an Ord
newtype Order a = Order { unOrder :: a }
  deriving (Eq, Ord)

instance Ord a => Lattice (Order a) where
  inf = min
  sup = max

这是极小极大。它通过将leaf :: a -> l最终值嵌入到所选晶格中来参数化。一个玩家最大化嵌入价值，另一个玩家最小化它。

-- | Generalized minimax
gminimax :: Lattice l => (a -> l) -> Game a -> l
gminimax leaf = cata minimaxF where
  minimaxF (Value x) = leaf x
  minimaxF (Play p xs) = foldr1 (lopti p) xs

lopti :: Lattice l => Player -> l -> l -> l
lopti Mini = inf
lopti Maxi = sup

“常规”极小极大直接使用游戏的分数作为格子：

minimax :: Ord a => Game a -> a
minimax = unOrder . gminimax Order

对于 alpha-beta 剪枝，我们的想法是我们可以跟踪最佳分数的一些界限，这使我们能够缩短搜索。因此搜索将通过该间隔进行参数化(alpha, beta)。这将我们引向一个函数格Interval a -> a：

newtype Pruning a = Pruning { unPruning :: Interval a -> a }

间隔可以表示为(Maybe a, Maybe a)允许任一侧无界。Ord但为了清晰起见，我们将使用更好的命名类型，并在每一侧利用不同的实例：

type Interval a = (WithBot a, WithTop a)
data WithBot a = Bot | NoBot a deriving (Eq, Ord)
data WithTop a = NoTop a | Top deriving (Eq, Ord)

我们将要求我们只能Pruning f在f满足时才可以构造clamp i (f i) = clamp i (f (Bot, Top))，其中clamp定义如下。这样，f如果搜索算法得知其结果位于区间之外，则可能会短路，而无需找到确切的结果。

class Lattice l where
  inf, sup :: l -> l -> l

函数通过逐点提升形成格子。当我们只考虑满足并且使它们对适当的等价关系（ if ）clamp i (f i) = clamp i (f (Bot, Top))取模时，晶格的短路定义就成为可能。Pruning f = Pruning gclamp <*> f = clamp <*> g

两个inf函数land的r给定一个区间i = (alpha, beta)，首先运行l (alpha, beta)以获得一个值vl。如果vl <= alpha，那么一定是clamp i vl == alpha == clamp i (min vl (r i))这样，我们可以停下来vl不看而归r。否则，我们运行r，知道最终结果不会超过，vl因此我们还可以更新传递给 的上限r。sup是对称定义的。

instance Ord a => Lattice (Pruning a) where
  inf l r = Pruning \(alpha, beta) ->
    let vl = unPruning l (alpha, beta) in
    if NoBot vl <= alpha then vl else min vl (unPruning r (alpha, min (NoTop vl) beta))

  sup l r = Pruning \(alpha, beta) ->
    let vl = unPruning l (alpha, beta) in
    if beta <= NoTop vl then vl else max vl (unPruning r (max (NoBot vl) alpha, beta))

因此我们得到 alpha-beta 作为极小极大的一个实例。一旦定义了上面的格子，我们只需要一些简单的包装和展开。

alphabeta :: Ord a => Game a -> a
alphabeta = runPruning . gminimax constPruning

constPruning :: a -> Pruning a
constPruning = Pruning . const

runPruning :: Pruning a -> a
runPruning f = unPruning f (Bot, Top)

如果一切顺利，alphabeta应该minimax有相同的结果：

main :: IO ()
main = quickCheck \g -> minimax g === alphabeta (g :: Game Int)