読者です 読者をやめる 読者になる 読者になる

euphonictechnologies’s diary

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

follow us in feedly

Haskellで将棋 - KKP/KPP評価関数を見てみる

今回は

ボナンザ型の評価関数(ここでは単にfv.binを使ったKKP/KPP評価のことを指すことにする)、であるコードを解析していく。

コード:

hamilcar/Eval.hs at master · ysnrkdm/hamilcar · GitHub

KPP/KKP

Kは王、Pはピースで2つの王と一つの何かしらの駒、あるいは2つの駒と一つのどちらかの王との位置関係で点数をつけていく評価方式のことだ。 これは盤面全体をこの3駒関係の足し算で構成する、ということ。

まずは

このbonaPos関数を解読していく。

-- Translate Piece.Pos to bonanza position
bonaPos :: Piece.Co -> Piece.Pos -> Piece.Pos
bonaPos co sq = if co == Piece.B then a ! sq else b ! sq
    where
        a = listArray (0, 220) [sq `quot` 17 * 9 + sq `rem` 17 - 22 | sq <- [0 .. 220]]
        b = listArray (0, 220) [(80 -) $ sq `quot` 17 * 9 + sq `rem` 17 - 22 | sq <- [0 .. 220]]

元のコードからはかなりコメントを足している。

これは簡単で、このプログラムの内部の位置をfv.binをルックアップするためにボナンザの位置定数に変換している。 2009-11-07 - Bonanzaソース完全解析ブログによれば、ボナンザは9一を0として8一に1、7一に2,...ときて1一に8、9二に9を割り振るような盤面の一の持ち方をしている。

9 8 ... 2 1
0 1 ... 7 8
9 10 ... 16 17
... ... ... ... ... ...

このHaskellプログラムの内部では9一を38、8一を39,...ときて1一に46、9二に55を割り振るような割り振り方をしている。(つまり、右端まで来たら次の行の左端へは+9する)。

9 8 ... 2 1
38 39 ... 45 46
55 56 ... 63 64
... ... ... ... ... ...

どういう理由かは今のところわからないが、そのような変則的な割り振り方をボナンザ型の素直な割り振り方に変換する関数だ。

手番で上下を逆さまにするためにaとbで割り振っているようだ。ここは変数名をあとで変えておくことにしよう。aとかbとかはひどい。

次の関数を見てみる。posK関数だ。

posK :: Board.Pcl -> (Piece.Co, Piece.Co) -> Piece.Pos
posK pcl (kingColor, pieceColor) = bonaPos pieceColor . head $
    pcl ! Piece.Pc co Piece.Unp Piece.OU

posK関数は先のbonaPos関数を使ってBoard.Pcl(盤面上の駒から場所のリストへのマップ)から指定された王の場所を取り出してkingColorとして指定した王の場所にpieceColor色の駒がいる時の場所を返す。盤面の先手番と後手番を両方試すためにあとでこの関数を使って

  • 先手番の王の位置の後手番から見た位置
  • 先手番の王の位置の先手番から見た位置(つまりそのまま)
  • 後手番の王の位置の後手番から見た位置(つまりそのまま)
  • 後手番の王の位置の先手番から見た位置

の4通り全てを作り出す。

評価関数の実態の先ずは大枠を見てみる

今日の本丸となるbonaVa関数は以下の様な見かけをしている。

bonaVa :: Board.Bd -> Va
bonaVa (Board.Bd _ hs co _ pcl) =
    let
        [bk0, wk0, bk1, wk1] = map (posK pcl) [(Piece.B, Piece.B), (Piece.W, Piece.B), (Piece.B, Piece.W), (Piece.W, Piece.W)]
        k2h0 = sum [k2Va bk0 wk0 $ k2HsA ! p + hs ! p | p <- Board.hsRa Piece.B]
        k2h1 = sum [k2Va wk1 bk1 $ k2HsA ! p + hs ! p | p <- Board.hsRa Piece.W]
        k2p0 = sum [k2Va bk0 wk0 $ k2PcA ! p + bonaPos Piece.B po | p <- Board.pclRa Piece.B, po <- pcl ! p]
        k2p1 = sum [k2Va wk1 bk1 $ k2PcA ! p + bonaPos Piece.W po | p <- Board.pclRa Piece.W, po <- pcl ! p]
        v = k2h0 - k2h1 + k2p0 - k2p1
        h0 = [k1HsA ! p + hs ! p | p <- Board.bothHsRa]
        h1 = [k1HsA ! p + hs ! Piece.pcOppCo p | p <- Board.bothHsRa]
        p0 = [k1PcA ! p + bonaPos Piece.B po | p <- Piece.pcRa, po <- pcl ! p]
        p1 = [k1PcA ! Piece.pcOppCo p + bonaPos Piece.W po | p <- Piece.pcRa, po <- pcl ! p]
        lB = sortBy (flip compare) $ h0 ++ p0
        lW = sortBy (flip compare) $ h1 ++ p1
        f [] _ = 0
        f bs @ (b : bb) ws @ (w : ww) = sum (map (k1Va bk0 b) bs) - sum (map (k1Va wk1 w) ws) + f bb ww
    in
        co == Piece.B |-> negate $ (v + f lB lW) `quot` 2

let ...でいろんな変数を作りながら計算をしていって最後にそれらを使ってinの中で(v + f lB lW)として計算を行っている。 Piece.B |-> negate $の部分は敵の場合はマイナスにするために符号を反転させているだけだ。quotはintをintで割って小数点以下を切り落としてintとして割り算の答えを返す。ここも定数なので無視しよう。するとletの中身を解読していけば良さそうだ。

posKを使っている1行目

let
    [bk0, wk0, bk1, wk1] = map (posK pcl) [(Piece.B, Piece.B), (Piece.W, Piece.B), (Piece.B, Piece.W), (Piece.W, Piece.W)]

> [76,4,4,76]

ここで初期局面を評価してみると、こうなる。 つまり、自玉は自分から見ると76の位置(9*8 + 4 なので5九)にあるし、敵玉は自分から見ると4,つまり5一にある。同じように自玉は敵から見ると一行目にあるように見えるし、敵玉は敵から見ると一番手前にあるように見える。 [bk0, wk0, bk1, wk1]はそういった位置を保持している4つの変数だ。この4つはKKP/KPPをするのに必要だ。この見え方は敵から見た時と自分から見た時とを混ぜてもしょうがないので、bk0とwk0、bk1とwk1はそれぞれの組み合わせで使われる。bk0とwk1は意味が無い(同じマスにあることになってしまう)。

KKPの処理

手駒の処理

        k2h0 = sum [k2Va bk0 wk0 $ k2HsA ! p + hs ! p | p <- Board.hsRa Piece.B]
        k2h1 = sum [k2Va wk1 bk1 $ k2HsA ! p + hs ! p | p <- Board.hsRa Piece.W]

この部分は手駒に対してKKP(k2Va関数)を適用している。Board.hsRaは手駒として使える駒のすべてをリストアップする。つまり王以外だ。これは見ての通りリストの内包表記を使って、forEachしている。mapを使って書き換えるほうが良い。

bk0wk0が自分から見た玉の位置であることに注意すると、k2h0は自分から見た自分の手駒のすべての評価を与える。fv.binをルックアップするために、インデックスの位置をk2HsA ! p + hs ! pで得る。コマごとの先頭位置に駒の数分だけずらしたところの値を読み込めるようにしてある。

盤上の駒の処理

次のコードだ。

        k2p0 = sum [k2Va bk0 wk0 $ k2PcA ! p + bonaPos Piece.B po | p <- Board.pclRa Piece.B, po <- pcl ! p]
        k2p1 = sum [k2Va wk1 bk1 $ k2PcA ! p + bonaPos Piece.W po | p <- Board.pclRa Piece.W, po <- pcl ! p]

ここは上の同じだが、盤上の駒の評価を行っている。k2PcAは盤上のコマの種類ごとのインデックスの開始位置、それに盤上の駒の実際の位置分だけシフトしてルックアップしている。

最後にまとめる

v = k2h0 - k2h1 + k2p0 - k2p1

このようにして自分の駒はプラス、相手の駒はマイナスとして足してKKPの値を出す。

KPPの処理

駒の評価前にボナンザのfv.binインデックスを得る

続いて次の行へ行くと、

        h0 = [k1HsA ! p + hs ! p | p <- Board.bothHsRa]
        h1 = [k1HsA ! p + hs ! Piece.pcOppCo p | p <- Board.bothHsRa]
        p0 = [k1PcA ! p + bonaPos Piece.B po | p <- Piece.pcRa, po <- pcl ! p]
        p1 = [k1PcA ! Piece.pcOppCo p + bonaPos Piece.W po | p <- Piece.pcRa, po <- pcl ! p]

この部分に駒をKPPインデックスに変換する部分が入っている。k1HsAは手駒用、k1PcAは盤上の駒用だ。ルックアップの仕方はKKPの時と同じ。それぞれh0,h1,p0,p1はリストになっている。そしてそれらのリストを結合しソートする。

        lB = sortBy (flip compare) $ h0 ++ p0
        lW = sortBy (flip compare) $ h1 ++ p1

これでソートされた駒のインデックスリストが手に入った。

KKPの実際の評価を再帰で行う

先ほど得たインデックスのリストを使って実際に評価を行う部分が次の部分だ。

        f [] _ = 0
        f bs@(b : bb) ws@(w : ww) = sum (map (k1Va bk0 b) bs) - sum (map (k1Va wk1 w) ws) + f bb ww

この関数に実際にはf lB lSとしてインデックスのリストを与えて評価する。 見て分かる通り、lBの先頭の要素を取り出して、自玉とその駒をk1Vaに適用してポジションを与えると評価を生み出す関数(k1Va bk0 b)を作っておいて、その関数をすべての駒について考える。

bs@(b : bb)

はアズ・パターン(as pattern)といってリストの先頭要素bと残り要素のリストbbに分解するためにパターンマッチしながらbbbを分解する前のリストとして扱うためにbsという名前にしてとって置けるという機能だ。すごいHaskell楽しく学ぼう!の40ページに説明がある。英語版はオンラインでフリーで読むこともできる: Syntax in Functions - Learn You a Haskell for Great Good!

最後にまとめ上げて評価する

さて、ここまでくれば、

co == Piece.B |-> negate $ (v + f lB lW) `quot` 2

として評価できることがわかると思う。

今回のまとめ

今回でKKP/KPPで評価する部分が説明できたと思う。今のところ駒割りとfv.binをつかった評価の足し算で盤面を評価している。

コンピュータ将棋の肝は盤面評価、探索、そして指し手生成だ。

次はMoveGeneratorモジュールについて見てみながら指して生成について考えてみる。

今回上げたすごいHaskell楽しく学ぼう!は非常に勉強になる割にすごい突っ込んだ機能まで解説しているすごい本なので、ぜひ手元においておきたい。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!