#HTTF 2021予選に参加しました。
atcoder.jp
2020/11/07に開催されたHACK TO THE FUTURE 2021 予選に参加しました。
社会人になってから初めてAtCoderに出た気もします。
面白体験だったので参加記を書いておきます。
HACK TO THE FUTURE, HTTFとは？
フューチャー(株)が主催するプログラミングコンテストです。
特徴は以下の通りです。
- ヒューリスティックな問題が出る
- コンテストが8時間と長い
- ビジュアライザが付いてくる
誤解を恐れずに簡単に表現すれば「ゲームAIコンテスト」だろうか？
今回の問題について
- 2次元平面上に数字の書かれたカードが散らばっている。
- ロボットが平面上を走り回ってカードを回収する。
- ロボットはスタックでカードを管理していて、新しく拾ったカードを平面上の空きスペースに置き直すことができる。
- 全てのカードを回収&スタックの状態がソート済みになるまでの移動距離が評価値
最初問題をみた時に、3つめの項目に気づかなくて「工夫要素無いじゃん」って思った。
コンテスト後に配信されたビジュアライザの動画があるので、それを見るのが一番分かりやすいです。
↓集めて、置き直して、順番に回収の分かりやすい動き。
コンテスト中の流れ
コンテスト開始前
「お仕事で疲れてるし、問題見て意味不明だったら撤退しよ...。でもワンチャン賞金が貰えたら嬉しい。」みたいな気持ちで準備する。
ここで言う準備とは以下の様なとても簡単なやつです。
- パソコンにc++が入っているか確認
- 制限時間ギリギリで処理を終わらせる記述の確認
- コンテスト中の流れ「正の点数を取るプログラムを書く→評価部分を自前で書く→ビジュアライザで眺めて改善要素を探す→考察して改善実装」をメモしておく
コンテスト開始後
カードを順番に集めるゲームであることが分かる。
評価部分の実装がとても簡単そうで嬉しい。（文字列を舐めるだけ）
正の点数を取りに行くことは簡単そうなので、ゲームをコントロールするクラスを書き始める。
node.movePick(num);で特定のカードを拾いに行ったり、node.moveTo(x, y);で移動できるようにした。
提出したらコンパイルエラーになって困る。よくよく見たら言語周りの設定を間違えていた。
ここら辺もコンテスト前にやっておけば良かったね。
いろいろ確認しなおして出したら133k点。まず正の点が取れたのでビジュアライザで眺めるフェーズに移行。
ビジュアライザで考察
この時点まで改善方法が思い浮かんでなかったので、ビジュアライザがあって助かる〜。
ビジュアライザで最初のプログラムを眺めていると動きに無駄を感じます。
↓順番にカードを拾いに行く手法。終盤だけ抜粋。94を拾ってから95に移動する際に、ついでに99を95近くまで運んでやると嬉しそう。
ということで「SからGに移動する際に、Gの近くに移動させると嬉しいカードCがあればついでに動かす」を実装します。
ここで嬉しさとは「カードCから見たC-1, C+1との距離」として、ついでに動かすことで多少回り道をしても嬉しさの変化が大きいならその行動を選ぶようにします。
するとスコアが跳ね上がって155kになりました。スコアが上がると嬉しい。
味を占める
↑ビジュアライザで動画を確認すると、賢そうな動きをしていてあまり無駄が感じられません。（強いプレイヤーからすれば無駄を感じるのでしょうが、この時点で僕の理解を上回る動きでした）なので無駄を指摘して改善するのではなく、行動の幅を広げることでスコアを上げることを考えます。
今までは「SからGに移動する際に、Gの近くに移動させると嬉しいカードCがあればついでに動かす」でしたが、
これを「SからGに移動する際に、どこかに移動させると嬉しいカードCがあればついでに動かす」に変えてみます。
するとスコアが156kに微増しました。
味を占めて、もう少し行動の幅を広げることを考えます。
「SからGに移動する際に、どこかに移動させると嬉しいカードCがあればついでに動かす」から
「
SからGに移動する際に、どこかに移動させると嬉しいカードCがあればついでに動かす。
Cの位置を新たなS, Cの移動先を新たなGとして再帰的に動かすカードを決める。
」
に変えてみます。
スコアが161kに上がりました。
↓ビジュアライザで眺めてみると、よく分かりませんが良い動きになっています。
そして手詰まりへ
ビジュアライザを眺めても改善方法が思い浮かばないので、乱数に頼ることにします。
↑の手法は0.05秒くらいで動くので、3秒の制限時間内で数十回試行できます。
嬉しさ関数を乱数でブレさせると解もブレますが、数十回の試行から上振れを引いてくればスコアが上がる気がします。
これでスコアが162kに上がりました。
思い浮かんだ手法を試しては上手く行かずを繰り返したり、ビジュアライザを眺めたりしていました。
ビジュアライザで↑動画の挙動とその前の挙動を比較すると、序盤に密を作っている方がスコアが高いことに気付きます。
ここで、中心からの距離を嬉しさに影響させるようにしてみます。
これでスコアが163kになって、これ以上は上がりませんでした。
他いろいろ
- 10x10の領域に集める方法は試しましたが、ついでに動かす手法と相性が悪かったです。これは密になりすぎて、ついでに動かす余白が生まれなかったからです。
- 考察に使えないかと思って「ついでに動かす」の状況を確認した。最初の2手くらいで数十枚のカードをついでに動かしいて、その後は微調整する程度。動かす量を絞って順番を探索したりしたけど効果はなし。
- 「カードCとカードC+1が隣接しているときは、同一とみなして嬉しさを求めたり動かしたりする」を試しましたが上手く行かず。
- 途中で家のネットがダメになって、ビジュアライザにアクセスできなくなりました。手詰まりフェーズに追い討ちをかけてきました。（のちに復旧した）
家のネットがダメになったので撤退です...。 #HTTF pic.twitter.com/UdXQffoE9M
— かがさん (@kaga3twi) November 7, 2020
- あまり多くのケースでテストしていなかった。苦手なケースの傾向をみると、改善の余地を見つけられたかも。
- 主流(?)の「10x10にまとめる→順番を焼きなまし」は想像すらできませんでした。そこに落とし込むスキルを持つ人はすごい。
- 発売直後のゲームを手探りでプレイしている感じがあって楽しかった。
- 8時間コンテスト+前後数時間は長いぜ！もちろん参加する選択をしているのは自分ですが、楽しさとは別に疲労も感じる...。
