2023-12-02

CPU自体が準光速で動くことで計算時間を短縮するコンピューター【いろいろなコンピューター Advent Calendar 2023 1日目】

この記事はいろいろなコンピューター Advent Calendar 2023(さっき作った)の1日目の記事です。

背景

さて、昨今のCPUはどんどん高速化し、クロック周波数も5GHzを超えることは珍しくなくなりました。一方で、ここまで高速化すると問題になるのが光速です。

5GHzというのは50億分の1秒に1サイクルということなので、この間に光は真空中でも60mmしか進むことができません。媒質中では屈折率に反比例して遅くなるので、例えば屈折率1.5の光ファイバーがあったとすると、40mmほどしか進めません。

一方で、単位体積あたりに詰め込める計算ユニットやメモリセルは有限なので、大きな並列度を持った計算機を作ったり、大容量の記憶装置を持ったりするには、それに応じた体積が必要です。しかし、光に限らずあらゆるものは真空中の光速を超えることはできないので、大きくなればなるほど光速の制約がきつくなります。

記憶装置と光速の壁

簡単のため、CPUは大きさを持たず、空間中のある1点にあるとします。このCPUからアクセス要求をだしてからnサイクル以内にデータが帰ってくるには、アクセス要求とデータ返送が真空中の光速で到達するとして、メモリセルはCPUから $n*60/2=30n$ mm以内*1になければいけません。したがって、半径 $30n$ mmの球に入るメモリセルであることが必要条件となり、半径 $30n$ mmの球の体積は $\frac{4}{3} \pi (n * 30) ^ 3 \approx 113097.33n ^ 3$ mm³となります。

今、1mm³あたり1GiBのメモリを積めると仮定します（stacked DRAMの密度はたぶんこのくらいのオーダーになるはず、このあとの話的には定数倍が変わるだけなので、1MiBでも1TiBでもよいです）。すると、nサイクル以内にアクセスできる容量は約 $110n ^ 3$ TiBとなります。

全世界のデータ量が約100ZiBだとすると、これをすべておさめたメモリにアクセスするには半径約30m必要で、およそ1000サイクルかかることになります。今は全世界分で1000サイクルなので大したことはないですが、今後も人類の扱うデータ量が増大していくと、（メモリの3次元的な密度上昇が追いつかなければ）必要な体積とアクセス時間も増大していきます。

すべてを収めるメモリの大きさはどんどん大きくなり、やがて地球サイズを超え、太陽系を飲み込み、はるか星間空間、銀河系まで埋め尽くしていくことになります(もっとも、現在の物質密度で太陽系いっぱいにメモリを配置すると、ブラックホールが発生してしまいますが、ここはなんとかするとして)。こうなるとメモリアクセスのレイテンシーがあまりに大きくなり、1データにアクセスするのに年単位あるいはそれ以上の時間がかかってしまいます。これではなにか1回計算しいてる間に、寿命が尽きて死んでしまうことが多発し、人類は滅亡してしまいます。

コンピュートフローアーキテクチャ

この解決策として、本記事ではデータがやってくるのを待つのではなく、CPU自体を計算機利用者とともに光速に近い速度で動かすことで、大幅なアクセス時間削減を実現する計算機アーキテクチャを提案します。

まず、計算機利用者と利用するCPUを、光速に近い速度で移動できる宇宙船に搭載します。CPUはメモリセルに向かってアクセス要求を出す代わりに、自分でメモリセルのある場所まで航行します。

すると、計算機利用者とCPUからみると、メモリセルに到達するまでの主観時間は、相対論的効果によりメモリセルから見た時間より短くなります（追記: CPUから見ると、ローレンツ収縮によりメモリセルまでの主観距離が縮み、メモリセル側から見るとCPUの時間の進みが遅くなって見えます）。光速に近ければ近いほどどんどん主観時間は際限なく短くすることができ、これにより計算が高速化され、計算機利用者の寿命が尽きてしまうことを防ぐことができました。めでたしめでたし。

このアーキテクチャをコンピュートフローアーキテクチャと命名することにします*2。このアーキテクチャの計算機の構築にあたって、私の許諾等は不要です。作れるならな！

*1:通信が往復するので/2している

*2:データが流れるように移動しながら計算していく、データフローアーキテクチャのアナロジー

2022-12-04

架空伝統ゲーム「机戦」のAIを作るその1 【ボードゲーム・パズルプログラミング Advent Calendar 2022】

この記事は「ボードゲーム・パズルプログラミング Advent Calendar 2022」3日目の記事です（遅刻すみません）。

adventar.org

架空伝統ゲーム「机戦」とは

創作上の異世界ファイクレオネで遊ばれている（という設定の）伝統ゲームです。日本机戦連盟では、それを実際に遊べるようにする様々な活動が行われています。

sites.google.com

今回から、机戦のAIを作っていきます。

今日の成果

リポジトリを作りました。
- もう半分くらいできたといっても過言ではありません（過言）。 github.com
- リポジトリ名は東島通商語（という架空の言語）でのこのゲームの名前 cetkaik と AI から取りました（お気に入り）。
ランダムプレイヤーを実装しました。 github.com 状態遷移が複雑で、ランダム要素もあるため、既存の実装GitHub - cetkaik/cetkaik_full_state_transitionを活用しています。
単純に役を作れるなら作る、駒をとれるなら取る、という戦略を実装したAI (greedy)を実装しました。 github.com
cetkaik_full_state_transitionのバグを発見しました
- 踏越え後の可能な行動をリストアップすると、非合法な行動が入ってしまうバグがあることを発見しました。近いうちに id:hsjoihs が直してくれるそうです。

今後の展望

踏越えルール等により、手の可能性が多く、何手も先まで探索することは非現実的です。モンテカルロ法を利用したり、評価関数を実装したりすることにより、現実的な計算量で戦略的に行動するAIを作っていきたいです。

2021-12-19

ととりにゃああつめて早し最上川それにつけても金の欲しさよ - あるいは、ととりにゃあの語感の良さについて【ととりにゃあ Advent Calendar 2021 Day 19】

ネタ

こんばんは、そすうぽよです。この記事はととりにゃあ Advent Calendar 2021の19日目の記事です。

adventar.org

概要

まずは、こちらのツイートをご覧ください*1。 https://twitter.com/totori_kpr/status/1472143266753953795

2021年12月18日現在、ととりにゃあさんの名前は「毎日進捗」となっています。しばしば「毎日進捗ととりにゃあ」とフルネーム（？）で呼ばれることもあるようです。

毎日進捗ととりにゃあ
— olphe (@_olphe) 2021年8月15日

ツイート本文は「毎日懇親」となっています。以下のように、Twitter上ではしばしば「<ここに四字の熟語が入る>ととりにゃあ」として親しまれています。（このパターンに収まらないツイートもありますが）

https://twitter.com/totori_kpr/status/1469494096859660288

全部最強ととりにゃあ
— ドラ@ (@u_yeiyei) 2021年12月10日

入国禁止ととりにゃあ
— 毎限遅刻 (@pu__Ne) 2021年11月30日

形而上学ととりにゃあ
— ねぼこ (@nebocco27) 2021年11月28日

https://twitter.com/totori_kpr/status/1464120109190975491

六法全書ととりにゃあ
— 毎限遅刻 (@pu__Ne) 2021年11月21日

疾風怒濤ととりにゃあ
— しゃく(Suunn) (@dem08656775) 2021年11月6日

猪突猛進ととりにゃあ
器物損壊ととりにゃあ
一汁三菜ととりにゃあ#いろいろなととりにゃあ
— そすうぽよ (@_primenumber) 2021年9月23日

これらのツイートを読むと、妙に語呂が良いことに気付きます。

「ととりにゃあ」は五音なので、五・七・五のリズムの中に取り入れやすくなっています。これまで取り上げたツイートは、そのほとんどが四字の熟語が七音や、四音+四音になっており、七・五のリズムが語呂の良さを与えているように思われます。

主題

これを拡張して、ととりにゃあを便利な五音として乱用していこうというのがこの記事の目的です。既存研究としては、

「最上川」を五音として使う

dic.nicovideo.jp

もともとは漫画・アニメ「日常」らしいですが、現代ではしばしばツイッター等で観測することができます。元の句は松尾芭蕉の「五月雨をあつめて早し最上川」。

「それにつけても金の欲しさよ」を下の句（七・七）として使う

狂歌 - Wikipedia

江戸中期に流行ったらしい。どんな優雅な上の句も破壊できるパワー下の句。

「メイクアメリカグレートアゲイン」

トランプ元米大統領のスローガンが実は下の句になる。どんな優雅な上の句もトランプの顔がちらつくようになってしまう。

ということでこの記事のタイトル「ととりにゃああつめて早し最上川それにつけても金の欲しさよ」は「ととりにゃあ」と「それにつけても金の欲しさよ」を「五月雨をあつめて早し最上川」と悪魔合体させて作った句です。

実践

ではドンドン行きましょう。

素晴らしい毎日進捗ととりにゃあ

毎日進捗、してますか？

使います伝家の宝刀ととりにゃあ

元ネタ:

電子レンジで何分温めたらいいかわからない？wフッフッフw心配することなかれwwこんな時にも役に立つのが競技プログラミング、伝家の宝刀†二分探索†を使わせていただきますぞ！wwwまずは時間を(0+2e9)/2=1e9分にセットして……\ﾎﾞﾝｯ/グオーーーー！！！！！！！！家が燃えてしまった……(悲しい)
— のいみ (@noimi_kyopro) 2020年1月28日

ミカヅキモおこづかい帳ととりにゃあバチカン市国液体窒素

元ネタ:

ねこ、座布団、セガサターン、ミカヅキモ、おこづかい帳、バチカン市国、液体窒素、週刊誌、消化器系、ミソサザイ、チャイルドシート、釈迦三尊像、瞬足、Anitube、緊急脱出用出口、レレレのおじさん、大憲章、カヤック、千歯扱き、感情、陸軍の統帥権など
— しゃく(Suunn) (@dem08656775) 2019年6月10日

ドラムには、ととりにゃあさえないんだな…

ととりにゃあ墾田永年私財法
ウマ娘プリティダービーととりにゃあ
あたしンちグラグラゲームととりにゃあ
俺でなきゃ見逃しちゃうねととりにゃあ
ととりにゃあ人には人の乳酸菌
大型で非常に強いととりにゃあ

まとめ

ととりにゃあの語呂、良すぎ

*1:飯テロの意図はありませんよ、本当です

2021-12-14

マナ回路設計と魔術アーキテクチャ【存在しない技術 Advent Calendar 2021】

ネタ

この記事は存在しない技術 Advent Calendar 2021 - Adventarの14日目の記事です。

この記事はあなたのお住まいの世界には存在しない技術をもとに記述されているため、あなたのお住いの世界ではご利用いただけません。

マナ回路前史

近代以前は、魔術を発動できるのは人間、それも多くのマナ*1を備えている人間に限定されていた。これは、まず魔術を発動するには、一定以上のマナの密度が必要であるが、マナを蓄えられるのは人間に限られていたためである。

しかし、近代になり、マナを遮断する材料(断魔体)が発見されると、それを用いて任意の場所にマナを集めることが可能になった。さらに、マナを集めた空間を圧縮することにより、マナの密度を魔術を発動するのに十分なだけ高められるようになると、魔術を発動できる機械である魔術機が登場した。

最初期の魔術期は発光、浮遊・移動、加熱・冷却といった単純なものに限られており、またその魔力も弱いものであった。大きな魔力を扱うにはとても巨大な魔術機および、それに足るだけのマナが必要となるため、動力としての利用は蒸気機関の隆盛により小規模なものに限られるようになった。

一方で、微弱な魔力でよければ、小さな機構と少量のマナで魔術を発動することができ、小さな機構であれば微弱な魔力でも制御が可能である。そこで、微弱な魔力で制御できる魔術機を複数並べ、これを連鎖的に、繰り返し発動できる魔術機が作られた。マナを供給する限り半永久的に動き続けることから、マナ回路と呼ばれている。

マナ回路基本素子

マナ回路は、魔術を発動するのに必要なマナを圧縮する"圧縮機構"と、発動する魔術を決定する"発動機構"から構成される。圧縮機構は、筒状の空間に集めたマナを板状の断魔体で押すことで圧縮する機構がよく用いられる。

念力はマナ回路で最もよく使われる魔術で、これによりほかの圧縮機構を制御する。

念力により単純に魔術を発動するだけでなく、圧縮機構を無効化したりすることでより複雑な制御を行える。

マナ回路例: リングオシレータ

圧縮機構を連鎖させることによって、状態を一定間隔で変化させ続けるマナ回路。圧縮機構を制御する断魔体の位置を往復させることで、ぐるぐると魔術の発動を連鎖させることができる。

ポイントは左上橙波線で示した部分で、ここだけ他と断魔体の動かす向きを変えることで、状態がループして継続的に魔術を発動し続けることが可能となる。

現代の魔術アーキテクチャ

魔術機は、その大きさを小さくすることで必要な魔力、消費されるマナを低減することができるため、世界中の魔術師が魔術機の小型化、集積化に取り組んだ。その結果、現代では米粒ほどの大きさに、億単位の魔術機が集積できるようになった。それに伴い高度で複雑な魔術を大量のマナ回路素子を組み合わせて実現することが可能になった。さらに、マナ制御技術の向上等により、強力な魔術を発動する魔術機（フォース魔術機）が実用化されるなど、ますます魔術の応用範囲は拡大している。

*1:魔力を司る粒子。目で直接見ることはできないが、空間中を飛び回っている。

2021-12-04

『フカシギの数え方』の数え上げを、全探索のままGPGPUで高速化した【KMCアドベントカレンダー 2021 4日目】

ネタ

この記事はKMCアドベントカレンダー2021の4日目の記事です。

adventar.org

概要

元ネタ：『フカシギの数え方』

www.youtube.com

問題としてはN×Nマスのグリッド（頂点としては $(N+1) \times (N+1)$ 頂点）を左上から右下まで移動する経路であって、同じところを二度通らないものの数を数える、というものになっています。

『フカシギの数え方』でお姉さんが数え上げていた問題を、実際に全探索で解いてみて、組合せ爆発の凄さを体感しつつ、GPGPUで頑張って高速化してみます。

CPUで全探索

これを全探索で解くためには、これまでに通った場所を覚えておいて、そこを通らないようにしつつ、右下の頂点までたどり着けるものを探せばよいです。これはバックトラックによって簡単に数え上げることができます。

RustでCPU向けに実装したものがこちらになります

github.com

バックトラック部分の本体は

fn solve_impl(n: isize, visit: &mut BitVec, row: isize, col: isize) -> usize {
    if row == n && col == n {
        return 1;
    }
    let mut ans = 0;
    let d = [(1, 0), (0, 1), (-1, 0), (0, -1)];
    for (dr, dc) in d {
        let new_row = row + dr;
        let new_col = col + dc;
        if min(new_row, new_col) < 0 || max(new_row, new_col) > n {
            continue;
        }
        let new_pos = new_row * (n + 1) + new_col;
        if visit.get(new_pos as usize).unwrap() {
            continue;
        }
        visit.set(new_pos as usize, true);
        ans += solve_impl(n, visit, new_row, new_col);
        visit.set(new_pos as usize, false);
    }
    ans
}

こんな感じで容易に書くことができます。今いる場所から4方向に対して、枠外になっていないか、既に通っていないかを確認して、大丈夫なら移動する、ということを再帰的に繰り返しています。

並列化のため、最初の2Nステップほどを並列に実行するようになっています（async-stdとfutures-rsを利用しています）。

実行するとこんな感じです（oneesan(N)でN×Nマスでの数え上げを行います）

$  cargo run --release
    Finished release [optimized] target(s) in 0.54s
     Running `target/release/kazoeage-oneesan`
oneesan(1) = 2, elapsed: 0.001s
oneesan(2) = 12, elapsed: 0.001s
oneesan(3) = 184, elapsed: 0.001s
oneesan(4) = 8512, elapsed: 0.002s
oneesan(5) = 1262816, elapsed: 0.019s
oneesan(6) = 575780564, elapsed: 6.891s
oneesan(7) = 789360053252, elapsed: 12195.893s

実行時間はCPUの性能等に依存します。この調子で行くと、oneesan(8)の計算には1年半ほどかかる計算になります。

GPUで全探索

今回はoneesan(7)の計算をGPGPUで高速化してみます。まず、GPUは並列化しないとその性能を発揮できないため、最初の一定ステップをCPUで全列挙し、そこからゴールまでの経路をそれぞれGPUで数え上げることにします。しかし、GPUは再帰関数の処理が苦手なため、並列化しただけではとても効率が悪いです。手元で試したところ、oneesan(6)の計算に40秒ほどかかってしまいました。

効率が悪くなる主な原因は、GPUの内部構造にあります。GPUは内部的には複数スレッドを一定数(32や64程度)束ねて、すべてのスレッドで同一の命令を実行する仕組みになっています(SIMT)。このままだとスレッド間で計算内容が異なる場合に対応できないので、一方のスレッドの計算を行っている間は、別の命令を実行したいスレッドを待機させます。その結果、バックトラックでの分岐が発生するたびに、一度に実行できるスレッドが絞られていき、束ねたスレッドのうち、最終的には同時に走るのは1スレッドのみになってしまいます。

今回は、再帰関数を明示的に用意した配列で実装したスタックを用いたループに展開することで、分岐して別行動になったスレッド同士が再び同時に実行できるチャンスを増やすことで、効率化を行いました。その実装がこちらになります。

github.com

細かい点としては、ローカルメモリ消費量を抑えるために、再帰1段分のスタック用配列サイズを2bitに抑える工夫を入れてあります。

これらの工夫の結果、手元のGPUではoneesan(6)を1.8秒、oneesan(7)を1728秒で求めることができるようになりました。 oneesan(7)の計算は実に7倍高速になりました！このペースだとoneesan(8)も83日程度で求められる計算になります。ぎりぎり希望が持てる時間になりました（？） CPUとGPUの性能比を考えるとそう悪くない結果だと思います。

『フカシギの数え方』ではスーパーコンピュータは1秒間に2000億通り数えられる想定でしたが、このプログラムでは手元のGPU(GeForce RTX 3080)1枚で毎秒約4.5億通り数えられます。現代のGPUを500枚程度用意すれば、おねえさんのスーパーコンピュータより速く数え上げることができるかもしれません。

2021-06-03

AtCoder Heuristic Contest 003で5位(2.921T点)を取りました

競技プログラミング

AtCoder Heuristic Contestは、最近始まったAtCoderの定期コンテストで、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストです。 1週間程度の長期コンテストと、数時間程度の短期コンテストが交互に行われます。

atcoder.jp

今回のコンテストでは参加者1000人中5位と、非常にいい成績をとれました。システムテスト前の得点（コンテスト中に表示される暫定得点、100ケースの合計）は97,323,736,361(97.32G)点、システムテスト後の得点（3000ケース合計）は2,921,245,705,250(2.921T)点でした。

今回のコンテストでやったこと、やらなかったこと、考えたこと等をまとめます。

問題概要

30*30のグリッドグラフ上で、ジャッジが指定した2点間に対して最短経路を求めるクエリが1000回投げられます。しかし、各辺の長さは隠されており、自分のプログラムの返した経路の長さ（に0.9～1.1の範囲の一様乱数を掛けた値）のみを知ることができます。

得点は、各クエリに対して、真の最短経路aを自分のプログラムの返した経路の長さbで割った値a/bを、後半のクエリほど大きな重みを付けて和を取った値です。 1テストケースあたりの得点の上限がほぼ10⁹点になるように定数が掛けられています。

辺の重みの決定方法が若干特殊で、 $M$ というパラメータがテストケース毎にランダムで1か2になり、その値によって重みの付け方が異なります。また、 $D \in [100,2000$ ]というパラメータもテストケースごとに一つ生成されます。（これらの値を直接知ることはできません）

$M=1$ のとき

各行、各列ごとに、基準となる重みを $[1000+D,9000-D$ ]の範囲から一様ランダムに生成し、ここに各辺に対して $[-D,D$ ]の一様ランダムな値が加えられる。

$M=2$ のとき

各行、各列ごとに、基準となる重みを $[1000+D,9000-D$ ]の範囲から一様ランダムに二つ(ここでは $W_0, W_1$ とします)生成し、また、"切れ目"を1～28の範囲から一様ランダムに生成し、グリッドの片方の端から"切れ目"までを $W_0$ を基準、そこからもう片方の端までを $W_1$ を基準とし、ここに各辺に対して $[-D,D$ ]の一様ランダムな値が加えられる。

詳細についてはhttps://atcoder.jp/contests/ahc003/tasks/ahc003_aを参照。

自分の解法

ここからは時系列順にやったことを書いていきます。見出しの得点はpretest時の得点。

愚直解 (61.67G)

Submission #22782181 - AtCoder Heuristic Contest 003

まずは入出力が正しくできるか確かめるため、常にすべての辺の重みが一定であると仮定した状態で、毎回Dijkstra法で最短経路を求めるコードを書きました。

今回は提出コードをRustで書きましたが、proconioが内部のバッファリングの影響か、インタラクティブ環境でうまく動かなかったので、温かみのある入力パースを行いました。

勾配降下法の実装 (81.59G)

Submission #22784737 - AtCoder Heuristic Contest 003

$i$ 番目のクエリの応答の経路の長さ $y_i$ は、辺 $j$ の重みを $w_j$ 、その経路に含まれる辺の番号を $p_{i,1} , p_{i,2} , ... , p_{i,k_i}$ とすると、

$\displaystyle y_i = \sum_{j=0}^{k_i} w_{p_{i,j}}$

と書けます。ここで、行列 $A=(a_{ij})$ を $i$ 番目の経路に辺 $j$ が含まれていれば1、そうでなければ0として定義すると、

$\displaystyle \textbf {y} = A \textbf{x}$

と書くことができます。これを $\textbf{x}$ について解けば辺の重みが分かりますが、辺の数が1740あるのに対し、経路の数は高々1000個しかないため、一意な解は存在しません。また、帰ってくる経路長は乱数でスケーリングされているので、解が存在するとも限りません。

ここではとりあえず、辺の重みの近似値を、 $\textrm{min}(||A \textbf{x}- \textbf{y}|| _2)$ （最小二乗法）を勾配降下法によって求めることにしました。スケーリングは正規分布ではなく一様分布であるため、最小二乗法でいいのかという問題はありますが、とりあえず計算が簡単なのと、このあとCG法を使ってみようと思ったためこうしました。

勾配降下法の高速化、辺の重みの初期値の調整 (87.74G)

Submission #22785943 - AtCoder Heuristic Contest 003

雑に疎行列演算等を実装したところ、各クエリに対して20回しか勾配降下法のステップを回しただけで1200msほどかかっていたので、不要なメモリ確保をなくすなどの高速化をして、30ステップほど回すようにしました。また、未探索の辺を積極的に調べるため、未探索の辺の重みを期待値である5000よりも若干小さくしました。

高速化、学習率の調整 (92.19G)

同時に疎行列ベクトル積を高速化して、クエリごとに50ステップ程回せるようになりました。 get_unchecked (配列の境界チェックをせずに配列の要素にアクセスするunsafe関数)使ったら速くなった！（これでいいのか？）

もう少し1ステップで更新する大きさ（学習率）増やしても行けそうだったので、5倍(0.0001→0.0005)にしました。また、Dijkstra法は負辺/負閉路があるとまずいので、辺の重みを1000-9000の間になるようにclampした（Rust 1.42.0にはclampがなかったのでminとmaxで書いた）。

共役勾配法の導入 (92.83G)

二乗誤差の最小化 $\textrm{min}(||A \textbf{x}- \textbf{y}|| _2)$ は、実は方程式 $A^tA \textbf{x} = A^t \textbf{y}$ （正規方程式）を解くことによっても求められます。これは線型の連立方程式なので様々な方法で解けますが、行列サイズが1740*1740とかになるのでガウスの消去法等では計算量が大きすぎます。しかし、 $A$ はほとんどの要素が0の疎行列なので、これを生かした高速な求解アルゴリズムがいくつか存在します。ここでは共役勾配法（CG法）を使いました。

大きすぎる/小さすぎるweightの抑制(正規化) (93.15G)

辺の重みは1000-9000の間にありますが、経路長に誤差が乗っているため、方程式はその範囲外の値を解としてもってしまうことがあります。これを補正するために、 $|すべての辺の重みの平均-5000|$ も最小化対象になるように、行列 $A$ に入れました。さらに辺の重みの初期値をいじって93G点に乗せました。

重大な事実に気付く

ここまで初日の内容で、このときは1桁順位で満足していましたが、土日が明けた頃には40位程度まで落ちていました。で、上位の得点を見ると、すでに96G点台になっていました。この時点ではなんとまだ $M$ パラメータの存在に気付いておらず、1740辺に対し1000経路では明らかに情報が不足して、こんなに精度が出るのはおかしくないか？と思っていました。

何か勘違いとしているとまずい、ということで問題文やテストケースの生成方法をよく読むことにしました。すると、 $M$ というパラメータがあり、とくに $M=1$ の時は同じ行/同じ列の辺の重みはほとんど同じになっていることに（今さら）気付きました。たしかにこれを使えば大きくスコアを改善できそうです。

隣り合う辺の重みの差の抑制 (95.53G)

ということで、同じ行/列の辺であって、隣り合っているものについて、その重みの差を最小化対象に入れました。これは $A$ に片方の辺に $w$ 、もう片方の辺に $-w$ を掛けて足す行を追加すればよいです。

解と行列の使いまわし (96.85G)

いくらCG法が高速に収束するとはいえ、TLEしない10回程度の反復では、得られる解（辺の重み）の精度は限られています。そこで、辺の重みベクトルをクエリ間で使いまわすようにします。すると、前回得られた解からスタートするので、多くの場合今回求めるべき解の近くからスタートすることになり、収束が速くなります。また、これまでは行列やベクトルをクエリごとに再構築していたのを、使いまわすようにして高速化し、反復回数を増やせるようにしました。

この時点で暫定2位まで来ました。びっくりです。さすがに3日目まで問題文をよく読んでない人ばかりではないと思うので、おそらくCG法によって1740辺個別に重みを推定できるようになったのが大きく効いたのではないかと思います。

重みスケーリング (97.02G)

$M=2$ のときは、行中のどこかで辺の重みが一気に変わる場所が存在するはずで、このとき隣り合う辺の重みの差を抑制していると、真の重みから遠い重みを推定してしまいます。そこで、隣り合う辺の重みの差によるペナルティーがどれくらいかかっているかに応じて、ペナルティーを軽減したり増やしたりするようにしました。

パスの長さによる正規化 (97.13G)

これまで、各経路に対して、 $| \sum x_{i_j}-b_i|$ (と他の正規化項)の二乗和を最小化してきましたが、 $| \sum x_{i_j}-b_i|$ は経路中の辺の数が多いほど大きくなりやすいです。二乗和の最小化なので、この場合長い経路ほど頑張って誤差を最小化しようとすることになります。しかし、得られる経路の長さが真の値に対して0.9～1.1倍スケールされていることを考えると、短い経路の結果も長い経路の結果も同程度に重視すべきです。

そこで、経路中の辺の数 $n_i$ を用いて、 $|Σ(1/n_i)*x_{i_j}-b_i/n_i|$ (と他の正規化項)と正規化してやると、スコアが伸びました。

$M$ の推定、その他微調整 (97.32G)

$M=2$ かどうかをlossを見てアドホックに推定して、それに応じてペナルティーをいじるようにしました。あとは細かい改良を積み重ねたり、optunaでハイパーパラメータチューニングをしたりして、スコアを積み上げていきました。最後までM=2でDが小さいときに対するうまい対処法を思いつけなかったのが残念です。

解法そのものとは関係なくやったこと

複数テストケースを並列で走らせて、たくさんのテストケースについての得点を素早く集計する

問題の性質上、テストケースによって点数が大きくずれる、また、パラメータによって得点傾向が違うことから、少数のテストケースのみで変更点の有効性を確認するのは危険です。コンテスト中の提出は30分に一回しかできず、また、100ケースしかないため、かなり大きな改善でないと有効性を言えるほどの点差がつきません。さらに、改善が進むにつれ、一つの変更による得点の上昇が少なくなっていくので、その分テストケースの数を増やしていかないとテストケースに対して過学習を起こしやすくなります。

そのため、ローカルでたくさんのケースについて得点を集計する仕組みを構築しました。複数ノードにバイナリをばらまいて、各ノードで計算を走らせ、それを集計するスクリプトをRubyで書いて、コマンド一つでできるようにしました。最終的には家の計算機5台(Ryzen 7 Pro 4750GE * 4 + Ryzen 9 5950X * 1)の計48コア96スレッドで7680ケースについて回すようにしました。

性質上、並列度はテストケースの数だけ増やせるはずなので、次回の長期コンテストまでにはAWS Lambda等を用いて1000並列とかで回せるベンチマークシステムを構築したいです。

M,Dの値とスコアの関係をプロット

これも考察に大いに役立ちました。 $M=2$ のときだけでなく、 $D$ の大きいときもかなりスコアが下がっていることが確認できました。コードをいじった時にも、どういうところでスコアが改善・悪化しているかが見てわかるので良かったです。

optunaによるハイパーパラメータチューニング

使いどころが難しい（本質的な改善の方が大事）ですが、次のような場合に使ってとてもいい感じでした。

他のパラメータとの相対的な重みの大きさが変わるような変更の後

パスの長さによる正規化を実装したとき、経路に関するlossは（辺の数で割られるので）かなり小さくなります。それに応じて他の正規化パラメータの大きさも小さくする必要がありますが、複数パラメータ間のバランスをとるのは大変で、ここでoptunaで自動的にチューニングできたのはとても便利でした。

これから寝るとき

寝てるだけでスコアが良くなって便利。

もうできることが思い浮かばないとき

ボーっとしてるだけでスコアが良くなって便利。

計算機を温めたいとき

マイニングでもしとけ。

512ケース程度ではかなり過学習してしまうので、かなり計算資源が必要なのが難しいところだと思います。最初に128ケースまわしてとても悪そうだったらそこでやめて、悪くなさそうならもっとたくさんのケースを回す、とか工夫の余地はありそうです。

特に、今後クラウドで回そうとするならば、そのへんの計算量削減策を考えないとすぐにお金が融けていきそうです。

やったけどうまくいかなかったこと

隣接辺の重みの差をペナルティにするのではなく、ダミー辺との重みの差をペナルティにする

M=2のときに全然上手く行かなかった
M=1のときもスコアの分散が大きくなっただけであまり改善されず
辺ごとの重み推定を捨てて、行ごと(60変数や120変数/180変数のモデルにする)でやればよかったかも

経路の結果を正規化する際に、辺の数ではなくスコアで正規化

他のパラメータの重みもずらす必要があるのでoptunaで最適化もしたが、それでもだいぶ悪かった
経路長に乱数がかかった後の値がやってくるのがまずそう？

やっておけばよかったこと

$M,D$ の推定値によるモデルの切り替え

これをできなかったのは結構良くなかったな、という気持ち… M=2の時のモデルをどうするか、というのが本質的に難しそうですが… Dが大きいときには、わりとできることは少なそうで、ここの改善はあまり期待できなさそうです。

事前の環境整備

インフラ回り等、事前に準備できることは結構あるはずなので、そのへんを次回の長期コンまでにやっていきたいです。

感想

とてもよくできた問題だと感じました。これがM=3とかがあると、割と打つ手がなさそう（複雑度に比べて、得られる情報が少なすぎるため）で、かといってM=1だけだとすぐほぼ理論値までたどり着いてしまうはずで、この辺の塩梅が良かったように感じます。

結果にはとても満足していて、望外のいい結果を得られてとてもうれしいです。今後もいい結果を残せるように頑張ります。

2021-03-21

AtCoder Heuristic Contest 001 解法メモ

競技プログラミング

最終スコア(システムテスト後)は980,823,067,375点で95位でした。

atcoder.jp

自明解の生成

広告の希望(x, y, r)に対して、長方形( (x, y), (x+1, y+1) )は解の条件を満たす

スコア計算

解の条件を満たしているかを判定する
満たしていれば、各広告についての点数の和を取って全体のスコアを算出する

基本方針

山登り法、乱数の値の幅を徐々に小さくする

1点探索 (resize_1way)

広告を一つランダムに選択する任意の方向に適当な大きさ伸ばし/縮めることを試すこれを何度も繰り替えす

1点探索 (move)

他の広告の邪魔になっているところを解消するため、広告を平行移動する広告を一つランダムに選択する任意の方向に適当な距離移動させることを試す

2点探索 (redelineate)

接触している2つの広告のペアをランダムに選択する接触している境界線をどちらかの方向に適当な距離移動させることを試す

スコア計算の最適化

解の条件を満たしているかを判定するのがO(n²)かかっており、遅い
操作前に解の条件を満たしていることを仮定すると、上記の操作では、変更した広告と他の広告のペアについて、解の条件を満たしているかを判定すれば十分
判定にO(n)、スコア計算にO(n)で全体でもO(n)でスコアを計算できる
また、スコア計算自体も差分更新できる（依然として判定にはO(n)かかるので、オーダーレベルでの改善にはならない）
そもそも、スコアをずっと持っておく必要もなく、スコアが増大するかどうかが関心の対象なので、変更した広告の得点だけを見ればよい

greedy

何度も改善を繰り返し、制限時間を迎えたとき、shake操作等により広告間に隙間ができていることがあるもったいないので、改善できるなら貪欲に改善する

redelineate skip 最適化

自明解から広告を拡大している途中では、広告同士が接触していることはまれ 2点探索は接触判定にO(n²)かかっており遅いため、最初のうちは行わないことで高速化

全体再配置 (gravity)

方向をランダムに選択するすべての広告を、他の広告にぶつからず、位置の制約を満たす範囲で選択した方向に平行移動するこの際、平行移動の代わりに拡大してスコアを改善できれば、する

1点探索 (resize_2way)

1方向だけに対してサイズ変更をした場合、すでに要求の大きさに近い面積になっていると、これ以上拡大・縮小が不可能になることがある 2方向に対してサイズ変更をすることで、これを緩和する

複数回探索 (多点スタート)

局所解に嵌ってしまうと、抜け出すのは困難なため、何度も探索してもっともよさそうな解に対してさらに最適化を掛ける

2点探索高速化

2点探索では、接触判定の計算量O(n²)が支配的で、その後の試す部分では解の条件判定にO(n)掛かる他は定数時間で終わる。そのため、一度接触判定をしたら、その後たくさんのペアに対して変更を試すことで、変更当たりの計算量を削減して高速化できる。

2点探索 (dodge)

接触面を平行移動するのではなく、接触面を0にするようにそれぞれの広告の大きさを変更した後、もとよりスコアが改善するように接触面のあった方向に広告を伸長する

resize_1way強化

resizeの結果他の広告にぶつかった場合も、そこで失敗判定にせずに、ぶつかった広告を縮小して回避できるときは回避することを試す