F# で三目並べ（まるばつゲーム）

1. ゲームのコアロジック

先攻Aが置いた場所をあらわす 9bit と 後攻Bが置いた場所を表す 9bit の合計 18bit 、つまり 整数値でボードを表現できる。さらに、ボードには「Aが勝ち」「Bが勝ち」「ドロー」「未決着」の四状態で全てである。したがって 4状態の Discriminated Union で実装するのが妥当::

  type Board =
    | BoardA of int // Aが勝っている
    | BoardB of int // Bが勝っている
    | BoardD of int // ドロー
    | BoardX of int // 未決着

ボードのゲームでの利用シーンを考えると、既存のBoardに対し「場所 1にバツをつける」などのようなアクションが発生すると、次にどんなBoardになるか？というような 差分更新のための関数 tryPlaceが利用シーンの全てである（もちろん表示等のユーティリティは必要であるが）。

あとは Board型にメンバとして生やして外部に公開する:

// 実装は本稿末尾に
  type Board with
    static member create = create // ファクトリ関数
    static member init = create 0 |> Option.get // 初期盤面
    static member tryPlace = tryPlace // 差分更新関数
    member this.Repr = boardString this // 文字列関数

利用例:

Some Board.init
|> Option.bind (Board.tryPlace (true, 3)) 
|> Option.bind (Board.tryPlace (false, 5))
|> Option.bind (Board.tryPlace (true, 2)) 
|> Option.get |> fun x -> x.Repr |> printfn "%s"
// 出力: --AA-B---

2. 状態と状態遷移

ゲームの流れをこう捉える: 状態State にアクションAction を次々と演算していく。その結果、状態が Aのターン→Bのターン→... と状態遷移していき、最終的に ゲーム終了に落ち着く。以上を表現していこう

2-1. アクションの表現

前述の描像で 三目並べを捉えなおすと、アクションActionは「どの印を」「どの場所に」書こうとするかの指定とみなせる。「どの印を」というのはプレイヤーと同一視できるので結局以下のように記述できることになる

  type Player = A | B
  type Action = { player: Player; location: int }

ファクトリ関数をメンバに生やすとよい:

  let private createAction (str, loc) =
    match str, (0 <= loc && loc < 9) with
    | "A", true -> Some ({ player=A; location=loc})
    | "B", true -> Some ({ player=B; location=loc})
    | _, _ -> None

  type Action with
    static member create = createAction

2-2. 状態の表現

状態は「Aのターン」「Bのターン」「ゲーム終了」の3つ。各状態は Board をその内容物として含むべきだが 本稿はこれまでのアクション一覧も保持する:

  type State = 
    | TurnA of Game
    | TurnB of Game
    | Finish of Game * GameResult
  and Game = { board: Board; history: List<Action> }
  and GameResult =
    | Draw
    | Winner of Player * message: string

2-3. 状態遷移

状態遷移といっても、遷移の原因となるアクションは1種類しかないので複雑さはない。

• アクション・現在の状態 から必要な情報を取り出し
• （手番ミスなどの不正な遷移を見つけたら 反則勝ちにし）
• ゲームロジックに 取り出した情報を渡し ボードを進めてもらい
• そのボード状態を見て、ゲーム状態を遷移させる

トップレベルの状態遷移コード。決着が着いたなら以降のアクションは無視。AのターンとBのターンでやることもほぼ同じなので、どちらでも使えるヘルパーを用意してやってもらう

  let private stepState state action =
    match state with
     | TurnA game -> helper A game action 
     | TurnB game -> helper B game action
     | Finish _ -> state // ignore successive input

そんでヘルパー関数。起こりうる反則は「自分のターンじゃないのに印をつけようとした」「印をつけてはいけないところに印をつけようとした」。前者はヘルパー自身が状態遷移のエラーとして検知すべきであり、後者はゲームのロジックが判別するべき内容である。そのへんを踏まえて以下のようになる:

  let private helper turn game hand =
    let ctor = if turn = A then TurnB else TurnA
    let history = game.history@[hand]
    match (hand.player = turn), (Board.tryPlace ((hand.player = A), hand.location) game.board) with
    | false, _ ->  
        Finish ({ board=game.board; history=history } , Winner (turn, "手番でないのに印をつけようとした"))
    | _, None ->
        Finish ({ board=game.board; history=history } , Winner ((if turn = A then B else A), "無効な場所に印をつけた"))
    | true, Some board ->
        match board with
        | BoardA n -> Finish ({ board=board; history=history } , Winner (A, "三目並べた"))
        | BoardB n -> Finish ({ board=board; history=history } , Winner (B, "三目並べた"))
        | BoardD n -> Finish ({ board=board; history=history } , Draw)
        | BoardX n -> ctor ({ board=board; history=history })

2-4. 公開とユーティリティー

基本的には、上述のトップレベルの状態遷移関数(reducer)であるstepState を公開すれば事足りる。だが「アクションの列をユーザ入力として、最終的にゲームがどうなったか？」というAPIを公開するのも悪くない。また、ゲームの状態をわかりやすい文字列に変換する関数もあってよいだろう:

  type State with
    static member init = initState
    static member step = stepState
    static member fold = List.fold stepState initState // ハンドのListを渡すと結果を教えてくれる
    member this.Repr = stateString this

使い方例:

[ "A", 0; "B", 4; "A", 3; "B", 2; "A", 6 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// A-BAB-A-- (A,0), (B,4), (A,3), (B,2), (A,6) Winner:A.三目並べた

3. 実例

3-1. 勝負あり

[ "A", 0; "B", 4; "A", 3; "B", 2; "A", 6 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// A-BAB-A-- (A,0), (B,4), (A,3), (B,2), (A,6) Winner:A.三目並べた

3-2. 反則負け: 連続でマルをつけようとした

[ "A", 0; "A", 4; "B", 3 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// A-------- (A,0), (A,4) Winner:B.手番でないのに印をつけようとした

3-3. 反則負け: すでに印があるのに上書きしようとした

[ "A", 0; "B", 4; "A", 3; "B", 3; "A", 6 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// A--AB---- (A,0), (B,4), (A,3), (B,3) Winner:A.無効な場所に印をつけた

3-4. ドローゲーム

[ "A", 0; "B", 4; "A", 3; "B", 6; "A", 2;
  "B", 1; "A", 7; "B", 5; "A", 8 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// ABAABBBAA (A,0), (B,4), (A,3), (B,6), (A,2), (B,1), (A,7), (B,5), (A,8) Draw

4. コード

module Board = 
  type Board =
    | BoardA of int // Aが勝っている
    | BoardB of int // Bが勝っている
    | BoardD of int // ドロー
    | BoardX of int // 未決着

  let private unbox = function
    | BoardA n -> n
    | BoardB n -> n
    | BoardD n -> n
    | BoardX n -> n

  // 勝負つくときの判定マスク
  let private wval = 
    [[0;1;2];[3;4;5];[6;7;8];[0;3;6];[1;4;7];[2;5;8];[0;4;8];[2;4;6]]
    |> List.map ((List.map (fun i -> 1 <<< i)) >> List.sum)

  let private create n =
    let a = n &&& 0b111111111
    let b = n >>> 9 
    let validval = n >= 0 && n < (1 <<< 18) && (a &&& b) = 0
    let allFilled = (a ||| b) = 0b111111111
    match validval, allFilled, (List.contains a wval), (List.contains b wval) with
      | false, _, _, _ -> None
      | true, _, true, true -> None
      | true, _, true, false -> Some (BoardA n)
      | true, _, false, true -> Some (BoardB n)
      | true, true, false, false -> Some (BoardD n)
      | true, false, false, false -> Some (BoardX n)

  // ボードに (印,場所) を与えて既に印が書かれていなければ次のボードを作る
  let private tryPlace (sgn, loc) board =
    let n = unbox board
    let x = if sgn then 1 <<< loc else 1 <<< (loc + 9)
    let b2 = (1 <<< loc) ||| (1 <<< (loc + 9)) // both
    match (n &&& b2) = 0 with
    | true -> create (n ||| x)
    | false -> None

  let private boardString b =
    let n = unbox b
    [0..8]
    |> List.map (fun i -> 
        match ((1 <<< i) &&& n) <> 0, ((1 <<< (i + 9)) &&& n) <> 0 with
        | true, _ -> "A"
        | _, true -> "B"
        | _ -> "-" ) 
    |> String.concat ""

  type Board with
    static member create = create
    static member init = create 0 |> Option.get
    static member tryPlace = tryPlace
    member this.Repr = boardString this

module GameSystem = 
  open Board

  type Player = A | B
  // -- action: NOTE: for more complicated game, Action will be DU of Records
  type Action = { player: Player; location: int }

  let private createAction (str, loc) =
    match str, (0 <= loc && loc < 9) with
    | "A", true -> Some ({ player=A; location=loc})
    | "B", true -> Some ({ player=B; location=loc})
    | _, _ -> None

  type Action with
    static member create = createAction

  // -- state
  type State = 
    | TurnA of Game
    | TurnB of Game
    | Finish of Game * GameResult
  and Game = { board: Board; history: List<Action> }
  and GameResult =
    | Draw
    | Winner of Player * message: string

  let private initState = TurnA ({ board=Board.init; history=[] })

  // -- state transition
  let private helper turn game hand =
    let ctor = if turn = A then TurnB else TurnA
    let history = game.history@[hand]
    match (hand.player = turn), (Board.tryPlace ((hand.player = A), hand.location) game.board) with
    | false, _ ->  
        Finish ({ board=game.board; history=history } , Winner (turn, "手番でないのに印をつけようとした"))
    | _, None ->
        Finish ({ board=game.board; history=history } , Winner ((if turn = A then B else A), "無効な場所に印をつけた"))
    | true, Some board ->
        match board with
        | BoardA n -> Finish ({ board=board; history=history } , Winner (A, "三目並べた"))
        | BoardB n -> Finish ({ board=board; history=history } , Winner (B, "三目並べた"))
        | BoardD n -> Finish ({ board=board; history=history } , Draw)
        | BoardX n -> ctor ({ board=board; history=history })

  let private stepState state action =
    match state with
     | TurnA game -> helper A game action 
     | TurnB game -> helper B game action
     | Finish _ -> state // ignore successive input

  let private historyString =
    List.map (fun h -> sprintf "(%s,%d)" (if h.player = A then "A" else "B") h.location)
    >> String.concat ", "

  let private stateString = function
    | TurnA game ->
        sprintf "TurnA: %s %s" game.board.Repr (historyString game.history)
    | TurnB game -> 
        sprintf "TurnB: %s %s" game.board.Repr (historyString game.history)
    | Finish (game,res) -> 
        let a = match res with 
                | Draw -> "Draw" 
                | Winner (p, msg) -> sprintf "Winner:%s.%s" (if p = A then "A" else "B") msg 
        sprintf "%s %s %s" game.board.Repr (historyString game.history) a

  type State with
    static member init = initState
    static member step = stepState
    static member fold = List.fold stepState initState // ハンドのListを渡すと結果を教えてくれる
    member this.Repr = stateString this

使い方

open GameSystem

[ "A", 0; "B", 4; "A", 3; "B", 2; "A", 6 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// A-BAB-A-- (A,0), (B,4), (A,3), (B,2), (A,6) Winner:A.三目並べた

[ "A", 0; "A", 4; "B", 3 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// A-------- (A,0), (A,4) Winner:B.手番でないのに印をつけようとした


[ "A", 0; "B", 4; "A", 3; "B", 3; "A", 6 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// A--AB---- (A,0), (B,4), (A,3), (B,3) Winner:A.無効な場所に印をつけた


[ "A", 0; "B", 4; "A", 3; "B", 6; "A", 2;
  "B", 1; "A", 7; "B", 5; "A", 8 ]
|> List.map (Action.create >> Option.get)
|> (State.fold >> (fun x -> printfn "%s" x.Repr))
// ABAABBBAA (A,0), (B,4), (A,3), (B,6), (A,2), (B,1), (A,7), (B,5), (A,8) Draw