2017年4月14日～4月24日に開かれた競技プログラミングコンテスト、codingame「coders of the caribbean」の備忘録です。

結果

世界17/3635位、日本2/69位でした。17位は自己ベスト。
今回のお題は海賊！、、、なのですが、正直何を競えばいいのか最後までよくわかりませんでした。

考えたこと・やったこと

初日
「Hexタイル！？初めてや…まともに距離計算できねぇよ…。」
※このあとめちゃくちゃツール系関数作った。（距離計算、周囲のマスの取得、マスの移動等）

とりあえず、いつも通りルールベースでBronzeリーグまで行きました。

2日目
TODOメモを作成しました。
あと、2～7ターンまでの極短ビームサーチを作りました。攻撃系は初手のみ、相手の行動は見ません（常にWAITを出力）。かなり行動しぼっても50msでは3隻だと36回くらいしか試行できなくて、ほぼ貪欲と変わりません。。。

↓実際のメモ（✓マークは、最終的に実装したもの。☆は間に合わなかったもの）

■ルール
砲撃は船首、船尾で25、船腹で50ダメージ
機雷は5マス以内で見える
機雷は接触25、爆発時隣接10ダメージ
機雷は砲撃で破壊可能
1ターンで1ダメージ
移動のあと方向転換
ターン終了時にhp0で死亡
他の船と被ったら移動はキャンセル、速度0
スピード2はニ段階でチェック
✓死ぬと直前のhp分の樽を出す

■戦略
✓相手を固まらせて、身動きを取れなくする
✓引き撃ちできる展開に
☆1点集中ではなく、範囲攻撃を
✓相手の進路を妨害する

■課題
✓サーチ化※50ms
☆一隻ずつの評価をする
✓スコア評価
✓編隊の組み方、適当に距離を保つようにした
✓→座標圧縮→やめたほうがいいかも
✓相手の進行を妨げたらプラスするとか
✓一人を大勢で囲む
☆機雷即爆破戦法でいく
✓HPが少ない時樽を狙う
✓機雷を打つ
☆相手の行動予測
✓機雷は相手の近くに置く
✓リードしている時は逃げでいい
✓hpが最低のやつはアイテム優先
✓waitは最初のターンだけ
✓ちょくだいサーチ化
☆やられる時に相手にアイテムとられないよう、自身に撃っておく

3～6日目
ガチヒューリスティック&バグ修正。ひたすらパラメータ追加・調整。ここらへんでアルゴリズム選択ミスに気付くが後の祭りです。
同時行動なのと、船同士の衝突有無はかなり盤面影響でかいので、単純に評価値を最大化するようなアルゴリズムは向いていませんでした。。。結局、あまり近寄らないように評価関数組んで偽装しました。あと、とりあえずchokudaiサーチ化。
＃MinMax法とかが良かったのかなぁと思っています。やっぱり評価関数ゴリゴリ書くんでしょうけど…。

7,8日目（最終日）
敵の動きをそれなりに読みました。このターンのダメージを避けるように動きを一つ、決め打ちさせました。で、ちょっとだけ工夫として、偏差射撃の概念を入れてみました。

処理内容
１．敵に砲撃する。
２．ターン経過させ、敵は決め打ちした移動をする。
３．着弾ターンで敵がいる場所に１．の砲撃先の座標を変更。
＃距離変化による着弾ターンのズレは知りません。

簡易化したソース＃色々端折ってるので行間読み解いて下さい。><

Player.java


    // 他の部分は省略
    class Node {
        Ship[] ships = null;
        Cannon[] cannons = null;

        public void nextTurn(String[] acts) {
            action(acts);           // 砲撃や加速減速
            moving();               // 移動 ※省略
            turning(acts);          // 回転 ※省略
            hitCannon();            // 砲撃の着弾
            deadCheck();            // 死亡判定 ※省略

            return;
        }

        private void action(String[] acts) {
            Ship me = null;
            for (int i = 0; i < acts.length; i++) {
                me = ships[i];
                Ship enemy = me.getNearEnemy();
                if (acts[i].equals("FIRE")) {
                    me.output = "FIRE " + enemy.x + " " + enemy.y;
                }else{
                    // 他の行動パターンは省略
                }
            }
        }

        private void hitCannon() {
            for (Cannon c : cannons) {
                c.rest--;
                if (c.rest == 1) { // 着弾ターン
                    Node cur = this;
                    while (cur.parent.parent == null) { // 1ターン目の盤面情報
                        cur = cur.parent;
                    }
                    Ship enemy = this.getEnemy(c.targetId);     // 着弾時の敵
                    Ship me = cur.getMy(c.fromId);              // 1ターン目、砲撃発射時の自機

                    me.output = "FIRE " + enemy.x + " " + enemy.y;// 着弾位置の書き換え
                }
                // ・
                // ・
                // ・
                // 砲撃の着弾計算は省略
            }
        }
    }

まさに因果の逆転！ゲ○・ボルグ！（なお、適当な位置予想なので当たらない。原作に忠実。）
でも、射撃地点がAとBとCとDと…ってやると、簡単にパターン数が爆発して簡単にTimeOutするので、短時間で、それっぽい所に打てればいいって場合は使えるかなぁと思いました。同じ親Nodeでも、子Nodeの状況に応じて行動が変われば計算リソースの省エネ化（正確性は欠くけど）。ランキング下位勢はよく壁や船にぶつかるので、止まった所に船体ど真ん中に撃ち抜けて、かなり勝率上がりました。

そして終戦。せっかくなのでラム酒で宴。

最後に

ここまで読んで頂きありがとうございました。
おそらくこれも通期コンテスト化するんと思うので、気になった方は一緒にやりましょう！

また、弊社は競技プログラミング部を創部しました。
やっぱり、戦略やアルゴリズムをわいわい言いながら語りたいし、語れたらずっと面白いです。

お客様も歓迎いたしますので、興味があればご一報を。
＃創部間もないのでまだ窓口がありません。御用の際は私のTwitterアカウントに連絡下さい。@tsukammo

以上

競プロ備忘録～codingame「coders of the caribbean」～

結果

考えたこと・やったこと

最後に