1

この週末のプログラミングの楽しみは、F# で 300 行のリバーシ プログラムを作成することでした。アルファベット検索を並列化する方法を見つけるには、おそらくあと数週間かかるでしょう。実際、これはこの質問の範囲外です。

しかし、私が見つけたのは、alphabeta 関数を実装するための「純粋に機能的な」方法を思いつくことができなかったことです。つまり、可変状態はありません。

そのための良いアイデアはありますか？

私の頭に浮かんだ唯一のアイデアは、状態の変化を格納するためにアキュムレータ状態が使用される Seq.foldUntil() 関数のようなものを書くことです。そして、渡されたラムダ関数によってキャンセルできます。

多分このように見えます：

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

ここで、不純なアルファベット関数...

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

それは、関数型プログラミングのプロが行うようなものですか? または、あなたは何をしますか？

以前のブルート フォース検索は末尾再帰 (コール スタックが構築されない) でしたが、この純粋な機能バージョンは末尾再帰ではなくなりました。誰かが再び末尾再帰にする方法を見つけることができますか?

4

2 に答える 2

1

私はアルゴリズムにも F# にも精通していないので、ウィキペディアの疑似コードを純粋に機能的なバリアントに変換しました。

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)できるノードのコンス リストを返すと仮定しました。headtailNil

明らかに、これをテストすることはできませんが、適切なアイデアが含まれていると思います (そしてほとんど Python です...)。

また、これはメモ化のケースかもしれませんが、それはドメインによって異なります（私はよく知りません）。この種の再帰では、並列化はおそらくより困難です。vそのためには、 s とアルファ/ベータのリストを並行して作成し (呼び出しalphabetaがおそらく最もコストのかかる部分であるため)、takeWhileそれらのリストの再帰を s に置き換えることができます。

于 2015-02-16T17:54:47.790 に答える