CODE ROYALE

CodinGameの10日間コンテスト。簡易RTSみたいなゲームです。クイーンを操作して建設を行い、兵舎から生産した兵士で相手のクイーンを倒すのが目的です。

建設は「兵士を生産する兵舎」「金を稼ぐ炭鉱」「防衛を行うタワー」の3種類で、兵士は「クイーンを攻撃するKNIGHT」「タワーを倒すGIANT」「GIANTを倒すARCHER」の3種類です。

f:id:y_kwn:20180501213933p:plain

リプレイ : https://www.codingame.com/replay/307856967

世界18位/2120人、日本2位/60人でした。

アルゴリズム概要

ヒューリスティックとシュミュレーションの合わせ技みたいな感じでした。どこにどんな建物を建てるか・どのタイミングで逃げに走るかはヒューリスティックで決めて、実際にどの座標にMOVEするかはシミュレーションして探索で決める感じです。

ヒューリスティック

基本戦略

速攻で相手のHPを削って、相手を後手に回らせて押し切るor守り勝つつもりでした。兵士はKNIGHTしか生産しません。

初手

できるだけ敵クイーンに近い場所に兵舎を建てに行きます。建てに行く道中に土地があったら炭鉱を建てます。

初手以降

こちらのHPが上ならタワーを建てて守りに入ります、そうでないなら炭鉱を建てて第2波を狙いに行きます。余裕があったら兵舎の2つ目を建てます。

逃げ動作

近くの敵の距離が800以下になったら逃げモードに入って、できるだけ自陣深くのタワー(orタワーを建てるための空き地)に逃げ込みます。道中にタワーか空き地があったら立ち寄ってタワーを建設・強化します。

距離が200以下になったらガン逃げモードに入って、できるだけ自分のライフを削られないように動きます。

神風アタック

自クイーンの近くに兵舎があったら兵舎を潰しにクイーンを突撃させました。(終盤に入れたので効果があったかは不明)

生産

序盤はひたすら何も考えずにKNIGHTを生産します。

中盤は連続でKNIGHTを生産できるくらい金が溜まったら生産するようにしました。(条件は200gold以上か収入16以上)

兵舎に相手クイーンがのこのこ近づいてきたときも生産するようにしました。

シミュレーション部

シミュレータ

https://github.com/csj/code-royale を軽く移植した感じです。コリジョン周りとKNGIHTの動きだけを実装しました。 ただ、なんか見落としかバグがあるのか結果と微妙なズレがあって、それを潰せずに終わってしまいました。

で、そのシミュレータを使って32方向を1手読みで探索して、最も評価値の良い動きを採用しました。2手読みもやったんですが、シミュレータが荒かったせいか全然強くならず、むしろ弱くなってしまったので諦めました。

上位陣は2手どころか10手以上の探索をしてるので、完全にこの探索の差が上位に入るかの分かれ目になったのかなと思ってます。

建設時の評価

土地との距離がそのまま評価値になっています。

逃げ時(距離800以下)の評価

タワーを建設or強化するためにどこかしらの土地に向かうので基本は建設と同じですが、敵との距離にボーナスを与えました。

ガン逃げ時(距離200以下)の評価

距離200以下の敵を対象にして、距離をなるべくとるように動きます。自クイーンがダメージを食らったら(距離が5以下になったら)大減点、敵が自タワーの範囲に入っていたら加点するようにしました。

反省点

  • シミュレータ雑すぎが勝敗を分けたと思ってます。

  • 久々にパラメータ弄ってなんとかしようとしてしまったので反省。(いつもはやんないように気をつけてる)

  • ↑で時間取られたからか、ヒューリスティック部もシミュレーション部も詰めが甘くて、なんか全体的に雑だった。

  • 詰まったら書いたコードとルールを全部読み返すのは効果がありそうなので次からやりたい。(抜けがないかチェック&心を落ち着かせるため)

Botters of the Galaxy

CodinGameの10日間コンテスト。LoLのようなゲームです。 ヒーローを2体操作して、相手のヒーローを倒す or 相手の塔を破壊する or 相手よりkill数を稼ぐということが目的です。

f:id:y_kwn:20180313204617p:plain

リプレイ : https://www.codingame.com/replay/294861078

世界5位/1713人、国内2位/90人でした。

アルゴリズム概要

結論から言うとif文連打のルールベースでした。

今回は戦略と戦略のぶつかり合いになると思ってました。つまり、環境を席巻する戦略が生まれて、それをメタる戦略が生まれて・・の繰り返しになると思ってました。 なので正確なシミューレーションを元にして細かく稼いでいく事よりも、素早く環境に適応できる事が重要だと考えました。

シュミレータと評価関数を元にした探索アルゴリズムは、人間より深い思考を行い人間より頭の良い手を打つことは得意ですが、 自分の思った通りの行動を行わせることには向いてないので、今回は探索系のアルゴリズムを採用せずにルールベースを採用しました。

アルゴリズムを改善した際によくやる自分vs自分も今回は何も意味をなさないので、アルゴリズムを弄ったらアリーナ上の誰かしらをボコすことで改善を確認してました。

なので今回はシミュレータを作ってません。

ゲームの戦略

IRONMAN&DOCTORで戦いました。

  • 相手が近距離戦を挑んできた場合 → 塔に引きこもって迎え撃つ
  • 近づいてこない場合 → FIREBALLを撃って殺す
  • 隠れて引きこもる場合 → kill数で勝つ
  • ミラーマッチ → 頑張る

という戦略で、理論上どんな相手にも勝てるという布陣です。

なお

  • 塔なんて気にしねぇ!ガチムチ特攻だ! → 殺される
  • FIREBALLで死なないように命だいじに作戦 → KILL数で負ける

という戦略に敗北した模様。

各種行動

リーダーの行動

IRONMANはひたすらFIREBALL連打をするのが仕事です。 DOCTORはそのサポートみたいな感じでPULLして敵ヒーローのHPを削る手伝いをしたり回復をしたりです。

お買い物

IRONMANだけがアイテムを装備します。買う装備は最初に決めていて、500gold分を使ってマナ増加装備だけを買います。無かったらマナ増加量を上げる装備を買います。 残りのgoldは全てポーションに消えます。

ポーション使用法

普通のポーションは死にそうになったら使います。 マナポーションはIRONMANのマナを満タンに維持するぐらいの勢いで使います。

スキル

  • BLINK : 何故かマナが回復するので使えるときに無制限に使用してます。
  • FIREBALL : HPの低い相手にぶっ放してます。小癪にもFIREBALLを避けてくる相手もいるので、そういう相手には動きを先読みして当てています。grootにFIREBALLでちょっかいを出して敵ヒーローを殴らせる戦術もパクりました。
  • BURNING : 自タワー付近に押し込まれている場合、敵兵士を一掃するために使ってます。
  • PULL : 引き込んだ先に味方兵士が3体以上いるなら引き込みます。
  • SHIELD : PULL等で引き込まれて、周りが敵だらけになった場合自分にSHIELDを打ちます。
  • AOEHEAL : 雑に使います。

攻撃

敵ヒーローの周りに味方兵士が居るなら敵ヒーローに攻撃します。 敵兵士を1撃でkill出来るならkillします。 味方兵士を1撃でdeny出来るならdenyもしますが、相手がハルクで殴り殺すマンだった場合denyはしないようにしました。 あとは雑に射程圏内に敵が居たら攻撃してました。

移動

自分のリプレイを見てたらわかりますが、基本的に自兵士の後ろについていくように行動します。 ただし、移動先がやばそうなスキル圏内(PULL・CHARGE・SPEARFLIP)とかだったら移動しません。 移動できるところがない場合は、自タワー付近のBUSHに逃走します。

コーディングテク

メインの関数は↓みたいな感じで見通しを良くしてます。

f:id:y_kwn:20180313205509p:plain

MOVEは↓のようなマクロで、「行動できたらその行動を採用して、行動できなければ次のMOVEを試す」みたいな感じです

#define MOVE(move_func) { Cmd cmd = move_func; if (!Cmd::IsNone(cmd)) return cmd; }

関数は↓みたいな感じで出来るだけ細切れになるように作ってます。(全部で約60関数)

f:id:y_kwn:20180313205526p:plain

なので、例えば「操作していない方の味方ヒーローに一番近い敵を攻撃する」みたいな処理は↓みたいなこんな感じで30秒で書けます。

Unit* other_hero = GetOtherHero(hero);
if (other_hero != NULL)
{
    Unit* near = GetNearUnit(_enemy_units, *other_hero);
    if (near != NULL)
    {
        return AttackOutRangeMove(hero, *near, "Sample Attack");
    }
}
return Cmd::None();

できるだけ考えた作戦をノータイムでかつバグらないように書けることを重視しました。

反省点

5位に入れたので概ねは満足。

最終日にメタり合いになるのは分かりきっていたので、気力・モチベーションのピークを最終日に持っていくべきだった。

なんだかんだでゲームのセンスは重要。

Mean Max

ゲーム概要

CodinGameの10日間コンテスト。水を運ぶTankerをぶっ壊し水をかき集めるゲームです。2人対戦ゲームでそれぞれ3つのユニットを操ります。3つのユニットはそれぞれ役割とスキルが異なっていて↓のような感じです。

ユニット名 役割 スキル
Reaper 水の採集 動きを鈍らすTarを撒く
Destroyer Tankerを破壊する 相手を吹き飛ばすグレネードを投げる
Doof スキル使用に必要なrageを走って溜める 水の採集を妨害するOilを撒く

f:id:y_kwn:20171128223517p:plain

リプレイ:https://www.codingame.com/replay/274184926

世界21位/2512人、国内2位/67人でした。

アルゴリズム概要

1手読み+匠の評価関数で戦ってました。ビームサーチ系で探索しても2手が限度だろうし、相手が絡むと読んでも意味ないし、2手読みくらいなら評価関数でカバーできるやろの精神でした。

シミュレータ

まず1・2日目に完璧なシミュレータを作りました。シミュレータ部分に関しては公式でjavaのコードが上がっていたので基本そのまま移植した感じです。移植が終わったらArenaを全員自分にして動きを完全に予測できる状態にして、シミュレータの結果と次のターンの入力に差異があったらAssertをかけるって感じで細かいバグを潰していきました。

探索

まず全員WAITにして各ユニットがスキルを何処に打つかだけを探索します。

Reaper:自分自身 + wreckに近づいてる敵reaper
Destroyer:自分自身 + 自Reaper + 敵が近づいてるWreckの周り8箇所(吹き飛ばし目的)
Doof:敵が近づいてるWreckの中心 + 自Repaerと敵Reaperが同居してるWreckには敵にだけoilがかかる位置

上記の位置をそれぞれ探索して一番評価が高くなる位置をスキル発動位置にしました。

その後、各ユニットの「8方向の全速力(reaperは半速も)+↑で求めた位置にスキル」の組み合わせを全探索しました。つまり(8+8+1) * (8+1) * (8+1)の全探索です。時間はほぼほぼ余裕でしたが、衝突が起きまくるシチュエーションでタイムアウトしてたので45msで雑に打ち切る処理は入れてました。

敵の動き予測も軽く入れてましたが効果があったかは謎です。

評価関数

ベーススコア + reaperのスコア + Destroyerのスコア + Doofのスコア - 敵のスコア

ベーススコア

水とrageの量によって加点。

Reaperのスコア

Reaperが既にWreckに乗っている場合、速度に応じて加点(速度が0に近いほどプラス)。
それぞれのWreckについて「Reaper-Wreck間のスコア」を算出して、一番高いスコアを評価値に加点。
ただし自DestroyerがTankerをすぐに壊せそうなら「Reaper-Tanker間のスコア」も算出して、そっちの方が高いければそっちのスコアを加点。

Reaper-Wreck間のスコア

「水の量/Reaper-Wreck間の距離」をベースにして敵Doofが近くに居たら減点、Wreckに到達できそうにないなら大減点。

※到達できるかの判定方法
f:id:y_kwn:20171128222733p:plain
この画像のように、reaperから見て一番近い端と左右の端までのレイが全てブロックされてたら到達できないと判定。敵ユニット+Tankerがブロックの対象です。

Destroyerのスコア

それぞれのTankerについて「Destroyer-Tanker間のスコア」と言うものを出して、一番高いスコアを評価値に加点。
Destroyer-Tanker間のスコアは「水の量/Destroyer-Tanker間の距離」で算出。

Doofのスコア

自Doofの一番近くにいる敵Repaerに近づくと加点
自Doofの一番近くにいる敵Repaerに一番近いWreckに近づくと加点

敵のスコア

水の量+一番近くにあるWreckの距離に応じて加点

反省点

・今回のゲームを見た瞬間「Coders Striker Back」や「Fantastic Bits」が頭によぎり、それで上位を取った人のアルゴリズムはGAだったので「すわっ!これはGA案件か!?」と思ったんですが、対戦ゲームAIをGAで書くことにまだちょっと懐疑的だったり、50msでは収束しなさそうだし相手の妨害は予測できなさそうだからGA止めたんですがやっぱりやればよかった。(収束早めるには行動数削ればいいし、敵は無視しても良さそうだった)

・匠の評価関数戦術はやっぱ限界がある気がする。

Wondev Woman

CodinGameの10日間コンテスト。↓こんな感じの二人対戦のボードゲームでした。

https://www.codingame.com/replay/243365172

f:id:y_kwn:20170703234846p:plain

世界15位/国内1位でした。

ルール

5x5~7x7の盤面を互いに行動しあって得点を稼ぐゲームです。取れる行動は「8方向いずれかに移動して8方向いずれかにブロックを生やす」「相手を押し込んで相手が元いた場所にブロックを生やす」の2種類です。

移動できるのは今いる段より1段上の高さのブロックまでです。高いところから降りる場合は何段でも降りることが出来ます。

3段目の高さまで積み上がったブロックに乗ると得点が入ります。ブロックが4段目まで積み上がると進入禁止の壁になります。

ゲーム性

なるほど3段まで積み上がったブロックに乗りまくって得点を稼ぐゲームやな!っていうのは間違いです。

相手を詰ますことができれば、その後で自分の得点はじっくり稼ぐことが出来るので、いかに相手の行動範囲を絞っていって相手を詰みまで持っていくかみたいなゲームになってます。

アルゴリズム

Minimax法(正確にはネガアルファ)を採用しました。計算時間が1秒くらいあればモンテカルロってたのですが、今回の制限時間である50msでは上手くモンテカルロる自信がなかったのでMinimaxにしました。

基本は3手読み(自分→相手→自分→評価)ですが、計算時間に余裕がありそうなら読む手数を増やしていきました。40msで160000回シミュレーションを回せたので、1手増やしてもシミュレーションの回数が160000回以下に収まりそうなら手数を増やすみたいな手法を取ってました。

評価関数

まず初手時の盤面で「開けた場所が高得点になるような影響マップ」と「相手の行動範囲を削れそうな位置なら高得点になる影響マップ」を作って、

稼いだ得点*1000
+移動可能な方向数*1000
+相手の行動を削る影響マップ点*1000
+開けた場所影響マップ点*100
+今いる高さ
-味方同士が接していたら1000点ペナルティ

みたいな感じの評価関数にしました。

影響マップは初手時の盤面じゃなくて最終手まで読んだ時点でのマップを採用したほうが正確な評価はできると思うのですが、それだと計算量が半端ないことになるので、初手時の影響マップを最終手でも流用することにしました。

影響マップ

この盤面を例にして影響マップの作り方の具体例を示してみます。 f:id:y_kwn:20170704224112p:plain

開けた場所影響マップ

まずそれぞれのマスについて8方向のうち何方向に移動できるかを出します。そして周囲3マス(ただし移動可能なマス限定)の値を足し合わせると影響マップになります。

これを 足し合わせる
f:id:y_kwn:20170704222517p:plain f:id:y_kwn:20170704223013p:plain

削れそうな位置影響マップ

この影響マップはプレイヤーの人数分だけ生成されます。ここでは下記の赤丸のプレイヤーさん分の影響マップを作ることを考えます。

まず移動可能なマスの数を算出します。今回の例の場合は10マス移動可能です。つづいて下記の星の位置の周囲に壁を生やしたと仮定します。すると移動範囲は3マスまで減ります。

このとき星の位置の得点を10-3=7点とします。これを全マス分計算すると影響マップになります。

これが こうじゃ
f:id:y_kwn:20170704224046p:plain f:id:y_kwn:20170704224053p:plain

敵位置予測

今の盤面と直前の盤面を比較して、敵の位置としてありうる位置を全て算出しました。予測位置が複数ある場合は、一番評価値が高くなる場所に敵が居ると決め打ちしてMinimaxを回してました。

自作シミュレータ

さて、今回のMVPは間違いなく自作シミュレータです。

f:id:y_kwn:20170703225235p:plain

今回のパラメータ調整とか評価関数調整は自己対戦を回して強さを確認してたんですが、CodinGame上ではなくて自作のシミュレータで対戦をやってました。

CodinGame上でやるのとは速度が段違いで、数分あれば数千試合は回せるので強くなったかどうかの判定はかなり正確にできてたんじゃないかと思います。

10戦して8勝2敗くらいだったら「強くなったやん!」と思いがちですが、そのあと1000試合回すと400勝600敗とかに平気でなったりするので、強さを測るには少なくとも数百回単位で回さないとダメかなーと思います。

シミュレータの正確性の担保には「CodinGame上で自分vs自分をやって、それと同じ初期盤面で自作シミュレータを回して最終結果が同じになるかチェック」ってのをやってました。

もちろんこのシミュレータはMinimaxのシミュレータとしても使ってました。

反省

ご自慢の自作シミュレーターですが、実は終了直前まで5x5・6x6の盤面しか生成しないバグが仕込まれてました

5x5・6x6・7x7は個別でチューニングすべきだったかも

終わったコンテストで1位を取るくらいの復習をしないともう上には上がれないかも

CODE4LIFE

CodinGameの10日間コンテスト。↓こんな感じで薬を作って得点を稼ぐゲームです。

https://www.codingame.com/replay/228356470

世界21位/国内5位でした。日本つよい。

ルール

↑のエリアではサンプル(薬の素)を取得できます。取得する際にはrank1~3を選べて、高ランクであるほど作るのが大変だけど高得点です。

←のエリアではサンプルを解析してレシピにします。不要なレシピはクラウドにアップロードするという形で捨てることが出来ます。なおアップロードしたレシピは敵・味方問わずいつでも再取得できます。

↓のエリアでは薬の材料を取得できます。材料は各種類5つづつ用意されてあり、それを敵味方で奪い合います。

→のエリアにレシピ+レシピに合った材料を投入すると得点になります。薬を作るとA~Eどれかの経験値を得られて、経験値分だけレシピより少ない材料で薬を作れるようになります。

アルゴリズム

ルールベースで処理しました。αβも考えたんですが、ルールベースの強さを超える自信がなかったし、評価関数がどーせヒューリスティックっぽくなるだろうなと思ってやめました。

↑の戦略

シミュレータのソースを見るとどんな種類のサンプルが取得できるかが載ってあったので、とりあえずそれはテーブルとして持っておきました。

ランク毎に平均得点(A)と手持ちの材料+下の材料で何割作れるか(B)を算出して、A*Bが最大になるランクを拾うようにしました。

←の戦略

とりあえず全部解析します。

解析後、手持ちに作れないものがあって、クラウドに得点が高くてかつ作れるものがあったら交換します。

1個でも作れるものがあったら↓に行って、作れなかったら全部アップロードして↑に戻ります。

↓の戦略

まず嫌がらせを優先します。A~Eそれぞれに対して[場にある数-敵の薬を作るのに必要な数]を算出してそれが3~0だったらそれを奪います。(今思えば3はやりすぎだったかも)

嫌がらせが終わったら、得点の高いものから順に材料を集めていきます。作り易い順でもやってみたんですが、何か弱くなったので採用しなかったです。(ここちょっと考察不足)

場にあるものを拾っても作れるものが無くなったら→に行きます。ただし、ここで相手が→に投入する直前で、欲しい材料が戻ってきそうだったら待機します。

→の戦略

何も考えずに薬を作成します。(ちょっとは考えたほうが良かったかも)

全部作成し終わって、手持ちのレシピに作れそうなものがあったら↓に行って、なければ↑に行きます。

反省

終盤何が強いのか分からなくなってしまいました。これは、AgadeさんがGhost in the Cellでやってたことなんですが、シミュレータを作ってローカルで数万回自己対戦して強くなったかどうか判断すべきでした。

そろそろパラメータの自動調整を実装したい。今回もrankの選び方とか嫌がらせの閾値調整とかに無駄に時間取られたので何とかしたいし、常に最強のパラメータを選んでるという安心感が欲しいです。

最後までゲームの肝がよく分かってなかった(考察不足)。後半思考を放棄していたのがダメダメでした。考えることを諦めては勝てるものも勝てません。

CODERS OF THE CARIBBEAN

CodinGameの10日間コンテスト。↓こんな感じで船を操舵して樽を拾ってHPを回復しつつ砲弾・機雷で相手を潰すゲーム。

https://www.codingame.com/replay/212959177

世界11位 / 国内1位 でした。

アルゴリズム概要

3手読みのchokudaiサーチでした。ホントは全探索したかったんですが3隻+3手だと時間的に無理だったので時間管理が楽なchokudaiサーチを採用しました。

1手につき味方全隻のTurnLeft・TurnRight・Faster・Slower・Waitの組み合わせを探索してます。(つまり3隻なら1手が53=125パターン)

探索の結果TurnLeft・TurnRight・Faster・Slowerが選ばれた場合は普通にその通り行動するんですが、Waitが選ばれた場合は、機雷を置いて効果のある場面なら機雷を置いて、それ以外だったら砲撃するみたいな行動をとります。

探索の最中、敵のターンは基本的に流すだけですが、最低限砲撃を避ける・機雷を避けるという行動は取らせるようにしてました。

機雷の置き方

敵の進行方向上に置けるなら置くって感じでした。また、劣勢時に敵が近くに居ない場合は、砲撃しても無駄なので機雷をばらまいてました。

砲撃地点の選び方

基本的には敵の未来位置に対して砲撃するだけです。未来位置付近に機雷が置いてあった場合は爆発巻き込み狙いで機雷を砲撃します。 敵が近くに居なくて自分が優勢のときは機雷の除去に走ります。また、自分より敵に近い樽を見つけたら容赦なく樽を砲撃しました。

評価関数

  • ラム量がベース
  • 速度が0ならペナルティ
  • 味方同士が近づきすぎたらペナルティ
  • マップの端に突っ込んだらペナルティ
  • 敵のケツに突っ込んだらペナルティ(機雷警戒)
  • 速度0の敵に砲弾を飛ばしてたらボーナス
  • 樽に近いとボーナス
  • 優勢時は敵から離れればボーナス
  • 劣勢時は一番ラム持ってる敵に近づくとボーナス

シミュレータのデバッグ

これは前回のCodinGameでもやってたんですが、シミュレーションした盤面と実際の盤面を比較して差異があったらエラーログを飛ばすってことをやってました。これやると、完璧と思ってたシミュレータのバグがボロボロ見つかったので、これやるのは必須と言っていいんじゃないでしょうか?

反省

αβやっても良かったんじゃないか?

3手読む必要が本当に合ったのか?(でも3手読みたい場面があったのは確か)

自殺してラムを生み出す手法は軽く導入しただけだったけど、もっと注力しても良かったかも。