gotutiyan’s blog

プログラミング関係のことをたまに書いています。

CodinGame「UNLEASH THE GEEK」参加記

CodinGameというサイトの10日間コンテスト、「UNLEASH THE GEEK」に参加しました。Bronzeリーグ到達、世界1354/2162、日本52/62の成績でした。 www.codingame.com

はじめに

これはCodinGameのコンテストに初めて参加した人の感想です。技術的な攻略はあまり参考にならないかもしれません。

ゲームの概要(ざっくり)

二人対戦のゲームです。各プレイヤーの目標は、5台の車を動かして、盤面に埋められた鉱石をできるだけ多く回収することです。盤面は30x15の固定で、ある程度のマスには鉱石(amadeus)が埋められています。車には「移動」「掘削」「レーダーの要求」「トラップの要求」の指示を出すことができ、いずれの操作も1ターンを消費します。レーダーは設置すれば、設置したチームはその周辺に埋めれられている鉱石の座標と量を知ることができます。また、トラップが設置されているマスを掘削しようとすると、その周辺で爆発が起こり、巻き込まれた車は失われます。

コンテストの様子

Wood Bossとの死闘

最初はWoodBossと戦いました(まだリーグの存在を知りませんでした。)

CodinGameのこの手のコンテストでは、Wood<Bronze<Silver<Gold<Legendという5つのリーグがあり、コンテスト期間の後半になるにつれて上位のリーグが解放されていく仕組みです。各リーグにはBossが存在し、Bossよりも高い評価を獲得すれば上のリーグに上がれます。よって、誰しも最初はWoodリーグなわけです。

WoodBossは必ず1つだけ鉱石を持ち帰るようでした。これなら勝てると思って実装しましたが、どこの入力を使えば鉱石の位置を取得できて、かつ車を向かわせられるかというところに少し苦労しました。データの持ち方にも少し悩みました。でもなんとか実装してWoodBossを撃破しました。

Bronze Bossとの死闘

Woodの次はBronzeリーグです。なんかいきなり強くなってびっくりしました。レーダーめっちゃ置くし、トラップめっちゃ置くし。でも目標は高いほうが良いです、頑張ります。

Woodの時点では、「とにかくランダムに動きランダムに掘る。偶然鉱石を掘れたら一直線に左端に帰る」を実装していました。これでは足りないことは明らかでした。

考えると、盤面は450マスしかないので、適当にループを回しても1ターンあたりの思考時間である50msは余裕で下回ります。また、レーダーさえ置けば鉱石の場所はわかるので、「自分に一番近い鉱石に向かって移動し、掘る」ことは簡単にできそうでした。これを実装すると、スコアが大きく伸びました。楽しい。

でもBronzeはトラップを置きまくります。見ていると、結構な確率で自分の車が2,3台死んでしまいます。なのでトラップを避けることを考えました。
トラップを埋められた時点で、そのマスには穴が空きます。なので、穴が空いているマスを掘らなければ絶対にトラップは引きません。相手が爆破して巻き込まれるケースは消せませんが。しかしこれを書くと、ore==3の時しか掘ってくれず効率がダメダメです。

そこで、「自分が過去に掘った座標を最新20件保存しておき、そこに含まれる座標も掘る」ことにしました。最近自分が掘ってトラップが置かれていなければ、ちょっとやそっとの時間では新たにトラップが置かれることはないだろう、という根拠のない考えに基づいています。これをやると、また結構スコアが伸びました。楽しい。ついでにレーダーの位置を決め打ちもしました。

他の人のを見る

でもBronze Bossは強いです。なんか強いです。何が強いのかはよくわかりませんでした。この辺で、自分では発想がなくなったのでリーダーボードから他の人の対戦の様子を見ることにしました。この頃にはシルバーあたりが解放されていましたが、Bronzeの人たちは案外トラップガン無視で、とにかく掘ることに専念している人が多い印象でした。この人たちがトラップ避けの対策をしているのかは分かりませんでした。この頃から、「トラップを意識すればするほど、鉱石入手量は下がる」ということは分かっていました。でも少なくともBronze Bossには勝てないといけない(ほんまか?)ので、トラップを避けることは続けました。

トップを走る上位陣の様子も見ましたが、あまり分かりませんでした。

終わり

そのまま特に策がないまま、コンテストは終了しました。

感想

とにかくどんな手法が効くか分からないので、思いついたものは悪そうでもやって見るのは大事そうでした。あと、入力としてどんな情報を知ることができるのか、というのは問題文をよく見返すのも大事そうでした。 他の人のを見ても今回は良く分かりませんでしたが、機能として公開されている以上、利用する価値が十分にありそうでした。

さらに、コンテスト中の思考回路的に、どんどん付け足す感じでコードが出来上がって行きます。少し試すつもりでベタ書きしたコードが良い性能を発揮したとき、流れでそのまま置いてしまうことはよくありました。結果、特に部品化されていないコードがmain関数内に溜まるので、非常に見栄えが悪いです。これはバグの元にもなり、反省点でした。

総合的には結果はどうであれ、(自分のAIを作るのも、観戦して他の日本勢を見ているのも)楽しかったので良かったです!また参加したいと思います。