1

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

我发现，虽然我无法想出一些“纯功能”的方式来实现字母函数。即没有任何可变状态。

有什么好主意吗？

我想到的唯一想法是编写类似 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

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

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!")

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

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

4

2 回答 2

1

我既不熟悉该算法，也不熟悉 F#，因此我将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, α, β))

诀窍是将foreachwithbreak转换为具有适当基本情况的递归。我假设children(node)返回一个 cons 节点列表，可以使用head/解构tail并测试Nil.

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

此外，也许这是记忆化的一个案例——但这取决于域（我不熟悉）。这种递归可能更难并行化；为此，您也许可以并行建立一个vs 和 alpha/beta 列表（因为调用alphabeta可能是最昂贵的部分），用takeWhile这些列表上的 s 替换递归。

于 2015-02-16T17:54:47.790 回答
0

在John Hughes，为什么函数式编程很重要中描述了一种深度函数式方法。

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

于 2020-10-11T21:09:04.763 回答