用递归方案修剪Alpha Beta

Question

我正在尝试更精通递归方案，因为到目前为止，它们确实有助于将粗糙的显式递归代码转变为较少的尖峰。在实施可能真正令人困惑的显式递归混淆的算法时，我倾向于提供的其他工具之一是Monad Transformers / Mutability。理想情况下，我想对递归方案感到足够的舒适感，以便我可以完全抛弃状态。我仍然可以触及的算法的一个示例是带有alpha beta修剪的minimax。我使用can态和minimax f-algebra（ data minimaxf af = mmresult a | mmstate [f] bool ）进行了正常的minimax，但是我不确定如何扩展此操作以进行alpha beta beta修剪。我认为也许我可以使用组织态性，或者也许有一些与ComOnads的自定义解决方案，但是我不知道如何使用任何一种技术来尝试解决方案。

除了具有递归方案的Alpha Beta修剪版本外，您对解决类似问题的任何一般建议都将不胜感激。例如，我很难将递归方案应用于通常以命令式实施的Dijkstra等算法。

Answer 1

alpha-beta可以看作是minimax的实例，其中 min 和 max 是使用精心选择的晶格实例化的。 完整的GIST 。

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

-- | 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> ord> ord ：和代码>实例是 lattice ，具有可决定性等效的（ eq ）。如果我们可以重新定义 ORD ，那么将 lattice 作为超类是适当的。但是在这里，newtype必须做：

-- 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

这是minimax。它是通过嵌入 leaf :: a - ＆gt进行参数化的。 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将游戏的分数直接用作晶格：

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

对于Alpha-Beta修剪，其想法是我们可以跟踪最佳分数的某些界限，这使我们可以在搜索中缩短搜索。因此，搜索将通过该间隔（Alpha，beta）进行参数化。这使我们进入了函数的晶格间隔a - ＆gt; ：

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

一个间隔可以由表示（也许是A，也许是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 如果 f 满足夹具i（fi）=夹具i（f（bot，top）），其中夹具在下面定义。这样一来， 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

函数通过尖端提起形成晶格。而且，当我们仅考虑满足夹具i（fi）=夹具i（f（bot，top））的功能时>如果 clamp＆lt;*＆gt; f = clamp＆lt;*＆gt; g ），则可能是晶格的短路定义。

两个功能的 inf l 和 r ，给定间隔 i =（alpha，beta），首先运行 l（Alpha，beta）获得值 vl 。
如果 vl＆lt; = alpha ，则必须是夹具i vl == alpha ==钳位i（min vl（ri）），因此我们可以停止并返回 vl 而无需查看 r 。否则，我们知道最终结果将不超过 vl ，因此我们还可以更新传递给 r 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))

因此，我们获得了α-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)