30 June 2018

    3三将棋アプリのソース公開しました

     3三将棋アプリもそろそろ安定してきたと思うのでソースをgithubに公開しました。Bonanzaを始めとする優秀な将棋ソフトをカスタマイズしようとは思わないけど、CoffeeScript(JavaScript)で将棋ソフトが作れるならやってみようと思う人はいるかも知れないと思ってます。また、プログラミングには興味ないけど9マス将棋の正解を知りたいと思う人は結構いるかもしれないと思ったので記事を書いてみました。ただ、詰みがある場合は別ですが、ここで示す方法で得られた解答が必ず最善手だとは言い切れないことには留意してください1
     ちなみに最近9マス将棋オンラインというアプリで遊んでいるのですが、単純な配置でも未だに最善手が何か悩まされることがあります(特に入玉形の場合が難しい)。そういう時スクショを取ってこの記事の方法で何が最善手だったか検討したりしています:sweat_smile:


     追記:3三将棋アプリはVersion1.0.5.0からCSA形式(*.csa)の棋譜の入出力に対応しましたので、CUI(コンソール画面)でコマンドを入力しなくてもアプリを使って自由に初期配置を編集出来ます。やり方については3三将棋アプリの記事を参照してください。


    テスト環境

     9マス将棋の解答を得るために必要なものはgithubリポジトリ内のファイルとCoffeeScriptのインストールだけです。編集する必要があるのはCUIテスト用スクリプトファイル(game.coffee)だけです。CoffeeScriptのインストールに関しては環境に依りますので省略します。

    git clone https://github.com/happyclam/shogi33simple.git
    cd shogi33simple
    coffee game.coffee
    

    将棋盤面(初期配置)の編集

     将棋盤に駒を配置するにはBoardクラスのpiecesメンバに駒をpushしていくのですが、コピペして書き換えれば簡単だと思います。
     例えば先手の玉を3三に配置したい場合はnew Piece.Ou(Const.FIRST, Const.Status.OMOTE, [3,3])としてPieceクラスのインスタンスを生成してBoardオブジェクトのpiecesメンバにpushします。

    初期配置 例1

     上記の初期配置をセットするコードは以下のようになります。

    b = new Board()
    b.pieces = []
    b.pieces.push(new Piece.Ou(Const.FIRST, Const.Status.OMOTE, [3,2]))
    b.pieces.push(new Piece.Ou(Const.SECOND, Const.Status.OMOTE, [1,1]))
    b.pieces.push(new Piece.Ky(Const.FIRST, Const.Status.MOTIGOMA))
    b.pieces.push(new Piece.Ki(Const.SECOND, Const.Status.MOTIGOMA))
    
    駒の種類  クラス名  
    玉(王) Ou
    飛  Hi
    角  Ka
    金  Ki
    銀  Gi
    桂  Ke
    香  Ky
    歩  Fu

     先手・後手、駒の状態(不成、成、持ち駒)の区別は以下の定数を使用します。

    定数  意味  
    Const.FIRST 先手
    Const.SECOND 後手
    Const.Status.OMOTE 駒の状態、表
    Const.Status.URA 駒の状態、成り
    Const.Status.MOTIGOMA 駒の状態、持ち駒

    読む深さの指定

     Playerクラスのdepthプロパティに読む深さを指定します。0になるまで局面を先読みしますので6を指定すると7手読みになります。

    first = new Player(Const.FIRST, false)
    second = new Player(Const.SECOND, false)
    first.depth = 6
    second.depth = 6
    

     5手詰めの詰将棋を解くには7手読みする必要がある2のでdepth = 6を指定しないと解けないかというとそういうわけでもなくて、それ以下でも詰み手順を正確に辿っていくこともあります。上記の初期配置の例だと、詰み手数で言えば7手詰め(1三香、1二金、同香、同玉、2二金、1三玉、2三金)ですが、depth=3(4手読み)の設定でも正確に詰み手順を辿ることができます。読み切れていなくても最善手を指せるかどうかは評価関数の巧拙にかかっています3
     ちなみに3三将棋アプリの評価関数は(先手の駒の重みの合計 ー 後手の駒の重みの合計)という非常に単純なものですが、9マス将棋ならこの程度の評価関数で十分だと言えるでしょう。

    将棋盤面(初期配置)の表示

     以下の表のように先手が大文字、後手が小文字のアルファベットで将棋の駒を表現します。

    駒の種類 \ 表記  先手(後手)   成り駒  先手(後手)
    玉(王) O(o)    
    飛  H(h) R(r)
    角  M(m) U(u)
    金  X(x)    
    銀  G(g) 成銀 N(n)
    桂  K(k) 成桂 E(e)
    香  Y(y) 成香 S(s)
    歩  F(f) と金 T(t)

    初期配置 例2

     上記の配置はgithubに置いてあるgame.coffeeの初期配置です。githubからソースを取得した後、コンソール画面でcoffee game.coffeeと打てば以下のように対局が進行するはずです。

    coffee game.coffee
    x
     3 2 1
    | | |o|1
    | |f| |2
    |O| | |3
    H
    x
     3 2 1
    |H| |o|1
    | |f| |2
    |O| | |3
    
    x
     3 2 1
    |H| | |1
    | |f|o|2
    |O| | |3
    
    x
     3 2 1
    |H| | |1
    |O|f|o|2
    | | | |3
    
    
     3 2 1
    |H| | |1
    |O|f|o|2
    |x| | |3
    
    
     3 2 1
    |H| | |1
    | |f|o|2
    |O| | |3
    X
    
     3 2 1
    |H| | |1
    | | |o|2
    |O|t| |3
    X
    
     3 2 1
    |H| | |1
    |O| |o|2
    | |t| |3
    X
    
     3 2 1
    |H| | |1
    |O|t|o|2
    | | | |3
    X
    Second Win
    

     これじゃぁ分かりにくいという方も多いと思いますがすぐ慣れます:sweat_smile:。それか、ある程度結論が得られたら初期配置のコードをgameGui.coffeeに移してトランスパイル(webpackとコマンドを打つだけです)してブラウザで確認するのもいいかもしれません。但し、ブラウザであまり深読みさせると応答しなくなる可能性があります。

    詰みが見つからなければ、最善手は当てにならない

     局面の先読みメソッド(Player.think)の戻り値は[駒オブジェクト, 座標(筋、段), 評価値, 成(不成), 次善手情報]となっているのでtemp = first.think(b, second, i, Const.MAX_VALUE)と呼び出した場合temp[2]に評価値が入っています。temp[2]に最大値(50000)か最小値(-50000)が入っていれば勝ち(あるいは負け)を読み切った(詰みを発見した)ということです。前述の単純な静的評価関数によって指し手を選んだだけなのか、詰みを読み切った上でその手を選んだのかはここで判断出来ます。
     例えば上記の例題の場合、「3一飛、1二玉、3二玉、3三金、同玉、2三歩成、3二玉、2二と」と進行していますが、depth = 7で実行すると3一飛と打たれた後の後手番での先読みメソッドの戻り値を見ると、1二玉が最善だと返してきますが、評価値は-18(後手やや有利)になっています。1二玉と指せばやや有利になりますよと言っているだけで、AIは後手の勝ちだとはわかっていません。しかし、depth = 8にすると1二玉が最善手で評価値も-50000(後手勝ち)と返してきます。初手3一飛と打たれた時に後手の立場で考えて自分の指し手から数えると「1二玉、3二玉、3三金、同玉、2三歩成、3二玉、2二と」までの7手詰めですので、9手先まで読まないと詰みが分からないはず(depth = 8は9手読み)ですので辻褄が合います。このように詰みを発見した上での最善手と、単なる評価関数による最善手は意味合いが全然違うので注意が必要です。詰みがない場合の最善手というのは読みの深さを変えたら変わる可能性があるのに対して、詰み発見後の最善手は絶対不変4の正解手です。この辺の事情は有名な将棋ソフトでも同じことで、読む深さを決めてその手数で詰みが見つからなかった場合は、そのソフトの評価関数を使った最善手というだけの話で客観的に絶対正しい最善手というわけではありません。それでも近年は人間の判断より正確なようですが。
     また、githubに置いてあるソースは候補手を絞るという作業をしていません(αβ法を使った全件探索)ので、depth = 8をセットしてAIの評価値が最大値(50000)または最小値(−50000)が返ってこない場合は7手以内の詰みは存在しないという言い方も出来ます。でも、全件探索ということは読む深さを深くする(depthの値を大きくする)と読む局面の数は指数関数的に増加しますので、いくらハイスペックなPCを使っても十数手しか読めないと思います。どうしても長手数の詰みも確認したいという方は、このソースコードを他のコンパイル言語に移植したりするより、まず将棋盤をビットパターンで表現する手法を取っている他のやり方を探る方がいいと思います。自分はそこまでやろうとは思ってませんけど、このアプリをReactNativeに移植したらどれぐらい速度アップ出来るのか興味を持ってます。


    1. 有名な将棋ソフトを9マス将棋に対応させるのはそれなりに大変だと思いますが、どうしても9マス将棋の正解を得たいという人は、あの「どうぶつしょうぎ」を完全解析した人のソースコードを改変する方法があるようです。でも、それもまた簡単ではないと思いますが…。 

    2. 前回の記事にも書きましたが玉を取るところまで読まないといけないので、1手詰めの問題を解くには3手読み、3手詰めの問題を解くには5手読みが必要となります。 

    3. これは9×9の本将棋のプログラムでも同じことですが、完全読み切りが出来るのであれば静的評価関数は先手勝ち(+1)か後手勝ち(−1)かそれ以外(0)の3値を返すだけの単純なものでいいのですが、完全読み切りが出来ないので世のプログラマが苦心して評価関数の出来を競っているわけです。 

    4. 詰み手順が複数ある可能性はあります。 



    blog comments powered by Disqus