• 詰将棋の実装

    2017-12-31 02:57
    詰将棋の壁は一般的には、3手詰めと5手詰めの間にあるらしいです。

    詰将棋のコツを検索すると色々アドバイスが書いてあります。

    参考

    参考2

    詰将棋のコツは人それぞれらしいです。
    小さい頃から得意な人は難なく解けたりするそうです。

    ということで、詰将棋を解く処理の設計をします。

    詰将棋の設計


    全コマ検索します。
    まず、5手詰で検討。
    詰将棋を解く処理の単純化を検討。

    通常、人が詰将棋を解く時は、ボンヤリ詰将棋を眺めながら詰みの形が閃くの待ったり(人それぞれですが。)割りと混沌とした処理ではないかと思います。

    今回の設計では、1手目以降、王手する駒の順番を固定にします。
    成り駒も当然含まれるのですが、下記はイメージですね。

    <テーブルイメージ>
    koma={飛車、角、金、銀、桂、香、歩}

    上記のテーブルの順番に考慮します。

    実戦形式ではない通常の詰将棋では、1手目で大駒を捨てる事が多いのでこの順番にしています。

    テーブルの駒の順番に王手可能な箇所の和を数えます。

    例:1手目 飛車(4),金(5),桂馬(1)

    以下イメージ…

    飛車1で王手し、相手陣側を動かします。
    → 相手陣の移動可能な箇所を数えます。
    例:2パターン移動可能
    2パターンあるとするとどちらか一方が詰まなければ、検討を打ち切り可能です。
    1パターン目:
    テーブルの駒の順番に王手可能な箇所の和を数えます。(再帰的な処理になります。)

    例:3手目 飛車(2),角(3),金(1)

    人間の感性(第一感)では金が一番詰みが有りそうとか勘が働くんですが、
    テーブルの順番通り考慮します。

    飛車1-1で王手し、相手陣側を動かします。
    → 相手陣の移動可能な箇所を数えます。
    例:2パターン移動可能
    2パターンあるとしてどちらか一方が詰まなければ、検討を打ち切り可能です。
    1-1パターン目:
    5手目も同じように
    テーブルの駒の順番に王手可能な箇所の和を数えます。(再帰的な処理になります。)

    例:5手目 金(1)、歩(1)

    5手目で詰みが無い状況はハッキリしているので瞬時に判断可能です。
    5手目も両方詰みがないかどうかを見ます。

    以上を全パターンループします。

    テーブルの順番に考慮するメリットは、
    ・戻りが無い。(テーブルの順番に検討して最後(テーブル上では「歩」)まで行ったら終了)
    ・考慮漏れがない。

    5手詰めであれば、100パターン以下ではないかと思いますが実際はどうでしょうか。。

    ということで下記の詰め将棋を上記設計の処理で検討します。

    将棋タウン内、詰将棋専門学校さんの5手詰問題集の2番



    <テーブルイメージ>
    koma={飛車、角、と}

    手が進むと飛車角が成ったり駒が増えたりしますが、そこは更新していくイメージです。

    1手目
    飛車(2),角(1),と(1)
    2二飛車、1三飛車の2パターンの内、2二飛車から検討します。
    (1手目2二飛車から始まるような詰将棋はまぁ無い気がしますが、「戻りが無い」というテーブル順のメリットのために検討します。)

    2手目は1三玉の一択です。

    3手目
    第一感では3五角打ちですが、テーブル順に飛車での王手から検討します。
    2三竜、1二竜の2パターン。

    2三竜の検討。
    4手目同玉で5手詰み無し。

    1二竜の検討。
    同香か同玉の2パターン。(どちらかが詰まなければ、検討打ち切り可能。)
    同香は2二角打ちで詰みます。
    同玉は、飛車無しで問題の盤面に戻るだけですし5手詰みは無いです。

    拠って1手目2二飛車打ちのパターンは消化しました。

    次、

    1手目、1三飛車打ちの場合。。
    以下省略気味に
    同金だったら2一角打ちで詰みますが、同玉の場合は、3一角打ち→合駒or1二玉→2二馬で詰みます。

    ということで
    一応、
    1三飛車 → 同玉 → 3一角打ち → 2二金打ち(何をやっても) → 2二角成
    で詰みそうです。

    全パターン消化前に詰みがあると残りも一応確認したくなりますが、
    時間がある場合は、検討してみても良いのではないでしょうか。

    以上を自分に実装してみるのも有益ではないかと思います。

    for文等が詰みがあるパターンまで再帰的にループしているようなイメージですね。

    エンジニアであれば、脳内デバッグの精度上昇が見込めたりしないでしょうか。
    プロ棋士の様に脳内に盤面はなくてもソースコードのロジックは脳内でイメージ出来る人もいると思うので、このようなロジックを自分の脳内に実装するとまでは言いませんが、脳内デバッグする事でメリットがありそうな気がします。

    詰将棋得意な子供の頭がどうなっているのか気になりますね。
    上記のようなロジックを誰に教わるでもなく脳内に築き上げてしまったのか。
    全く別のロジックが高速に動いているのか。
    閃きなのか。

    上記のようなロジックでも詰将棋を大量に消化して行く内にひと目で解けるようになるんでしょうね。機械学習的な感じで。分かりませんが。

    以上。

  • 広告
  • Backbone開発環境

    2017-10-11 23:47
    Backbone generatorをWin環境にインストールしました。
    (Yeomanをインストール)
    <プロジェクト作成>
    コマンドラインにて
    ①ソースを置くディレクトリを作成し移動します。
    ②backboneを起動します。
    $ yo backbone
    ③そのままEnter押下します。(RequireJS、CoffeeScriptは使用しないため)
    ④テストはBDを選択。

    <サーバ起動>
    ①サーバ起動します
    $ grunt serve

    <コンポーネント生成>
    $ yo backbone:model model_hoge
    $ yo backbone:collection collection_hoge
    $ yo backbone:view view_hoge

    上記コマンドで依存関係の指摘で下記コマンド実行
    $ npm install generator-backbone-mocha
    $ npm install yo

  • 評価関数について

    2017-09-20 01:07

    将棋ソフトの評価関数

    評価関数の参考リンク

    Aperyの評価関数

    <学習>
    f(x) = 1 / ( 1 + exp( -7/32 * max( -32, min( 32, x ) ) ) ))

    d(x) = 7/32 * f(x) * ( 1 - f(x) )
    <usi>
    勝率を求める
    f(x) = 1 / ( 1 + exp( -x / 600 ))

    d(x) = 1 / 600 * f(x) * ( 1 - f(x) )

    三角配列に入れる値 = 2 * d(浅いx) * (f(浅いx) -f(深いx) )
    Loss = ( f(浅いx) -f(深いx) )^2

    Elmoの評価関数

    <学習>
    f(x) = 1 / ( 1 + exp( -7/32 * max( -32, min( 32, x ) ) ) ))

    d(x) = 7/32 * f(x) * ( 1 - f(x) )
    <usi>
    勝率を求める
    f(x) = 1 / ( 1 + exp( -x / 600 ))

    d(x) = 1 / 600 * f(x) * ( 1 - f(x) ) 未使用

    勝敗 = 結果 == 勝 ? 1 : 0

    三角配列に入れる値 = ( f(浅いx) - 勝敗 ) + 0.5 * ( f(浅いx) - f(深いx) )
    Loss 未使用