rewritemath's blog

rewritemath’s blog

これマシュマロ。質問も受け付ける(https://t.co/VfNWTuMqau)

評価関数の表現力と、線形とかDeepLearningとか。後は探索について

WCSC28では、たぬき、CrazyShogi、DL将棋、ねね将棋、YSSzeroなど、三駒関係を捨ててDeepLearningを用いた評価関数を使ったチームが目立った。そもそも三駒関係とDeepLeaering系の評価関数は何が違うのかについて説明しながら、この傾向が何故流行りだしているのかについて、私のメモも兼ねて記事にしていく。

 

ただし、たぬきの論文は私も理解して読めていないので、私は書き手としては力不足であることをはじめに断っておく。

 

三駒関係の仕組みについてはまた後日気が向けば書く予定です。

 

三駒関係はつまり、3つの駒の配置の仕方それぞれに数値が割り振られていて、その数値の合計を評価値に反映させる手法なのである。4駒関係などの亜種もこれと基本的な仕組みは同じ。

 

だから、三駒関係は線形の関数の和で表されることになる。しかし、3駒関係の表現力は、最新のコンピュータ将棋ソフトをこれ以上強くしようとした際には、不足している(あるいはその表現力は限界近くまで来ている)と言えるのではないか。

 

(ちなみに、評価関数の表現力というのは、人間で例えれば自身の形勢についてどの程度正確に判断する事が出来るかという問題である。当然の事ながら、表現力があるほど形勢を正確に判断しやすい。)

 

開発者によってその意見は異なっていた

elmo瀧澤さん「まだ最適化の余地があるだろうと考えているが、方法は分からない」

nozomi大森さん「ほぼ限界まできていて、これ以上は伸びないので『三駒関係は終わった』と思う」

 

ちなみに、表現力問題には計算資源が有限であるという問題も絡んできていて、表現力を高くしすぎると計算資源が足りなくなる。3駒で足りなければ4駒関係にすればいいというのは当然の発想で、大将軍などはその様な実験的な方法に取り組んでいた。しかし、4駒関係は3駒関係と比べて非常に評価関数の収束までに時間が長くかかる。時間が長くかかるという事はつまり、「ある改良を加えた時にその改良で強くなったかどうかを検証する」というサイクルを回すのに時間がかかる様になる。

 

そして、表現力の高い重い評価関数ほど、「評価関数が局面を評価するのにかかる時間」が長くなる。つまり、読める局面数が減るのである。コンピュータ将棋世界では読める局面数が2倍に増える度にレートが150程度上昇するという暗黙の(そしてある程度検証によって正しいという認知が一般化している)法則が存在し、重い評価関数が仮に1局面の評価にかかる時間が倍かかるなら、その表現力の優位性はR150以上必要となってくるのである。

 

ちなみに3駒関係絶頂期のトレンドはelmoの「その局面から対局させた際の終局時の勝率を重く評価して評価関数に適応する」というアイデア、「その局面を深く読んだ場合の将来の評価値を現在の局面の評価値として適応する」というNDFが採用していた方式(通称雑巾絞り)、であり、これらの手法の集大成はこれまでのコンピュータ将棋が不可能であった「教師となる棋譜が無くても人間より強くなる」という革命的なソフト(rezero評価関数)を生み出すに至っている。

 

そもそも三駒関係が表現力の足りない手法であるのは、表現力を落とすことでその結果計算量を減らし、学習コストが現実的になるという結果を生み出している。

合理的な理由があって表現力を落としているのだ。

 

 ところで、三駒関係と比べてDeepLearning系統の評価関数は理論上線形ではない局面評価が可能であるから、表現力が高いと言える。

 

それでも一定のNPSを保っているのはNNUEの設計思想、技術力の高さの証明である訳だが(DeepLeaning系統のコンピュータ将棋ソフトは他にも取り組んだチームはあるようだが、結果としては上手くいかないという結論を出していたりするチームも結構あった)

 

表現力問題についてもう少し触れていこう。評価関数を左右対称にするべきかどうかという問題がある。Ponanzaの山本さん、Aperyの平岡さんは、対称にしない方が強くなるのではないかとtwitter上で言っていた。やねうら王の、…

(選手権でやねさんは、本名で呼ばれると警戒すると言っていたので気にしている)

やねさん、ボンクラーズの伊藤さんは、対称にするべきだと言っていた。

 

理論上は当然、完全な評価関数なら対称にするべきであるが、両陣営の主張は見るべきところがあるので書いて残しておきたい。

 

山本さんは、「居飛車のように、飛車が右側にある時は、左側は居飛車の囲いになっていると考えられる。その分の評価を、居飛車の飛車に与えることなどは、表現力を高めることにつながる」

やねさんは、「理論上の最適解を求めるという意味でもそう。また、左右対称にしないと、その分、一つの合法局面が複数通りの評価を受けることになる。これを一通りにすることは教師局面を増やすことにつながる」

 

というような発言をしていたように記憶している。

私は理論上の最適解を求めるべきだと考えているので、対称の評価関数にするしか選択肢はないと考えている。

伊藤さんも概ね私と同じような見解の様である。

ちなみに、伊藤さんはボンクラーズの時点で手元の実験環境での計測データを取っており、計算量が倍に増えるとレートは100~200ほど上昇するという結果だった様だ。(上記の根拠の一つ)

 

ここに書き加えておくと、stockfishの探索では96スレッドにもなると(?、詳細は把握していないが)計算量が増えることによる影響を受けていないのではないかということがWCSC28以降com将棋開発者の間で噂されている。

 

Bonanzaは全幅探索だったから計算量とレートの推移については概ね線形でも違和感がないが、stockfish探索の場合は枝刈りがあるのでそうもいかない。枝刈りによって上がっていたレート分を解消してしまうまで探索して、結局深くは読めないという結果をもたらすこともあるだろう。少なくともstockfishではそういう挙動になるようだ。stockfishの大本では、その挙動に気がついていないことが理由で修正されていないのかもしれないとやねさんが発言している。

 

伊藤さんが将棋ソフトの開発から引退したのは、将棋ソフトの強さが人類を超えたと判断したからだと思う。私は、クラスタによるレートの測定はそういう意味を持って行われたと思っている。将棋ソフトはとっくに人間を超えていたのにも関わらず、それを隠すように米長が動いた。興行としては成功したかもしれないが、将棋界にそういうメリットがあろうと、Xデー(人間をコンピュータが越えたタイミングの意味)が分からなくなったことは、研究者としては悲しむべき結果だろう。

 

Novice熊谷さんのtwitterによると、手元の研究では探索で成果が上がっているとかなんとか言っていた。「チェスと将棋で同じ探索が最適になるはずがない」とかなんとか。

 

私個人の見解では、探索と評価関数にも相性がある。評価関数が変わると探索との相性が悪くなるかもしれないのだ。そのことも考えると、手が回らなくなりそうだから他の開発者の方は最適をそこで探すより、別のところにてを付けた方が強くなるのではないかと考えているのだと思う。

 

実は探索については、与える時間とマシンの変化とレートの伸びが色々とごちゃごちゃする。時間は指数関数的に実験で与える訳にはいかないが、探索できる手の深さに対して局面は指数関数的に変化する。

 

新しいソフトを開発したとしても、そのソフトが強くなっているかどうかは分からないのだ。強くなったかどうかを検証するには時間と計算資源が必要。

評価関数も三駒以上に駒を増やすと局面の評価に時間がかかって読める手数も減るし、検証も大変だし、沢山手元に用意するだけでも容量を圧迫するし。

 

表現力の話に戻るが、表現力を高くしすぎるとそもそも意味がないということもある。評価値をつけられなくなるのだ。無理に評価値をつけようとすれば、必要な教師局面の数も膨大になる。あえて表現力を落としてしまわないといけない。ほんの少しだけ違う局面は、ほとんど同じ局面だから同じような評価値を与える、というくらいの曖昧さが残るようでないと、教師の量が多くなりすぎて破綻する。

 

見たことない局面であってもなんとなく近い局面から評価値を類推するという余地をのこさなければいけない。そういう時に自分で判断できなくなってしまってはいけない。だからあえて表現力を落とす。もちろん計算資源の問題もあるけれど。

 

三駒関係の仕組みは記事にするかもしれないがとりあえずは自分で調べて頂いて、ニューラルネット系の(多層の)評価関数が有力ではないかとされている理由とか、その周りを少し書く。

まず、計算資源が足りないのでそもそも、Googleそのままの手法で学習させるのは無理に近い。Googleはこのタイプの計算を高速化するための独自のプロセッサを開発しているし、資金力もある。計算の効率も、使っている台数も、ひたすら強い。個人でそれに追い付くのは無理だ。数時間で終わったとか言っている計算も、一般人の自宅PCで行ったら何万年かかるかわからない。CPUじゃあ遅すぎて無理。GPU(CPUより相性がいい)でもたくさん必要。TPU(Googleが開発した専用の計算機)を並べてこそできる力業だ。

差分計算を取り込むことでたぬきは高速化をしたらしいが、(実装が難しすぎて並みの天才では)無理(並みの天才ってなんだ)。

たぬきはどうやらまだ最適化の余地があるみたいだ。

 

というか、タヌキはそもそも1から学習したんじゃなくて、もともとの評価関数を真似るようにニューラルネットを学習させていて…

 

ところで、ニューラルネットは三駒関係と比べて素晴らしい特徴がある。

三駒関係は線形の関数の和だが、DL型だと、関数の結果を関数に投げてその結果を関数に投げて…という構造になっているので、外から見たら何が起こっているのかは分からないが、その実態はものすごく複雑な多次元の関数になっているはずだ。

 

多層ニューラルネットを使うと、実はあらゆる関数を表現できるらしい。(2層で十分。ただし、層を深くした方が表現力と計算資源の都合上から実用性は高いので深層学習が重宝されている訳である)

この証明は前世紀には行われていて、ニューラルネットの研究は実は昔からあるのだが、計算資源が足りないことと教師データを集めるのが大変(なら作るのも大変)という理由で停滞していた。インターネットが出てきて大量のデータを集めて利用することが手軽にできるようになってきた今、やっと成果が上がってきた。新分野みたいなもんだ。まだブームが来て10年も経ってないし。

 

とにかく、ニューロンを増やせばあらゆる関数を表現できるという魅力から、期待は大きい。(ただし出費も大きい)

 

三駒はもう大体最適近くまで来てしまったので、強いしさらにまだ最適化の余地があると思われる新手法はcom将棋界では期待のニューウェーブってわけ。乗るしかない。このビッグウエーブに。

 

まぁでも、この波は乗るのも大変です。Googleなんて異常な札束パンチをしてきているわけで、この札束パンチを真似しようと思うと厳しい。この業界、お金にならない趣味の領域なんでね。人間を超えたら研究対象としてはもう終わってるし。

 

まぁそういうわけで、たぬきを含めDLをやっている将棋ソフトはこれからも増えていくんじゃあないでしょうか。

 

散文を書き散らす結果になりましたが、ここまで読んでいただいた熱心な方には感謝の気持ちしかありません。マイナー分野とマイナー分野の高度な掛け合わせみたいな知識が求められるcom将棋業界ですが、興味を持って読んでくださった方は本当にありがとうございます。