たくさん読めば強くなる？解決編２
解決編に２があるってどういうことだよ…orz
ちなみに某所を思わず荒らしてしまったのはいかにも漏れですたいへんｽﾏﾝｶｯﾀ、。n_
下手の横好きも度を過ぎると犯ざ（ry
これまでのあらすじ
走れメロス状態で始めたやつがいつしかカチカチ山になってしまった。
消火できたと思ったらラスボスが目前に迫っていた。
GMA0BNはキ○ン○ルの呪文をつかった。
GMA0BNは社会的にしんでしまった…
今日のお題
他人に先に言われるぐらいなら間違った方がマシ*1と固く信ずるので、今日わたくさん探索したらなんで強くなるのかについて、つい3秒前に思いついた説明を書く。
期待利得というものを定義汁、
ある評価関数h:{局面}→{評価値}の下で、当方は当方手番においてh(子局面)を最大化する手を選び、相手プレイヤーは相手手番において相手なりの基準で手を選ぶとする。簡単のため相手の確率的性質は相手手番の盤面のみによって決まり、時間によって変化したりしないとしよう*2。
こうお膳立てすると、当方と相手が当たった時の局面の実現確率が一意に定まるはずだ*3。ということは、ゲーム終局の実現確率も一意確定である。
で、さらに、終局局面については利得というものが定義されているとする。将棋の場合、ゲームのゴールにはルール上「勝ち」と「引き分け」と「負け」しかないから、これは（例えば）+1、0、-1の3値だけと考えればよろしい。
すると、任意の局面nについて、（それが終局に至る有限の手順しか持たない以上は）利得の期待値が計算でくる。すわなち、＜現局面がnである＞という事象の下での終局局面fの実現確率の事後確率を求め、それとfの利得を掛け合わせたものを、全てのfについて足し合わせれば宜しい。
探索汁、
ここまでお膳立てしたところで、これに「探索」という操作を追加したとき、利得の期待値に対してどうなのか？ニュートラルなのか、なんらかのバイアスをもたらすもののかを考えて見ゆる。探索といってもいろいろありそうだが、ふつうに深さNのmin-max探索を考えよう
min-max探索を行うと何が違ってくるかというと、「読み筋」というものが発生し、かつ、相手がどうふるまおうとも、N手先において、探索で得た評価値h_minを下回ることがないという意味での評価値の下限h_minが得られるということだる。
読み筋は、相手がそれに乗ってくれたときのみ実現するシナリオのようなものであり、かつそうでないケースが星の数ほど生じ得るのでいまいち分析しにくいが、他方、h_minが言っていることはわかりやすい。すわなち、探索木の葉のうち、評価値がh_min未満である局面の実現確率*4が0に変更されるということだる。相手がどう足掻いても、当方がミスしない限り、当方の努力だけによって、この事実を変えずに済む。
一方、探索木の葉のうち、評価値がh_minを超える葉の実現確率はどうだろうか？→これは当方の読み筋と、相手の確率的性質次第の兼ね合い次第としか言えない*5。
ここで、「相手が無限に強ければ評価値がh_minを超える葉の実現確率は0になるのではないか」と早合点してはいけない。無限に強い＝相手の利得が毎度理論上成し得る最大値である、だが、ここで言っているh_minはあくまで評価値であって利得ではない。評価値と利得の関係など知れたものではない。そう、まともでない評価関数ならね。
もっと考察汁、
ここまでの議論で明らかなのは、探索しないときに対して、探索することによって我々が確実に手にするのは、探索木の葉において、評価値がh_min未満の葉の実現確率が0になる、という事実だけだということだる。評価値がh_minより大きい葉の実現確率が変わらないとか、上がるとか言う保証は全く無いことがわかる。というのは、それは当方の読み筋と、相手の確率的性質の兼ね合い次第という話なので。
一方、相手がもし無限に強い＝相手の利得が毎度理論上成し得る最大値である、なら、ゼロサムゲームである以上、当方の利得が毎度理論上の下限まで削られることになる。
まとめると、探索という当方の努力はN手先における評価値の下限を押さえ、相手の強さはゲーム終局における当方の利得の上限を押さえるというある種挟み撃ちの原理のようなものが存在し、それが毎度毎度ゲームの行く末を決めているということだる。
N手先の評価値と、ゲーム終局における当方の利得の関係はようわからんが、ようわからんので両者の食い違いを誤差εとして表すことにしよう…
数理モデルが登場汁、
だいたい解法がわかってきた。将棋の場合利得は[-1, 1]*6ので、任意の局面nについて、適当な正の係数αを用いて、
- nの期待利得〜α×（適当なシグモイド関数Σ（nの評価値 - 適当なオフセット）- 0.5）・・・(A)
という関係がおおよそ当てはまるはず
式(A)より、
というモデルを仮定することができる。もちろん「適当なオフセット」は、誤差εの平均が0に来るように決める。
シグモイド関数の逆関数は、x-y平面上において、もとの関数うを直線y=xに対してひっくり返した形の関数である。この逆関数自体（誤差εを考えない）は、x=±1において急激に立ち上がったり立ち下がったりする関数であることに注目しよう。式(B)の下での話なので、x軸が期待利得、y軸が評価値にあたる。
こうお膳立てした上で、当方の努力によりN手先における評価値の下限をh_minに押さえられるという事実が何をもたらすか考えてみよう、
ぶちゃけ、式(B)のふるまいを大別するならば、本当は小さい期待利得なのに高い評価値がついてしまう（false positive）なケースとしては、次が挙げられる。
- nの期待利得が小さいが、nの誤差εが大きく正の側に振れている・・・(C)
反対に、本当は大きい期待利得なのに小さい評価値がついてしまう（false negative）なケースとしては、次が挙げられる。
- nの期待利得が大きいが、nの誤差εが大きく負の側に振れている・・・(D)
以上のfalse事象(C)、(D)を除けば、当方の努力によりN手先における評価値の下限をh_minに押さえることによって、順当に期待利得が小さい葉から実現確率が0になるから、期待利得を押し上げようとする力学を生じる。これは気体通りのふるまいである。*7
一方、false事象(C)、(D)だが、これらについては、シグモイド関数の逆関数が、x=±1で急激に立ち上がったり立ち下がったりしていることを思い出そう。これは、期待利得がはっきり+1か-1付近であるnについては、評価値の誤差εが多少大きくとも、期待値と評価値の対応関係は順当となり、さほど問題を生じないことを導く。これもまあ、気体通りのふるまいである。
したがって、問題になるのは、期待利得の絶対値が小さい領域（期待利得が0付近）ということになる。すると、false要因(C)、(D)には期待評価値の大きさと誤差εの大きさが絡むが、問題となる領域（期待利得が0付近）では、相対的に、誤差εの大きさだけで論じて良い。つまり、(C)と(D)は次の形にまとめられる：
- 期待利得の絶対値が小さく、誤差εの絶対値が大きい・・・(E)
探索の段数を増す効果
探索の段数を増やすことで、(E)の出る幕が減るかどうか考えよう。
その前に、（α×適当なシグモイド関数Σの逆関数（(α^(-1))×（nの期待利得 + 0.5）））自体を、期待利得2.0と位置付ける。これは、期待利得0を0のまま変えず、期待利得の大小関係を保存する写像なので、写像結果自体を期待利得とみなしてもあまり差し障りが無いからである*8。式(B)は次となる。
- nの評価値＝nの期待利得2.0＋適当なオフセット＋誤差ε・・・(F)
さて、min-max探索とは、大量のnからなるサンプル集合の部分集合の中で、(F)の値が最大値をとる（または最小値をとる）要素nを選択し、それを複数の部分集合について行った結果を集めた集合について、再び(F)の値が最大値をとる（または最小値をとる）要素nを選択する、という操作を再帰的に繰り返すことだとみなせる。
しかし、誤差εの分布は（適当なオフセットをそう選んだのだから）期待値が0である。もしこれが、0を中心とする正規分布のように、0付近にそこそこ集中してピークを成す分布に従うなら*9、上記操作において、0付近が選択される頻度が、そうでない頻度より多くなるから、繰り返すうちに誤差εは0に近づく*10。
さらに、うんと先まで探索するか、あるいはゲームが終盤に近づいてきた場合、（引き分けが最善手である特殊なゲームでもない限り、）期待利得は+1か-1に向けて振れ始めるだろう。すると誤差εの大きさは、上のシグモイド関数Σの逆関数の議論の通り、相対的に目立たなくなる*11。
以上の2つの力学により、誤差εが0でピークを成す一つ山様の分布を示し、かつ、裾野の幅が期待利得の絶対値に対して十分小さい評価関数であれば、深く探索すればするほど強くなることがわかった*12。
結び
二人零和確定完全情報ゲームにおいては、当方の期待利得の下限を正確に見積もることが勝利の鍵である。見積もりを誤り、かつ相手が十分強ければ、見積もりの誤差分はたちまち相手の期待利得に転換する（∵ゼロサム）*13
完璧でない評価関数の下では評価値と期待利得の対応のアバウトさ故に、探索を行っても常に正確な見積もりを行えるわけでは無いが、期待利得2.0に対する評価値の誤差εが、0を中心とする一つ山分布なら、探索の規模を増すことにより、正確な見積もりに近づけることができる。
*1:期待利得を最大化できる。
*2:変化するとしても長時間平均をとれば似たような議論ができる（多分）。なぜなら、期待値をとる操作E[・]は線形なので、相加平均ベースの加重平均（この場合の加重は、相手プレイヤーの確率的性質別の遭遇確率）は、それを行うのが期待値をとる前だろうが後だろうが同じ値になるはずだし、
*3:いや知らんけど多分、
*4:正確には、＜現局面が探索木の根である＞という事象の下での実現確率の事後確率
*5:特定の主張をした端から反例を持ち出せる。
*6:有限範囲かつ0に対して対称と考えても一般性を失わない
*7:あくまで期待利得を上げようとする力学が生じるだけで、本当に上がるかどうかは、挟み撃ちの原理のもう片側担当である相手の強さ次第。
*8:シグモイド関数が非線形なため、差し障りが全くないわけでは無いのだが、期待利得の順序が保存されることから、少なくとも勝敗を覆すような悪さはしない。
*9:0を挟む二つ山の分布とかは断じてNG、
*10:いや知らんけど、
*11:いやこれも知らんけど、
*12:いや責任持たんし知らんが。
*13:『ヨルムンガンド』で言っている通り、ナイフの数の総和が一定であるゲームにおいて、投げたナイフが再び戻ってくると仮定してはならない。
