ハル研究所プログラミングコンテスト2017 参加記
ハル研究所主催のプログラミングコンテストに参加しました！ www.hallab.co.jp
ハル研究所プログラミングコンテストとは
ハル研究所主催の、年1回行われるマラソンマッチ形式のプログラミングコンテストです。 元々は、ハル研究所のプログラマの方たちが内輪の遊びとして始まったのが発端らしいのですが、2003年からは学生が参加可能なコンテストになったみたいです。
今年の問題
今年の問題は、「UFOを使って中央にある農場からフィールド上にあるすべての家に箱を届ける」というものでした。すべての家へ箱を届けられるまでのターン数の少なさを競い合います。
UFOには大UFOと小UFOがあり、大UFOは「多くの箱を持てるが、移動スピードが遅い」、小UFOは「少ししか箱を持てないが、移動スピードが速い」という特徴があります。この特徴を活かしつつ、各UFOをうまく連携させて効率よく箱を家に届けることが問われます。
詳しい問題の内容についてはこちら
自分の実装したプログラムによるUFOの動きは以下のようになりました。
中央の緑色の●が農場で、動いている白色の●がUFO、周りに散らばってる小さな●が家です。このViewerはハル研の方が準備してくださいました。
実装方針
自分の実装したアルゴリズムの方針は以下のとおりです。
小UFOの基本的な動き
- 家をクラスタリングして各小UFOにそれぞれのクラスタを割り当てる。
- 各小UFOには担当クラスタ内の家に箱を届けさせるが、このときの届ける順番をTSPの要領で決定する。
- クラスタ内の家の数が少ない場合は全探索、多い場合は3-optによる改善法を用いた。
- 担当クラスタ内のすべての家に箱を届けたあとは、まだ届けていない近くの家を貪欲に探してそこを次の対象にする。
- 持っている箱の数が0になったら近くの農場 or 大UFO (これらを補給地とする) を探してそこから箱を補給する。
大UFOの基本的な動き
- 家のクラスタリングのあと、要素数の多いクラスタを探してそこの中心(重心)を最初の目的地（これを初期目標位置とする）にする。
- 大UFOは2つあるので、この2つが近い場所を目指さないように調整する。
- 初期目標位置に到着したら、まだ届けていない近くの家を貪欲に探してその家に箱を届ける。
- 移動中に家を(たまたま)通過した場合は届ける。
- (大UFOは半径が大きいのでこれだけでかなり改善できる。)
ヒューリスティック
本当に改善されるのかの証明はせず、直感的に改善しそうだと思った処理を加えました）
- ノリでk-means++を改造
- クラスタ内のTSPを解く前に農場から近い順でソート
- 大UFOの初期目標位置を若干農場に近づける
- まだ箱を届けていない家を貪欲に探すときに、重複して同じ家を探さないようにする。
- 具体的には、各家に対してその家を目指すUFOとの最短距離を記録しておく。
- この最短距離は大UFO/小UFOのスピードの違いを考慮させる。
- 小UFOについて「持っている箱が少ない & 補給地が近くにある」ときは、家に箱を届けるよりも補給することを優先させる。
- 小UFOについて、担当クラスタ内の家に順に箱を配る過程において、次の家をすでに他の小UFOが目指している かつ 近くにある場合はスキップさせる。
- 小UFOが貪欲に家を探す過程において
- 方向ベクトル
ufo.pos() - office.pos()に重み付けする。 - 大UFOに近い家には運びにくくするように重み付ける。
- 方向ベクトル
- 小UFOが近い補給地を探すときに、大UFOが動くことを考慮する。
- 現在の大UFOの速度ベクトルと大UFOとの距離からいい感じの位置を計算して、そこを補給地の候補にする。
- 大UFOが貪欲に家を探す過程において、近くにある箱の所持数の少ない小UFOへの方向ベクトルに重み付けする。
他にも、偏角ソートなど考えたけど実装方針とそぐわず破棄したアイデアがいくつかあります。
乱択
上の実装だと(特にヒューリスティックなアルゴリズムにおいて)マジックナンバーとなるところが多くあるので、それらを乱数にし、乱択によって最適なシード値を探す。→その最適なシード値を最終的なUFOの行動にする。
- 乱択を回す回数は、制限時間の60秒を超えない範囲でできる限り多くした。
- 実際に箱の運搬をシミュレートしてターン数を測定し、そのターン数を乱択の評価関数とした。
- 今回の問題の場合だと、入力として与えられるものがステージ情報のみなので、このようにターン数を直に評価関数にできる。
高速化
乱択を使わない段階では、一瞬で計算は終わるが、制限時間いっぱいで乱択を回したい。というわけで多少の高速化を検討した。
- 乱択において
- 計算済みのシード値に対する最適値よりも評価値が超えた瞬間でシミュレートを終了して次のシード値へ移行する。（枝刈り)
- ステージ上の家の数から最低目標スコアを決め打ちして、それを超えるシード値に対しては即計算を破棄する。
- 当然だけど
std::vectorやstd::listなどの各操作に対するオーダーを考慮してプログラムを組む。 - 距離の比較に関しては、
vec.distではなくvec.squareDistを用いる。rootの計算は遅いため
- 前計算として各家間の距離は計算しておく。
アルゴリズムをまとめると
「クラスタリング + 嘘TSP + 嘘貪欲 + なんちゃってヒューリスティック + 乱択」
です。
実際のソースコードはこの記事の一番下にあります。
ところで、問題の条件で
ほとんどの家はまとまって配置されていて、街を形成しています。
一方で、街から離れたところにある家もあります。
というのがありましたが、これをプロコンが終わったあとに知りました（は？）。
たまたま「クラスタリングして探索する家を決定する」という方針がこの条件に適していたので結果オーライだったのですが、ちゃんと問題文を読まないとなぁと反省してます。 街の存在を知った状態で考察してたらもう少し違ったアルゴリズムになっていたかもしれないです。
Stage.cppにステージ配置の実装があるので、そのコードを読んでアルゴリズムを考えるという手段も有効だったかも。
結果
最終的なベストスコアは、ターン数: 15,137ターン で、順位: 7位 となりました！
景品として、かわいいUFOが描かれたどんぶりをいただきました。
このUFOはハル研さんのスマホ向けゲームアプリ『はたらくUFO』に登場するキャラクターみたいですね。
感想
マラソンマッチ型のコンテストへの参加は初めてだったので最初は戸惑いましたが、楽しく取り組むことができました。 「アイデアを思いつく→実装する→改善する」の繰り返しで、徐々にスコアが改善する過程は楽しかったです。マラソンならではの面白さだと思います。
問題も、大UFOと小UFOの特徴の違いをどう活かさせるかなど、参加者の発想力を試すような面白い問題でした。
また、ハル研さんからは、サンプルプログラムとは別でviewerの提供がありました。 スコアが改善されるに連れてviewerの色が赤色から緑色へ変化していく過程はそれだけでも気持ちよかったです。UFOの動きを考察する上でもとても役に立ちました。
結果に関してですが、最初はベスト30入り&どんぶりゲットを目指していたので、達成できて嬉しいです。ただ、あと少しでベスト5だったので悔しい部分もあります。来年はもっと良い結果を残したいです。
来年も参加したいし友人にも積極的に勧めていきたいプロコンでした。
楽しいプロコンの企画・運営をありがとうございました！！！
後日
ハル研究所の山梨開発センターにてインターンシップに参加させていただきました！
詳しい内容は言えませんがとてもたのしいインターンシップでした。
