近年のコンピュータ将棋の急速な伸びの理由は?

表題の件を当事者視点で。

理由をたったひとつ挙げるとしたら、2016年時点での最新の回答は「誰でも機械学習が出来るようになった」ではないかと思います。

従来、将棋ソフトの機械学習というのはBonanzaメソッド(通称ボナメソ)一択でした。激指はオンライン学習風の何かをやっていたのですけど、Bonanzaの3駒関係ほどパラメーターの数が多いと(数百万パラメーター)、オンライン学習ではうまくいかないと信じられていたので、誰もやっていませんでした。

ボナメソについて書かれた保木さんの論文自体、当時の将棋ソフト開発者には難解で(見慣れない数式で)、何が書いてあるのかすら多くの開発者には理解できませんでした。

また、ボナメソが発表された頃は、機械学習の書籍と言うとビショップの『パターン認識と機械学習』(通称PRML本)一択でした。

パターン認識と機械学習 上  パターン認識と機械学習 下 (ベイズ理論による統計的予測)

この本がまた難しい。大変な良書なのですが、統計学の得意な大学院生向けと言った内容です。

将棋ソフトを作るのにガウス分布?ヤコビ行列?(を勉強しないといけないの?)
嘘でしょ?

と(コンピューター将棋開発者の)誰もが思ったに違いありません。

その流れが変わりだしたのは、近年の機械学習のブームです。オンライン機械学習についてのわかりやすい書籍がいくつも発売されました。

オンライン機械学習 (機械学習プロフェッショナルシリーズ)

いや、本すら買わずともWeb上に機械学習に関する記事が溢れかえるようになりました。

これにより、高校生レベルの数学力(出来れば偏微分ぐらいは理解できたほうが良いですが)であっても、SGD(確率的勾配降下法)を使ったプログラムを書くことが出来るようになりました。

というか、SGDの式自体は単純で、wを評価関数のパラメーター(ベクトル)、ηを学習率(適当な定数)、Jを目的関数(これを最小化する)として、次のようにwを更新していくだけです。

$$ w = w – η\frac{\partial J}{\partial w}$$

∂J/∂wは、wを少し動かしたときにJがどれくらい増えるかです。それがわかっていれば、偏微分を知らない人でも上の式は「Jが小さくなっていくように元のwから引き算して行くんでしょ?」ぐらいのことはわかります。そうです。それだけです。

おまけにPonanzaのようにある程度の深さで探索した局面とその評価値を教師データとして使い、浅い探索での評価値をそれに近づけるようにSGDを適用するだけなら、何も難しいことは必要ありません。

$$ J = \frac{1}{2m} \sum (深い探索の値 – 浅い探索の値)^{2}$$

深い探索での評価値と浅い探索での評価値の差(誤差)の二乗和が最小になるようにするだけです。(mは標本数とします。分母の2は、これを微分したときに出てくる2と打ち消すために置いてあるだけです。)

そして、80億局面もあるなら、AWAKEやNDFのような次元下げや、ボナメソのような複雑な式は不要なのです。L1正則化等も必要ありませんし、棋譜の指し手以外を減点するようなテクニックも必要ありません。ただの―本当に純粋なSGDです。機械学習の教科書の1ページ目(?)に載っている、まさにそれです。

※ ボナメソが将棋ソフトにおいてブレイクスルーであったかどうかはここでは議論していません。また、私はBonanzaの功績を否定しているわけでもありません。現在ではボナメソも激指の論文の手法も全く使っていないと言っているだけです。

例えば、AWAKEの次元下げは、とても実装が難しかったのを私は覚えています。私はその次元下げだけで4000行ぐらいのコードを書きましたし、また、とても学習が遅かったのを覚えています。新しい特徴因子を追加するごとに、この悪夢のような次元下げのコードを追加しないといけないのかと思うと、怖くて私はKKP/KPPの三駒関係に新しい特徴因子を追加できませんでした。

それが、ついに我々は悪夢のような次元下げから解放されたのです!

我々は、次元下げをしなくともApery(WCSC26)の評価関数バイナリと同じぐらい(それ以上)の強さのものが作れるようになったのです。

これを機械学習の勝利と言わずに何と言うのでしょうか。

※ これまた、私は、NDF・AWAKEの功績を否定しているわけではありません。現在では、NDFやAWAKEの手法(次元下げに関して)は全く使っていないと言っているだけです。

機械学習で何らかの問題を解くとき、普通は、
1. 特徴量設計(Feature engineering)に始まり、
2. その特徴量を使った目的関数を設計し、
3. その目的関数を最小化する手法を選択・実装
することになります。

そして、機械学習の教科書は2.について代表的な方法と、3.についてのいくつかの手法を教えてくれます。つまり、1.をやり、2.をうまく設計すれば、あとは機械学習のライブラリなり何なりを使えば答えが求まる、そんなイメージです。1.の部分には結構その分野の専門的な知識・工夫が要求されるのが普通です。

ところが、将棋ソフトでは、1.は、3駒関係+手番がかなり有力だとすでにわかっており、2.は今回のケースでは浅い探索の評価値が深い探索の評価値に近づくようにすると良いということまで周知の事実となっており(上で書いたJがそれです)、3.はSGDでも大丈夫とまでわかっています。

これだけわかっていれば、1.を変更しない限り、機械学習に関しては何も考える必要がありません。

また、表題の件について、80億局面を生成するだけの計算資源を個人開発者が手に入れられるようになってきたという点を挙げる人がいるかと思いますが、やねうら王で生成した棋譜を私が配布しはじめたのでこのへんの状況は変わりつつあります。

80億局面は深い探索を行なうので、生成にはとても時間がかかります。40コア(80HT)のPCで探索深さ6で1週間近くかかります。ところが学習は一瞬です。なぜなら、学習時には浅い探索しかしないからです。

20コアでやったときに80億局面1回のiterationが6時間程度した。(40コア、フルに使うとプロセッサを2つ使うことになって効率が悪いようで、それについては実験していません。) 何回のiterationで収束するのかはわかりませんけども、まあ1回でもそこそこの値には到達します。

つまり、4コアぐらいのPCでやっても1日程度であるということです。80億局面から学習させるのには、普通の家庭用PCでも1日。

この速度で出来るなら、家庭用PCしかなくとも、たくさんの実験が出来るはずです。
私が2年前の電王トーナメント前にAWSで何十万円も使ったのが嘘のようです。

これにより、コンピューター将棋ソフトは今年もまた全体的に昨年と比べるとR200ぐらい上がるのではないかと私は予想しています。

近年のコンピュータ将棋の急速な伸びの理由は?」への13件のフィードバック

  1. うーん…今年から来年にかけての説明としては非常に理解しやすいのですが、80億局面作るのに(本当はそんなに必要ないのかも知れませんが…)かかる時間とコストを考えると、やはり配布されたものを使うとかしないと…無理ぽですw

    • depth 3でよければ一瞬で作れます。そしてdepth 3で作ったものでも、そこから本文に書いた方法で学習すればR100ぐらい上がります。Let’s try!!

  2. ビッグデータを処理してサジェストするだけの簡単なお仕事っていうのでしょうけど、処理するためのビッグデータが不足していたのですね。
    ところで、チープラーニングは破棄してしまったのでしょうか。今、処理能力が余るくらいPCがあるわけですから、やろうと思えばできる規模なのでしょうか??それとも今試行中ですか?
    ちょっと名前が好きだったので気になってます。

    • > チープラーニングは破棄してしまったのでしょうか。

      機会があればやりたいと思ってますが、いまは40コアPCが大挙して攻めてくるので、それに対抗する武器を製作せねば…。

  3. 本記事は今年のコンピュータ将棋のトレンドみたいな感じがするんですが、ここ数年の伸びの理由とかも含まれているんですか?

    • Ponanzaチームだけ本記事の内容を1,2年早くやってますね。それ以外の上位チームは、ほとんどがNDF・AWAKEの次元下げをやって(いま振り返って考えるに)無駄足でした…。

  4. 機械学習もあまり工夫がいらない。探索もストックフィッシュのまんまが一番強い(間違ってる?)となるとどのへんで差が出てくるんですか?

    • ・機械学習の手法の違いで評価関数パラメーターが最終的に収束する値は微妙に違ってくるので、それによる棋力の差はあります。
      ・生成する棋譜、探索深さ6ではなく8とか10にしたほうがよさげですが、そのためにはいまの何十倍かの計算資源が必要になります。
      ・評価関数にどんな特徴因子を付け足すか(あるいは減らすか)で大きく変わってきます。
      ・探索自体まだまだStockfishから改良の余地はあります。
      ・探索パラメーターの調整には長い持ち時間での対局が不可欠で、そのためには大きな計算資源が必要になります。
      ・定跡の質による勝率の差
      ・データ構造の工夫やAVX2を用いた高速化による差
      ・持ち時間の使い方の調整に何らかの機械学習が使えます。
      etc..

      工夫すべきところは際限なくあります。

  5. > 1年で200ほど伸びるようになった理由

    20 探索部
    10 ハードウェアの高速化
    20 LazySMP
    10 定石
    130 評価関数
    10 火星からの謎の電波

    内訳はこんな感じ?

      • すんません。しったかぶりして適当な数字書いてました。

        >> L1正則化等も必要ありませんし

        正則化は過学習を防ぐシステムだと思ったんですが、すごすぎます。「ブレーキとハンドルの無い乗用車」くらいのインパクトです。

        • まあ、出現率の低い特徴因子があると、反復してそれを学習させようとしたときにおかしな値になってしまうでしょうけど、まあ、80億局面もあればそういうのはほぼ存在しないのかも…。

コメントを残す

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