CSAの会誌に書いた原稿(WCSC29優勝記)をそのまま転載すると著作権違反になると思うので、記憶を頼りに内容を掘り下げながら書いていきます。昨日の記事で書いたように猫砂はいくらでも受け付けております。

教師depth

ここで言うdepthはαβ探索の時の探索深さのことを意味する。

教師局面(の生成時)のdepthは深ければ深いほど正確性が増し、良い教師であると仮定して我々は強化学習を行っている。とりあえず、観測できる範囲の現実的なdepth(12程度まで)においては、それは成り立っているように思える。特にNNUEではパラメータの数が少なく、KPPTのときほど教師局面を必要としないため、教師局面のdepthを少しぐらい上げても、現実的な生成時間で収まる。そのため、やねうら王ではdepth 18(相当)で教師を生成した。

depthを上げるほど良い教師であるという仮定がどの範囲まで成り立つかはまだ知られていない。極端な例としてdepth = ∞(無限大)の場合、勝ち/負け/引き分け(千日手)しかなく、この場合、評価値による情報よりも情報として欠落している意味がある。実際、elmo式でlambda = 0の場合がこれに相当する。(このときQ学習に近くなる)

lambda = 0に設定された教師から学習させた場合であっても強化学習はできることは確かめられていて、実際、やねうら王でもlambda = 0で強化学習すること自体は可能である。(lambda = 0.5で強化学習を繰り返したNNUE評価関数より、幾分弱くはなる。簡単な実験では、R200ぐらい弱かった。それでもR4000の将棋ソフトがR200弱くなったところでR3800であって、人間のトッププレイヤーは超えているわけだから、学習できているかいないかで言うと学習できていると言えるとは思う。)

depth = ∞というのは初期局面において終局まで知っているわけだから、将棋の神様と同じ意味がある。評価関数はその局面で、同じ棋力のプレイヤー同士で対局させた時の期待勝率を表現する関数なので、将棋の神様が指した場合の期待勝率(0% or 100%)を知りたいわけではない。そういう意味ではdepthを上げすぎると良くないことは十分に予想されるのだが、探索時depth(実際に対局する時のdepth)は20～40程度であるので、そのへんまでは教師生成時のdepthを上げても良いのではないかと思う。(実験で確かめられたわけではない。単なる私の予想。)

ただ、人間が学習する時に、あまり細かい概念を先に学習するとそのあと支障をきたすように、NNUE評価関数でも最初は単純な概念から学習させるほうがそのあとの学習がうまくいくような気はしている。体感的には低いdepth(depth 8ぐらい)の教師局面から順次教師局面のdepthを上げながら学習させていくほうが手元の実験では最終的な伸びが良いようであったが、これについてきちんとした比較資料を出せるだけ私は実験をできていない。

教師生成時の組み合わせ爆発について

やねうら王では王手のかかっている局面について1手延長している。「やねうら王では」というか、Stockfishがそうなっているからというのが大きい。チェスでは王手がかかりつづけることは少ないためこれで問題ないのだと思うが、将棋ではやや延長しすぎであるように思う。いずれにせよ、終盤で王手がかかり続ける(即詰みがあるような)局面に関して、depth 18で読ませようとした時、17手詰めまでを力任せに調べようとしているような状態になる。これはdf-pn+などの詰将棋用のアルゴリズムに比べて非常に効率性の悪い探索であり、指数関数的な時間を必要とする場合がある。

教師生成時にdepth 18で生成するとは言っても、このような罠に嵌ると膨大な生成時間が必要になってしまう。そこで、実際には、探索ノード数(局面数)でαβ探索を打ち切るという手法を併用する。このアイデアは、たぬきチームの野田さんによるものである。このような手法であるため、教師生成時のdepthは「depth 18」ではなく「depth 18相当」というように私は呼んでいる。

実際、depth 18 + 50k(nodes)のようにして打ち切っている。depth 18 + 100kだとかdepth 18 + 200kだとか打ち切りノード数は探索部に合わせて現実的な時間に収まるように調整している。

教師生成時のノード数固定について

それならば、教師生成時にdepth固定ではなく、ノード数を固定すれば良いのではないかという話になるのだが、残念ながらこれはとても良くないアイデアである。

何故なら、ノード数を固定すると各局面で読みの深さが異なることになる。読みの深さが異なるものを比較することは基本的にはできない。将棋は、形勢が有利なほうは、その有利を拡大することができるはずであり、ply手先の局面において、plyにおおよそ比例する形で形勢の差が開いていくのが普通である。つまり、異なるdepthで探索させた教師(評価値)は、その優劣を比較できないのである。

実際、ノード数固定で教師を生成した場合、生成時間はほぼ固定時間で収まるのでとても都合が良いのだが、教師の質はあまり良くないようで(類似の局面での評価値の分散が大きくなりすぎるのが原因だと思われる)、そこから学習させてもdepth固定より明らかに悪い結果しか出なかった。

ただし、教師生成は、終局までのシミュレーション(対局)を行っている意味もあり、depth 2～4ぐらい異なるだけであれば、そのシミュレーションに多様性(≒ばらつき)をもたらすので一般的に悪いとは言い切れない。2016年ごろはAperyもやねうら王もそのような方法で教師生成をしていた時期があった。

ただ、ノード数固定しての教師生成は、depthにそれ以上のばらつきをもたらすようで、明らかに悪いようであった。

教師生成時の可変depthについて

教師生成時のdepthに関して、序盤はdepthを上げてもそこまで時間はかからないのであれば、序盤と終盤でdepthを変えれば(あるいは探索ノード数を下げれば)良いのではないかという発想は当然でてくるだろう。WCSC29の時に参加者の何人かから私はその質問を受けた。

ところが、これは良くないことが私は自身の実験からわかっている。異なるdepthの教師は良くないという上の事情も関係しているのであろう。

また、対局シミュレーションである以上、強い対局者であるほうが望ましい。(上で書いたようにdepth 20～40ぐらいまでの範囲においては)　しかし、生成のための時間は有限であるから、その限られた時間のなかで一番強い対局者になれるように時間配分を調整するのが望ましい。

つまり、一局当たりの持ち時間が一定である時に、どのようにタイムマネージメントするのが最強となるのかという問題に帰着するのである。

実際、やねうら王では通常対局の時にどのようにすればベストになるのか調整しているので、この結論を私は知っている。簡単に言うと、一手当たりの配分はほぼ同じにするのがベストである。(形勢が難しい局面は時間をかけるが、それはそれとして。)　ここを極端に序盤に時間を費やしたり、終盤に時間を費やしたりするように改造しても勝率は下がる。ここを下手に調整するぐらいなら、一手あたりの時間が均等になるようにしたほうがマシなのである。

※　1局に使える時間が決まっているとして、終盤の1手の時間を序盤の1手の時間の半分にするぐらいなら、序盤と終盤で均等に時間を使ったほうが強いことが実験からわかっている。ただし、将棋では何手で終局するかが不明であるため、終盤に割り当てる時間をどこかで減衰させていかないと仕方ない意味はある。

つまりは、教師生成時もノード数固定かdepth固定というのは、そこまで悪くないタイムマネージメントなのである。本当は一手当たりの時間を一定にするには、ノード数固定が望ましいのだが、上に書いたようにdepthがあまりに異なる教師になってしまうので良くない。ノード数を固定せず、depthを固定したほうが良い。終盤に少し時間は要するが、これそれ自体はそれほど悪いタイムマネージメントではない。ただし終盤で時間がかかりすぎる場合があり、そこだけ仕方なく、ノード数で打ち切るという冒頭の話になる。

まとめ

10万円ぐらいのPCでもdepth 12 + 10kぐらいでなら教師生成は十分現実的な時間でできると思うので、そんな感じで教師を生成すると良い感じだよということで。(手元の実験では、depth 18 + 100kのときと、R30程度しか違わなかったので…)