読者です 読者をやめる 読者になる 読者になる

ふるつき

記事と内容がないです

SuperCon(スーパーコンピューティングコンテスト)2016の本選に出た

競プロ

SuperConで検索したら出なくてスーパーコンで検索したらでるとかあり、やなのでタイトルがアレになった。なんか夏の電脳甲子園とか言われてるらしいが私も今日(最終日)初めて知った。

結末

SuperCon本選でチームワークを発揮したので、我らがkingyo(奈良高専から出場。うち二人は情報処理研究会所属)は3位だった。すごいな。

SuperConについて

よくわからなかったが、SuperComputerのすっごい資源をつかって計算させてくれるプログラミングコンテストだと思う。今年は東工大TSUBAMEというスパコンを使った。

予選

SuperConには予選がある。倍率は1.5~2.5倍くらいじゃないだろうか(予選応募総チーム数をちゃんと聞いていないのでわからない)。

予選はスーパーコンピュータは使わせてもらえず、まずはC言語アルゴリズム力を試されるようだった。

私は予選の問題はさっぱりわからなかったので(愚直実装ならばn時間悩めばできるだろうな、くらいだった)。チームメイト(名前を出していいのかわからないが二人いる。AとBにする)のAが去年JOIの本選にでるなど健闘していたのでJavaで解コードを書いてもらい、C言語に移すなどしていた。要項にはANSI Cに準拠すること、とあったが、ANSI CがどんなCか全然わからず、不安のなか移植をした。

結局Aが書いてくれたのは枝刈り全探索みたいなコードだったと思う。C言語のよくわからない型挙動(わかるひとにはわかる)に苦戦しつつ(特にint[]とint*がまるきり一緒だといつでも言えるわけではないのにやられた)、なんとか動くコードにして、提出した。このときは予選突破があるとは思ってなかった。

それからn日くらいたって予選突破報告がTLに流れ始めたが、我らのチームにはメールが来ず、やはりだめか……と言っていた。しかし本戦出場の意思がないチームがあったのか、なんか一番お尻につっこまれて本選にでられることになった。かなり嬉しかった。Aさまさまという感じだった。

本選

本選では5日間阪大に通った。家からだと2.5時間くらいかかるので移動が長くて最悪の日々といえた。私は移動の時間が嫌いだということを再認識させられた。

それはそれとして、とりあえず本選で問題の説明がされたりした。できるだけ良いスコアを出す系の問題だった。詳細は他の人のブログとか公式っぽいサイトとか見るといいと思う。

私はそういう問題の対策は山登り法と焼きなまし法しか知らなかったので、焼きなましっぽいのの実装を始めた。AとBはなにかしらランダムではない方法を模索したり、GPUで評価値を求めるプログラムを書いたりしていた。

二日目の終わりくらいにはほとんど焼きなまし完成みたいな感じで、動くコードができていた。手法としては、グラフ中の四点(二点同士が辺で結ばれている、などグラフの正則性を保つような制約つきでランダムに選択したもの)の辺をつなぎ替えるみたいな感じだった。これをtsunaginao_c関数と名づけて、ファイル名をtsunaginao.cとしてうまいじゃんと笑っていたが、後にcudaを導入してtsunaginao.cuになったりした。

あとは重み付けとか、評価関数とかを書いていた。評価関数のわーしゃるふろいどをバグらせていたのは笑える。

三日目くらいにはちゃんと動くようになっていた。サンプルの小さいケースを食べて値が出る! などと無邪気に遊んでいた。この時点では初期グラフの良さがそのまま出力に直結する感じだったので、初期グラフをn回つくれるように改良したりしていた。

提出練習でもそれなりに動いたので手応えみたいなかんじだった。そういえばこの日にはAが行列積のGPU高速化番を作ってくれていたのでそれを使ったら最大ケースで2.5s程度で評価関数が動作して歓喜していた。なんかもっと早く、10倍くらいにはなるらしいのでここで満足してしまったのは一種の失敗。

四日目朝には、ずっと考え続けていたBの手法を実装してみた。それというのは初期グラフをランダムではなく規則的に並べるというもので、初期値はものすごく悪いが、入れ替えによるカイゼンがしやすいことがわかって採用となった。ちなみに初期グラフが綺麗なのでプログラム名はkireiとなった。

さらに、Bの考えがもう一つあり、辺の交換ではなくて色の交換を行った。これ自体はあんまり機能しなかったがこれとtsunaginao_cを組み合わせるといい結果がでるケースがあり採用となった。これを用いたプログラムがchimeraとkirei_swapvと名付けられた。

さらに、競技直前に、「ある程度結果を出した後のグラフからもう一回やりたくない?」という話がBから出て爆速実装を行った。これは初期グラフ生成のかわりにグラフを読み込む処理を加えるだけなのでそんなに難しくはない。しかしここまでで、gpu(これが最初のプログラム)、kirei、chimera、kirei_swapvとよっつのプログラムを作ってしまい(それぞれコピーしてディレクトリごとに管理していた)、それらのすべてに手を加えなければならないので大変だった。じっさい、gpu以外のプログラムでのrestore機能の実装は競技開始してからだった。

四日目なのでお昼すぎから競技だった。だいたい、一つの問題ケースにたいして5minずつ割り当てて、chimeraとkireiをつかって頑張っていた。最初はGPU利用の競合を懸念して一つしかSolverを走らせなかったが、とちゅうから並列で走らせた。ちゃんとプログラムが遅くなって面白かった。

最初は全然振るわなかったkingyoだが、なんか次数がでっかいケースなどつよいのでは?とか適当に考えて6問目を回したところ、1位かそれに準ずる順位を取れて俄然士気が上がった。それぞれの問題で10~6位程度を取れたので、restoreプログラムを活躍させて一回submitしたファイルから計算を再開させるなどしてちょっとずつスコアを改善するちくちく作戦をやっていた。ここでrestoreでは焼きなましが走ってしまいなんかせっかく山に登っていたのに降りやすくなってしまっておもしろかった。kireiに関しては完全に山登りにしたnouseというプログラムをforkして走らせたりしていた。どちらでも結果はそんなに変わらない感じだった。

そんなことをしていると1位を取れる問題がいっこでたので、それのSolverは競技中ずっと走らせていた。これがなくば1位は死守できずしんでた。

競技終了前の平均得点は4位相当だった。最後に! と最後の5分も計算させてsubmitし四日目を終えた。早く帰れてご満悦だった。

これは嘘でなんかインタビューがあった。そこでは大和郡山市での金魚の養殖が300年ほどの歴史を持つことを語り、武士の小金稼ぎがいまの大和郡山市の繁栄をもたらしていることを語った。大和郡山市が繁栄しているとはあんまり思ってないが。

最終日は表彰式などあった。なんか最後の5分で4位くらい浮上している問題があり栄光の3位を手にした。これはめちゃうれしかったのでうれしい!!!って感じだった。チームワークの勝利だ。もちろん1位や2位ではないので悔しいが、予選も危ういようなチームだったので期待以上の結果と言えた。 メダルと賞状ももらったが回収された。なにやら後日郵送となるらしい。ほんまか。

表彰後は懇親会みたいなのがあったのでたこ焼きとフライドポテトを食べながら優勝チームやそうでないチームと話をした。あとらてという人(これがつよいひとで優勝チームのつよいひとのひとりでありたいへんつよい)にきんいろモザイクという漫画の1巻をプレゼントした。誕生日だったのと、きんいろモザイクが欲しいというのが重なるとふるつきからきんいろモザイクをもらえたりする。わたしは金色のコルダという多分乙女ゲーのこみからいずっぽいのもすきです。

他のチームのひとの話をきいていると考察がなされていて頭がいいとおもったり、うちの評価関数はめちゃおそいということがわかったりしてもっと戦えたのではと思ったがそういうときは他のチームも戦えてしまうので結果オーライとした。

その他

阪大には学食があり、多分自炊の方が安いが安めの値段でお昼が食べられた。サラダバー的なところに杏仁豆腐があり、毎日堪能した。

SuperCon中はツイッターができずかわりに掲示板のようなものが用意されるのだがそこに迂闊に九条カレンちゃんのパーカについて書き込んで「性的マイノリティを揶揄」してしまった。この件については重く受け止めており、これからは性的マイノリティとして揶揄される覚悟も辞さない(日本語が正しいかわからないが)。

何かもっと書きたかったかもしれないが忘れたのでいいや。