chokudaiサーチ(ビームサーチ亜種)の利点の話
たまには技術ネタを。やたら要望が多いので。
最後の「多様性って何？」が本番です。ここの説明さえできればいいなって思ってました。実装の話まで行こうかと思ったけど、長くなるから要望があれば、って感じで。
貪欲法とは？
多分分かる人しか読まないのでざっくり。
現在の状態から、１手先だけを探索し、もっとも評価が上がる１手を選んで状態を更新する、というアルゴリズムです。
ビームサーチとは？
ビームサーチでは、「１手先のみ」という条件は変わりません。変わるのは、保持する状態の数です。
ビーム幅Kのビームサーチは、現在持っているK個以下の状態から、１手先だけを探索し、評価値で上からK個の状態を、次の状態として保持する、という感じです。
当然、K＝１の時は、貪欲法と同じ結果になります。
貪欲法である程度良い解が出せるが、最適な解が出せない、というような問題に対し、手軽により良い解を見つけることが出来ます。
chokudaiサーチとは？
自分が愛用してたらなんか自分の名前がついてたアルゴリズムです。（命名はcolunさん。当時アルゴリズム名不明で、とりあえず暫定的につけたら普及した。）
アルゴリズムの名前を色々知っているわけではないので確認取ってませんが、Beam Stack Searchの一種、という説が有力です。海外の人に説明するときにはそう言いましょう。
ビームサーチでは、上位K個を探して次の状態へ、って感じでしたが、プログラミングコンテストなどの、「実行時間が決まっている場合」、もしくは、「○○以上の結果が出るまで探索をしたい！」みたいな場合に、この「K個」を固定するのは面倒です。
そこで、
・とりあえず最後までK=1のビームサーチを走らせる
・発見した全状態は、全部保持する。ターンごとの優先度キューにぶち込む感じ。
・最後までいったら最初に戻って、優先度付きキューからまた取り出して再計算
って感じのことをすると、Kを固定せずにうまいことビームサーチを走らせることが出来ます。
ソースコード
fmrhさんのところより引用。（元々自分がTwitterに書いたコードをバグ修正したもの）
chokudaiサーチにおけるメリットとデメリット
メリット
時間管理が楽
超ラクです。時間いっぱいまでループ回せばいいだけなので、ビーム幅の調整とかいらないです。短時間コンテストだったらビームサーチの調整が間に合わないので、こっちでやると吉。
メタヒューリスティック側での多様性の確保
ビームサーチでは、評価値の上の方のものから採用していきます。すると、似たような状態だけどちょっとだけ違う、というのが大量に発生してしまいます。これだと、ビーム幅が広くても、様々な局面を探索することが出来ません。
ここで、chokudaiサーチを使うと、「先行してあんまりよくなかった結果」と「後から見つけてとりあえず良さそうな結果」の両方が探索されます。ざっくり見積もって、ビーム幅Kだと、logK種類くらいの結果がそこそこ探索される感じになります。ビームサーチだとこれが1種類になりがちなので、悪いパターンにハマってしまうことが多いです。
デメリット
良い結果の探索回数が減る？
多様性が生きない場面だと、単純に悪くなることが多いです。
ビームサーチは「厳選された結果に対してのみ探索」するのに対して、chokudaiサーチは「とりあえず先行したのも探索」しちゃいます。
ってことで、多様性が要らない場合は、chokudaiサーチの最初の方の探索は純粋に無駄になります。
追記 メモリ使用量が増える
デメリット書き忘れ＞＜
ビームサーチだと直前の状態だけ持てば良いのに対し、chokudaiサーチは全状態を持たなければいけないので、メモリ使用量が多くなります。足りない場合はどうにかしましょう。
多様性って何？
さて、多様性って言いましたが、あんまりよくわからん、って人が多いと思います。
そこで、ちょっとした問題を出題してみます。
問題
すっごい雑に書きます。
- あなたの初期スコアは０である。
- あなたは、ここから100回の状態遷移をすることが出来る。
- 遷移先の状態をAとして、スコアは、前の状態からf(A)とg(A)を足したものとなる。
- ただし、f(A)は即座に観測可能だが、g(A)はLターン後に初めてわかる。
- つまり、評価値は、「それまでのfの和＋Lターン前までのgの和」という形で得られる。最後のLターンはg(A)はわからないまま答えを出す感じになる。
- 関数f, gはAによってランダムに決まる。0から1までの一様分布。
- 最終的なスコアを最大化しなさい。
問題の補足
関数fは「とりあえず簡単に出せる評価値」、関数gは、「内部的に潜んでいる隠れ評価値」として、gはLターン後に明確になる、みたいなのをイメージしています。
本当はここまで簡単なモデルにならないし、頂点１個じゃなくて、どういう連続の仕方をしているか、とかで決まるものではあるのだけど、今回は簡単のためにこんな感じに問題設定してます。
２つのアルゴリズムによる実験
隠しパラメータが存在しない場合
さて、とりあえずL=0にすると、評価丸見えな状態になります。この状態で、ビームサーチ、chokudaiサーチの両方で、ビーム幅30、状態遷移先30でやってみましょう。
これを100回やったスコア平均は、以下のようになります。
ビームサーチ： 185.02
chokudaiサーチ： 183.68
当然ビームサーチのが良いです。これは、隠しパラメータがない場合、純粋に良い評価値のものを調べたビームサーチに軍配があがる、という例になります。
なお、これは、ビーム幅が30だからこの差で済んでるだけで、ビーム幅が小さいとひどいことになります。
隠しパラメータが10ターンで顕在する場合
さてここで、L=10にしてみましょう。結果が疑われそうなのでこちらは1000回の平均。
ビームサーチ：152.74
chokudaiサーチ：153.12
わずかですが、今度はスコアが逆転しました。正確な評価が得られるのが遅くなるため、どちらもスコアは大幅に落ちていますが、chokudaiサーチが、ビームサーチより少し良い結果を得ることが出来ています。これが「chokudaiサーチによる多様性」によって得られるメリットです。
今回の実験では、隠しパラメータと顕在化された評価を同じ重み付けでやりましたが、この重み付けが変わると結果がだいぶ変わります。例えば、fを0-1、gを0-10にすると、
ビームサーチ：635.81
chokudaiサーチ：646.29
ってな感じで、chokudaiサーチが圧勝します。逆にf,gの重み付けを逆転させ、隠れ評価の重要性を下げると、
ビームサーチ：1040.44
chokudaiサーチ：1036.27
・・・ってな感じで、ビームサーチが圧勝します。こんな感じで、「評価値に現れない部分がどれだけ重要か」、「そのタイムラグはどれくらいあるか？」によって、chokudaiサーチとビームサーチの優位性は変わってくるわけです。
つかったコード：
https://dl.dropboxusercontent.com/u/2627723/beamvschokudai.cs
chokudaiサーチは本当に必要か？
さて、chokudaiサーチなんですが、正直個人的にはあんまりいらないかなー、と思ってます。最初は便利なんだけど、だんだんいらなくなってきます。
何故かと言うと、以下のような理由があります。
- 評価値は徐々に洗練されていくため、隠れ評価値の比重は評価関数が洗練されるごとに下がっていく
- 多様性の確保は、ビームサーチやchokudaiサーチ以外の部分でも確保することが出来る。重複状態の排除にちょっとアレンジを加えるだけでそれっぽくなる
- chokudaiサーチが有利に働く場合も、ビームサーチがまともにチューニングされていれば、chokudaiサーチの優位はあんまり大きくならない。
ってことで、そんなに覚えなくてもいいけど手軽に実装出来るアルゴリズムとして記憶しておくといいかもしれません。
時間制限ぴったりに終わるようにビーム幅を調整する、とかは結構難しいので、手軽さという点ではchokudaiサーチはかなり強いアルゴリズムと言えます。
chokudaiサーチのさらなる改良
さて、先程、Lが出ましたが、「Lターンで大体結果が分かるんだったら、Lターン分だけ先行させればよくない？chokudaiサーチの１本目超無駄じゃない？」みたいなのがあります。そういうのが思いついたら、「Lターン分だけ前のビームより先行したら、そこで次のビームに移る」みたいなのを書いてもいいわけです。（これをちょっといじったのを時間差chokudaiサーチって呼んでます。）
結局のところ「○○な部分が不満だな」って思ったら、それを改良するためにどうしたらいいかを考えて、適当にいじればいいわけです。chokudaiサーチだとかビームサーチだとか、そんな型に嵌って実装するのは勿体無いです。問題によって求められるものだって違います。
自分もそのまま使ってるわけでもないので、キューを２つ用意するダブルchokudaiサーチとか色々作ってます。コンテストで上手いこといったらそのうちお披露目します。
chokudaiサーチは、ビームサーチに対する、「時間調整」と「多様性」に対する不満を解消するお手軽アルゴリズムでした。他の不満も解消出来るアルゴリズムもどんどん作っちゃいましょう！
