RECRUIT 日本橋ハーフマラソン 2022夏(AHC013) 参加記

はじめに

先日行われたRECRUIT 日本橋ハーフマラソン 2022夏(AHC013) に参加しました。自分にしてはいい順位を取れたので、 嬉しかった記録ということで参加記を残します。

問題

atcoder.jp

成績

最終 2000 テストケースで 13,808,196 点 (平均 6904 点)、 19th / 850 でした。2回目の橙パフォ+レート黄色到達+1ページ目めでたい!

解法

自分の解法は、ざっくり以下の通りです。

  1. 貪欲法っぽく同じ種類のサーバを繋げて巨大な木を構成する操作を、1種類ずつ行っていく
  2. 2種類目以降のサーバを繋げやすくするために、最初に作る種類のサーバだけ入れない領域を作成する
  3. 空白が足りなくなったら、既に繋げたサーバ間の空白を消して縮める
  4. 木の構築開始地点、禁止領域の形、木を構築するサーバの種類の順序を色々試して最善のものを選択
seed1 (6603点)

以下、もう少し詳細です。

同じ種類のサーバを繋げて巨大な木を構成

得点の計算方法から複数の小さなクラスタを作るよりも一つの大きなクラスタを作った方が高得点になりやすいため、同じ種類のサーバを100台繋げることを目指します。巨大な木を作るために、1台ずつサーバをくっつけて木を構築する方法を実装しました。

ただし、真面目にコスト計算すると処理が重いと判断して、クラスタに属するサーバと、クラスタに属さないサーバを接続するためのコストを、以下のように妥協して見積もりました。

左上のクラスタ内サーバに、右下のサーバを繋げる例

例えば、上の図で種類 "3" のサーバを接続する場合として、左上のクラスタ内に接続されたサーバを、右下のクラスタに属さないサーバに接続する例を考えてみます。この場合、

  1. 各サーバを上下左右に動かす範囲、かつ2サーバで構築される長方形領域内部に限定して、どの位置で接続するかを列挙する
  2. 各サーバを移動する軌跡および予定する接続上に存在する、種類 "3" 以外のサーバの個数を計測(邪魔なサーバ、と呼びます)
  3. 接続を作るためにどかす必要のある、邪魔なサーバの個数が最も少ない接続の位置を選択する

という流れで、接続位置の候補を決めます。

縦方向の接続候補、横方向の接続候補、選択される位置

この例では上下の接続5本、左右の接続候補5本のうち、右から2番目の縦方向に接続しようとします。

ただし、結構細かな実装は割と複雑で、

  • クラスタに属するサーバは、既にある接続の整合性を保ったまま動ける範囲は限られている可能性があるので、その場合はより限定された候補になりえる
  • 既に同じ数字で接続が張られているところへ移動する場合は、その接続の整合性を保ったまま1マスずつ動かす関数を実装して頑張る

等を考慮する必要があります。

クラスタに属するサーバ、クラスタに属さないサーバ)のペアは、サーバ間の $x$ 座標、$y$ 座標の差分をそれぞれ $dx, dy$ とすると、 $ \min(dx, dy) <= 3 $ に収まる範囲で全探索しました。これは、接続までに要するターン数の下限が $ \min(dx, dy) $ のためです。

実際に上記の接続を行うときは、邪魔なサーバを最も近い空白へ押しやるために毎回復元付きの BFS で邪魔なサーバをどかしています。ただし、後から全体を俯瞰した時に明らかに手損の状態もそのまま残して進んでいきます。

最初に作る種類のサーバだけ入れない領域を作成

最初にクラスタを作る種類のサーバだけ入れない領域

上記の方法でサーバを自由に繋げた場合、2種類目以降に作るクラスタの木のサイズが小さくなってしまったため、最初にクラスタを構築する種類のサーバだけが入れない、かつ接続の辺も張れない領域として、上記のような王の字を指定しました。例えば、1 → 2 の順にクラスタを作るとすると、1は王の字に辺も含めて入ることができないため、次にクラスタを作る種類である2の木が構築しやすいことが期待できます。王の形は、横方向に盤面サイズ/4、縦方向に4マスを空けた、幅2の王の字のみを試しました(最終的にこの形になったのは、単に時間が足りなかったからです)。

ただし、特に空白が少ない場合などでは禁止領域がない方がよい場合もあったので、全く制約を書けない場合なども試しています。

最初予定していた禁止領域の形状

最初は上記のように周囲2マスを空けるような禁止領域を作ったのですが、開発序盤で貪欲法の探索部が弱かったことで移動量の損がかさんでしまったりしたこともあり、最終的な調整まで間に合いませんでした。王の字の形状は、周囲2マスを全部禁止にするよりも禁止領域の面積が狭くある程度全体に届くため、私の解法のように貪欲法の探索度合いが弱くても機能しやすいかなぁという気持ちで設計しました。

余談ですが、後で周囲2マスを禁止領域に指定するコードも後日追加してみたところ、それだけで50テストケースで 350,376 → 354,334 になったので、王の字で全てはカバーできていなかったようです。結果論ですが、コンテスト残り2時間の時に一番費用対効果が高かったのはこの部分だったのかもですね。

既に繋げたクラスタを縮める

上記のように、空白が少ないテストケースだと、雑に貪欲で繋げていくとすぐに空白がないせいで手詰まりになってしまいます。そこで、手詰まりを回避するために、余計なサーバが移動不可能になったら既に繋げたサーバ間の接続の空白を見つけて縮める操作を行いました。

色々試して最善のものを選択

高速化する時間が十分とれず、1試行解を作るのに数10ms 程度必要だったので、Nが小さなテストケースでも100回程度しか試行回数が稼げませんでした。
そのため、乱数に頼って乱択せずとも、(クラスタを構築するサーバの種類の順序、最初の種類のサーバで木を構築開始する地点、禁止領域のパターン)を色々変えて一番良い解を出力するだけで十分時間を使い切ることができました。

結果の解釈

テストケース毎の分布は、wleite さんの統計情報がとても参考になりました。

tc-wleite.github.io

終わってみれば、サーバの種類が少ない K = 2 がとても弱かったようです。クラスタを構築するための手順が全然最適化できていなかったので、雰囲気的には貪欲に繋げていく方法が限定的であったり、山登りなり焼きなましできなかった弱点が出てしまったのかなと感じています。

起きたこと(時系列)

本当にメモを取る余裕がなかったので、今回は何も書けず…

所感

  • 実装に苦労したコンテストでしたが、実装に苦労した分最初に100サーバ全部繋がった時にはめちゃくちゃ嬉しかった(AHC011 や AHC008 みたいに実装が大変だった系のコンテストは結構そうなりがち)。
  • 今回みたいに実装が重いコンテストは、実際にコードにバグはないけど論理的にバグがある状況になりがちなので、もう少しデバッグ周りで補助ツールを充実させたいなという気持ちになりました。これいつも言ってる気がするけど。
  • 次こそこういう実装重いコンテストで焼きなましたい。こっそり練習頑張ります。

「まわしてそろえる」のコスト計算過程の備忘録

記事の概要

「まわしてそろえる」とは、第3回 RCO日本橋ハーフマラソン 本戦Bの問題です。
atcoder.jp

本記事は、以下のmaspy さんの記事を見て復習していたのですが、コストの効率的な導出をきちんと理解するために、ちゃんとゴリゴリと式展開をした過程をメモした、自分用の備忘録です。
maspypy.com

解法の概略としては「2つの領域に分ける問題」の小問題として3つに分割し、各小問題では、一部の要素に限定して$x$座標または$y$座標の総和でビームサーチをします。例えば、0~3の数字を「0または1」と「2または3」に上下で分ける時、「0または1の$y$座標の総和」がコスト関数になります。解法の細かなポイントは他にもいくらかありますが、記事の本質ではないので省略します。

上記の計算は、2次元累積和を管理することで高速化ができるのですが、きちんとその導出を自分の手で行おうとしたら詰まってしまったので、その流れをメモすることが本記事の目的です。

導出方法

本記事でやることは1つだけで、現在の解の状態から特定の領域を90度、180度、270度、1回だけ回転させた時に、どのようなコスト差分になるか計算することを目指します。以下では、例として領域$S$を$a \leq x < a + s, b \leq y < b + s$(この$x, y, s$は、問題中の操作に対応します)、$D_S$ を$S$の内部で下へ寄せたい要素(上記の例では「2または3」)、$U_S$は$S$の内部で上へ寄せたい要素(上記の例では「0または1」)とし、$p \in U_S$ に属する$y$座標の総和がどう扱われるかを書いてみます。
$Y(p): Z^2 \rightarrow Z$を、座標$p = (x, y)$から$y$を取り出す関数、同様に$X(p): Z^2 \rightarrow Z$ を座標$p = (x, y)$から$x$を取り出す関数とすると、コスト関数は以下のように書けます。

$$
\sum_{p \in U_S} Y(p)
$$

今、$p$ を$(a, b)$を起点に時計回りに90度回転させて$f(p)$に移動させる時、回転させる小領域内部で左上を原点と見なす相対座標$(x_r, y_r)$は、以下のように移ります。

$$
(x_r, y_r) \rightarrow (s - 1 - y_r, x_r)
$$

ここで、$x = a + x_r, y = b + y_r $に注意すると、最終的に$(x, y)$ は以下のように式変形して移ります。

\begin{align}
(x, y) & = (a + x_r, b + y_r ) \\\
& \rightarrow (a + s - 1 - y_r, b + x_r) \\\
& \rightarrow (a + b + s - 1 - y, b - a + x)
\end{align}

今、関数$F(V) = \{ f(p) | p \in V \}$ を、集合$V$の各要素を回転を通じて移動させる関数として、

$$
\sum_{p \in F(U_S)} Y(p)
$$

が$\sum_{p \in U_S} Y(p)$と比べてどう変化するのかを知りたいです。これは、

\begin{align}
\sum_{p \in F(U_S)} Y(p) &= \sum_{p \in U_S} Y(f(p)) \\\
&= \sum_{p \in U_S} Y(f( (x, y) )) \\\
&= \sum_{p \in U_S} Y( (a + b + s - 1 - y, b - a + x) ) \\\
&= \sum_{p \in U_S} (b - a + x) \\\
&= |U_S| (b - a) + \sum_{p \in U_S} X(p)
\end{align}

みたいなことをすると、計算が展開できます($p = (x, y)$と置き換えたのが、やや不自然かもしれません…)。同様に$X(p)$の方も頑張って展開すると$|U_S| (b + a + s - 1) - \sum_{p \in U_S} Y(p)$のような式が出てくることから、結局以下の計算が高速にできると嬉しいことがわかります。

\begin{align}
c_y &= \sum_{p \in U_S} Y(p) \\\
c_x &= \sum_{p \in U_S} X(p) \\\
c_1 &= |U_S|
\end{align}

これらの計算は、$U_S$が長方形上の領域であることを考えると、2次元の累積和を用いることで高速化できることがわかります。

また、$f$で回転させる操作を何度も適用しても同じことなので、180度、270度の回転でも同じことが言えます。$F$を通じた$(c_x, c_y)$の変化を改めて明示すると、
\begin{align}
\sum_{p \in F(U_S)} Y(p) &= |U_S| (b - a) + \sum_{p \in U_S} X(p) \\\
&= c_1 (b - a) + c_x
\end{align}
と書けるので、$c_y \rightarrow c_1(b - a) + c_x$ と移ることがわかります。同様に、
\begin{align}
\sum_{p \in F(U_S)} X(p) &= |U_S| (a + b + s - 1) - c_y \\\
\end{align}
となるので、$c_x \rightarrow c_1(a + b + s - 1) - c_y$ と移ります。

この写像を1, 2, 3回適用させると、それぞれ90度、180度、270度回転に対応するので、簡単に計算ができることがわかりました。

ここまで振り替えってみると、線形の写像しか登場しないし、わかってしまえばそれはそうだよなーという感じでしたが、結局このきちんとした導出をするために数時間溶かしてしまったので、メモを残したのでした。少し冗長な表現な気もする(例えば、わざわざ$F$のようなものを持ち出したあたり)のですが、わからなくなった時に自分が一番しっくりきた表現だったので、ここでは将来の自分のためにそのまま残しておくことにします。

Codingame Spring Challenge 2021 参加記

問題

www.codingame.com

いなにわさんのわかりやすい日本語訳があり、ありがたく利用させてもらいました。

inaniwa.hatenablog.com

結果

Gold 1116位でした。
もうちょっと頑張りたかったけど、何もわからなかったのでどうしようもない。

やったこと

1日単位で Action の集合を生成する beam search を 5日分やりました。
1日単位での Action の集合を列挙するために、内部で possible_action() みたいな関数をベースに wait が終了条件の BFS をしました。 Zobrist hash とか基本的な重複除去は一通り取り込んでいます。 Action の列挙の際には、以下のような Action を省く戦略を埋めました。

  • completion → grow2 → grow1 → grow 0 → seed 以外の手順はやらない
  • seed で種を置く対象のマスに対して、高々3か所しか木を指定しない
  • 自分の木がある隣接マスには種をまかない
  • 自分の木と桂馬の関係にあるマスにしか種をまかない

3, 4 つ目の条件を両方満たす位置の候補がそんなにないせいで、sun 出力が伸びなくて厳しい盤面があったりしたのだけど、単に候補列挙のルールに優先順位をつければよかったということに感想戦で気づいた。

評価関数は、最初に適当に指定した

  • 最初16日: 直近6日で得られる sun の合計スコア
  • 後半8日: スコア

がそのまま採用されました。色々工夫を試していたけど、結局あまり強くなってくれなかった。

所感

  • 今回で3回目だったけど、1, 2 回目と比べてよりゲームの文脈で考察できるポイントが増えてきた気がする
    • それに比例して強い bot が作れているわけではないのが悲しいところ
  • 1, 2回目と比べて、意味不明なエラーで落ちて泣いてる時間がかなり少なかった
    • これは Rust の恩恵な気がしていて(これまでは C++)、まだ実装やライブラリ選定が不慣れな分を差し引いても、かなり元が取れていると感じる
  • パラメータチューニングを前提にした評価環境は最初に作りたい
    • 後半で評価関数のパラメータチューニングをやろうと思った時に、時間をかけて作るのが億劫になってしまう
    • コドゲのサービス上で動かすと、stderr の一部が切れて表示されないことを半年たつといつも忘れる気がするし、そもそも timeout があるから不便
  • MCTS をしたい状況が体感できた。
    • コスト関数の設計苦手なので、MCTS できるタイミングは積極的に探していきたい
    • 秋のコンテストまでには、MCTS でこの問題を解きなおすのはやっておきたい
  • ルールベースの bot も書いてみていいなと思った
    • 評価関数の設計や枝を刈るいい練習になる気がする

おまけ:コンテスト中のやったことメモ(時系列、自分用)

Wood 2

自分の木を選んで Complete。

Wood 1

1本ずつ Grow。

Bronze以降

実装①: 試合を見るための仮ソルバ作成

相手を無視したスコア関数を元に貪欲をして、とりあえず試合運びを確認する。 序盤は sun の最大化、終盤はスコアの最大化

考察: 自分以外の試合を見て重要そうなポイント

  • 盤面の richness は、中央であるほど高いので固定らしい
  • 一方で、完全に中央は日が遮られやすいので、注意が必要
  • 場所の強さが mod6 で異なるので、mod6 で育てる場所を変えたい
    • 中央に size 3 木を残しておいて、強い場所に1手で撒けるようにする
  • 桂馬っぽいの関係で正三角形を作ると、少なくとも自分で自分を遮ることがなくて強い
  • 相手のそばに置いて、相手の sun 取得を妨害するような動きができると良さそう
    • 相手の木に対して、多対一で接していると、妨害効果が強そう?
    • 相手から妨害される未来が見える時には得点に変換してしまうのが良い?

考察: 自分のソルバがダメそうな所

  • richness が高そうな場所に seed をまいてくれない
  • grow のコストが過剰に低く見積もられている

実装②: ビームサーチ化

基本的には自分のみを考慮 + 相手の行動や状態を基に若干のボーナスをつけて、ビームサーチ。 1 Action が 1ターン。

  • コスト関数
    • 12手以前は、それ以降で得られる sun の最大化
      • 今の手持ちの sun は加えない
    • 12手以降は スコアの最大化
      • ボーナス①:Complete した時に、相手が次ターン以降に行うと思われる Complete の回数 / 1.5ビームサーチの手数 で加える
        • 時間減衰させないと無限に後回しにする
        • 相手が次ターン以降に行うと思われる Complete の回数 = max(10 - これまでに complete した回数, 相手が今持つ size 2 以上の木の個数)
      • ボーナス②:Seed した時に、richness の分だけ加える
        • seed を撒くにしても richness の大きさも考慮したい
  • ビーム幅
    • 12手以前は 400
    • 12手以降は 600
  • 手数
    • 12手以前は 20 手
    • 12手以前は 40 手
  • その他
    • 候補を作る際、sun が少なかったり候補手が空出ない限りは、Wait をしない
      • 本当は入れたくないけど、ターン数が経過してしまうことを表現する方法が思い付かないので苦肉の策
    • 重複除去として、同一の (直前ターン盤面 id, action id) を2つまでしか持たないようにした

考察: 自分のソルバがダメそうな所

  • size 2 -> size 3 Grow を打ってから、Completion してる…
    • Grow に対する Action Bonus はないけど、Completion に対する Action Bonus がない、かつ Action Bonus は累積しないのが問題
      • 後ろで Action Bonus を選んだ方が有利になってしまうため
    • Bonus を累積的にして調整するなども検討したが、結局 possible_move で直前の action も状態に持たせたうえで上記の遷移を禁止
  • どうも richness の差が結構効いているように見える
    • ありえないけど、全部 richness 3 のマスで木を生やせたら、めっちゃ強いよねやっぱり
  • 初手の動きがかなり弱い
    • 自分の動きは、地震に隣接する場所に置かないのだけど、どうも初手で中央を制圧されてしまうことが richness の差で負ける要因にもなっている気がする
    • 最初は、速やかに中央を制圧するための手順を読むのがいいのかも?

アルゴリズム上の問題点

  • Action を評価するのが良くなさそう
    • 良いものにバイアスがかかる得点を入れるより、悪いものを選択しないようにするほうが調整が楽だし、ターン数に対するコスト値の普遍性もある
  • 1 つの Action を beam search の1ターンにしているのが良くなさそう
    • wait すると sun が入るので、wait を連打するのが比較的良好な戦略になってしまいやすい
      • 実際、seed を撒くような数日後によくなる手は、ビーム幅が狭いこともあって全部消えてた

実装③: 1日単位で行うビームサーチ

  • 実装簡略化のため、実装②のビームサーチの内部で、1ターンずつ進める BFS をやって、1日が終わるまでの盤面を生成する
  • ビーム幅
    • 100
  • 手数
    • 3日分
  • コスト関数
    • 前半16日: 直近6日で得られる SUN 値
    • 後半8日: スコア

ただし、時間制限が来たら途中で終わる実装を入れていて、実際中盤などは途中で終了していた。 これでギリギリ Gold には入れた。

実装④: コスト関数の設計

ビームサーチのスコアがさすがに雑なので、visualizer を見て試行錯誤していた。

  • スコア
  • size 0 ~ 3 の木の本数がそれぞれ [2, 2, 2, 5] に近い
  • 直近 N ターンで自分がもらえる sun の合計値 * 2 - 直近 N ターンで相手がもらえる sun の合計値

あたりを頑張って重みづけしようとしてたけど、思ったように動いてくれなかった。

AHC001 参加記

問題

atcoder.jp

結果

70 位でした。1ケースだけ TLE していたらしく、少し順位下がった。

やったこと

自明解

各広告が絶対覆う必要のある $(x_i, y_i), (x_i+1,y_i+1)$ に長方形を置くことで、必ず制約を満たす解を得られる。

自明解の改善①

コスト関数が改善する場合に自明解から上下左右に 1px ずつ拡大すると、自明解より大きくコスト改善しそう。 そこで、

  1. 自明解を初期状態にする
  2. ランダムに長方形を選択し、伸ばす方向も上下左右 1 方向をランダムに選択
  3. 2で定めた方向に 1px 伸ばせて、コスト関数が改善し、制約を満たしていれば採用
  4. 改善ができる間は 2 に戻る
    • don't look bit みたいなので、近傍ひと通り見て改善しなかったら探索候補から捨てていくみたいなのをやった
  5. 時間いっぱいまで 1. からやり直す

をやった。点数は 458,... 程度。

Submission #20681357 - AtCoder Heuristic Contest 001

自明解の改善②

自明解の改善①で、どう見ても伝播して押せるケースがあるのがわかったので、BFS で辿って押せるか判定する処理を追加した。 点数は 478,… 程度。

考察

ここまでで得られた画像を見てみると、より煩雑な操作で改善はしそうだったけど、トップと明確な差があったので中断して考察。

  1. アルゴリズム選択
  2. 1px ずつ伸び縮みさせるより、置ける範囲で最大の長方形を置く方法を考えたい
  3. 制約遵守を保証し続けると動き辛いので、最初は制約違反しても OK にしたい
    • 広告どうしが重なるのは OK そう
    • 他の広告が含まれるべき点 $(x_i + 0.5, y_i + 0.5)$ を含むのはダメそう
  4. 局所解を脱出する方法は作りたい

ついて考えた。

アルゴリズム選択

ビームサーチは、ビジュアライザとにらめっこしたり、特徴量を並べても何をどういう順に置けば良さそうかがよくわからなかった。 例えば、

  • (要求された広告面積 / 原理上置ける最大広告面積) が大きい順
  • 広告面積が大きい順 / 小さい順
  • 端から順に置く

みたいなのを考えていたけど、軽く実装して確かめた感じだと上手く行きそうになかった。

また、焼きなますのも考えてみたけど、改悪を許したとしても、十分小さい近傍では次のいい状態につながる想像が全くできなかった。 という訳で、最終的に山登り+大きめに状態を変えるような操作を時間いっぱい繰り返すことを考えた。

最大の長方形を置き直す

本当はちゃんと説明しようとしたけど、時間が経ちすぎて気力がないので省略。大まかに言うと、

  1. 座標圧縮
  2. 塗り絵みたいなことをやって、最大長方形の頂点候補を抜き出す
  3. その長方形に含まれるべき点からみて第一象限〜第四象限に分類
  4. 4重ループで全部列挙(多すぎたら適度に省略)
    • 経験的には大きくならないけど、一個 TLE したのはこれが原因っぽい?

制約違反をしても OK な方法

2 広告間の面積の重なりを合計したものをペナルティとして入れ、時間と共に線形でペナルティを重くするよう設計した。 これにより、自明解②の push 操作は、重い上に自然に達成されると判断して削除した。

ペナルティを別に入れることも考えたが、共通部分で重なる箇所は面積を直接減らすことでスコアを削減すれば良さそうとわかったため、 重なりが判定された長方形は、その分スコア計算時の面積を両方で減らす方針にした。 が、実装してみたけど全く上手く行く兆しが見えずにやめた。

局所解を脱出する方法

得られた画像を見ると、一部の長方形をまるっきり別の場所に置かないとどうにもならない、というパターンがあった。 そこで、

  1. スコアが悪い下位5個の広告 A と、それに隣接する広告 B をランダムに選択
  2. 広告 A, B を 1x1 に縮める
  3. A をスコア最大の長方形で置き直す
  4. B をスコア最大の長方形で置き直す

のようにして、kick 相当の処理を入れた。これが相対的にはいい工夫で、最終的には 493... 程度まで伸びた。 小さいケースだと、大体 8,000 回位は kick が行われていたらしい。

やり残したこと

スコアがサチっているけど、変形した方がいい長方形の扱いに少し困った。が、前述の置き直すコストが少し大きめだったので結局なんにもできなかった。

所感

  • バグらせはしなかったけど、最大長方形を置き直す部分の処理で無限に時間を溶かした。アルゴリズム力大事すぎる
    • 結局、計算量の観点でかなり損をしていたらしい
  • TLE を1ケース産んだのは反省ポイント高い
    • 実はローカル 1,000 ケースだと1度も起きてなかったので、対処は少し考える必要あり
  • 参加人数が多くて賑わってる1週間マラソン(実質2週間)かなり楽しい
    • TL を眺めていて、最後までずっと飽きなかった
    • フルで毎回参加できるかわからないけど、これからののんびり楽しみたい
  • できる範囲でやったことはブログに残していきたい
    • とある MM で自分が時間をかけてやった方針をなんも覚えていなかったのが、割とショックだったので

レイトレ合宿7 徒競走でやったこと

はじめに

今回のレイトレ合宿では、イベントの一環として BVH の構築/交差判定を高速化する徒競走というイベントが行われました。今いる会社的なあれで高速化に詳しくなりたいというのもありましたが、やってみるとこれがかなり楽しくて、 本題の CG 作品の提出を忘れて 取り組んでいました。そこそこ勉強込で時間をかけたので、何とか忘れないようにやったことを記したいと思います。

実際のソースコードこちら になります。
ソースコードの規約が統一されていなかったり、部分的におかしなコードがあったりしますが、昔書いたコードを必要最低限の改変で持ってきたりしてたので、許して下さい。

ルールは、BVH の構築 + 交差判定の時間が短い人の勝ちです。

とりあえず、効果が 0 でなさそうな、やったことの概要を記すと以下のようになります。
抜け漏れはあるかもしれません。あと、どうやらどこかがバグっているらしいのですが、特定できていません…

やったこと

3次元ベクトルを Expression Template 化

ソースコード

最初、SIMD 化もされていないコードだったので、BVH 構築/交差判定両方で一時オブジェクト作成を削減するためにやりました。最終的に、交差判定ではどのみち一時オブジェクトは作成されないので、最終的な貢献度は薄かったかもしれません。今見ると、きちんと作ろうとして途中で投げ出した後があって面白い。

ポリゴンの当たり判定を正規化した空間でやる(名前がわからない)

ソースコード

Polygon の当たり判定も、もっと速い方法絶対あるだろーと思って色々ググった結果、この記事 に行き当たりました。仕組みは割と簡単で、三角形を (0, 1, 0), (0, 0, 0), (1, 0, 0) の空間に写してから当たり判定するというものです。手元では、そこそこ効果があったように見えたので、採用しました。

三角形をなさない polygon の除去

ソースコード

本来は高速化の意図ではありませんでしたが、上記のポリゴン当たり判定方法を採用すると、obj の一部で nan を吐きまくったため、抑制のために入れました。誤差とはいえ、多少は影響あったかもしれません。

Top Down な SAH ベースの BVH の並列構築

ソースコード

この記事 を色々眺めた結果、とりあえず知ってるやつをやろうということでこうなりました。構築は Task Queue を使って並列化しました。詳細はアドベントカレンダーの記事 に書いたので、興味があれば見てもらえると嬉しいです。

std::stable_partition を使った O( n log n ) 構築(nはポリゴン数)

ソースコード

この内容は、 Bonsai の論文 で知りました。

TopDown SAH ベースの構築をする時、(僕の理解が間違っていなければ) polygon id を管理する配列を x / y / z 軸の3つ分用意し、 x / y / z 軸のそれぞれで sort した状態を保持します。 node を left / right で分けた時、この polygon id の配列を left / right の子ノードの分に分離しつつ、それぞれの子ノードの中では x / y / z 軸で sort されている状態を保ちたいです。
例えば x 軸で bounding box を 2分割したとすると、x 軸分の polygon id の分割は容易です(あるしきい値より左が left, 右が right なので)が、y / z 軸については left / right にいるべき polygon id がごちゃごちゃしているので、これを std::stable_partition を使って分離します。x 軸の polygon id list を見れば、「特定の polygon id が left / right にいるべき」というのは容易にわかるので、各 polygon が left / right のどちらにいるべきかフラグを持たせておき、 y / z 軸の polygon id を std::stable_partition で振り分けます。この時、stable 付きのものを呼ぶと、「 left どうし、right どうしの polygon ID の順番は元の配列のソート順を保つ」という性質があるので、y / z 軸で sort された状態も保つことが出来ます。

8分木の構築 + Node の当たり判定 8並列

ソースコード(2分木の展開)
ソースコード(8 並列 intersect)

定石がよくわからなかったので、2分木を作ってから展開して8分木にしました。
node の当たり判定については、reference 実装のものをそのまま SIMD に描き起こした感じなので、もうちょっと工夫が出来たかもしれません。

8 並列当たり判定で交差した node を効率的に抜き出す

ソースコード

この技術的課題は、この論文で知りました。

8 並列で node の当たり判定をした後、距離順に sort して 子ノードの traverse 順序を決めたいのですが、8要素のソートは重いので、交差した個数に応じて sort を分けるのがいいと記載がありました。これを実現するためには、交差した部分の index はどれかを高速に特定する必要があります。
ここで、「子ノードの bounding box との距離が INF でない bitmask を作成して、bitmask の位置にある index を 右詰めして抜き出す」という処理だと思うと、 pdep / pext 命令が使えることに気づきます。ざっくり書くと、

  1. 入力:1bit x 8 の bitmask当たり判定結果
  2. 8bit x 8 の bitmask を作成する
    • pdep で 8bit おきに bit を配置するように設定し、0xFF をかけて作る
    • avx512 でも大体似たような感じでいける
  3. 0x0706050403020100 は、64bit の数字に index を埋め込んだもので、ここから ↑の bitmask に被るところを pext で右詰めして保存
  4. 3.で作られた整数は実質 8bit integer なので、32bit interger に拡張して store
  5. 何個当たり判定したかは、入力の popcount を数える

みたいな感じになっています。この処理も参考にしたブログがあったのですが、メモに残っていませんでした。
なお、肝心のソート用関数を個数に応じて使い分けるのは、あんまり速くならなかったので、詰めた後は std::sort してます。

Polygon の当たり判定 8並列

ソースコード

これは本当に 1行ずつ SIMD にするだけ。

Polygon の(メモリ配置的な)並び替え

ソースコード

index の間接参照みたいなのを減らすためにやりました。バグらせるのが怖かったので愚直に配列作る + copy をしました。
こういうのが他にも複数あるので、多分構築は遅かったと思います。

(補足)やったけど、効果がなかったやつ(上2つはバグってた可能性大)

Bonsai

構築が明らかに遅かった+改善の余地があったので、とりあえず Bonsai しておけばいいだろうと思って実装したのですが、部分的に手抜きして作ったせいかめちゃくちゃ交差判定が遅くなり、時間切れで諦めました。今回唯一悔やまれる点があるとすると、これのきちんとした実装が出来なかったことだと思います。

insertion based optimization

論文

見た瞬間、これはやりてぇと思って実装しました。が、何か思うように速くならず…かつ、論文とか見ると結構構築が重そうで、終了判定タイミングも結構難しいなと思ったので、優先度をそこそこ落としてしまいました。

AVX512 化(16分木 + ポリゴン 16並列当たり判定)

ほとんど AVX2 の命令を移植するだけでしたが、AVX512 では bitmask が一部 __mmask16 のように圧縮されている形式だったので、その扱いを少し変える必要がありました。手元では全然速くならなかったので、結局諦めました。

SIMD の bitonic sort

ソートが遅いということで、子ノードの交差個数が多かったらこっちの方が速いかもなーと思って実装はしてみました。やっぱり交差するノード数の期待値の問題なのか、多少調整しても速くなったか微妙だったので、やめてしまいました。

intersectAny で leaf node を優先して当たり判定

シャドウレイを飛ばす場合などでは、 polygon に 1つでも当たったら終わりなので、距離よりも当たりやすさを優先すべきだよなぁと思っていました。というわけで、Leaf Node に当たったらそっちを優先的に調べることにしていたんですが、比較条件が複雑な割に改善ケースが少ないせいか、遅くなってしまいました。

開発過程でやったこと

visual studio のプロファイラを眺める

大体ボトルネックは全てこれで把握していました。途中 inline 展開された部分の把握が不可能だったので、もうちょっと何とかならなかったものか。

途中まで SIMD 化して残りを愚直に実装する

SIMD の処理を最初から最後まで書くと大抵 100% バグっていたので、「途中まで SIMD で書いて残りは愚直に書く」をして、愚直をどんどん減らすような方針で書いていきました。

intel intrinsics guide をざっくり眺める

https://software.intel.com/sites/landingpage/IntrinsicsGuide/

そもそも自明じゃないテーマで本格的に SIMD 高速化をするのが初めてだったので、とりあえず何ができるのかをざっくり把握することをやりました。1個ずつというのは到底出来ないので、カテゴリごとに似たような命令はすっ飛ばして、雰囲気を感じていました。

BVH の validator をたくさん書く

ソースコード

BVH の構築後に色々データをいじりまくっていたので、一度バグりだすと何が原因なのか特定するのは難しいです。この時、処理における事前条件/事後条件を書き出して、処理する度にチェックするコード debug build で入れてました。かなり役立ち度は高かったように思います。

開発過程でやらなかったこと

cache miss のプロファイルをとる

これは本当はやりたかったのですが、 VS 2019 でやる方法がわからず。わかる人がいたらぜひ教えて欲しいです。

BVH の visualizer とか評価尺度を見て考察する

割と定数倍高速化をしてたら終わってしまったので、BVH の構築は top-down SAH のものからほとんど進歩していませんでした。もうちょい構築の工夫を入れてたら、 SAH とか体積とか当たり判定の分布とかを真面目にとっても良かった気がします。

UT を書く

reference 実装がきっちり与えられていたので、あまり必要ではありませんでした。今回は validator があれば大体問題なかったような気がします。

最終的な速度

正確に計測するのは大変なので諦めましたが、本番環境(CUI 版) + 本番データセットの hairball で 3回計測したときの中央値を取ると、最初と最後でこれ位の差がありました。あと、embree みたいな現状最強格のやつとも比較したかったのですが、使い方がよくわからなかったので諦めました。まぁこれだけ速度差があるといっても、バグを修正しないと何とも言えないよなぁという気持ちはあります。

build(ms) intersect(ms)
reference 9,491 202,253
最終版 7,660 9,500
速度比(ref / 最終版) 1.24 21.29

終わりに

振り返ってみると、これは本当にレイトレ合宿の参加記なのかという気持ちになってきました。とはいえ、こうしてまとめてみると、意外と頑張ったなという気持ちになってきたので、とりあえずは良かったかなと思います。初めてガチで最適化を頑張ってみましたが、同じ言語でも、これだけ違うんだなぁみたいな感慨深さはあります。

来年こそは、綺麗な絵+CUDA を頑張りたい気持ちです。

役に立つかもしれない、Task Queueの作り方

はじめに

この記事は、レイトレ合宿7 アドベントカレンダーの記事です。

様々なタスクをマルチスレッドで処理するために Task Queue を使う場合があります。 OpenMP 等のように気軽に並列化できる処理もたくさんありますが、例えば BVH を構築する場合、 この記事 内に紹介されるような Task Queue が使われることも多いかなと思います。 BVH を何種類も作ったり、他の処理でも Task Queue は使いどころがある気がします(具体的にたくさん挙げられるとは言っていない)し、可読性向上の観点からも、モジュールとしては小さいですが、独立したモジュールを作りたい気持ちになります。

Task Queue を独立したモジュールとして作ろうと思って色々考えてみると、終了条件をどう表現するかが比較的難しいポイントと感じました。 例えば、今は Queue が空でも、処理中のスレッドが新しくタスクが放り込まれるかもしれないため、Queue が空だという条件は使えません。 また、処理が終了したら迅速にスレッドを終了する必要もあるため無限ループするわけにもいかず、終了条件を記述した関数を渡すのもあまりしっくり来ませんでした。

このような時、数値で表現される進捗を queue に登録する方法だと、比較的上手く表現できそうと感じたので、紹介してみることにします。 例えば、BVH の構築であれば、Leaf Node を作成したタイミングでその Leaf Node に含まれる primitive (Polygon とか) な object の個数を進捗として報告し、最終的に進捗が BVH 構築時に渡される object の個数に到達すれば終了して良い、といった感じになります。

実装

c++ での実装例はこちらになります。TaskQueue の実装と、BVH の構築とよく似た処理を行うサンプルコードを一緒に置いておきました。 この記事を書いた環境の都合上、std::optional の代わりに boost を使っています。

github.com

例えば std::queue との差分としては、

  • empty() や size() 相当の処理等はなく、進捗登録とタスク登録/取得しかできない
  • front() と pop() は同時にやる
  • 要素が取れる保証がないので、要素取得は optional で包む

といった感じになります。

おわりに

今回はこれ以上深追いしませんでしたが、もっといい設計はできるかもしれないので、いい方法等ありましたら教えて頂けると幸いです。また、この Queue に名前がついていたり、こんな使い方が出来そうみたいな例などあったりしたら、教えてもらえると嬉しいです。

レイトレ合宿6 参加記

要約

  • レイトレ合宿6 に参加した
  • めちゃくちゃ面白かった
  • アセットは適当に作っても美しくならない

はじめに

9/1(土)〜2(日)にかけて、レイトレ合宿6 に参加してきました。最終的に、僕はこんな絵を書いて、 16 / 19 位でした。

f:id:xyz600:20180903221808p:plain

スライド

speakerdeck.com

コード:https://bitbucket.org/xyz600600/xyz_renderer/src/v0.3/

コードは Rust で書かれていますが、初心者なのであんまり Rust っぽいコードとして参考になるかはわかりません… (一部 unsafe に const ptr の dereference とかやっている)(解決方法はわからず)

(当然)上位の方々に比べるとイケてる絵は出せなかったのですが、来年やりたいことを忘れないように、ブログにまとめることにしました。来年は僕もイケてる絵を出力してみせるぞ!!

本番前と本番とで、やったこと思ったことを中心にざっくり書いていこうと思います。
全部書く時間がなかったので、部分的に結構抜けてますが悪しからず。

本番前

5月

理屈を理解した上でレンダラを書いたことなかったので、今回の合宿の目標をあれこれ考えていた。最終的には

  1. オブジェクトをたくさん配置する
  2. 高速化を頑張る
  3. 理論を理解する
  4. アセットを自分で作ってみる

とかかなーと思っていた。この時は、適当にアセットを作ってもパストレだしきれいな絵が出るだろうくらいに思ってたので、アセットを考えるのは完全に後回しにしていた。そんなこと全くなかったんだけどね。

また、どうせなら新しい言語を習得したいと思って、Rust で書くことにした。そのため、5月は Rust の勉強をしつつ、Ray Tracing in One Weekend を読み進めていた。

6月

仕事が忙しい。レイトレ業はお休み。

7月

あれ、何もやってないけど残り2ヶ月しかないぞ…??
という訳で、焦り始めて割とここから頑張った。

色んな資料を見ながらレンダリング方程式の理解に挫折していたが、

www.slideshare.net

を見て疑問点が氷解し、念願のレンダリング方程式を会得した。@Shocker_0x15 さんの記事は割と最後までずっとお世話になっていた。

設計で悩んでいたこともあって、月末あたりでやっとコーネルボックスが動き始めたが、並列化をしようと思ったらライフタイム周りでたくさんコンパイラに怒られるようになり、厳しい気持ちになった。

あと、すっかり忘れてたけどアドベントカレンダーのネタを考えないと明らかにやばいので、月末あたりで書く内容をやっと決めた。結局、こんな感じのものを書いた。

xyz600.hatenablog.com

特に、Frustum Bounds とかめっちゃカッコイイと思ったので実装したかったけど、時間的に無理だった。残念。とはいえ、当日に数人から「アドベントカレンダー書いた人」という認知をされてよかったなぁと思ったので、次は実際に実装する技術を調べる感じで、積極的に書いていきたい。

途中でICFPC に出場していたり、その反動で3日位体調崩してたりしてた。

8月

BVH の実装とobj / mtl ファイルのローダが8月序盤で書き終わり、そろそろアセットを決めようと悩んでいたところ、交通渋滞のニュースを見て「車たくさん描画すれば、何かかっこよくね??」と思ってこれに決めた。そんなこと(ry

途中アメリカ出張が入り、時差ボケに苦しみながら書いたコードのあらゆる所にバグを埋め込んでいて、厳しい気持ちになった。

並列化の方法が全くわからなかった最中、プログラミング Rust が届いたことで解決した。rayon すごい。 またこの頃から「Rust PathTracing」でぐぐるようになり、Rust で パストレしてる先人の @gam0022さんの存在を知る。なぜもっと前からぐぐらなかったのか。

なんとなく道路っぽい雰囲気の何かを作り、車を並べてレンダリングしてみて、あまりのリアリティのなさに絶望した。思わず2度見して、3回くらい描画し直した。とはいえ、おそらく今年はこれ以上出来ることもないから、ノイズを出来る限り減らす方針で頑張ろうと決意した。

まずは強そうだし双方向パストレでも実装するか??と思って理屈を理解して頑張って実装していたけど、カメラパスで考慮した画素位置と別の画素位置にライトパスが飛び込むケース(伝われ)を完全に見落としていて、並列化の戦略と相まって実装困難になる。という訳で、諦めて合宿が終わってから実装することにした。

とはいえ、単純なパストレではノイズが全く取れず、 Next Event Estimation とか MIS を理解した上で実装したくて色々調べたり考えたりを繰り返していたのだけど、

rayspace.xyz computergraphics.stackexchange.com

あたりを見て割ときちんと理解できた。積分形式のままで考えることで、 MIS も割とちゃんと理解できた、はず…

よく考えたら、リアリティがない理由の1つは車も色も全部同じだからだよなぁと思って、せめて色だけでも変えることにした。適当に車体の色を表現するmtl ファイルの箇所を特定して、車体を6色の中からランダムに割り振ったり、車の位置をランダムに移動させたりしてごまかした。

このままフィニッシュできるかと思いきや、本番環境で動かない旨の通知を終了5時間前に受け取り、めっちゃ焦った。動的ライブラリが見つからないことが原因らしく、ここの一番最後の方法で --target=x86_64-unknown-linux-musl をつけてbuild したらOKだった。実行速度が15% 位落ちたけど、動いて本当に良かった…

こういうところは新しめの言語の方が強そうな気がしたけど、他のネイティブコードを吐く言語はどうなんだろうか。

本番

初日

CEDEC の話で盛り上がると過去の記事に書いてあったので、当日の資料 を見て意識を高める。なるほどわからん(ベイクが何だか知らなかったため)けど発表聞いたら絶対楽しかったんだろうなぁ。

到着するなり温泉に向かい、道中で色々話しながら親交を深めた。普段そんなにCGについて話す訳じゃないので、新鮮な話題ばっかりで楽しかった。途中、@gam0022 さんとお会い出来たので、Rust めっちゃ大変だったと伝えたら分かってもらえて嬉しかった。

特別イベント楽しみにしてたら、いきなり検定が始まるわ、三葉レイの応援メッセージが届くわで、かなり笑った。企画力高いなぁというのもそうだけど、これめっちゃ準備大変では… 運営の方々凄すぎる。 @ZinTwitt さんと @ishiyama_ さんのセミナーも普段聞けない話で面白かったんだけど、発表直前で自分のバイナリが果たして動いているのかが気になり始め、集中できなかった。ぐぬぬ

いよいよ発表会が始まったが、みんなめっちゃきれいな絵を次々に出しててめっちゃ焦った。自分でモデリングしている人もいるし、ただただ凄いなぁという感じ。僕のレンダラも無事動作したとわかってホッとしながら発表した。初めてにしては色々やってて凄いね〜 と@redqueenrenderさんに言ってもらえ、めっちゃ嬉しかった。発表会の後はご飯食べたり花火したりでワイワイしてた。

発表会後、色んな人に聞いてみると、Houdini や blender を使って1〜2日使ってモデル作ったぜって人がそれなりにいて、僕もすごく使ってみたくなった。自作モデルどう考えてもカッコイイんだよなぁ。僕も作れるようになりたくなった。

旅館の部屋で、@q_cinnamonさんにBCDというデノイザを詳しく教えてもらった。そもそもパストレの絵をデノイズする発想がなかったし、理論的にも面白いよと言って下さったので、落ち着いたら論文読むぞ。

絵に得点をつけるの凄い難しいよなぁと思いながら、寝る前までにみんなの絵に得点をつけた。みんなめっちゃきれいな絵なんだけど、どれか1つと言われたら @ushiostarfish さんの布が最高に好きだったなぁ。

2日目

いよいよ結果発表だったけど、流石に順当な順位だった。商品貰えなかったなーと思いきや、プレゼントが1個増えてじゃんけんで勝ったので、PS本体とレイトレ教材をもらった。翌日、きちんと教材をやりきって、無事にレイトレを完全に理解した。hardは無理ゲー。

船の出発まで時間があったので、海で飛び込みして遊んでた。天気が荒れたり晴れたりを繰り返してて、自分の荷物が危うく水没するところだった。次から島に行くときはゴミ袋を持っていくべきなのかも。

謎の力で@shuto_fmsさんと帰りの船の席が隣だったので、カッコイイ絵に関して色々話した。それまでは物理的に(ある程度)正しい絵が簡単に作れるってすげぇって思ってたのだけど、単純にきれいな絵が出せるのは楽しいよなぁという気持ちが強くなった。僕も「今回の作品は〇〇をこだわってみた。めっちゃカッコイイでしょ??」みたいなコメントが言えるようになりたい。

所感

  • 理論の勉強をきちんとしてよかった
    • 一部でいいから詳しい人の言ってることがわかると、めちゃくちゃ面白い
  • 今回の合宿に参加して、CGの絵がめっちゃ好きになった。
  • 来年こそはきれいな絵をレンダリング出来るようになりたい。