CodinGameで2019/10/05~2019/10/14の10日間にわたって行われたオンラインコンテスト「Unleash the Geek」に参加しました！
世界53位/2162人、日本8位/62人（Legend league）でした。 前回とだいたい同じくらいの順位ですね。今回もLegend Leagueに到達できたので良かったです（今回日本人が優秀すぎませんか？）
$15\times30$のフィールド上に鉱石が埋まっており、各プレイヤーは各5台のロボットを操縦して鉱石の発掘を行います。勝利条件は、200ターン経過時に相手より多くの鉱石を基地($x=0$)に運んでいることです。最初は鉱石が埋まっている場所はわかりませんが、自分が置いたレーダーから距離4以下のマスに埋まっている鉱石の数が見えるので、それを頼りに発掘を進めていくことになります。ロボットは1ターンに4マスまで進むことができ、基地でレーダーやトラップなどのアイテムを受け取ったり、鉱石を採掘したりする行動にはそれぞれ1ターンずつかかります。(試合の例)
試合を眺めていると、地道に鉱石を集めに行くタイプや序盤に地雷で相手のロボットを減らしてから効率で勝つタイプなどがよくいる印象でした。僕は最終的には地雷を設置することはやめて、鉱石を集めるスピードで勝負する戦略にしました。
レーダーを持っているロボットが地面を掘ると、その場所にレーダーが埋まります。自分のレーダーから距離4以下のマスは、埋まっている鉱石の数が見えるようになります。
序盤にレーダーを置く場所は重要です。基地から近いマップ左側の鉱石を素早く集めることで序盤に有利を取ることができます。最初の2, 3個のレーダーで充分な数の鉱石を捉えられなかった場合、その後のゲーム展開はかなり悲惨なものになる場合が多く、序盤30ターンでついたスコア差が全く変わらないまま200ターン目までいくということも珍しくありません。環境で多く見られた序盤戦略は、大きく分けて2つあったと思います。
上は最初のレーダーを$x=5$に置くやり方で、下は最初のレーダーを$x=9$に置くやり方です。これは一長一短で、どちらを使ってる人も同じくらいいた気がします。
$x=5$のメリットは、フィールドで最も左側にある鉱石を最速で取りにいける点です。$x\le10$に鉱脈がある場合には確実に序盤有利をとれるのは魅力です。ただし、このゲームでは鉱石の配置が完全なランダムではなく、フィールド左側は比較的鉱石が少なくなっています。$x\lt15$にひとつも鉱石がないこともあり、そのような盤面では序盤の事故リスクが非常に高いことはデメリットと言えます。
$x=9$のメリットは、事故率が比較的低く、序盤に安定した動きができる点です。殆どの場合に最初のレーダーで石を発見できることに加えて、仮にフィールド右側にしか石がないような盤面に遭遇しても2, 3番目のレーダーは画面中央に置くことになるのでなんとかつなぐことができます。逆に画面左側の鉱石を見つけるのが遅くなりがちなのは良くなく、相手が$x=5$戦略だった場合にはレーダー4, 5を置くときにはすでに石がないことも多いです。レーダー2, 3と4, 5の順番を入れ替えると中間くらいの性能になります(中途半端ともいう)。
コンテスト中にどちらも試しましたがどちらが良いのかはよく分からず、結局最後は$x=9$にしました。工夫した点として、最初のレーダーに映った鉱石の分布によってレーダー[2, 5]を置く順番を変えました。
最初のレーダーに映った石の分布が上図の赤マスのようだったとき、フィールド左上には鉱脈がありそうで、フィールド左下には何もなさそうだな〜ということがなんとなくわかります。もちろん外れる場合もありますが、左上(下)になんとなく鉱脈がありそうな感じがした場合には右より先に左上(下)にレーダーを置くことにしていました。また、右側でも上と下で石が多そうな方に先に置いていました。あとは、序盤で見えている鉱石がなくどこを掘ればよいかわからないときは画面中央あたりを適当に掘ると当たりを引く確率が比較的大きく、悪あがき程度にはなります。
最初の5つを置いたあとは、ロボットが基地に戻ってきたときにレーダーが使えれば受け取り、見えている鉱石の数が少なければ現在のレーダーで見えているところにできるだけ被らないように置く / 充分な数の鉱石が見えていれば鉱石を拾うときにその場に置くをしていました。また、レーダーを置く際はできるだけ埋まっている鉱石が2以上のマスを狙って置くことにしていました(後述)。無意味な場所にレーダーを置くことは本来1ターンのロスとなりますが、レーダーを狙って破壊してくるAIが環境にいたり、レーダーは地雷の代わりに使えるといった事情があるので、適当な場所にレーダーを置くことも有効だと考えてこのようにしました。
地雷を持っているロボットが地面を掘ると、その場所に地雷が埋まります。地雷が埋まっている場所をロボットが掘ると爆発し、爆発した地雷から距離1以内にいるロボットはすべて消え去ります。また、爆発した地雷から距離1以内に埋まっている地雷も同時に爆発します。
ルールにそう書いてあるわけではありませんが、地雷の本来の使い方といえば「敵が踏みそうな場所に埋めておいて爆発するのを待つ」だと思います。この方法で地雷を使うのであれば、鉱石が2つ以上埋まっている場所を掘りながら埋めるとよいです(鉱石がない場所を相手が掘る可能性は小さいので)。
ただ、現実的な問題として相手が自分で地雷を踏んで爆発してくれることはあまり期待できません。なぜなら、相手の地雷を回避することは非常に容易だからです。地雷を埋めた場所には必ず穴ができるため、最後に掘ったのが自分ではない穴を掘らなければ相手の地雷を掘ることはありません。レーダーで見えている範囲であれば埋まっている鉱石の数を追いかけることができ、自分が最後に掘ったときの残りの鉱石の数を記録しておくことで自分のあとに相手がその場所を掘ったかどうかがわかります。
相手が地雷を踏んでくれないなら地雷を置くことに意味はないのかというと、そうでもありません。地雷を掘ると周囲の地雷に誘爆し、その周囲にいたロボットをすべて巻き込んで爆発します。この性質を利用して、連結な地雷集合の周囲にいる相手のロボットの数が自分のロボットよりも多いのであれば、自分で地雷を掘ることで相手を巻き込んで有利な交換を仕掛けることができます。多くの場合は$1:2$交換になりますが、アドバンテージを取れれば何でも良いです。地雷を掘る操作はロボットの移動よりも高速で、ターン開始時に地雷の周囲にいたロボットはそのターン移動しようとしていても関係なくすべて巻き込まれます。地雷を埋める場所としては、石を掘りながら適当な場所に埋めても充分強いですが、$x=1$のライン上に埋める戦法が多く見られました。$x=0$は納品の際にかならず立ち止まることから多くのロボットを巻き込むことができるためです。僕も途中までこれをやっていて、まあまあの強さを発揮していました。
何もしていなくても爆発させられるなら怖くて石掘りなどしている場合ではありませんが、自爆に対してもある程度有効な回避策が存在しています。地雷を埋めようと思うと必ず基地で1ターン消費して地雷を受け取らなくてはいけませんが、これを利用して、相手ロボットが基地で停止したら地雷を受け取ったとみなすことができます。さらに、地雷を持っている(と思っている)相手ロボットがフィールド上で停止したとき、その周囲に新しくできた穴には地雷が埋まったと考えられます(新しくできた穴や鉱石の減ったマスがない場合は周囲の穴すべてが怪しいことになります)。このようにして、「相手の地雷が埋まっている可能性があるマスの集合」が得られます。これをすべて地雷だと思って行動すれば爆破される心配はほとんどないといって良いでしょう。地雷を持っていそうな敵ロボットの周囲も地雷だと思っておくとさらに安全です（置いて即座に自爆されることがあり得る）。
相手の地雷の集合が得られたとき、相手に1:2交換をさせないことは比較的簡単です。まずは地雷の集合を隣接するクラスタ(爆発の際に同時に爆発する地雷の集合)に分けます。クラスタの管理にはUnion-Find treeなどを利用するとよいです。ここで、1:2交換をされる可能性のある条件は「同じクラスタに自分のロボットが2つ以上隣接している and 当該クラスタから距離5以内に敵のロボットが存在すること」です。
あるターンにロボットと地雷の配置がこのようになっていたとします。ここで、赤が敵、青が味方で黒が地雷です。'x'の入った地雷は、次のターンにその地雷が所属するクラスタに敵が隣接する可能性があり、すなわち2ターン先に爆発する可能性がある地雷ということになります。前述のとおり地雷の爆発はロボットの移動より早いため、これに巻き込まれないためには次のターンの移動場所を工夫する必要があります。上図では、基地に帰ろうとしているロボット2台が危険なクラスタに隣接しようとしているため、片方が移動先を変更しています。一方で'o'のクラスタは2ターン先に爆発させられることがないので2台以上隣接していてもよいです(最左端)。
移動先の変更は、移動先が被ったロボットのなかでidが小さい順に優先し、idが大きいロボットの行き先を安全なマスのなかで目的地への距離が一番小さいマスに随時変更していました。被っているロボットの数が3くらいであればすべてのロボットの行き先を全探索しても充分高速だと思われるので、時間があれば試してみたかったです。
この試合は、地雷を敷き詰めて自爆する戦略を採用している相手との試合です。2ターン後に起爆されそうなクラスタに2台以上で隣接しないことで一度も爆破されずに試合終了まで進むことができています。相手が基地近くにいるときは1台ずつ基地に入っていますが、そうでないとき(145ターン目など)は同時に入っていることがわかります。
Gold以上のLeagueでは、ほとんどのプレイヤーが何らかの方法で地雷の回避を実装していました。ここで、自分が対戦するプレイヤーのうち多くが相手の置いた地雷を掘らない / 1:2交換を避けるような動きを実装していることを信じるのであれば、本物の地雷を使用することの意味は薄くなってきます。
相手が地雷を持ったかどうかを判別するには「基地で一時停止したかどうか」を使っていましたが、この理屈でいくと基地で一時停止さえしていれば実際に地雷を受け取っていなくても相手に警戒してもらえるということでもあります。これを利用して、基地で一時停止したあとに鉱石を掘ることでその場所に地雷を埋めたと思わせる戦略がコンテスト終盤では主流となっていました。このゲームでは基地に近い鉱石をより多く掘ったプレイヤーが単純に有利なので、序盤に鉱石の上に地雷を埋めたと思わせ、終盤に掘ることでアドバンテージを稼ぐという戦略は、Gold LeagueのBOSSにも実装されていました。
このゲームでの移動はそれほど複雑ではなく、基本的には基地と鉱脈の間でひたすらピストン輸送をすることになります。たまにレーダーを置きに行く以外はひたすら往復です。つまり、相手よりも輸送効率が悪いとじわじわと負けていくということでもあります。
どのロボットにどの石を掘りに行かせるかということは非常に重要です（自戒）。コンテスト中は、各ロボットと鉱石の組み合わせに対して((現在石を持っている場合は納品)→到着→採掘→納品までの必要ターン数, (納品)→到着→採掘までの必要ターン数)でソートして小さい順に貪欲に取っていました。移動距離が$n$であるとき、移動に必要なターン数は$\lceil \frac{n}{4} \rceil$です。この方法は計算時間の割にはそこそこ良く、最初から最後まで一貫して採用していましたが、結局計算時間をかなり余らせていたのでここで焼きなましやビームサーチなどすべきだったのではと今となっては思います。ただ、毎ターン計算し直すのであればターン毎に目標となる石が頻繁に変わるような方法はおそらく避けたほうがよいと考えられ、貪欲以外の方法ではその辺の兼ね合いがどうなっているのか気になります（やっていないのでわからない）
これは小技なのですが、鉱石を採掘するときにはできるだけ左から掘るようにするとよいです。理由は、基地に近いからです。ピストン輸送だけを行っていれば掘りたい鉱石よりも右側に出ることは多くありませんが、レーダーを置いた帰りや掘りたい石が相手に取られて目標を変更したときなどは右や上/下から掘りに来ることもあるはずで、そのときに「必要ターン数が変わらないのであれば」、できるだけ掘る前に左のマスに移動しておくと少し得です。
このゲームでは移動に使えるコマンドが"MOVE"と"DIG"の2種類あります。MOVEを使うと、指定した座標までの最短経路のひとつを通って最大4マスまで移動します。DIGは基本的にMOVEと同じですが、指定した座標から距離1以内だった場合にその座標を掘ります。これだけ見ると、石を掘りたいときにはその石の座標に対してDIGを繰り返していれば最短で掘ってくれるように見えるし、実際そうです。しかし、同じ最短経路でも経路を選べるなら選ぶべきです。
上の図は、「かならず縦移動を先にする人(赤)」と「かならず横移動を先にする人(緑)」の移動の軌跡です。2人は同じ場所からスタートし、最初に一番近い'x'の鉱石を目指します。しかし、4回移動したところで'x'の鉱石が相手に掘られてしまい、仕方なく次に近い'o'の鉱石に目標を変更しています。2人ともそのときの目標地点に対して最短経路で移動していますが、結果的に緑のほうが1ターン早くたどり着いています。これは、このゲームが左側の鉱石から順に掘っていくゲームであり、横移動は縦移動よりも無駄になりにくいためです。左の鉱石から順に掘られるとき、目標変更によって$y$軸がずれることはよくありますが左側に戻らなくてはならなくなることはほとんどありません。このことはゲーム終盤で遠くの石を掘りに行くほど大きく寄与します。
このような理由から、移動の際には横移動を先に行うのがおすすめです。しかし、MOVE, DIGコマンドに遠くの座標を入れてもこのような経路を選んではくれないので、移動の際には自分で次のターンの座標を指定して4マスずつ移動するのが良いでしょう。加えて、前述のように相手の自爆を警戒するなら次のターン自分がどこにいるかを把握することは絶対必要になるので、そういった意味でも自分で行き先を指定することは有利です。
小技として、納品の際に次に掘りたい鉱石を仮決めしておくと最後に少し$y$軸移動してその座標に寄せられるので少し有利になるような気がするのですが、実際のところ敵に先に掘られることが多いので速度に寄与しているのかどうかはよくわかりません（結局よくわからないまま最後までやってました）
コメント込みで918行でした。CodinGameではソースコードが公開できないので行数くらいしか言うことがない……。
コンテストが終わったあとにトップ付近の人の戦略を聞くと、やはり自分よりも1段階上のことをしていると感じます。他の人の参加記も読んで復習したいですね。
終了前日までわりとTシャツ圏内である20位に入っていたのですが、最後の1日のスピードについていけませんでした。 Code Royaleでは47位/2120人だったので少し下がったのは残念ではありますが、ほとんど同じ順位を取れたのはよかったことでもあります。次回も頑張ります。
トップに戻る