Marathon Matchの問題の概説とノウハウについてのまとめ

コルン @colun

で、最後に適切なメタヒューリスティクスを探す。 ノーフリーランチ定理というのがあるけれども、実際はマラソンマッチで出題される問題は種類が少ないので、大多数はビームサーチか、焼きなまし系っぽいので解ける。

コルン @colun

遺伝的アルゴリズム使っても良いよ？？

コルン @colun

とりあえず、手順の探索の場合はビームサーチが良い場合がかなり多い。 手順の探索じゃない場合は遺伝的アルゴリズムとか焼きなましとか。

コルン @colun

なのでマラソンマッチのメタヒューリスティクス選択には、ノーフリーランチがどうのとか考えなくて、わりと愚直に問題タイプに合わせて決め打って良いぐらいある気がする。

コルン @colun

と、ここまでで要するに、「評価関数」と「どう探索するか？」と「メタヒューリスティクス」だけ分かれば、マラソンマッチはだいたい行けるっぽい感じになってきた。 あとは「調査」だとか「方針の立て方」だとか「定数倍高速化をどうやるか？」ぐらいが分かれば、あとはレッドコーダーになるだけ。

コルン @colun

なんだけれども。。。 口で言うのは簡単だけど、これ教えるのは確かに難しい。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

純正ビームサーチも純正焼きなましもあんまり強力だと思ってないし、最後まで使ったことはないけど、「こういう系統が使える」というレベルの話であれば十分使えるし、メタヒューリスティックそれくらいの決め打ちでも評価関数設定が妥当ならRedは軽く到達しそうな気がする

コルン @colun

うん、まぁ、chokudaiさんの言う様に、純正である必要性はまったくないし、自分に合ったメタヒューリスティクスを工夫していけば良い。 ただ、適用するメタヒューリスティクスの種類ってそんなに多くないので、そうやって工夫したメタヒューリスティクスは色々な問題に適用できる。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

まぁなんか最近はメタヒューリスティックスで躓く人ってあんまり多くない気がしている。というか何でビームサーチが前回のマラソンであんなに当然のようにメジャーになってるのかがまったく把握出来てなくておどおどしてる。もっと偽DPっぽいの使う人多かったと思うんだけど（自分も好きだし

コルン @colun

あと、ハッシュでの重複探索除去の話とか、評価文脈の保存の話だとかが抜けてるな。。。

コルン @colun

@chokudai それは、偽DPとハッシュで重複除去したビームサーチが等価だからです。

コルン @colun

（「ナンダッテー」って聞こえてくる気がするw

コルン @colun

完全等価というと、語弊があるな。。。偽DPでできることは、ハッシュで重複除去（類似除去）したビームサーチでだいたいできてしまう。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

@colun 等価かどうかと浸透率ってそんな関係ないような？

コルン @colun

@chokudai 浸透率っていう話だと、Psyhoさんが少し前（TCO13MR2よりも前）のマラソンマッチでビームサーチって名指しで言っていた気がするので、それが原因の様な気が。。。

コルン @colun

@chokudai あと、日本国内に限った話だと、僕もビームサーチビームサーチ、最近は言って回っていますし。。。（ぇ

コルン @colun

みんながビームサーチ使う様になって、個性が失われて行くのは色々と残念ですが。。。でも個性は評価関数や「どう探索するか？」（僕は探索の文脈と呼んでいるけど、適切な専門用語がわからない状態）で出してね？　ってだんだんなっていくと思う。

コルン @colun

そもそも技術を競っているので、個性をかなぐり捨てていった先にしか個性は無いんじゃないかなぁ、、、と思います。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

colunさんみたいに、偽DPみたいなのも、自分のビームサーチ亜種も等価、みたいな感じに解釈してる上でビームサーチ、って言うのはいいんだけど、個人的には探索順って凄く大切にしてるし、その上で一番上から探索って大体の場合において弱いので、あんまり纏めたくなかったり

コルン @colun

（今回、僕もPsyhoさんもainu7さんもyowaさんもtomerunさんもビームサーチでしたからね。。。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

これはこういう問題だから、上からビーム幅決めて幅優先探索すればいいんだね、って感じになった時に、探索順で死ぬことってしばしばありそうで、なんかもやっとするなぁ、みたいな感じです。前回マラソンも（ちゃんと検証してないけど）純正ビームサーチだと多分３位だし

コルン @colun

んー、、、chokudaiさんが謎なことを言っている。。。chokudaiさんのビームサーチ亜種が優れているのは時間管理のみだと認識していたのですが、違うのだろうか。。。絞った場合に直近の手の多様性が上がるって話かなぁ。。。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

@colun 時間管理が楽なのは好きな理由の１つではありますが、本命は解の分散の上昇ですよー？　もちろん意図的にそういうチョイスをするような実装じゃないですし、運任せになりますけど、ローカルで1000ケース3点くらい違ったと思います。

コルン @colun

500→500→500→END って純正ビームサーチでやる代わりに、chokudaiさんは、 16→16→16→END を何度も繰り返してるという認識なのだけれども。

コルン @colun

純正ビームサーチだと、ビームが類似局面で満たされた場合に、各類似局面の最善手が一致するので、ビームの多様性が失われる。