递归方案的Alpha Beta剪枝

Question

我试图更熟练地使用递归方案，因为它们迄今为止非常有帮助，可以将复杂的显式递归代码转化为不那么难懂的形式。在实现算法并且显式递归变得非常混乱时，我倾向于使用单子变换器/可变性等工具。理想情况下，我希望能够熟练掌握递归方案，从而完全摆脱状态。我仍然会使用单子变换器来实现例如alpha-beta剪枝的minimax算法。我使用catamorphism和minimax f-algebra（data MinimaxF a f = MMResult a | MMState [f] Bool）实现了正常的minimax，但我不确定如何扩展它来实现alpha-beta剪枝。我想也许我可以使用histomorphism，或者也许有一些基于共范畴的自定义解决方案，但我不知道如何尝试使用这两种技术来解决问题。

除了递归方案中alpha-beta剪枝的版本外，如果您对处理类似问题的一般建议，我将不胜感激。例如，我在应用递归方案来解决通常以命令方式实现的Dijkstra算法时遇到了困难。

- Ace shinigami

---

关于 Dijkstra 算法；如果你还没有阅读过 fgl 论文，我强烈推荐你去看看。 - Daniel Wagner

我认为如果您在没有alpha-beta剪枝的情况下加入现有的极小化最大化解决方案，这个问题会更好。 - amalloy

Bool 是否代表当前玩家？ - Li-yao Xia

Answer 1

Alpha-beta可以看作是minimax的一种实例，其中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实例是带有可判等性(Eq)的Lattice。如果我们可以重新定义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)

我们要求只有在f满足clamp i (f i) = clamp i (f (Bot, Top))时才能构建Pruning f，其中clamp的定义如下。这样，f就是一个搜索算法，如果它学习到其结果在区间外，则可以截断计算而无需找到准确结果。

clamp :: Ord a => Interval a -> a -> a
clamp (l, r) = clampBot l . clampTop r

clampBot :: Ord a => WithBot a -> a -> a
clampBot Bot x = x
clampBot (NoBot y) x = max y x

clampTop :: Ord a => WithTop a -> a -> a
clampTop Top x = x
clampTop (NoTop y) x = min y x

函数通过逐点提升组成一个格。当我们只考虑满足clamp i (f i) = clamp i (f (Bot, Top))的函数，并将它们模以适当的等价关系（如果clamp <*> f = clamp <*> g，则Pruning f = Pruning g），格的短路定义变得可能。

给定区间i = (alpha, beta)，函数l和r的inf首先运行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作为minimax的一个实例得到。一旦定义了上面的格子，我们只需要进行一些简单的包装和解包操作即可。

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)

- Li-yao Xia

---

天啊，这太神奇了。这个观察结果（你可以将极小化最大值推广到格子中，并从中免费得到alpha-beta剪枝）是标准的吗？如果是的话，为什么通常对alpha-beta剪枝的解释如此复杂，而不直接使用这个观察结果呢？ - Daniel Wagner

不知道。也许这可以成为至少一个功能性珍珠的开端。我分享你的困惑。在寻找答案时，我发现维基百科关于Alpha-Beta剪枝的条目很混乱，那里的代码留下了更多问题而不是回答…… - Li-yao Xia