我正在嘗試更加精通遞回方案，因為到目前為止，它們對于將粗糙的顯式遞回代碼轉換為更少的尖峰-y 確實很有幫助。在實作可能與顯式遞回混淆的演算法時，我傾向于使用的其他工具之一是 monad 轉換器/可變性。理想情況下，我想對遞回方案感到滿意，這樣我就可以完全放棄有狀態了。我仍然會為轉換器使用的演算法示例是帶有 alpha beta 修剪的 minimax。我用變態和極小極大 f 代數做了正常極小極大（data MinimaxF a f = MMResult a | MMState [f] Bool)，但我不確定如何擴展它來進行 alpha beta 修剪。我想也許我可以使用 histomorphism，或者也許有一些帶有共胞的自定義解決方案，但我不知道如何使用這兩種技術嘗試解決方案。
除了帶有遞回方案的 alpha beta 修剪版本之外，您對解決類似問題的任何一般建議都將不勝感激。例如，我在將遞回方案應用于像 Dijkstra 這樣通常以命令式方式實作的演算法時遇到了麻煩。
uj5u.com熱心網友回復：
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: 更通用，并且Ordinstance 是Lattice具有可判定相等性 ( Eq) 的 a。如果我們可以重新定義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 fiff滿足clamp i (f i) = clamp i (f (Bot, Top))，其中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 gif 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))
因此，我們獲得了 alpha-beta 作為 minimax 的一個實體。一旦定義了上面的格子，我們只需要一些簡單的包裝和展開。
alphabeta :: Ord a => Game a -> a
alphabeta = runPruning . gminimax constPruning
constPruning :: Ord a => a -> Pruning a
constPruning x = Pruning \i -> clamp i x
runPruning :: Pruning a -> a
runPruning f = unPruning f (Bot, Top)
如果一切順利，alphabeta并且minimax應該有相同的結果：
main :: IO ()
main = quickCheck \g -> minimax g === alphabeta (g :: Game Int)
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/487727.html
上一篇：證明相互遞回類函式的減少子句