Kaggle コンテスト「Conway’s Reverse Game of Life 2020」で3位入賞しました！

はじめに

2020年9月から11月にかけて開催されたkaggleコンテスト 「Conway’s Reverse Game of Life 2020」 で、筆者 (kota.iizuka) を含むチームが 3位を獲得しました！

この記事では、今回のコンテストの概略を説明したのち、高速化という観点で私が行った手法を紹介します。

コンテストの概略

Conway’s Reverse Game of Life 2020 は、その名前の通り Conwayのライフゲーム の逆時間発展を計算するコンテストです。Conwayのライフゲームとは、格子上の値が一定のルールに従って動くセルオートマトンのひとつで、簡単なルールにもかかわらず下図のように複雑なパターンが得られることが特徴です。

各セルは「生きている」か「死んでいる」か2通りの状態を持っており（上図だとそれぞれ緑と黒）、生きているセルは周囲（8近傍）に2個か3個のセルがあるときに、死んでいるセルは周囲に3個のセルがあるときに、次の時刻に生きたセルになります。

コンテストの問題設定を大まかに言うと、「25×25の盤面が5万個与えられるので、t (1≦t≦5) ステップ計算したときにその盤面になるようなものを探せ」というものです。評価基準は、提出した盤面をtステップ計算したものと与えられた盤面とのセルごとの正解率、とわかりやすい内容になっています。

ルールから分かる通りこのコンテストは機械学習というよりは最適化の手法が問われています。kaggleといえば機械学習コンテスト、という印象があるかと思いますが、「Santa’s Workshop Tour 2019」など最適化系のコンテストもときどき開催されます。

解法

私の解法は kaggle notebookでも公開 したのですが、焼きなまし法をできる限り高速化するという方法をとりました。実装例はkaggle notebook のほうに書いた ので詳しくはそちらを確認してほしいのですが、今回のように最適化する対象がはっきりしている場合、性能向上のために重要となるのはなるべくたくさん探索すること、今回で言えば盤面の更新や評価を高速化することです。とくに、1か所盤面を変化させたときにtステップ後の盤面がどうなるか、を大量に計算する必要があります。

1. 局所更新

定義からも分かる通り、1ステップの更新では隣接セルにしか影響を与えないので、tステップの更新後も周囲tセルだけ計算すれば十分と分かります（下図はそれぞれ1ステップで1/4ずつ進むgliderと1/2ずつ進むlightweight spaceship, 1ずつ進むlightspeed signalsというパターンで、いずれも速度は1以下になっています）。

2. bit管理

また、状態が2通りしかないので更新をうまく書くことで1bitでセルを管理することができ、これも高速化につながります。詳細はnotebookに記載しましたが、盤面の各行は25bitなので uint32_t で管理して、25列あるテーブルは std::array<uint32_t, 25> とすればよいです。

3. SIMD化

さらに、25×25と盤面が小さいので、これを（手元のpcがryzenなのでavx2を使って）8並列でSIMD化できます（雰囲気としては array<uint256_t, 25> を32bitずつ区切って8個の盤面だと思って更新するような形）。焼きなまし法の並列化については問題ごとにタスク並列にもできますが、温度並列焼きなまし法というのがあるのを知ったのでそれを使用しました。

高速化の結果

これらの速度改善によって更新にかかる時間は以下のようになりました（測定環境は手元のryzen 5 3600, 測定コード全体は未公開）。それぞれの手法で数倍ずつの高速化ができていることがわかります。

• 高速化前は全体を毎回更新する実装で、ステップ数tに比例する時間がかかる
• 局所計算(1)については、理論的にはそれぞれ (25/3)² = 69.4 倍と 5×25²/(3²+5²+7²+9²+11²) = 10.9 倍になるはずなのでほぼ理想通りの高速化。ただしtの3乗に比例して遅くなっていく
• bit管理(2)は理論値の計算は難しいがbit演算を利用することで大幅に高速化される、またこの改善はステップ数tに依らない
• bit局所更新(1+2)は1個を更新するときに1行まとめて更新する必要があるので、tの2乗に比例して遅くなる

SIMD化(3)について、8並列なので理論値は8倍のはずですが実測値はそれぞれ8.9倍・14.2倍となっています。コンパイル後の命令列を見ると、コンパイラがSIMD化した結果ではレジスタスピルが発生しているほか、手でSIMD化したもの（リンク先の update_partial_x8 ）のほうが命令列としても短くなっており、これらが影響したものと考えられます。

このコードをさらにOpenMPで並列化して、PC2台（先ほどのRyzen 5 3600 (6C12T)と Core i7-8500U (4C8T)）を使って1問あたり約14分、5万問あわせて25日ほど回し続けました。

結果

このコンテストはスコアが簡単にわかり複数手法のマージが効果的なうえ、3位までしか商品（kaggleのロゴ入りTシャツ）が出ない、という事情があり、上位陣がチームを組んでさらにスコアを上げていく展開になりました。自分も3位以内に入れるかどうかで一喜一憂という毎日でしたが、最終日に markuskarmann さんとチームを組み、188チーム中3位を獲得しました。上位解法として多く使われたのはSAT（充足可能性問題）ソルバを使う方法でしたが、 markskarmann さんは CNN を使用した解法 で興味深かったです。

おわりに

kaggleで高速化が役に立つやや特異な例として今回の話を紹介しましたが、機械学習コンペにおいても前処理がボトルネックになっていたり、提出時の計算時間制限に間に合う範囲で精度の良いモデルを作る必要があったりして、高速化という切り口で考えることがたくさんあるなあと感じています。みなさんも気軽にkaggleコンペに参加してみてはいかがでしょうか？

参考文献など

• https://dev.to/yohhoy/conways-game-of-life-w-ffmpeg-cka
  • ffmpegを使うとコマンド1個でライフゲームの図が生成できるという記載があり参考にしました。記事中の図は下記のコマンドで生成しました
    • ffmpeg -f lavfi -i life=s=60x60:r=5:life_color=00ff00:ratio=.5 -sws_flags neighbor -vf scale=360:360,drawgrid=w=6:h=6 -vframes 100 lifegame.gif
    • ffmpeg -f lavfi -i life=s=60x60:r=5:life_color=00ff00:ratio=.5:f=spaceships.txt -sws_flags neighbor -vf scale=360:360,drawgrid=w=6:h=6 -vframes 31 spaceships.gif
    • ffmpeg -f lavfi -i life=s=110x30:r=5:life_color=00ff00:ratio=.5:f=lightspeed_signals.txt -sws_flags neighbor -vf scale=660:180,drawgrid=w=6:h=6 -vframes 62 lightspeed_signals.gif
    • spaceships.txt, lightspeed_signals.txt は空白文字とそれ以外で初期状態のセルを表現したテキストファイル
• http://www.gabrielnivasch.org/fun/life/lightspeed-signals
  • 速度1で進むパターン lightspeed-signals はここから取得しました。ほかにもたくさんあるようです
• https://ci.nii.ac.jp/naid/110002721831
  • 温度並列焼きなまし法の説明はこちらに記載されています。本文中では省きましたが温度管理がほぼ不要で、焼きなましの再開ができることが便利でした

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。