SuperCon2014 参加記

こんにちは、プログラミング班班長の松崎です。 スーパーコンピューターを用いて1つの問題を解く、SupercomputingContest2014に参加しました。

東京工業大学で8/18(月)~8/22(金)の5日間開かれ、同級生と僕の3人でチームNITAkashとして参加しました。

1日目

無事到着。荷物が重い。太陽が眩しい。駅から東工大が見える。工業大学は田舎に隔離されてるかと思っていた。

開会式の後オリエンテーションが始まり問題の説明があった。どうやら今年はテトリスのような問題が出るらしい。

そして本選会場で問題の詳細が説明される。おおまかに言うと、テトリスのようなゲームで16種類用意されたピースのそれぞれの個数が渡されて、それをできるだけ高さが低くなるように積んでいくといった感じらしい (詳しくは公式を参照)。中には空洞のあるピースや某対戦ゲームのタイトルっぽい十字もあり、難しそうだった。

それから解法を考え始めるが、案が浮かばない。 しばらく経ってから、以下のような案が出た。

  • 人力解法

    人間の手で組み合わせを見つけるというもの。 人力解法を行ったチームの成績が良かったので、今思えばこれが正解だったかもしれない。

  • 遺伝的アルゴリズム

    答えを生物に見立てて生存競争させるメタヒューリスティクスアルゴリズムの一つ。 しかしこの時点では知識がほとんど無く、少し不安だった。

  • 隙間なくピースを詰めてそれが答えになるか確認する

    隙間なく詰めるのが難しそうだったので没にした。

他にも色々あったけど、覚えてるのはこれくらい。

人力解法はアルゴリズマーとして敗北した気持ちになりそうだったので、僕が遺伝的アルゴリズム+少しの人力解法と決めた。後々知った話だが、遺伝的アルゴリズムは経験と勘が物を言う素人には難しいものらしく、調整に悩まされることになった。

途中で休憩が入り(これは3日連続で開かれたが、実質twitterのオフ会のようなものだった) 、その後本格的に作業開始。

とはいえやはり説明や解法を考える時間が長く、コードはまだ未完成だった。

2日目

チームメイトが解析・デバッグ用にprocessingをダウンロード(ネットからのダウンロードは禁止なので、運営の人にUSB経由で貰った)。ある人から「processingで遊んでると負けるよ」と言われてしまった。 並列実行するコンピューターについての説明。どうやら本番ではCPUのコアが384個も使えるらしい! 休憩時間には実際に使用するスーパーコンピューターを見学した。自分達が開発中に用いるCPUを見つけ、チームメイトの一人が夢中で写真を取っていた。

この日で一応プログラムが動くようになった。しかし遺伝子がうまく競争せず、最下位不可避。

3日目

とにかく遺伝的アルゴリズムの調整。いいスコアを残したものとすると微妙で、できるだけ低く積んで限界が来たらそこで切り上げるという手法を取った。序盤は優秀だったが、息切れしてからが絶望的な酷さだった。

夕飯に評判の台湾ラーメン店こころに行ったが、まぜそばが非常に辛くて5日間の食事で最もつらかった。次に来るときは無難に塩ラーメンを食べたい。

4日目

いよいよ競技も終盤、最終日は発表会だったので、競技は実質4日目の1時15分までだった。 とにかく調整するが、うまくいかない。結局、開発したプログラムを提出したものの少し書いた人力解法の部分は切り捨てた。しかも設定ミスで使う使用コア数は開発中の64個のままだった。悔いの残るまま競技は終了した。その後の(黒歴史と化する)インタビューも終え、時間が余ったので秋葉原を観光をした。 3人ばらばらだったが、僕はラブライブのファンなので神田明神や竹むらに聖地巡礼に行った。 非常に楽しかったし、また情報オリンピックの時にも行きたい。神田明神の絵馬の絵が良かった。

5日目

いよいよ発表会。まず4日目に収録した各チームの黒歴史インタビューが放送され、成績発表という形。当然我がチームの入賞はなし。

その後の懇親会でジャンケン大会。チームメイトの一人はgoogle glass…風の伊達メガネをゲット。僕はジャンケンに負け続けおまけとしてgoogleストラップをもらった。

懇親会の途中で全体の成績が公開された。成績は21組中14位。解答のミス等で失格したチームを除けば最下位であり、ある人に言われた通り敗北。最下位も不可避だった。

まとめ

反省はアルゴリズムの選択のミス。チームの連携不足が痛かった。

残念な結果だったが、東工大で情熱をささげた5日間はとても楽しかった。 来年はもう少しヒューリスティクスアルゴリズムをよく学んで参加しようと思う。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

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