TCO Announcement Fun Round - WaterfallFishingの反省
2017年5月の、ちょっと古いマラソンマッチですが、忘れないようにするために、書きました。
問題
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16930&pm=14615
川の幅 W (2≦W≦200)
川の長さ L (5≦L≦100)
川には、岩がある。(5≦岩の数≦W*L/10)。ただし、岩の場所は、分からない。
まず、D日間連続で、魚が上流から下ってくる(4≦D≦20)。
- 5≦魚の数≦100
- 魚は、魚群の中心の位置M・標準偏差Sの正規分布で、まず上流に配置される。(0≦M≦W-1, 2≦S≦W/4)。M,Sも分からない。
- 魚はまっすぐ下るが、岩にぶつかると50%の確率で左に1マス、50%の確率で右に1マスずれて落ちる。
- 魚が、下流に下ってきた魚の数は、場所ごとに分かる。
(範囲になっている変数は、テストケースごとに、ランダムに均一に選ばれる)
D日間分の下流に下ってきた魚の数の情報を用いて、D+1日目に落ちてくる魚の場所を予測し、罠をしかけて、できるだけ多く捕れ。スコアは、(捕まえた魚の数)/(罠を仕掛けた数)で決まる。与えられた計算時間は60秒間。
方針
機械学習で予測した。ただ、この問題、データが足りなすぎる、かつ、あまり当てにならない。魚群の位置M,Sは毎日変わるので、ここの予想が外れると、ほぼ魚を捕れない。そういうわけで、機械学習は避けて、確率の知識などで解答した人が多かったっぽい。
ただ、自分は機械学習でごり押しした。データ不足を補うために、自前でデータを生成した。やり方は以下の通り。
(1) 「岩配置」と「下流に下ってきた魚の数のデータ」のペアを、問題と同じ方法で200種類生成。
(2) 「岩配置」から、下流に下ってきた魚の数の期待値を場所ごとに求める。上流の魚の確率分布は、1000万回シミュレーションして求めた(数学強い方なら解析的に求められる)。上流での魚の確率分布と岩の配置を用いれば、簡単な期待値DPで、下流に下ってきた魚の数の期待値を求められる。これを機械学習の目的変数(予測したい値)として使用。
(3) 「下流に下ってきた魚の数のデータ」は、機械学習の説明変数(特徴量)の生成のために使用。最終的には以下を説明変数として用いた。
- 下流の位置 X
- 川の幅 W
- 川の長さ L
- 魚の数
さらに、Xの近傍のデータも説明変数に追加した。近傍をY (X-3 <= Y <= X+3)として
- D日間で、Yに下ってきた魚の総数
- D日間で、Yに下ってきた魚の割合の和
- D日間で、Yに下ってきた魚の総数とXに下ってきた魚の総数の差
(4) あとは、自前のランダムフォレスト(そろそろ、自前Gradient Boosting系のものを用意しておきたい…)で50秒間訓練。
(5) 全ての位置Xで、下ってきた魚の期待値を予測し、もっとも期待値が大きい場所1か所に罠をしかけた。
まとめ
他人の解法と、自分の解法がズレてたおかげで、まさかの1位!機械学習しても2位のスコアとの差は大きくないのですが、不確定要素が多すぎるこの問題においても、機械学習が有効だったのは、自分でも驚いた。データ生成の仕方が重要。
実は、このマッチはあまり時間の余裕がなく、また直前のマラソンマッチのミスでレートを大きく下げていて弱気になり、参加する予定はなかったのだけど、tomerun氏の無言の煽り励ましツイートで、参加することになったのでした。マラソンマッチは、最後まで何が起こるかわからないので、皆さんも参加しましょう!