センシ探しへの三分探索の応用

おれは非常に有能であり、多趣味な人間だが、趣味の一つにエイムがある。

今日はエイムとアルゴリズムを結びつける。

センシ問題

FPSなど、シューティングゲームの基本要素としてエイムがある。エイムというのは、相手にカーソルを合わせる技術のことだ。当然、これが早く正確なほど有利となる。

エイムは、PCゲームではマウスによって行う。（PS4やXBoxなどではコントローラのスティックを使う）通常、ゲームではエイムセンシが設定可能であり、これを「センシ（センシティビティの略）」と呼ぶ。センシを高くした時には、マウスを単位距離動かした時にゲーム内でカーソルが速く動き、低くした場合には遅くなる。

当然、狙いを精密に合わせるためにはセンシを低くして、カーソルがゆっくり動かせるようにした方がよいが、一方で、狙いを早く合わせるためにはセンシを高くしたい要求もある。

この二律背反する性質に、すべてのFPSプレイヤーは悩まされているのだ。

二分探索によるPSA法

では、最適なセンシはどうやって見つければよいのだろうか？これに対して、PSA法（Perfect Sensisitivity Approximation)というヒューリスティックな方法を考えついた人が海外にいた。もっとも初期の動画は、200万回再生されている。センシ問題は非常に関心の多いテーマなのだ。

この方法を本質的にただの二分探索だと指摘した上でブログで解説し、日本中に広めたのが他の誰でもないGodAimAkira、つまりおれなのだ。あぁなんという偉人だろう。これによって、日本のエイム力は大いに向上したと言ってもよいだろう。

ここで説明のために関数f(x)を導入しよう。この関数は入力としてセンシをとり、快適さを出力するものとしよう。

PSA法というのは、この中を二分探索により最適解を探すと言ってるに過ぎないのだ。

二分探索については二分探索のココロは「境界を探す」で書いたから参考にしてほしい。

PSA法の欠陥

ここでおかしなことを言ってることに気づいた人がいるかも知れない。

二分探索によって最適解が見つかるということは、f(x)は単調であるということを言っているからだ。いやいやそんなわけがなかろう。仮にそうであれば、すべてのプレイヤーはセンシ0かセンシ∞のどちらかを採用するはずである。

では、fはどんな形状をしているのだろうか？これは経験的には、凸型をしていると考えられる。ある最適解があり、その前後では同様に快適であり、実際、PSA法もこの性質を利用しており、最終的にlowとhighが等しく快適である場合、(low+high)/2を採用して終了する。

ただし、コブが1つかどうかはわからない。もしかしたら2つあるかも知れないし3つあるかも知れない。これは、プレイヤーの中には、すごくローセンシでもすごくハイセンシでも同様に快適にプレイ出来てしまう人がいることからもわかる。

しかしややこしいので、ここではコブは1つだけとしよう。経験を元にして、初期の探索範囲を十分に狭めておけるならば、これで実用上は問題ない。

fは、コブが1つの凸型の形状をしていることがわかった。では、これに二分探索を適用するというのはどういうことだろうか？

これは、それっぽい解を見つけ出せることは運まかせということだ。うまくいく場合の探索の様子を示すとこんな感じになる。

ここで運まかせといった運要素はどこにあるかというと、初期探索範囲のとり方にある。探すべき頂点が、探索領域から外れてしまう場合があるのだ。正確にいうと、コブが左右対称の場合は二分探索でも常に探しだせるはずだが、経験的にこれは嘘なので仮定しないことにした。

これは、PSA法の限界であり、欠陥である。

三分探索

凸型のグラフに対して頂点を探索するアルゴリズムとして、三分探索がある。

三分探索の本質は、「消去法」である。

ある探索区間[low,high]を三分割したとする。この時、頂点が存在する領域は3通りに分類出来る。そのうち、左の領域にある場合と、右の領域にある場合については f(m1)とf(m2)の大小関係について判定することが出来る。例えば、左の領域であればf(m1) > f(m2)が言える。したがって、f(m1) < f(m2)であれば、左の領域にないことは確定する。

このように、 f(m1)とf(m2)の比較結果から、左と右のうち一方については「そこにはない（消去法）」ということが確実に言えて、 3つの領域のうち2つの領域を常に残していくことが出来る。

これが三分探索の本質である。

GAA式PSA法 ver.2

この三分探索をセンシ探索に応用しよう。これを「GAA式PSA法 ver.2」と呼ぶことにする。 ver.1は二分探索法によるものだった。

手続きを示す。

初期の探索領域a,bを決定する。low=a,high=bとする
以下を繰り返す
- (1) low,highを3分割するm1,m2を求める
- (2) m1,m2でPSAを行い、快適さを比較する
- (3) m1の方が良い場合、high=m2とする。m2の方が良い場合、low=m1とする