指し手生成は大事

指し手生成は局面探索のために必要なルーチンで、非常に重要なコンポーネントの一つだ。

指し手生成の肝は無駄なく素早く必要な指し手を生成して探索モジュールに渡すこと。Bonanzaの指し手生成は指し手を幾つかのカテゴリに分類して必要な物だけ生成できるようにしてあるようだ(参考:2009-11-08 - Bonanzaソース完全解析ブログ)。

いまのHaskell将棋はすべての局面をとりあえず生成しているようだ。この部分について解析を進めてみる。

使われ方

指し手生成は先にいったように局面を探索して展開していく時に必要なので探索モジュールに使われている。具体的には

minmax dep bd = maximumBy (compare `on` va) nexts
    where
        nexts = map next $ MoveGenerator.mvGenFull bd
        next mv = conv mv . minmax (dep - 1) $ Board.bdDo bd mv

Search.hsにあるminmaxルーチンは渡された盤面からmvGenFullを使って指し手を生成して(考えうるあらゆる盤面を生成して)そのまま探索関数へ渡すことで深く探索していく。

実装

早速、MoveGeneratorの実装を見てみよう。

mvGenFull bd = allInNoCheck bd ++ dropMvs bd

つまり、allInNoCheck関数による生成と駒打ちですべての指し手を生成しているようだ。

駒打ち

駒打ちの方は簡単で、

dropMvs (Board.Bd sqs hs me _ pcl) =
    let
        pcs = map fst $ Board.sideHs me hs
        space = filter ((== Piece.Empty) . (sqs !)) Move.onBdPoss
        canDrop' pc to = Util.if' (Piece.p8 pc == Piece.FU, (&& (noPawnFile ! Util.posFile to)), id) $ canDrop pc to
        noPawnFile = pawnFile // [(Util.posFile pos, False) | pos <- pcl ! Piece.Pc me Piece.Unp Piece.FU]
        pawnFile = listArray (1, 9) $ repeat True
    in
        [Move.Drop to pc | pc <- pcs, to <- space, canDrop' pc to]

とあるが、ざっくり読むと持ち駒hsについて開いている場所(space)で、二歩にならない場所(noPawnFile)にMove.Dropでうつ、ことを持ち駒全てに適用して、その結果である盤面の集合をリストで返す。

Arrayの演算子//は配列の一部分について内容を入れ替える演算子だ。例えば

Prelude Data.Array> let a = array (1,4) [(1,"Apple"), (2,"Banana"), (3,"Carbon"), (4,"Duck")]
Prelude Data.Array> a
array (1,4) [(1,"Apple"),(2,"Banana"),(3,"Carbon"),(4,"Duck")]
Prelude Data.Array> a // [(2,"Bean"),(4,"Django")]
array (1,4) [(1,"Apple"),(2,"Bean"),(3,"Carbon"),(4,"Django")]
Prelude Data.Array> a
array (1,4) [(1,"Apple"),(2,"Banana"),(3,"Carbon"),(4,"Duck")]

こんな感じ。指定した2番めと4番目だけを入れ替えている。もちろん元の配列は変わらない。

盤面上のコマを動かす

今回の核心となるコードの外観を見てみると

allInNoCheck :: Board.Bd -> [Move.Mv]
allInNoCheck (Board.Bd sqs hs me _ pcl) =
    concatMap pcsMvs $ Board.sidePcl me pcl
        where
            pcsMvs :: (Piece.Pc, [Piece.Pos]) -> [Move.Mv]
            pcsMvs (pc, pcsqs) = concatMap pcMvs pcsqs
                where
                    pcMvs fr = concatMap (incMvs fr) (Piece.pcIncs pc)
                        where
                            incMvs cur inc =
                                case cap of
                                    Piece.Empty -> mvAdd ++ Util.if' (Piece.isSlider pc inc, incMvs to inc, [])
                                    Piece.Wall -> []
                                    otherwise -> if Piece.co cap == me then [] else mvAdd
                                where
                                    to = cur + inc
                                    cap = sqs ! to
                                    mvAdd =
                                        Util.if' (canPro pc fr to, (Move.Mv fr to pc cap True :), id)
                                        $ Util.if' (canNoPro pc fr to, [Move.Mv fr to pc cap False], [])

こんな感じだ。すごいwhereの繰り返しでネストが相当深い。なんなの。

この中でcanProとcanNoProはその駒が位置frから位置toに動かした時に、成れるか成れないかを返す関数だ。具体的にはその駒の性質(金とか王は成らない)や場所(当然敵陣内でないと成れない)を考慮してそれを返してくれる。

さて、この手の関数は内側から読み解くのが良いだろうから、内側から読んでいくと

where
incMvs cur inc =
    case cap of
        Piece.Empty -> mvAdd ++ Util.if' (Piece.isSlider pc inc, incMvs to inc, [])
        Piece.Wall -> []
        otherwise -> if Piece.co cap == me then [] else mvAdd
    where
        to = cur + inc
        cap = sqs ! to
        mvAdd =
            Util.if' (canPro pc fr to, (Move.Mv fr to pc cap True :), id)
            $ Util.if' (canNoPro pc fr to, [Move.Mv fr to pc cap False], [])

この部分。更に分解すると

mvAdd =
    Util.if' (canPro pc fr to, (Move.Mv fr to pc cap True :), id)
    $ Util.if' (canNoPro pc fr to, [Move.Mv fr to pc cap False], [])

この部分。これは簡単で、前半は成れる場合は成れる手をすべて生成して返す。後半は成れないものをすべてリストアップする。前半部分は[Mv]->[Mv]なる関数で、これは単純なadd関数だ。canProが正の場合は:で結合し、そうでない場合はidでそのものを返す関数になる。それに成れないものはそのリスト、成れるものは空白を返して前半と結合すると全体でMvのリストが得られる。

incMvs cur inc =
    case cap of
        Piece.Empty -> mvAdd ++ Util.if' (Piece.isSlider pc inc, incMvs to inc, [])
        Piece.Wall -> []
        otherwise -> if Piece.co cap == me then [] else mvAdd
    where
        to = cur + inc
        cap = sqs ! to
        mvAdd = (成れるものと成れないものの動き方のリスト)

incはつまり、どちら向きに動かすか、ということ。incは具体的には駒ごとに

[(BP,[-17]),(BL,[-17]),(BN,[-35,-33]),(BS,[-18,-17,-16,16,18]),(BG,[-18,-17,-16,-1,1,17]),(BB,[-18,-16,16,18]),(BR,[-17,-1,1,17]),(BK,[-18,-17,-16,-1,1,16,17,18]),(BPP,[-18,-17,-16,-1,1,17]),(BPL,[-18,-17,-16,-1,1,17]),(BPN,[-18,-17,-16,-1,1,17]),(BPS,[-18,-17,-16,-1,1,17]),(BPB,[-18,-17,-16,-1,1,16,17,18]),(BPR,[-18,-17,-16,-1,1,16,17,18])]

というふうに決まっている。歩は-17(前進)だし、今日も-17方向、...という感じに方向が全て入っている。curは現在位置だから、incMvs cur incは

何もない場所の場合は少し複雑なので後で解説するとして、
壁の場合は空リストを返す。動いちゃダメ。
なんかあった時はその駒がcapに入っているのでmvAddを返すと自然とcap入りのMvのリストが変える。もちろん移動先が自分の駒だったら動いちゃダメなので空リスト。

何もない場所の場合、mvAddは成・不成を考慮しているので、mvAddを返せばよいのだけど、飛車、角、香車はその方向に次々と開いている限り進むことができるので、Piece.isSliderでその方向へ次々進めるかを判定しながらincMvsを再帰的に呼び出し続ければよい。壁があるか何か駒があればその再帰は止まる。

まとめると、incMvsはある指定された方向へある駒を動かすときに得られるすべての移動を生成する関数だ。つまり、この関数を盤上のすべての駒に対してすべての方向に適用すればすべての手が得られそうだ。

まさにそれをやっているのがこの大きな関数の前半部分にある。

allInNoCheck (Board.Bd sqs hs me _ pcl) =
    concatMap pcsMvs $ Board.sidePcl me pcl
        where
            pcsMvs :: (Piece.Pc, [Piece.Pos]) -> [Move.Mv]
            pcsMvs (pc, pcsqs) = concatMap pcMvs pcsqs
                where
                    pcMvs fr = concatMap (incMvs fr) (Piece.pcIncs pc)

長々とは説明しないが、concatMap(mapしてflattenする)を着目する駒と着目する方向を次々変えながら適用していく。ここが二重whereになっている理由はmapをつかって二重ループ(どの駒を？とどの方向へ？の二重ループ)で処理するためだ。

これである盤面からありうるすべての"次の盤面"を生成する関数であるmvGenFull関数を理解することができたように思う。

ちなみに

この関数、一つ忘れていることがあって自殺手を生成する。さらに合法手じゃない合法手も生成してしまうのだ(参考:2011-10-17 - Bonanzaソース完全解析ブログ)。なので、現状のHaskell将棋は自殺手を打ってすぐ負けてしまう。

まとめ

今回は指し手生成部分を眺めてみた。次は探索部とさして生成部の関係について眺め、今後の改良について書いてみたいと思う。

euphonictechnologies’s diary

Haskell超初心者の日記です。OCamlが好きです。

Haskellで将棋 - 指し手生成

指し手生成は大事

使われ方

実装

駒打ち

盤面上のコマを動かす

ちなみに

まとめ