MM 138

やほーbb @yahoobb_th

順位表 - 第4回 RECRUIT 日本橋ハーフマラソン 本戦 atcoder.jp/contests/rcl-c… 何度見てもこの順位表好きだな

Psyho @FakePsyho

The last marathon qualifier just ended. At the end, we had a three-way fight between @colun, @tanzaku_sub and me. No screenshot of the results, because my last submit broke the scoreboard and it's a complete mess 😂

Psyho @FakePsyho

Uploaded the code to: github.com/FakePsyho/cpco… (same as final solution except minor dead code removal) I'll do the "Post Your Approach" thing tomorrow. Too tired today :(

Blackmath TC @blackmath_tc

@FakePsyho Congrats Psyho!👏 If you ever find your code to be not working, try compiling with warnings 😅 pic.twitter.com/eiGD9hazua

拡大

コルン @colun

ひとまず一区切りしたので、MM137に関してつぶやいて行きます。 真っ先に申し上げた通り、木製の碁石に数字付きシールを貼り付けていったのが僕の初手でした。 そのあと、焼きなまし法を実装しました。 最終的な解法構成は、 焼きなまし法→ビームサーチ→焼きなまし法 になります。 #MM137

コルン @colun

基本的に、ビームサーチで最大の数を伸ばしていって、最後にその連鎖を崩さない様に他の箇所を埋める焼きなましを行います。 最初に焼きなましを行うのは、大部屋での大連鎖の援護射撃が少しでも可能なように、小部屋で飛び飛びの値を予め生成しておくことにあります。 #MM137

コルン @colun

2つの焼きなましは、状態の管理および遷移は同じものを使っています。状態は置く順。遷移は、ランダムに選んだ石の置く順を、前か後ろにずらすのですが、このときに、隣接する八方のいずれかと順序が切り替わるタイミングまでずらし続けます。 #MM137

コルン @colun

前述の説明が少し分かりづらいですかね。変更を行う石がOのとき、隣接八方にある石が大文字、隣接八方にはない石が小文字とします。 AbCdefgHijklmnOpqrstUvwXyz という順序があったとすると、 AbCdefgHijklmnpqrstUOvwXyz AbCdefgOHijklmnpqrstUvwXyz のいずれかへの遷移を行うという意味です。

コルン @colun

焼きなましは変化させた場所に関してのみの差分評価が行えれば良かったのですが、思いつきませんでしたので、毎回全順序のシミュレーションを行っていました。 そのため、少し特殊なシミュレーションも可能でした。 #MM137

コルン @colun

と言っても、バイアスを生じさせる様なあまり特殊なシミュレーションは、むしろスコアを悪くしました。 とりあえず各座標は一度しか出現しないため、置けなかった場合は優先度付き待ち行列に入れて、置ける様になったら直ちに置く様なことのみ、シミュレータに追加機能として持たせました。 #MM137

コルン @colun

焼きなましとビームサーチの両方を解法に組み込む可能性が最初からある場合、焼きなましを先に実装するのがあらゆる意味で有利だなと今回感じました。それは焼きなましはシンプルなものになりやすく、ビームサーチの諸々の調整評価には焼きなましが欠かせなくなるためです。 #MM137

コルン @colun

ビームサーチに関してですが、なるべく外側から詰めていって内側を最後に残す様な部分評価関数を入れました。これは、まだ使っていないマスのXYの各座標の分散（標準偏差の二乗）をペナルティとする（石を置くとペナルティが取れていくので、加点されるのと同じ）のが、比較的簡単で強いです。 #MM137

コルン @colun

少し前から、唯一ハッシュ（＝uniqueハッシュ＝重複除去ハッシュ）とは別にペナルティハッシュという概念をmmlangでは実装しています。そう、今回のTCO予選3連戦は、全部mmlangで参加しています。ペナルティハッシュでは、同じハッシュ値のものが出てくると、除去するのではなく、減点します。 #MM137

コルン @colun

で、先に最後の3〜8手ぐらいに関してのペナルティハッシュを実装しましたが、そのあとに現局面に関する完全なハッシュを唯一ハッシュとして追加しようと思ったら、少しライブラリがバグっていたため一時的にペナルティハッシュとして入れていましたが、最終的にペナルティハッシュ同士の相性等により、

コルン @colun

（続き）なぜか唯一ハッシュのバグが取れた後も、ペナルティハッシュとして扱う方が点数がよくなる傾向が強く出ました。この辺はよく分かりません。 #MM137

コルン @colun

あと、ビームサーチの次の手の候補に関してですが、初手1をどこかに置くとすると、その隣接八方にとっての周囲の統計情報はcount=1, sum=1の状態になるわけじゃないですか。1<=countのセルに対して、sumを添字とした配列の配列へと座標を入れてあげるようにします。 #MM137

コルン @colun

こうしてあげると、たとえばsum==7になっているセルがいくつあって、それは具体的にはどのセルとどのセルとどのセルなのか……が、一瞬で引ける様になります。 #MM137

コルン @colun

で、2手目になりますが、先ほど1を打ったので、次は2を打ちたいのです。なお、さきほど添字はsumでと言いましたが、実際には[2<=count][sum]の2段階の添字で管理してあげます。こうすることで、すぐに打てるのか、それとも周りにもう1つ置かないと打てないのかも管理できます。 #MM137

コルン @colun

こうなってくると、次に2を打ちたいときに、すぐに2を打てる場所が一切存在しないことに瞬間で気付くことができます。そして、今のところsum==1だけれどもcount==1なので横に1つ置けば2が置ける様な場所がどこにあるのかも、瞬間で分かる状態にあります。 #MM137

コルン @colun

mmlang以外でビームサーチを使う場合は、setにタプルを突っ込んで管理してもよいのかもしれません。それでも同じことが出来ます。コピーコスト大きそうですけど。あるいは、mmlangの様にvectorを大量に持たせて同じことをすると、それこそコピーコストが大きすぎて死ぬ気がします。 #MM137

コルン @colun

ぶっちゃけ、こういうデータ構造でビームサーチ局面を管理できた今回の事例を見るだけでも、もはや僕はmmlang以外のどんな言語でももはやマラソンマッチやりたくないです。そこまで何もかもが変わります。 #MM137

コルン @colun

まあそれはともかく、そういうわけで、ビームサーチの次の手候補は、以下になります。 ・次に打ちたい数が直接打てる場所 ・隣に1を置くことで、次に打ちたい数が打てる様になる場所 ・次に打ちたい数よりも1つ少ないものを直接打てる場所 #MM137

コルン @colun

また、ビームサーチの世代管理に際しては、ターン数で揃える様にしました。すなわち、「隣に1を置くことで、次に打ちたい数が打てる様になる場所」を使うことで1世代で2手連打した場合には、1世代休むことでターン数を揃えます。 #MM137

コルン @colun

世代管理にかんしては、「ターン数」で揃えるか、「次に打ちたい数」で揃えるかの、ほぼ2択です。どちらかで揃える場合、もう片方は評価関数の対象にするのが良いです。今回は「ターン数」のほうで揃えました。 #MM137

コルン @colun

なお、どちらでも揃えない場合、両方を評価関数に加えることになりますが、そうするとどちらの局面の方が有利なのかが微妙になったりで調整が面倒だったりするので、今回は揃えました。揃えなくても良いのかもしれません。 #MM137