如何以功能方式编写 alphabeta 搜索功能（无可变变量）？

Question

这个周末我的编程乐趣是用 F# 编写了一个 300 行的黑白棋程序。可能还需要几个周末才能找出如何并行化 alphabeta 搜索，这实际上超出了这个问题的范围。

但我发现我无法想出一些 "pure functional" 方法来实现 alphabeta 函数。 IE。没有任何可变状态。

有什么好主意吗？

我想到的唯一想法是编写类似 Seq.foldUntil() 的函数，其中累加器状态用于存储状态的变化。并且可以通过传入的lambda函数取消。

可能看起来像这样：

let transformWhile<'t,'s,'r> (transformer : 's -> 't -> 's * 'r * bool ) (state : 's) (sequence : 't seq) : 'r seq

这里是不纯的 alphabeta 函数...

let rec alphabeta depth alpha beta fork (position : ReversiPosition) (maximize : bool) : (SquareName option * int)  =
    match depth with
    | 0 -> (None, snd (eval position))
    | _ -> 
        let allMoves = 
            allSquares 
            |> Seq.map (fun sq -> (sq,tryMove (position.ToMove) sq position))
            |> Seq.filter (fun pos -> match snd pos with | Some(_) -> true | None -> false )
            |> Seq.map (fun opos -> match opos with | (sq,Some(p)) -> (sq,p) | _ -> failwith("only Some(position) expected here."))
            |> Array.ofSeq
        let len = allMoves.Length
        match len with
        | 0 -> (None, snd (eval position))
        | _ ->
            if maximize then
                let mutable v = System.Int32.MinValue
                let mutable v1 = 0
                let mutable a = alpha
                let b = beta
                let mutable i = 0
                let mutable bm : SquareName option = None
                let mutable bm1 : SquareName option = None
                while (i<len) && (b > a) do
                    let x,y = alphabeta (depth-1) a b false (snd allMoves.[i]) false
                    bm1 <- Some(fst allMoves.[i])
                    v1 <- y
                    if v1 > v then
                        bm <- bm1
                        v <- v1
                    a <- max a v
                    if b > a then 
                        i <- (i + 1)
                (bm,v)
            else
                let mutable v = System.Int32.MaxValue
                let mutable v1 = 0
                let a = alpha
                let mutable b = beta
                let mutable i = 0
                let mutable bm : SquareName option = None
                let mutable bm1 : SquareName option = None
                while (i<len) && (b > a) do
                    let x,y = alphabeta (depth-1) a b false (snd allMoves.[i]) true
                    bm1 <- Some(fst allMoves.[i])
                    v1 <- y
                    if v1 < v then
                        bm <- bm1
                        v <- v1
                    b <- min b v
                    if b > a then 
                        i <- (i + 1)
                (bm,v)

在等待答案的过程中，我决定尝试一下我的 transformWhile 想法，结果是这样的：

module SeqExt =
    let rec foldWhile<'T,'S,'R> (transformer : 'S -> 'T -> 'S * 'R * bool ) (state : 'S) (sequence : seq<'T>) : 'R option =
        if (Seq.length sequence) > 0 then
            let rest = (Seq.skip 1 sequence)
            let newState, resultValue, goOn = transformer state (Seq.head sequence) 
            if goOn && not (Seq.isEmpty rest) then 
                foldWhile transformer newState rest
            else
                Some(resultValue)
        else
            None

一些交互式测试表明它适用于一些琐碎的事情，所以我决定编写一个新版本的 alphabeta，现在看起来像这样：

let rec alphabeta depth alpha beta fork (position : ReversiPosition) (maximize : bool) : (SquareName option * int)  =
    match depth with
    | 0 -> (None, snd (eval position))
    | _ -> 
        let allMoves = 
            allSquares 
            |> Seq.map (fun sq -> (sq,tryMove (position.ToMove) sq position))
            |> Seq.filter (fun pos -> match snd pos with | Some(_) -> true | None -> false )
            |> Seq.map (fun opos -> match opos with | (sq,Some(p)) -> (sq,p) | _ -> failwith("only Some(position) expected here."))
        let len = Seq.length allMoves
        match len with
        | 0 -> (None, snd (eval position))
        | _ ->
            if maximize then
                let result = SeqExt.foldWhile 
                                ( fun (state : int * int * SquareName option * int ) move -> 
                                    let curAlpha,curBeta,curMove,curValue = state
                                    let x,y = alphabeta (depth-1) curAlpha curBeta false (snd move) false
                                    let newBm,newScore =
                                        if y > curValue then
                                            (Some(fst move), y)
                                        else
                                            (curMove,curValue)
                                    let newAlpha = max curAlpha newScore
                                    let goOn = curBeta > newAlpha
                                    ((newAlpha,curBeta,newBm,newScore),(newBm,newScore),goOn)
                                ) (alpha,beta,None,System.Int32.MinValue) allMoves
                match result with
                | Some(r) -> r
                | None -> failwith("This is not possible! Input sequence was not empty!")
            else
                let result = SeqExt.foldWhile 
                                ( fun (state : int * int * SquareName option * int ) move -> 
                                    let curAlpha,curBeta,curMove,curValue = state
                                    let x,y = alphabeta (depth-1) curAlpha curBeta false (snd move) true
                                    let newBm,newScore =
                                        if y < curValue then
                                            (Some(fst move), y)
                                        else
                                            (curMove,curValue)
                                    let newBeta = min curBeta newScore
                                    let goOn = newBeta > curAlpha
                                    ((curAlpha,newBeta,newBm,newScore),(newBm,newScore),goOn)
                                ) (alpha,beta,None,System.Int32.MaxValue) allMoves
                match result with
                | Some(r) -> r
                | None -> failwith("This is not possible! Input sequence was not empty!")

这看起来像函数式编程专家会做的事情吗？或者你会怎么做？

虽然我之前的暴力搜索是尾递归的（没有建立调用堆栈），但这个纯函数版本不再是尾递归的。谁能找到使它再次尾递归的方法？

Answer 1

我既不熟悉算法，也不熟悉 F#，所以我将 pseudocode from Wikipedia 翻译成纯函数变体：

function alphabeta(node, depth, α, β, maximizingPlayer)
  if depth == 0 or node is a terminal node
    return the heuristic value of node
  if maximizingPlayer
    return take_max(children(node), depth, α, β)
  else
    return take_min(children(node), depth, α, β)

function take_max(children, depth, α, β)
  v = max(v, alphabeta(head(children), depth - 1, α, β, FALSE))
  new_α = max(α, v)

  if β ≤ new_α or tail(children) == Nil
    return v
  else
    return take_max(tail(children), depth, α, β))

function take_min(children, depth, α, β)
  v = min(v, alphabeta(head(children), depth - 1, α, β, TRUE))
  new_β = min(β, v)

  if new_β ≤ α or tail(children) == Nil
    return v
  else
    return take_min(tail(children), depth, α, β))

诀窍是将 foreach 和 break 转换为具有适当基本情况的递归。我假设 children(node) returns 一个节点的缺点列表，可以使用 head/tail 对其进行解构并测试 Nil.

显然，我无法对此进行测试，但我认为它包含正确的想法（并且几乎 Python...）。

另外，也许这是记忆的情况——但这取决于领域（我不熟悉）。这种递归的并行化可能更加困难；为此，您也许可以并行构建 v 和 alphas/betas 的列表（因为对 alphabeta 的调用可能是最昂贵的部分），用 [=19 替换递归=]在这些名单上。

Answer 2

John Hughes, Why functional programming matters 中描述了一种深度功能方法。

此外，您可以查看 Russell & Norvig 的实现，人工智能 - 一种现代方法

in Lisp（Norvig 本人！），
in Haskell (by @chris-taylor),
in CoffeeScript（我自己）。

如何以功能方式编写 alphabeta 搜索功能（无可变变量）？

How to write alphabeta search function in a functional way (no mutable variables)?

f#

functional-programming

alpha-beta-pruning