αBeta剪枝与递归方案
我正在努力使递归方案更加熟练，因为到目前为止，它们确实有助于将显式递归代码转化为不太尖峰的代码。在实现算法时，我倾向于使用的其他工具之一是单变压器/可变性，这会使显式递归变得非常混乱。理想情况下，我希望对递归方案足够满意，这样我就可以完全放弃状态。一个例子，一个算法，我仍然会达到变压器的是极小极大与αβ剪枝。我做了一个普通的极小值和极小极大的f-代数(data MinimaxF a f = MMResult a | MMState [f] Bool)，但我不知道如何将它扩展到进行αβ剪枝。我想也许我可以使用组织形式，或者可能有一些自定义的解决方案与comonad，但我不知道如何尝试一个解决方案使用这两种技术。
除了使用递归方案修剪alpha beta版本之外，您对于解决类似问题的任何一般性建议都将不胜感激。例如，我在将递归方案应用于Dijkstra这样的算法时遇到了困难，这些算法通常以命令式的方式实现。
回答 1
Stack Overflow用户
发布于 2022-06-07 17:00:19
α-β可以看作是极小极大的一个实例，其中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 | Maximinimax将在由以下类定义的任何格上工作：
class Lattice l where
inf, sup :: l -> l -> lLattice类比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)参数化。这就引出了一个函数格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满足clamp i (f i) = clamp i (f (Bot, Top))时，才能构造clamp，其中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))的函数，并将它们等价于一个合适的等价关系(Pruning f = Pruning g如果clamp <*> f = clamp <*> g)时，格的短路定义就成为可能。
两个函数的inf ( l和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))因此，我们得到了α-β作为极小极大的一个实例。一旦定义了上面的格，我们只需要一些简单的包装和展开。
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)https://stackoverflow.com/questions/72517172
复制相似问题
腾讯云开发者
