技巧の強さの秘密

電王トーナメント1日目ですが、会場の受付までにあと1時間ほどあるので簡単に記事を書きます。

技巧の強さの秘密は利きの計算にあります。利きがSSEを用いて高速に計算できることを発見したのが一つのブレイクスルーだと思います。まあ、私を含め、一部の開発者の間では知られていたことではありますが。

(読者「なんや?今度は、それ、俺も知ってたわー。か?地獄のミサワか!」)

つまり、KE(玉と盤上81升の利きの数の組み合わせ)であれば、利きの数に比例した評価値にしていいのであれば、利きをbyte board(bitboardのbyte版)で持っておき、SSE命令のPMADDUBSWが使えるということですね。

その他、技巧について詳しいことは今日の予選の時に聞いてみます。

さて、やねうら王も新しい評価関数は利きに関するN駒関係となっています。そもそもN駒関係ってなんだ?って話ですよね。N駒関係を実装したソフト(研究?)はすでにあります。

名人を超える将棋序盤アルゴリズムの開発
https://kaken.nii.ac.jp/d/p/24500192/2013/11/ja.ja.html

本研究ではコンピュータ将棋の序盤をプロレベルにすることを目指して、プロ並みの良い「形」の評価をさせることを目指す。「形」を理解するプロ並みの序盤を実現するには多くの駒位置からなる評価が必要になるが、評価要素が増えるとメモリと時間が指数的に増大するため、現在コンピュータ将棋でよく行われているように駒組み合わせをすべて評価する方法(all型と呼ぶ)では実現し難い。この問題を解決するには、無駄な組み合わせを排除し重要な組み合わせのみを評価する方法(freq型と呼ぶ)が必要である。

上の研究のアプローチと実装方法は(私に言わせれば)間違っていて、計算コスト(主に特徴因子の抽出)が大きすぎてBonanza程度の棋力にすらならないと思います。

2駒関係、3駒関係、4駒関係…を愚直に駒の位置の組み合わせとしてやってしまうと、(全数やるなら)3駒が限界、その3駒もPPPではなくKPPが限界というのがコンピューター将棋の現状です。部分的にやるということは、部分的に4駒、5駒、…のような関係があったとしても、1局面のために評価している因子の数では3駒関係に到底及ばないのでこれでは強くなる道理がないのです。

私は上の研究が学術的に意味がないだとか言いたいわけではないのです。将棋ソフト、特に電王トーナメントのような大会は勝負の世界です。勝ちと負けしかありませんので、勝てるか/勝てないかの視点で語らざるを得ないのです。上位のソフトに勝てないようなアプローチに対して「間違っている」だとか「非現実的である」と私は言うことがありますが、しかしそこに学術的な価値がないわけではないです。

話を戻します。

任意N駒というのは組み合わせの数が大きくなりすぎて、そして、それを与えられた局面から抽出するコストが大きすぎて、こういうアプローチは非現実的なのです。

つまり、任意N駒をしようとした時に、駒に複数の種類があるから、組み合わせの数が膨大になるのがいけないわけです。この意味で4駒関係なんてのも筋の悪いアプローチなわけです。

それに対して利きであれば、基本的には1種類しかありません。(ある升に)利いているか、いないか。あるいは、(ある升への)自駒の利きの数(最大10)、後手の利きの数(最大10)ですね。これならば、簡単に集計できます。しかもSSE命令を使えばKEは16升ずつ処理できるので非常に少ない計算量で済みます。

そもそも実はKPPという3駒関係自体がアプローチの仕方がややおかしく、飛び利きを考慮していなくて、色々目立った欠陥のある、おかしいものだったのです。利きを近似しようとしたのがKPE次元下げであり、そして、その飛び利きを部分的にボーナスを与えようとしたのが、NDF(2015)ですが、NDF(2015)はおそらくそれほど強くはなっていなかったと思います。それというのも、この方法では正しく飛び駒の利きの評価が出来ていないからです。

3駒(KPP)に他にも利きっぽい特徴因子を付け加えたりして評価関数の精度を挙げていく方法は色々考えられます。計算コストに見合うかどうかはよくわかりません。

また、今回のやねうら王の新しいほうの評価関数は、この利きの組み合わせ、そして次元下げを色々工夫していたのですが、その部分のコードを書くのが結構難しく、思いの外、時間がかかってしまい、大会には間に合いませんでした。残念です。来年は開発に4週間ぐらい確保して、技巧・Ponanzaのレベルのソフトにしたいと思います。

技巧の強さの秘密」への7件のフィードバック

  1. 今日の予定

    朝食を平岡さんと食べること。
    技巧作者へのインタビュー。
    やねうら王miniの開発に向けて、できるだけ早く帰ること。
    今年の雪辱は来年の開発の糧とすることを誓うこと。
    ・・・・
    そうそう、電王トナメの予選に参加すること。

  2. 超やねうら王の部分的に深く読むというアプローチ自体は、昔の将棋ソフトのリバイバルですよね。
    ただ、コンピュータの処理速度が上がってできることが増えた分なんていうか、知見が増えて粒度が下がったように思います。
    汎用型がいいのか専門型がいいのかっていうのはいつも循環していてメタの応酬なわけですよね。
    汎用型を食い殺す超やねうら王が見たかったです。
    まだ終わってないので頑張ってください。

  3. 電王トーナメントお疲れ様でした。

    さて、利き評価ですが、持ち駒が評価しにくいのでは?
    打てる全ての升の利き先に潜在的利きになる?

    また、2値でなく複数利きを加算すると3利きと4利きで違う評価にすることとなり
    複数利きの有利さが分散するような。
    すると3利きは3以上利きの意味で4利きも3利きで含めて評価?

    素人考えでは、利きの評価は相手方との利きとの相対評価でよく、
    1手で動く利き値は最大2なので、それを越える相対利きは過剰とすれば、プラスマイナス2または3まででそれ以上は両端に含めていいのでは?

    • > 3利きと4利きで違う評価にすることとなり複数利きの有利さが分散するような。

      4利き = 3利き + 3利きと4利きとの差
      のように次元下げするので4利きに対してもそこそこ妥当な値がつきます。

      > 素人考えでは、利きの評価は相手方との利きとの相対評価でよく

      全然よくないです。詰将棋問題を少し見ればわかると思います。受け方のほうがすべての升において利きが多かろうと詰むときは詰みます。利きの差は重要ですが、「攻め方の利き1、受け方の利き1」と「攻め方の利き0、受け方の利き0」とでは利きの差はいずれも0ですが、後者のほうがはるかに受け方にとって安全です。

      • 返信ありがとうございます。
        つまんない思い付きにお付き合いいただきすみません。

        なるほど、とられちゃ不味い駒にとっては
        相手の利きの有無は決定的ですね。失礼しました 。

        しかしその意味では相手利きの有無だけが問題ですからこんな感じになるのでは。

        相手の相対1-2利き
        相手利き1以上ある自分相対0-2利き
        相手利き0の自分0-2利き

        まあ下手に人間が良し悪しや意味を判断するより、
        なるべく素直にデータを食わせてコンピュータに考えさせる方がいいんでしょうけど、、、

        さておき、利き評価はSIMDで計算が早くなるだけでなく、もしかして3コマ関係が回り道して求めている部分を直接評価するものだとすると、大きな可能性を感じます。
        が、持ち駒や駒得など3コマ関係の方が評価しやすい部分が残るとすると併用、合議にする方がよさそうに思います。

        あと、決勝第2局では壁形への評価と玉周辺制空権?捕まりにくさ?の評価が足りなかったようですが、
        利き評価でそれらに対策可能なんでしょうか?

        玉の固さについては、馬鹿げてますが、相手の今の持ち駒と無関係に飛車角銀桂歩で自陣に仮想攻撃を加えてみるとか

        • いや仮想攻撃は点数にしようがないですね。

          詰みの有無だけじゃなくて必至や詰めろのかかりやすさ、その相手の必要条件を考慮して、
          相手が必要条件を満たしやすい場合は不利に評価する、、、。
          しかし必至や詰めろが判定できてればそこ
          をマイナス評価で避ければいいだけ?

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です