読者です 読者をやめる 読者になる 読者になる

雑巾絞りにおけるランダムムーブの意味考

コンピュータ将棋の評価関数を強くする方法に「雑巾絞り」というものがあります。簡単に言えば、1-2手先までしか読まない設定の弱いコンピュータの見解(先手/後手のどちらがいいか、次に何を指すべきか)を3-8手程度まで先を読んだ相対的に強いコンピュータが修正するという手法です。

この手法は第26回コンピュータ将棋選手権から第4回電王トーナメントにかけて、コンピュータ将棋開発者の間で爆発的に流行しました。多くの開発者は雑巾絞りの最適化にまい進してましたし、大会結果そのものも、雑巾を上手く絞れたかに成績が強く依存していたといっても過言ではありません。

雑巾絞り用の教師局面を作成する際に、多くのソフトは極めて短い持ち時間(1局1秒以内に終わる程度)で対局させたものは使わず、何手かに1回、ランダムで手を動かすようにしています。

将棋の手の大半はパスに劣るという格言があるように、ランダムで行われる手の殆どはすさまじく酷い手です。故に、1-2割の確率でランダムムーブを行わせていた浮かむ瀬(apery)の教師データには将棋が強い人から見たらあり得ないほどの悲惨な局面が含まれていたはずです。

この仕様を目の当たりにして、私は「こんな悲惨な局面だらけの学習が効率的なはずがない」とMultiPVの上位3手を評価値の差に応じてランダムに選ぶなどの教師生成を行っていたのですが、どうしてかランダムムーブ入りの教師よりも弱くなってしまいました。教師局面の数は同じなのに、です。

この問題についていろいろ考えた結果以下のような仮説にたどり着きました。

【感覚的な話】

将棋にはいくつもの優れた形があります。矢倉囲いや美濃囲い、棒銀、腰掛銀などが一例です。では、矢倉囲いと美濃囲い、棒銀と腰掛銀はどちらの方がより高得点な形でしょうか。

人間であれば、駒の並びを論理的にとらえて評価したり、他の駒の動きによるとお茶を濁すことができますが、駒の並びに点数をつけ、それらの和を局面の点数としているコンピュータにはそういう芸当はできません。

コンピュータにこうした形の価値を学ばせる簡単な方法、それこそが、形を崩すとどれだけ困るかを確認することなのです。人間と同じ、試しに変な手を指してみて、指導してもらう方が、理由もわからずに定跡本に従って指すよりも強くなるというわけです。

 

で、これをもう少し難しく書くとこういうことになります

【数学的な話】

雑巾絞りにおける学習とは、教師局面の点数を教師として与えられた点数に近づけることに等しいです。学習が収束するとは、教師局面に対する誤差の和に対する各評価パラメタによる微分が0になることを意味します。

しかし、実際の学習ではこれら微分値が綺麗に0になることはありません。教師データそのものに誤差があったり、ミニバッチ法によって評価パラメタは逐次更新されていくからです。結果、評価パラメタは極小点から教師局面に対する誤差の和に対する、各評価パラメタの二回微分の値の逆数程度にぶれることになります。

各評価パラメタの二回微分値は教師局面のなかで当該パラメタが何回出現したかに比例します。教師局面の数が同じなら、各パラメタの二回微分値の和はオーダー的には同じになりますが、MultiPVなどで過度に定跡系に偏った棋譜については、よく出るパラメタ(88の玉と89の桂馬とか)と滅多に出ないパラメタの差が大きくなってしまいます。

結果、評価パラメタのブレの総和(出現回数の逆数の和)は増えてしまうため、適切な値に収束しにくくなります。パラメタの数が有限である以上、あまり無意味な局面は教師に入れたくないのですが、ランダムムーブを入れることでパラメタのブレの巨大化を防ぐ効果が、無意味な局面が入るデメリットを打ち消してくれているようです。