CodinGame - Code4Life - 参加記
keraです。
いつもCodinGameはタイトルが何かしらの映画タイトルになっているはずなのですが、今回の元ネタはよくわかりませんね。
今回のゲームは、市民のために薬を開発してスコアを稼ぐゲームです。
今回の順位は世界8/2366位、日本3/48位でした。
今回のゲーム「Code4Life」の概要
とりあえず、こんなゲームです。
↓ゲーム画面
研究室のロボットを操縦して、様々な病気に対する薬を生産することが目的です。色々ルールがあります。
・市民に蔓延している病気の(病原体?)サンプルが配達される
・サンプルを解析すると必要な材料が特定できる
・材料には5種類の分子が存在する
・必要材料が揃えば、そのサンプルに対する薬ができ、スコアをもらえる
・サンプルにはランクがあり、高いものほどスコアと必要材料が多い
・薬を作成するとロボットのスキルが上がり、以後、作成の必要材料数が減る
・最終ターン時に、相手よりスコアが高ければ勝ち
これに加え、いくつか制限があります。
制限
・一度に持てるサンプルが3つまで
・一度に持てる分子は10個まで
・研究室で同時に存在する分子は、常に各5つ(ある条件下で6つになるが無視)
つまり一言でいうと、限られた資源をいかに上手く利用するか、いかに相手の邪魔ができるかが勝負のキモとなります。
実装したアルゴリズム
※この部分はプレイした人向けなので、説明してない部分が大量に出てきます。
基本設計方針
ステートマシン、だと思います。(定義をあまりしらない)
つまり、SAMPLES、DIAGNOSIS、MOLECULES、LABORATORY別にそれぞれ独立した関数を持っていて、ロボットがいる場所を担当する関数しか実行しません。
共有している変数があり(ほぼ全て)、それを利用して各処理が連絡を取り合ってます。
基本戦術
高ランクのサンプルはほぼ無視して、扱いやすいランク1サンプルを集めながら相手の妨害を優先します(同時に自分の専門スキル上げも狙います)。すると相手は諦めてクラウドにサンプルを上げるので、それを奪います。
奪うのには以下のメリットがあります。
・相手が自分の代わりに解析してくれるので、時間節約につながる
・相手が諦めるのは自分がそのサンプルの材料を持っているからであり、つまり相手が上げたものは自分にとって美味いサンプルである
まあこの2点が論理的に正しいかはわかりませんが、大体その通りに動きます。
どれくらい相手の邪魔をするかというと、相手がサンプルを解析しに行った段階で自分の行動をキャンセルし、分子供給場に向かって妨害待機するくらいです。
薬の作成
今回はいかに節約するかが大事なので、薬を提出する順番による専門スキルアップの差も考慮した最適・最小数な方法を追い求めるようにしました。
実装としては、薬の全提出パターンをシミュレートして、最も少ない分子数だったパターンを採用するような形です。
相手の妨害
相手が必要としている分子について、相手より先に集められそうならば集めます。自分の薬作成をそっちのけで妨害に走ります。
妨害は自分の手持ち分子が10個になるまでやり尽くします。
サンプルのアップロード
いらないサンプルをむやみにアップロードするということは、結局、すぐ相手に持って行かれ(上記の理由より)自分が不利になります。
ここでその時1位だった人の戦術を真似し、既にクラウドにいい物がある時に限り、手持ちのサンプルと素早く交換するようにアップロードするようにしたところ、確かに強くなりました。
感想
まあまあ満足です。
今回は一日平均3時間しかかけないでこの記録を出せました(今までは平均約9時間)。Ghost in the Cellの記事で書いた今後の目標の「最低限文化的な生活を送りながら」という部分が達成できたと思います。
また、今回は前回のCODERS OF THE CARIBBEANの記事でも書いた、コンテストにおける知見・改善案を実践してみました。以下の2つです。
・バグ撤去よりも新機能の実装を優先する
・上位陣の戦略をよく観察する
2つ目はいいと思いますが、1つ目に関してはこれが良い決断かは断言できません。しかし、実際にこうして好成績を残せたのは事実です。考察の余地はあるのではないでしょうか。
ちなみに、実は最終提出AIには(割りと致命的な)バグが有りました。結構頻繁に無限反復横跳びやり始めます(もちろん負けます)。これがなければもう少し順位上がったと思いますが、時間がありませんでしたね。
やっぱりバグ撤去と新機能の実装はトレードオフなんですかね。バランスが大事なんですかね。
一度でいいから優勝したい。