競プロ日記010: MM142に参加しました

TopCoderマラソンマッチ(MM142)に参加しました．最終結果は19位でした．

問題の概要

N×Nのグリッド上にいくつかプレゼントが配置されています．このグリッド上(一番外側)に，一定の確率でエルフが生えます．このエルフたちをN×Nターン操作して，プレゼントを盗み出すという問題です．障害物としては，所々に木が生えています(初期盤面から固定されていて，途中で現れたり消えたりすることはありません)．また，エルフの動きを邪魔するため，AIがグリッド上に木箱を配置(0個以上，複数設置可)する場合があります．ただし木箱設置にはお金(金額はパラメータCとして固定)がかかり，お金は毎ターン1ずつAIに与えられます．AIはテストケース毎に5種類の中からランダムに選ばれ，これらのAIは過去の問題(MM131)で参加者が作成したプログラムだそうです！

プレゼントをエルフがグリッド外まで持ち出すことができれば，盗んだとみなされます(つまり持っているだけではダメです)．すべてのプレゼントを盗むことに成功すると，N×Nターン経っていなくてもプログラムは終了します．プログラムが終了したとき，持ち出したプレゼント数×100と，終了までにAIが使用したお金の合計額を加えたものがスコアになります．たとえばプレゼントを3個盗み出し，その間AIが50のお金を使ったとすると，スコアは350になります．

やったこと

最初の解答

おそらく多くの人がやったであろう，

プレゼントまでの最短経路を通ってプレゼンを取る
プレゼントからグリッド外への最短経路を通って脱出する
プレゼントまでの経路が見つからない場合は適当な箱に対して同じような処理を行う

といったものでした．当然プレゼントまで進む途中に箱を置かれてしまうので，プレゼントを取れずに箱ばっかり取る事になります．それでもCが大きくグリッドが大きいものであればそれなりにプレゼントを取ってくることができるので，これだけでも70点くらいは取れそうな感じです．経路の計算が間違ってて最短経路じゃない場合，AIが余計に箱を設置することになってスコアが少しだけ高くなったりすることもありましたが，そういうので得点が上がってもあまり嬉しくないです．

2番目以降の解答

2番目以降の提出では，プレゼントまでの経路中に箱が置いてある場合への対処を主に行いました．

プレゼントの前に箱がある場合，これを持ち去ったとしてもまた箱を置かれてしまってプレゼントが取れなくなるため，手助けが必要になります．

1人が箱を取り去り，空いた部分にもう一人が素早く(同じターンに)入り込みます．

しかしこの方法だと，多くの場合はさらに箱を置かれて道がふさがってしまいます．

ですので，プレゼントを取りに行ったエルフの隣に箱を持ったエルフを潜り込ませて，帰り道を確保しておきます．

70点以上を目指すには，基本的にこの動作に類するものが必要になります．

やりきれなかったこと

私の解答では，上手くいった場合に上記のような動作をしてくれますが，実際のところはいろいろと不具合があって，エルフが閉じ込められたりすることも結構ありました．対処としては，脱出したいエルフの逃走経路を確保するために別のエルフを派遣することです．これも上手くいったりいかなかったりなので，しっかり修正して提出したかったですが間に合いませんでした．あとは逃走経路に他のエルフが立ち入ってしまってデッドロック状態になる場合もあって，その辺の対処も不完全でした．この辺りがもう少しスッキリ書けていれば，もう1～2点上がるかなーと思っています．

それから，この問題では5種類のAIがランダムに選ばれるので，上位に入ろうとするならAIの特定と，それらに対して最適な行動ルールを設計すべきです．これには各AIの特性を見極めるとかソースコードをちゃんと読むなりしないと行けないので，とても大変そうです．考察力とか実装力が高まればその段階に進めると思いますが，今のところは難しいです．

ハイレベルな解法

simanさんのブログやValGrowthさんのブログにわかりやすい解説がありますので是非ご参考に！

日記

以下，メモしていた日記を簡単にまとめておきました．あまり得るものはないです．

12/8(Thu)

午前2時開始と思い込んでいましたが，3時からでした．3時になると同時に登録して，いつも通りサンプルコードとテスターのダウンロードを済ませました．その後「あーこれ系かー」と思いつつもよくわからず入眠．お昼にサンプルを動かそうとしてけれどもテスターが動かなくて困った．どうもファイルパスの問題っぽいのでフォーラムに質問したら修正版を用意してくれた．これで戦える！という感じだけど今日はこれで終わりっぽい．疲れた．

12/9(Fri)

方針を決める．とりあえずプレゼントを狙えば良い気がするので，プレゼントからグリッド外への最短ルートを調べることにする．しかしルートの途中に箱があると通れないので，箱を処理する部隊が必要．箱を持っていると他の箱を乗り越えられないため，ルートの歩数分だけ人数が必要になる．まあその辺はあとで考えるとして，各プレゼントを起点とした枠外へのルートを取得する部分から書き始めることにした．

12/10(Sat)

実装が結構大変な気がするので，まずはシンプルに箱とかプレゼントを拾ってくるコードを書くことにした．基本的なコードは書けたけど完成はせず．明日に持ち越し…．

12/11(Sun)

いろいろと勘違いに気付く．

箱やプレゼントがあるマスに移動すると自動的にそれを拾ってしまう(拾うかどうかを選択できると思ってた)
ターン毎の出力に改行を入れちゃダメ

修正したものをひとまず提出して70点くらい．まあそんなもんかな．seed1で1つもプレゼントが拾えてないので，まずはこれをどうにかする必要がある．プレゼントまであと1歩のところまで来ると目の前に箱が置かれるので，その時点でもう1人エルフを連れてくる必要がある．

12/12(Mon)

プレゼント毎にチームを作れば良いんじゃないかとか考えすぎて無駄なクラスを設計しまくった結果酷いコードが出来上がった．あまりに出来が悪すぎて最初の解答とさほど点が変わらずコード量だけが膨れ上がった．

12/13(Tue)

膨れ上がったコードにいろいろと機能を追加する．どんどん酷くなる．泣きそう😢

12/14(Wed)

書いたコードを全部捨てることを決断する．最低限やることをルールベースで書き直す．最終提出2時47分で前回に引き続いてまたギリギリ．大変疲れた．

感想

こうやって振り返るとかなり無駄な作業が多かったので，時間が無かったのではなく時間の使い方がとても悪かったということがわかりました．今回はテスターの不具合で早々に精神を削られたのでモチベーションの維持が結構大変でした．こういうゲームっぽいお題は結構好きな系統なんですが，その割には問題へのアプローチ方法が整理されておらず試行錯誤が多すぎるように感じたので，無駄な行動を減らすためにしっかり復習せねばと思いました．

カメヲラボ

主にプログラミングとお勉強全般について書いてます