ALGO ARTIS プログラミングコンテスト2024 夏(AHC035) - Breed Improvement 参加記録
ALGO ARTIS プログラミングコンテスト2024 夏(AHC035)に参加しました。
問題名はBreed Improvement。穀物の交配シミュレーションでした。
結果は提出1024人中9位で、短期AHCでは最高記録。
問題
6×6の畑に種を植えてね。
隣接した作物同士でそれぞれ新しい種を作るよ。
新しい種を作るときは、15項目の評価項目をそれぞれいずれかの親から各50%で引き継ぐよ。
10回のサイクルで至高の種を1つ作ってね。
考察
この問題の元ネタは…アストロノーカじゃな？*1
遺伝時の引継ぎは評価項目ごとに独立だし、突然変異も無いのでシンプル。突然変異が無いうえに複数の遺伝子の組み合わせによる評価も無いということは、子は評価項目単位で見れば両親を上回ることは無いということか。一度最高値が下がると上げなおすことは出来ない。
種60個を6*6の盤面に配置するのが1回あたり0.2秒と時間に余裕はあり、アプローチは自由そう。ただ探索より前に、良い貪欲/ルールベースを見つけるのがとても大事そう。
交配のルール上、初期種の評価項目のベストを寄せ集めたものが理論値となる。となると、各評価項目のベストを持つ種だけが重要で、それ以外は実は考慮する必要が無いのでは？実際はターン毎に6.25%でベストな値が失われてしまう*2ことや、15項目のベストを合体させるのが間に合うかを考えると2位～5位前後までは評価してもいいのかもしれない。
まずは「ベスト（上位）な値を1つ以上持つ種を増やす」「ベスト（上位）な値を複数持つ種を増やす」の方針で、違う長所を持つやつ同士で交配するところから始めてみようか。
とりあえず貪欲で行きたいけど、決める場所の順番はどうしようか。優秀な種は種4つと隣接するよう外周以外に配置したいし、他の優秀な種と交配したい。それはいいんだけど、(2,2)(3,3)と埋めた後に(2,3)と2つ隣接を作ってから埋めるべきなのか、(2,2)→(2,3)→(3,3)と2つの隣接を事前に作らないように埋めるべきなのか。そういう細かいところは全然分からないな。凝った配置を考えてChatGPTくんに作らせようとしたけど、指示通り作ってくれないのでもうExcelで手打ちして渦巻きでいいや。
実装
まずは種の1項目の評価を考える。上位数件だけを評価したいが、最大値は毎回100みたいな決まりは無いので正規化が難しい。今回の関心は順位だったので、そのまま順位を最優先評価にした。1位は10000点、自分より評価が高い種1つごとに評価を半減。に、一応素の評価(0～100)も加えてやる。順位点の減衰率やそれぞれの重みは後で調整すればいいでしょう。*3
次に種同士のペアの評価。項目ごとに各50%で値を引き継ぐが、各種の値を持つ子は平均2つに増えるので序盤は別々の長所を持つ種同士でハイリスクハイリターンな交配をしたい。終盤になると流石に「ベスト値を14個とワースト値を1個持つ種」と「ベスト値を1個とワースト値を14個持つ種」の交配は悪手で、こうなると両方の種の値が高いことにも価値が出てくる。あとは全項目ベストのマージが間に合わないケースを考えても、低い側の値も大きい方がいくらか嬉しい。そんなお気持ちを込めて、項目ごとに[評価が高い種の評価 * 0.8 + 評価が低い種の評価 * 0.2]を取り、全項目分を合計したものを種同士のペアの評価とした。重みとかは後で調整すればいいでしょう。*4
そこまでしたら、真ん中の1つである(2,2)から渦巻き型で外に向かって貪欲に置く種を決めていく。
今回は短期のインタラクティブ問題ということで、デバッグがやや難しい。仮提出しながらテスターを通してビジュアライザを眺めたりコードを眺めたりして、バグが取れたところで提出して263,582,131点。えーと何位だ。4位…4位！？
興奮を抑えて更にビジュアライザをぐっと睨むと、最初の配置である(2,2)の種がイマイチ変なやつが選ばれていると気付く。配置済みの隣接した種とのペア評価をしているのにどうして…。最初に配置する種より前に配置されている種とは？ということで、最初の種はペアでなく単体評価で配置する。これは種の各項目の評価の総和とする。改めて提出すると269,777,633点で順位は1位…1位！？
これが240分のうち114分時点で、方針としては大当たりで間違いなさそう。*5
問題はここからどう点数を上げるかで、評価関数を弄る、探索する、提出ガチャをする、と色々ある。評価関数はターン毎に低い種側の評価も上げていくとか、探索は初手を全パターン試してみるとか、単体で優秀な種の周りから埋めるとか、あとは単純に配置順を変更とか、色々試したがあまり伸びなかった。守りに入って手を縮めないようには注意したが、そもそも伸びる方針が見えなかった。
最終的にはそこで完全に伸び悩み、270,848,464点の9位で終了。
他の人の解法を見て
見ていて気になったもの。
同じ項目が優秀な種同士の隣接をマイナス評価する
これはうちとは逆な方針で、おそらく序中盤を伸ばしやすい方針。ビジュアライザを見ると中心だけ強くて他が微妙ということは稀によくあったので、確かに効くケースはありそう。
最高値との差で考える
1位と2位が大差と僅差なら扱いは違うじゃんという話。
それはそうで、うちではほとんど考慮していなかった。ただ早期に妥協しすぎるのも考え物で、調整は大変そう。
評価カーブを改善する
これはwriter解で、logsumexp関数を使っていた。
毎回お気持ちするのもありだけど、引き出しがあったり性質に慣れておくに越したことはないね。
焼畑
焼きなまし法。うちは上位の種を改善することが最重要だと思ったので、あまり重要でない部分の評価を上げるために中央を捨てるのはどうかなーと思ってやらなかった。適切な評価付けが出来ればもちろん強いだろうけど。
盤面全体でどういう性質を持てば改善に繋がるかがいまいち見えなくて、貪欲を超える盤面全体の評価は難しそうだった。（初手全探索が空ぶったことで、自分が盤面全体の評価を正しく出来ていないことが分かっていた）
盤面全体の評価も単純に総和でいいのか？ペアの評価式自体が全体評価とマッチするか？でうちは噛み合わない式になってたんだろうなぁ。
感想
方針は遺伝アルゴリズムを少し齧っていたことで正解に綺麗に入れたと思った。子が親を超えるために突然変異がある→それが無いということは、とか。*6
項目の評価は頑張って凝った数式を作っている人が多かった中、順位に着目するという手法で足し算と掛け算だけの評価に落とし込んだ。これは最高値との差という考えがあるので局所最適だけど、それでも格段にシンプルな手法で赤パフォが取れたので綺麗にはまってくれて嬉しい。
そういえば今回で入橙。*7途中1位など取ってしまったせいでまた欲が出てきたけど、のんびり続けていきたいですね。
CodinGame Summer Challenge 2024 with Fiverr - Olymbits 参加記録
CodinGame Summer Challenge 2024 with Fiverrに参加しました。
ゲーム名はOlymbits。
オリンピック競技を模したミニゲーム4つを共通の操作で遊ぶゲームでした。
結果はGoldリーグで、全体順位は86/5,237位。Goldリーグ内だと24/980位でした。
ルール
詳しいルールは例によってツカモさんが日本語で要約してくださっています。
codingame:SUMMERF CHALLENGE 2024 ルール要約 - tsukammoの収穫記
ざっくり言うと、役割はゲームによって違いますがファミコン風な上下左右操作です。*1
4つのゲームでバランス良く勝つ必要があります。
最終的にやったこと
貪欲法。評価は[各種目の評価*重み]の総和。
重みは現在のメダル数に応じて軽く（相対的に他の種目を重く）する。各種目で最低6点、出来れば9点強取りたい。あとは終わりが近いゲームは優先される。重みは100/(100+weight)で分母を増やす。分子を減らすとマイナスになったりするので、分母を増やす方が制御しやすい。
種目の評価は全員が各種目に全力で取り組んだら何敗何分になるかで大きく評価して、暫定点や状態（距離など）でタイブレーク用に細かく点を付ける。*2終わったゲームの補充はしない。
スケートは狙っても確実に1位を取れる競技ではないので、初動で3マス動いて先頭を取ったらあとは転倒せずに先頭キープを狙う。下位同士で衝突なり非効率な移動をしてくれればあとは勝ち確。終盤で狙って取れないと悲惨なので、5点までは優先。*3
種目を両立できるかは全然考えてない。ダイビングに専念すると他は後で切り捨てられる運命。
やったけど捨てたこと
原始モンテカルロ法
Bronzeリーグでは使った。Silver以下は1種目だけ全力でやり続けるBotが多く、相手が何処かで手を抜いてくれる前提だと1点も取れずに爆死する。*4
プレイアウトがランダムは明らかにダメダメなので、じゃあプレイアウトのために貪欲も鍛える必要があるのでは？で貪欲を始めて戻ってこなかった。貪欲を鍛えた先のMCTSはまだ可能性はあったと思う。貪欲はMCTSへの組み込みも見据えて相手視点で評価できる作りにしてたし、実際MCTSで上位の人はいたっぽい。
1ターン読みマクシミン戦略
ラスト1日で試したけど、貪欲の方が強かった。
やってみたかったこと
様子見ムーブ
頑張っている人がいない分野で最低限の努力でトップに立ちたい
牽制ムーブ
ダイビングで序盤からコンボしている人は中盤前に徐に参入されると辞め時が分からない
複数手読み
相手の手が読めないので、安易にやれば強いというものではなさそうだった。
主にダイビングで、最終的に他の種目と両立できるかは大事そうなのでやりたかった。
小技
ハードル走
ゴールから後ろ向きにDPすると、各マスからゴールに必要な最低ターン数が高速に求まる。*5
1位争いはゴールまでのターン数で評価するが、2位争いは距離で行う。
スタンによるペナルティは残りターン数も考慮する。*6
上記2点より、1位がゴールするタイミングではハードルの手前で止まるよりハードルに突っ込む方が良い。
アーチェリー
複数手読みはY,Xそれぞれに移動できる距離の絶対値を求めると高速。*7
感想
よく分からないようで実力差はしっかり出る、面白いゲームでした。
下位帯では1種目全振りするBotがバランス良く動こうとするBotを駆逐してしまっていて、楽しくなるのはGoldリーグからだったかな。そこの沼に足を取られて、終盤に割くリソースが削れてしまったのでちょっと惜しかった。
MC Digital プログラミングコンテスト2024(AHC031) - Event Hall 参加記録
MC Digital プログラミングコンテスト2024(AHC031)に参加しました。
問題名はEvent Hall。複数次元の充填問題でした。
結果は1064人中98位。（事前テストは88位）
問題
1000*1000のホールを複数日(D=5～50)、複数の予約(N=5～50)に対して分割して貸し出すよ。
面積不足やパーティションの設置/撤去を減らそう。
考察
高さ1000で千切りすると*1、予約ごとに無駄な面積が0～999発生する。また、予約ごとに1000のパーティションコストが発生する。
高さ500で分割すれば、無駄は0～499に抑えられる。また、予約ごとに500のパーティションコストが発生する。ただし余った幅は捨てることになる。高さの分割線は引きっぱなし、かつ初日コストは免除されるので実質無料。
なるほど、つまり段を増やしまくって面積ロスやコストを減らしましょうという問題？そのためには段ごとの余りを減らすのが必要になりそう。
あとは段数は一旦固定するものとして、高さを先に決めて予約を充填するのか、予約を分配して高さを計算で求めるのか。ここはまず適当にやってみるか。
あとは面積ロスのペナルティが大きいのでそっち特化の緊急解法も用意したい。縦横に面積ロスが小さくなるよう残りスペースを貪欲に切ればデッドスペースはかなり小さくなるはず。
実装
エコ方針で、最終的にやったことだけ書く。
基本的に貪欲で、条件を少しずつ変えながら回す。
1周目、段数を仮定(1～N-1)して貪欲。
全日の予約を纏めて大きい順にソートし、大きい順に配置する段を決める。
優先順は、入る中で空きが小さい段、新しい段、入らず過剰量が小さい段の順。
2周目、小さな過剰*2を認める貪欲をしながら、最善解で使用率の高い1段ずつ割り当てを固定する。
時間がかかるので、最善スコアの段数に対して-1～+3段を試行する。最善を更新したときは範囲もずらす。
大半はこの解法で出てきたのが最終的な回答となる。
3周目、別解で段の容量を一部ずつ先に決めながら貪欲。
容量を1000ずつずらして探索するアホアホ探索、しかも段ごとに容量を貪欲で決めているので、時間の足りなさもありこちらが刺さるのは全体の25%くらいのケース。
一旦仕上げ、ここまでの最善解から、面積不足の日を縦横に貪欲カットする解法で改善できないか試みる。
また、全日を貪欲カットする解法も一応試す。
これでも時間が余ったら、最善解+1段ができないかを焼きなましで試みる。
その段数の最善解をベースに、1予約を別の段に移動、別の段の予約同士を交換、で焼く。
ここまでやって最善だったものを最終解とする。
他の人の解法を見て
上位の基本解法は各段の容量を焼くっぽい。序盤の初期解が悪い時代に割り当ての焼きなましが上手く行かなかったことや、貪欲が弱い時代を引きずってそちらに手が伸びなかった感がある。
感想
他の方針と共存/転換しやすいものだけで場を繋いでしまったので、良くも悪くもそんな順位に落ち着いた。
理論値が出せる極端なケースなども含め、パラメータで向く方針が違うのでどれだけ手広くカバーできるか（時間を注げるか）だったり、あるケースでコストを半減させても相対スコアの低いケースでは無意味という、相対スコアの嫌なところが出やすい問題だったと思う。
爆死覚悟で方針決め打ちしないと今後レートを伸ばすのは厳しいかなぁ。
RECRUIT 日本橋ハーフマラソン 2024冬（AHC029） - Business Simulation Game 参加記録
RECRUIT 日本橋ハーフマラソン 2024冬（AHC029）に参加しました。
問題名は Business Simulation Game。拡大再生産カードゲームでした。
結果は提出833人中83位。（暫定テストでは99位）
あまり上手くやれた気がしないけど、その割にはまあまあ。
開催期間4日強に対してクリスマス＋イブが被ってたし、全力参加できなかった人が多そう。
カップルに恨みでもあるのか？
問題
労働カードでプロジェクトカードを倒してお金を稼いでね。
プロジェクトを爆破するカードや、増資して全ての倍率を上げるカードもあるよ。
考察
MCTSが強そうな問題。でも2000ms/1000Turnか。何はともあれ、まずルールベースか貪欲だな。
平均比率はほぼ[金1:労働力1:残務1]なので、上振れを引いていかないと利益が出ない。増資20回まで…そんなに行けるのか？多くて10回とかじゃない？
心の目で見ると、増資カードを買って使わなければ、コストを増やさないままもう1枚買えるって書いてる。うーん、そこまでする価値あるのか？
分からん。こういうのはまず手を動かす。
やったこと
初日
まずローカルテスターを作る。長期インタラクティブでは毎回やってる。ジャッジとやり取りする入出力の部分を注入する形にすると、ソルバーを標準入出力に依存させずに作れる。お気に入り。
カードのピック（手札に加える）は適当な貪欲で、プレイはルールベースで適当に書いてみる。スコアは平均13K。ちなみにサンプルは平均1K。苦労して稼いだお金で高いカードを買って安いプロジェクトにぶつける、という賽の河原をすることが多かった。そうなると常に1枚無賃金労働や、キャンセルカードを抱えたいわけで…。あ、これもしかしなくてもピック→プレイの順に変えてセットで評価した方がいいな。そうしたら無賃金労働をその場で拾って使えるから、無駄に何かを抱える必要は無い。
というか、サンプルは無賃金労働を999ターン続けるから約1000円なのか。1ターンの価値が上振れ無しで1円ということで良さそう。
2日目～
ピック→プレイの順に変えてセットで評価、を書く。評価値は1000ターン目の見込みスコアを目標にするのが安定かな。
以下評価値*1
・所持金はスコアなのでそのまま。ただし、お金があれば上振れしたカードを買えるし、増資のために貯蓄することも必要。0～30円帯と200～700円帯に追加ボーナスを付ける。
・労働カードは無賃金労働の代わりに使うことで時間を生み出せる。時間は1ターン1円換算で。ただし見込みスコアなので実際の価値より下げておく。
・キャンセル系のカードは分からん。無賃金労働よりは上、2枚目以降は価値が落ちるように。
・増資カードは使うことだけ考える。1ターンの価値が上がるので、残ターン数*増資倍率にすればいいよね。ただ拡大再生産なので、いくらか複利で増えることも含めておこう。毎ターン2%複利くらい？
・プロジェクトは…何？
いや、実際に何ターンかかるか、どういうカードを購入して倒すかが決まっていないんだから評価しようがなくない？早く完了させることによる複利効果とかは…残ターンの評価に仕込んじゃったんだよなぁ。
MNW（マジで何も分からん）
労働カードを使ってプロジェクトを進めることはプラス評価されるべきだから、所持金＞プロジェクト＞労働カードという大小関係にはなるよね。
利益率の良いプロジェクトから片づけたいし、あと複利で回る都合上、小さいプロジェクトを先に片付けたい。
前者については、価値でソートして下位ほど得点を減衰させた。また、赤字プロジェクトは爆破できるので、赤字を減衰させたりする。黒字プロジェクトがある限り全体除去を撃つ必要性はやや薄いので、黒字があるなら減衰率を上げたり。
後者は[無賃金労働でかかるターン数^0.8]をペナルティとし、ターン数が短いものを先に処理したくなるようにした。
・終局間際の詰め
ラストN（持てるカード数）ターン＋αで現金以外の価値を減衰させていく。
・手持ちカードの労働力カーブも評価したい。
効果が2^Nの労働カードやプロジェクトをNマナと定義する。2マナ労働だけではファッティプロジェクトに対抗できないし、8マナ労働だけでは接死持ちである低マナプロジェクトとの相性が悪い。
カーブとは言ったけど枚数を積みたいわけじゃないし、手持ちカードと3,4,5,6マナとの各最小差をペナルティとして付ければいいかな。
やらなかったり没になったこと
・複数手読み
腰が重くて最後まで渋ってしまった。
・終盤に終わらないプロジェクトに打ち込むのを直す
上振れ労働カードを引けば終わる可能性があったり、判定が難しい。最後まで対策できなかった。
・各カードの出現率を考慮する
それを気にする段階まで行ってないと思う。
・プロジェクトの価値を正確に評価する
何も分からん。
・全力労働（全体労働）を使いやすい盤面作り
つまりプロジェクトの評価だけど、それよりもっと基本的な部分が綺麗に動いていないので。
・増資カードの一括使用
上手く回らないんじゃないかという、やりたくない理由を積み重ねてた。
そんなに実装重くないだろうし、最後手詰まりだったんだから試すだけ試しても良かったね。
・増資前の弱いカードの処分
でも使わないと捨てられない。そして使うのは弱い。本当にやるべきなのか？
・手元1000ケースへの過学習をしない
3日目からこれに縛られて、あっちは上がったけどこっちが4桁まで落ちたとか、不毛な調整に走ってしまった感。
インフレ＋終盤の詰めで点数が大きく変わるうえ相対スコア評価なので、正当に伸ばすか、足を止めて相対スコア対策に回るかという択が出来てしまう。いつも後者を選ぶので、システスで順位は伸びるけど何と戦ってるのかよく分からない。
他の人の解法を見て
モンテカルロ系もあるけど、貪欲の評価関数差だけで大きく離されている人もいる。
差が付くとしたらプロジェクトの評価かなぁ。後で見直してみたい。
感想
今回は短めの長期で新鮮でした。
半分がクリスマスと被り、更に全体がコドゲと被っているのはAHC乱立も含めてなんとかなりません？とは思いつつ。
問題も面白かったけど、噛み合いで絶対スコアが数桁変わる問題で相対スコアなので、本質以外の部分と向き合って慌ただしかった感もあるかな。
じっくり本質と向き合ってみたい問題でした。
*1:増資0回として書いています。増資回数に応じて2^L倍する。
トヨタ自動車プログラミングコンテスト2023#6(AHC026) - Stack of Boxes 参加記録
トヨタ自動車プログラミングコンテスト2023#6（AHC026）に参加しました。
問題名はStack of Boxes。積み上げた箱を移動しながら順番に取り出す問題でした。
結果は提出789人中13位。
短期の最高順位を大幅更新でとても嬉しい。
問題
200個の箱が10の山に分かれているよ。
ある箱を移動するときは上の箱ごと動かすよ。このとき箱の数+1のコストがかかるよ。
一番上にある箱は取り出せるよ。
なるべく小さいコストで、小さい番号の箱から順に取り出してね。
考察
複数の山を並べて、小さいものから順に除外して。ソリティア？
いや、階段を作るわけでもないし、妥当でない盤面を経由するので雰囲気が似ているだけか。ソリティアの知見は使いづらそう。*1
それよりも、各山内の大小関係だけ保てていれば順番に取り出せる。トヨタコン頻出のヒープかな。
実行例を見ると、取り出す箱より上を全部除けて箱を取り出すの繰り返し。箱をどう除けるかを改善すれば、とりあえずスコアは伸びるかな？適当な貪欲を組んで、どういう方針が良いか探るところからか。
あとは本番中のメモをそのまま掲載。
動かした箱の個数＋１の体力を消費
・動かす箱の個数を減らしたい
・動かす回数を減らしたい（１個２回は２個１回より重い）
・動かした箱の再移動を減らしたい
→箱の最小値が一番大きい山に動かす
・転倒数が減るよう移動する
→箱を数回に分けて動かす
→次に使う箱は別の山へ
動かすルール
・上からチェックする
・各列の最小値より小さいものが出たら、それだけを別の列に退避する
（それより上を予定移動列に移動、それを任意の列[最小値が最小の列]に移動）
・最後まで見終わったら、残りを何回かに分けて移動する
・最大値を一番下にする？最小値を一番上にする？
実装
まずは実行例と同じ方針で、動かす先の山だけ変えてみる。
箱の数を平均化する方針はどうかな。
→1,319,252点。これより上に同点数集団があり、もっと良い方針がありそう。
転倒数は減らしたいけどそれより目先を追って、直近使いそうな箱を塞がないことが大事か？最後まで使わない山、つまり最小値が大きい山にどかす。
→1,356,657点。同点数集団のほぼ最高帯（47位タイくらい*2）。強豪の面々もここにおり、良い方針を引いたっぽい。
全ての箱を一度に動かす必要は無い。基本方針はこのまま、複数回に分けて動かすことを考える。
ヒープもどき、かつ小さい箱から取り出すルールなので、「各山の上N枚が最小値からでソート済み」な状態が良い状態と見定める。下側や大きい数の転倒数はそんなに気にしてもしょうがない。
箱を除けるときに、ある箱を単独で任意の山*3に移動して良い状態を作れる/保てるならそうしてみる。それ以外の箱は変わらず、最後まで使わない山へ移動。
単独移動の候補山が複数ある場合、少し試した感じだと山の最小値を下回らない範囲で最小値が最小の山に動かすのが良かった。6 Nimmt!はマラソンの役に立つ。
→1,393,545点。11位。バグ取って1,399,894点。うへへ。
大量移動する側を効率化することを考える。例えば半々で2回に分けて移動すれば、上半分と下半分を交換できる。これは試した感じ、移動する中の最小値を一番上に持ってくるのが良かった。ただ1個だけ移動するのは若干筋が悪く、許容する移動個数の下限を増やしていくとスコアもじわ伸び。
→1,400,609点。大台突破。
もうルールベースで出来ることはやりきったか？シミュレーションして良い分割位置を探す。シミュレーションでは爆発防止のため分割移動しない。実スコアで評価したが、これも分割しすぎにペナを入れた方が良さそう。
→1,406,616点まで。瞬間風速6位。
残り1時間。ここからビームサーチを試みるも良い結果が出ず、13位で終了。
他の人の考察を見て
ソリティアよりはハノイの塔らしい。確かにそっちの方がまだ解法を流用できそう。窮屈さが全然違う＆最小を除外できるので、やっぱり流用する意味は薄い気がするけど。
最上位帯を見ると、完全にソートしてしまうらしい。
1山を9山に分けて戻して。コストは平均2個ずつ移動するのに3*10、戻すと20個+9回で29、これを10山で(3*10+20+9)*10で590ペナの9410点、150ケースで1,411,500点（本番6位相当）の計算。
上下の大小関係は50%なので、一度に動かせる期待値が約2個という感じか。もうちょっと少なそう？*4
なるほどなぁ。これは確かに強いし、方針を決める時点で高得点が見える。
ただ実際はどうソートするの？とか、それでもソートしきれなかったらどうするの？といった部分を詰める必要があり、それを本番で仕上げきった人達の強さもあると思う。
私は短期コンではこういう駄目だったときにリカバリが難しい方針には手を出さないのだけど、検討自体投げ捨てちゃったので計算まではしても良かったかなと思った。回数側のペナルティが膨れて筋が悪そうと間違っていたので。
一方非ソート勢の中ではかなり良い順位。差別化できた点は、箱を除ける際に小さい箱を別の山に退避する、をルールベースで書けたところかな。ここはヒープ(ソート)と問題の性質を意識したことで良い状態を導き出し、ルールベースで十分良い結果が出るという答えに辿り着けたと思う。*5
感想
自分が得意とする、自明（そう）の中から答えを探し出すという勝ち方を綺麗に出来た。ビームまでは撃ち切れなかったけど。
摂動を入れて焼く、もよく見かけるけど地味にやったことが無いのでいつかやってみたい。
実装苦手マンが中盤で1ページ目に入ったことと最高スコアで30msという実行速度からルールベースがバレるかと思ったけど、案外大丈夫だった。WJの長さでカモフラージュ出来た？
RECRUIT 日本橋ハーフマラソン 2023夏(AHC022)参加記録
RECRUIT 日本橋ハーフマラソン 2023夏(AHC022)に参加しました。
問題は盤面構築＋推定問題。
結果は提出1070人中、40位（事前テスト51位）でした。
問題
対応が不明な入口と出口があるよ。
出口側の世界（トーラス空間）全体に空調を置いて温度調節して、温度を元に出入口の対応を求めてね。
不正解数や温度測定数&距離、温度の崖が少ないほど高得点だよ。
ちなみに測定温度には、平均0、標準偏差1～900の正規分布誤差が付くよ。
考察
正規分布の95%信頼区間とかを使って統計でなんとかする感じかな。複数の測定はベイズ推定っぽい。統計何も分からん、ベイズの表面だけなんとなく理解してるつもりの感じなので、統計入門がてらちょっと頑張ってみる。ちなみに「独立した確率を順に掛けていけば事前確率から事後確率が求まって、それがつまり…ベイズってやつなんだろ？」くらいの乱暴な理解です。間違ったことを言っていたら、優しくご指導いただけると幸いです。
さて、出口を特定するためには温度に特徴を持たせる必要がある。ぱっと思いつくのはQRコード。ソースコードと混同しそうなので、以後"模様"と呼ぶ。しかし出口が密集している場合は、模様同士を重ね合わせてそれぞれがユニークな模様になるように組まないといけない。*1 また、模様は温度の分解能（温度が何段階か）とマス数で表現できるパターン数が決まる。何段階目かが離れていたり、S（誤差の標準偏差）が大きいと、離れた温度同士の隣接を強いられることがある。この辺りをクリアするのは大事そう。
他の温度配置としては、全体で大きな1つの模様を形成する方法。初期段階で浮かんだのは、チェック模様を作り、線の間隔やタイプ（二重線や太線など）で何処の線かを知る配置。この時点では必要な温度差や測定が分からず、配置コストや測定コストは感覚で考えている。
測定は、出入口の対応を得ること、そのために第一候補と第二候補以降の確率に大きな差を付けることを目的とし、より多くの情報が得られるように。黒いのは直吊りするから占わなくていい。*2
入口に対応する出口を絞り込んでいって、ある程度絞ったら組み合わせまで行けたら上等かな。*3
温度差は、段階ごとに4S離すと誤認識には誤差2Sが必要で、つまり95%で誤認識が発生しないことになる。*4現実的には4S離すのは大変で、2Sになることも多いかな…。というか、S >= 512だと、そもそも2Sも差を付けられない。
実装
まずは任意の誤差が出る確率を求めるところから。注意点として、0や1000で丸められること、ケース生成時の端数処理方法も考慮する。検索したりchatGPTに聞いたりしながら、CDFというやつを使えばいいことは分かったので、注意しながら実装する。ここは大事なので、単体テストも組んでしっかりやる。正しい値のソースにはkeisanを使った。初期考察から終盤までずっとお世話になった。*5なお、うっかり新ジャッジでしか使えないライブラリを使い、提出時には確率を埋め込む形に変更した。
サンプルコード同様に10℃差を付けるコードから始め、下記グラデーション配置も試す。全体に満遍なく温度差を付け、配置コストを最低にするにはこんな感じだろう。計測は出口＋4近傍で、おおよその位置は分かるが4近傍隣接や斜め隣接などには弱いと分かる。遠くの山や谷を測定すればそれでも識別出来そうだが、誤差が多いと無理そうか。大きめの崖が必要なのかもしれない。あとは縦横に線を引いてグリッドも作るが、あまり芳しくない。簡単な実験はここまで。
ちなみに測定は、入口を固定して出口を特定する探索を行う。まずは各出口の相対尤度*6を1.0とする。これに、出口ごとにその測定結果が出る確率を掛けていく。…と、値がアンダーフローして全てが0.0になってしまう。そのため、新しい確率を掛ける際には事前確率のMax値で割ることにした。つまり、今回測定前の最尤値(?)を1.0とした相対値になる。絶対確率を求めるときは、相対尤度の総和に対する、ある出口の尤度の割合を取る。これで良いのか訝しみつつ、ここはそんな感じ。
測定位置は、出口の尤度を重みとして、測定位置の温度の重み付き分散 / 計測コストを評価にした。候補を半々に分けられる方がいいよねというお気持ち。400℃vs600℃より200℃vs700℃が優先されやすいなどの良くない部分も感じつつ、最後まで位置決めはこれで通した。
そして、ある出口の絶対確率が0.999に達したら確定とし、測定を終える。回数オーバー（この解法の場合は入口ごとに100回）でも終える。0.999は一見高く見えるが、0.999^100は90.5%程度なので結構攻めている。入口と出口の対応は1:1に限定していないので、組み合わせによる補正も得られていない。
模様作りを開始。下図のように、出口と4近傍の計5マスを4段階の温度に設定する。4^5=1,024なので、余裕を持って割り当て出来る。模様同士が重なる部分は両立させる必要があるので、カツカツだとどちらかの模様を壊すことになる。
また、中央セルをチェックサムにすれば計測誤差に強くなるはず。*7
これだけでは温度ムラが大きく配置コストが大きいので、同じ温度が固まるように配置したい。配置コストを下げるための大きい配置は…さっきやりましたね。グラデーションを目標にし、目標や配置済みの温度との差を評価にして貪欲する。そして適当に4近傍との温度を平均化する処理を何回も回して温度を均す。*8*9
時系列が逆転するけど、このままチューニングの話も。上図のような十字型では隣接するセルとの大きな温度差を吸収できない。なので隣接ではなく2マス先を使うと温度差を吸収しやすく、スコアが増加した。最終的には全てのS <= 25のケースで採用された。
ちなみに、測定位置は模様の構成部分に限定しない。*10万一の模様重複対策も兼ね、模様外でも利用できるなら利用してねのスタンス。
ここで初提出。Sが大きいケースに弱いのは覚悟していたが、1位の25%程度の相対スコアしか出ない。相対スコアの内訳を調査したい要求を抑えつつ*11、別の解法にも着手。
上図は最終的に採用されたパターン。左の方が小さいS向けでS={36, 49}、右側はSが64～121の全てと、144～841の一部ケースで採用された。まず足元の測定で自分が属するエリアを知って、その後隣のエリアの温度や境界位置を調べに行く。
境界位置をはっきりさせたいので、温度はある程度の崖が必要そう。温度差は抑えたいが、時に明確な温度差を引き立たせて武器にすることも出来る。なんか聞いたことのある話だなと思ったら、ラーメン発見伝のつけ麺の話だった。良い本なのでお勧めです。
このパターンについてはそんなに語ることもないので、次のパターンへ。の前に、コストについて。Sが上がると温度差も大きくする必要があり、設置コストは指数的に上がっていく。一方で測定コストは、今までのパターンだとN（出入口数）やL（盤面サイズ）に依存するくらいで大体線形。それなら、設置コストを測定コストと同程度まで下げて、それにより測定しにくくなって測定コストが上がるのは構わない、とするのが賢そう。*12幸い今回のtesterは、各コストも出力してくれる。1000ケース回した結果をExcelで表にするとこんな感じ。
S（横軸）が200以上で設置コストが重く、特にSが400以上は測定コストを倍にしてでも設置コストを軽くしたい状態。0と1000が4つ隣接するだけで4,000,000も設置コストがかかるのに、4,000,000くらいまで設置コストを下げる方法なんてあるのか…？
あったわ。
1か所だけ高温にすると、設置コストが最大4,000,000になる。測定は各出口から高温座標への相対座標だけ調べればいいし、対応を1つずつ決めるなら最有力候補の検証だけすればいいのも計算量に優しい。*13
最大100:100の対応を調べるが、対応が終わったものを除外すると約5050ペア、平均半分で見つかると考えると更に余裕がある。*141測定で特定出来るわけではないのでSが大きいと厳しいが、とにかくSが大きめのケースをカバー可能になった。
ただ回してみると、Nに対して測定コストが異様に多いことがある。*15ビジュアライザで追ってみると、高温部分を測定したのに誤差でハズレと判断され他の候補に移ってしまい、そのまま他の全てがハズレだと思うまで戻ってこないようだ。その時長距離の測定が入るのでロスが大きい。そこで、この解法パターンの時だけは出口に対応する入口を探すことにした。また、測定は短距離のものから行う。こうすると序盤にロスが出ても距離が短い測定で1周するだけなので、ロスが小さくなる。長距離の測定ならば既に候補数が減っているので、このロスも怖くない。
これで解法は一通り出そろい、あとはチューニング。
最後の解法は出口に対応する入口を決める都合上、誤答があると入口が浮くことがある。*16そこで他の解法も含めて、浮いたものや自信が無い回答に対しては余りから再度選び直して割り振ることにした。単純な出力違反回避と、消去法運ゲーによる誤答数軽減。追加測定とかもして良かったんだけど、体力不足でそこまで出来なかった。
最終的なコストはこんな感じ。もうちょっと設置コストの高い天才解法があるかと思ったけど、見つからなかった。
あとは目ptunaして、S、N、Lに相性の良いパターンを選んだりしておしまい。
他の人の解法を見て
トップ層を見ると、1～少ない点だけ温度を上げる（下げる）方針はそのまま、割と崖は無くしているように見える。測定が重なれば、僅差の温度差まで見抜いてしまえるということか。うちでは似たことをしても改善されなかったので、測定との噛みあいかなぁ。
それから入口ごとに個別に推測ではなく、組み合わせで評価している人も多い。これは精度が良くなるのは当然。
あとは測定の位置決めかな。統計に基づいてやってる人もいて、これも強いのは当然。
色々調べたいけど、パラメータが多様なことや相対スコアがあって、何が強く効いているのかいまいち分かってない。＋知らない統計用語が飛び交っていて、流石に全てを追いかけるのは厳しい。理解できそうなものからコツコツ調べていく。
調べておきたいキーワード
・対数尤度
感想
大層な手法は使わなかったけど、すごくマラソンしたという感想。1つの手法を突き詰めた人も多いけど、私は無数の配置を検証したので無限に疲れた。多分まだまだ出来ることがあるので、人生のハーフをマラソンできる。
問題は正規分布の扱いがちょっと大変なものの、何を求めたいのかは分かりやすいので調べながら参加することも出来て楽しかったです。
*1:実際は同じ模様が複数個所にあっても、模様外の何処かで判別できるので致命的ではない。
*2:占って白が出ても、囲いと言われるので面倒。
*3:行けませんでした。
*4:つまり5%で発生するということで、ある程度はあるものという覚悟が必要。
*5:今回以外でも、組み合わせや順列数の計算などによく使う。
*6:尤度=確率そのものではないが、確率に比例した値とする。したい。
*7:結局やらなかった。
*8:もちろん、模様を構成するセルの温度を変えてはいけない。
*9:序盤は順番の影響を受けないようダブルバッファを使い、終盤は微調整のため使わない。
*10:最初何回かは限定する。
*11:これコンテスタント側が使える手段を使うのは何も間違ってないけど、不毛なのでなんとかなりませんかね…？
*12:自由にコントロール出来るものではなく、良い配置を考える必要はある。
*13:別の手法は全座標が対象なので、まじめに全部は計算しきれない。
*14:測定は最大10000回。
*16:回答で出口は複数回登場してもいいが、入口は必ず1回ずつ使う必要がある。
CodinGame Spring Challenge 2023 参加記録
CodinGameのコンテスト、Fall Challenge 2022に参加しました。
お題はマルチエージェント資源回収ゲームです。
結果はGoldリーグ400人中308位で、全体では5290人中403位でした。
問題
ツカモさんが問題要約を書いてくださいました。
考察
距離が遠いほどChain強度が弱くなるので非効率なうえ、相手よりChain強度を強くできないので簡単に殺される。原則自分の方が近いリソースしか安全に取れない感じ？ それだけだと勝てないので、隙を突いて相手陣から少し取るとか、Chain強度が相手と同じで済む場合は踏み込むとかが必要そう。
ルート構築は最小全域森ド安定。
やったこと
今回は意地でもジャッジ解析に依存したコードを書かないことを決意。
戦略としては、卵を取って蟻を増やす→増えた蟻でクリスタル回収を雑に行う。蟻負けが無くなるくらいまで卵を優先させたが、卵優先期間が長すぎたかもしれない。
あとは今の蟻数で作成可能な最小全域森を作り、ビーコンを全セルに同強度で置く。
やって没になったこと
根側のビーコン強度を葉側に移す
蟻が先に進まない対策だが、短距離の接続が弱く&途切れがちになるので没。
Chainの太さ毎に探索して最善を採用
近場のリソースを取り終わっては大移動を繰り返し、かえって効率が悪いので没。
相手のAttackChainを考慮する
攻めっ気が全然無くなり、大移動も発生しがちになったので没。
感想
クリスタルが1山だけなど、偏った盤面が生成されることも多かった。そのため他の盤面だと強い方針が邪魔になることも多く、結局最初の方針から大きく変わったことはしていない。閾値やタイブレークの変更で強化された感じ。
ゲームAIを作って強化したぜ！という気分にはあまりならなかったので、そろそろ何かに全力投入をしたい。
