2017年11月18日～11月27日に開かれた競技プログラミングコンテスト、codingame「mean max」の備忘録です。

結果

世界18/2512位、日本1/67位でした。
今回のお題はアイテム回収ゲー。要素が多く、まだまだ底の見えない大作ゲーでした。

<登場する要素>

考えたこと・やったこと

初動（26時～寝るまで）

まずは最低限の評価関数でBronze到達を目指しました。
・最寄りのWreckからReaperが離れるほど-
・最寄りのTankerからDestroyerが離れるほど-
・相手のReaperからDoofが離れるほど-
・Reaperが相手のLootersに近いほど-

1,2日目（土日まったりと）
ゲーム考察とひたすらシミュレータ・アルゴリズムの実装（出力決定のアルゴリズムはこの時点から大きく変わっていません）。
当時考えたことは下記です。

戦略

1点1点、確実に取っていく。

Reaperの回収精度向上を重点的に。各車体で相手Reaperの妨害も。スキルでの妨害は余ったときのオイルだけにして、点を取る方向でrageを使っていく。

タンク破壊は相手にやってもらえばいい、Destroyerは中央に陣取ってグレネードで発射台に。もちろん肥えたタンクがいれば、確実に取れる状況を作ってから頂く。

Doofはたくさん走ってrage貯めて妨害役。

3～5日目（0時間）
「…（お仕事で死亡）」

6日目（勤労に感謝）

謎タイムアウトとずっと戦ってた。結局根本解決ならず。50ms制限で35msで返すようバッファを設けてその場しのぎ。
あと、日本トップを独走していたy_kawanoさんが寂しそうだったので、一旦できるだけ上位を取れるように評価関数を作りました（ここから評価関数は大きく変わっていません）。

7日目（0時間）
お仕事で(ry

8～10日目（4時間）
温泉旅行に行ってた（良いお湯でした♨）。夜にちょっとだけパラメータ調整して、後はサブミットガチャ。

終了。
Tシャツ県内の20位に入れたのはとてもとても嬉しいのですが、1,2日目に考察したっきりゲーム性に関わる部分に全く時間を避けませんでした。新しいアルゴリズム案も、僕の考えた最強戦術も、一切手をつけられず。。。

実装したアルゴリズムについて

深さ2のchokudaiサーチ、敵はWAITのみでした。
1ターン目と2ターン目で探索内容を変えていて、

1ターン目

各Looters8方向 + 各Looterのスキル使用（同時使用なし）の組み合わせを全通り実施。
タールは、自Rearperのみ。
グレネードは、自Reaperの中央 + 8方向に1ドットだけ進んだ点。
オイルは、最寄りの敵Reaperの最寄りのWreck。

2ターン目

Reaperのみ8方向、他は4方向。スキル利用無し。

評価関数
（ちょっと自然言語化が辛かったんで評価関数そのまま貼ります。。。）

Player.java

final int XPOINT_WATER = 50_000;
final int XPOINT_WATER_E = 30_000;
final int XPOINT_RAGE = 600;
final int XPOINT_RAGE_E = 400;
final int XPOINT_DIST_WATER = 1;
final int XPOINT_DIST_WATER_E = 2;

double eval() {

    double score = 0;
    score += me.water * XPOINT_WATER;
    if (me.water >= 50) {
        score += me.water * XPOINT_WATER;
    }
    score += me.rage * XPOINT_RAGE * (1 - (1.0 * Math.max(gameTurn - 100, 0) / 90));
    double minD2 = Double.MAX_VALUE;
    Point tar = null;
    int point = 0;
    for (Water w : waters) {
        if (w == null) {
            continue;
        }
        double tmpd2 = me.Reaper.dif2(w) * Math.max(0, 1.2 - w.point * 0.2);
        if (minD2 > tmpd2) {
            tar = w;
            point = w.point;
            minD2 = tmpd2;
        }
    }
    if (tar != null) {
        score += Math.max(0, (3000- me.Reaper.distance(tar))) * point * XPOINT_DIST_WATER;
    }
    Tank tarU = null;
    minD2 = Double.MAX_VALUE;
    for (Tank t : tanks) {
        if (t == null) {
            continue;
        }
        double tmpd2 = me.Destroyer.dif2(t) * Math.max(0.1, 1.1 - t.point * 0.1);
        if (minD2 > tmpd2) {
            tarU = t;
            minD2 = tmpd2;
        }
    }
    if (tarU != null) {
        score += Math.max(0, (6000 * 2 - me.Destroyer.distance(tarU))) * tarU.point;
    }
    score += -Math.min(6000, Math.max(me.Destroyer.distance(me.Reaper), 1200));

    for (Ope o : op) {
        score -= o.water * XPOINT_WATER_E;
        score -= o.rage * XPOINT_RAGE_E;
        minD2 = Double.MAX_VALUE;
        Water tarW = null;
        for (Water w : waters) {
            if (w == null) {
                continue;
            }
            double tmpd2 = o.Reaper.dif2(w) * Math.max(0, 1.1 - w.point * 0.1);
            if (minD2 > tmpd2) {
                tarW = w;
                minD2 = tmpd2;
            }
        }
        score += Math.min(me.Reaper.distance(o.Doof), 1600) * 2;
        score += Math.min(me.Reaper.distance(o.Reaper), 1600);
        score += Math.min(me.Reaper.distance(o.Destroyer), 1200);
        if (tarW != null) {
            score -= -o.Reaper.distance(tarW) * XPOINT_DIST_WATER_E;
        }
    }
    int topOp = 0;
    if (op[0].water < op[1].water) {
        topOp = 1;
    }
    score += -me.Doof.distance(op[topOp].Reaper) * 2;

    return score;
}

狙い
Reaper：Wreckとの距離とpointに応じて、狙い先を決める。敵のLootersからは一定距離を取る。
Destroyer：自Reaperが近く、相手Reaperが離れている時にTankerを破壊する。
Doof：リードしている相手のReaperにまとわり付く。

グレネードを妨害ではなく、点数獲得に使ったのが良かったと思います。オイルはそこそこ使ってくれるのですが、タールは加点要素が無いのでほとんど使ってくれません。
衝突判定のあるゲームの性質上、探索可能なノード数が状況に大きく左右されるのですが、大体10～30ノードくらい読んでくれます。

最後に

ここまで読んで頂きありがとうございました。成績の割にあまり目新しいことに挑戦できていないことが悔やまれます。けれど、ゲームAIコンテストで重要なのはやはり戦略であって、それをどのようなアルゴリズムで実現するかは二の次なのかなとも思いました。

【定期】弊社競技プログラミング部のアカウントができました。@future_ocv
活用方法が定まらず放置気味なので、このアカウントでつぶやく話題を募集中です。

以上

競プロ備忘録～codingame「mean max」～

結果

考えたこと・やったこと

実装したアルゴリズムについて

最後に