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

汎関数を用いた時間攻めの導出(の数学的解説)

前回の記事で紹介した汎関数を用いた時間攻めの導出について解説したのですが、読者の方から数式をもう少し解説して欲しいとのリクエストをいただきましたので、此方にて解説します。

数学マニアじゃない方にも雰囲気が伝わる用に善処はしますが、元が理系大学生が3−4年頃に習うものなので、それなりに高難易度な話です。

 

1.問題条件の定式化

 T(x) ・・・x手目に使う持ち時間(単位は秒)

 R(x,t) ・・・x手目にt秒使った時に正しい手をさせる確率

 F(T(x)) = \sum_{x} R(x,T(x)) = R(1,T(1))+R(2,T(2))... ・・・今回最大化したいパラメタ。各々の局面において正しい手を指せる確率の和

 \sum T(x) = H ・・・持ち時間の総和はHとする

持ち時間を制御することで最大化したいのは、厳密には勝率であり、各々の局面において正しい手を指せる確率の和ではありません。しかし、この記事 で検証したように、この指標はそれなりの精度で勝率と対応してくれていると考えています。

なお、 F(T(x))が所謂汎関数というやつです。

 

2.ラグランジュの未定乗数法を使って最適な時間配分が満たすべき条件を求める

時間を無駄にしている = 本来読むべき局面でない局面に時間を使っている = 無駄に読んだ局面と読むべき局面とでは同じ時間を費やしても得られる利得が後者のほうが大きい という思考実験をすれば、「無駄のない時間配分では、どの局面についても時間対効果が同じになっているのだろう」という予想を立てることができます。即ち

\frac{\partial R(x,t)}{\partial t} = 一定

 とするのが最適な時間配分となります。(ラグランジュの未定乗数法を用いだ導出はオマケを参照)

 

3.実験結果から、stockfishの時間配分が2の条件を満たしていることを証明する

レートの持ち時間依存性から考える技巧の敗因と探索部最適化で行った持ち時間に差があるソフト同士の勝率から、将棋の探索部は以下のような特徴を持つことが示唆されています。

・正しい手をさせる確率Rは読んだ手の深さに浅い領域では線形依存する(R = \alpha(x) d。dは深さ。\alpha(x)は局面の複雑さを意味するパラメータ。複雑な局面ほど大きくなります(複雑な局面ほど深く読むと反省することが多いため、手の深さの価値が上がる))

・消費時間は読む手数に指数関数的に依存する(T(d) = \beta^{d}。T(d)はd手読むのにかかる時間)

ここで、\frac{\partial R(x,t)}{\partial t}を計算すると

\frac{\partial R(x,t)}{\partial t} = \frac{\partial d(t)}{\partial t}\frac{\partial R(d)}{\partial d} = \frac{1}{\ln \beta} \frac{1}{\beta^{d(t)}} \alpha(x)(d(t)はt秒使った時に読める深さ)

これを一定にするには、\frac{\alpha(x)}{\beta^{d(t)}}が一定である必要があります。stockfishでは測定の中で手が変化する確率を計算しているため、\alpha(x)はある程度の精度で求められています。また、\beta^{d(t)} - 1 = (\beta -1) (1+\beta + \beta^{2}+...+\beta^{d(t)-1})であるため、\beta^{d(t)}は大雑把に言って今まで使った持ち時間とみなすことができます。

以上より、stockfishの時間配分ルーチン

「手の変化する確率と、消費時間の比率がある一定量に達したら探索を打ち切る」が浅めの読みの近似において最適な戦略であることが証明できます。

 

おまけ.ラグランジュの未定乗数法の例題と持ち時間の導出

ラグランジュの未定乗数法は2で述べたことをより一般的な話に落としこんだものです。wikipediaの記事が解りやすいので読んでみることをオススメします。あまり高度な説明は此処では扱いませんが、例題をひとつ紹介しますので、参考にしてください。

ラグランジュの未定乗数法 - Wikipedia

 

例題:x,y x^{2} + 2y^{2} = 1を満たすときf(x,y)=x+yの最大値を求めよ。

x,yが束縛条件を満たすのであれば、x+yの最適化は、 F(x,y) = x+y - \lambda (x^{2} + 2y^{2}-1)と等しい。

 x+y - \lambda (x^{2} + 2y^{2}-1)x,y偏微分すると

\frac{\partial f}{\partial x} = 1-\lambda 2x ...(1)

\frac{\partial f}{\partial y} = 1-\lambda 4y ...(2)

 となる。(1,2)を同時に0にし、かつ、 x^{2} + 2y^{2} = 1を満たすx_{0},y_{0},\lambdaを求めると

x_{0}=\frac{1}{2\lambda} , y_{0}= \frac{1}{4\lambda}

x_{0}^{2}+2y_{0}^{2} = \frac{3}{8\lambda^{2}}=1

\lambda = \pm \frac{1}{2}\sqrt{\frac{3}{2}}

よって、

x = \pm \sqrt{\frac{2}{3}}

y = \pm \sqrt{\frac{1}{6}}

解が2つ出てるのは、ラグランジュの未定乗数法で得られるのは値の極であるため、最小値も同時に得られてしまうからです。今回の問題(最大値)は2つ出てきた解のうちの、x = \sqrt{\frac{2}{3}}y =  \sqrt{\frac{1}{6}}の方となります。

 

おまけ2.将棋の持ち時間への適用

将棋の持ち時間についても同様にF(T(x))の代わりに

G(T(x)) =  R(1,T(1))+R(2,T(2))... - \lambda (T(1)+T(2)+...-H)

の最適化を考えます。

 \frac{\partial G(T(x))}{\partial T(n)} = \frac{\partial R(1,T(n))}{\partial T(n)}- \lambda

から、\lambdaが何であるかはHに依存するものの、兎にも角にも\frac{\partial R(x,t)}{\partial t}が一定でなければならないことが解ります。