Amadeus Challenge

CodinGameの14日間コンテスト。陣取りゲームです。

f:id:y_kwn:20180724071020p:plain

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

世界2位/199人、日本1位/16人でした。人数は少ないですが、TOP5常連の強者は軒並み出場してたので上位を取る難易度は普段と変わらなかったと思います。

ルール

ルールはかなり単純でした。リプレイを見たら雰囲気はだいぶ伝わると思います。

  • 味方と敵のユニットは同居できて、味方ユニットのほうが数が多ければコントロール配下の星となる。
  • 1ターンに5体ユニットをコントロール配下にある星、または隣接する星に送り込める。
  • 1つの星にユニットを送り込める回数は5回まで(1ターンに5体送っても1体送っても1回とカウント)
  • 5つ以上ユニットが居る星を1つ選んで、その5体を犠牲にして周りの星に1つづつユニットを送り込むことができる。(通称spread)
  • 隣接する星が、敵の星より味方の星のほうが多ければ敵ユニットが1体消える。
  • 最終的にコントロール配下の星の数が多いほうが勝ち。

アルゴリズム概要

1手読みのミニマックスでした。ただ1手読みでもTLEするので、評価値でソートしてビームサーチっぽい処理を入れてました。

シミュレータ実装

シンプルなルールなのでシミュレータは楽勝で作れます。47msで100k回くらいの性能でした。

ミニマックス

まずは送り込む候補となる星をピックアップします。ピックアップする星は前線の星、つまり敵と味方お互いが関与できる星を候補とします。

ピックアップした星に送り込む全パターンを手とします。ただし、ユニットを送っても敵ユニットの数より味方ユニットの数が少なくなるパターンはカットしました。 それに加えてリンク数が5つ以上の星に関してはspreadも考慮します。

で、まずは味方の手全てに評価を付けてソートします。その後ソートした順にミニマックスを展開していって最優良手を選んでいきます。 ざっくり図にすると↓みたいな感じです。

f:id:y_kwn:20180724071300p:plain

評価関数

コントロール配下にある星の数がベースでしたが、敵ユニットを削れる場合はボーナスを与えて、そのボーナスが一番重い評価関数でした。

このゲームは最終的により多くの星をコントロール配下に置けば勝ちですが、ユニットをより多く持っている方が当然より多くの星をコントロール配下に置きやすいです。 なので、星の数よりもユニットの数に重きをおくような評価関数にしました。

SpecialPlanet

今回のゲームでは、下記のような作為的なマップが結構な頻度で出現しました。

f:id:y_kwn:20180724071407p:plain

この例だと、16番の星を取るとめちゃくちゃ美味しいです。なので、こういうパターンが出たときは特殊処理を入れてました。ちなみに自分はこの16番みたいな星をSpecialPlanetと読んでました。

基本は通常のミニマックスと同じですが、ピックアップする方法と評価関数を変えてました。

まずピックアップする星は、自分が送り込めるのが可能なすべての場所にします。ただしユニットを送り込むパターンは同じ星に5体まとめて送るパターンのみに絞ってます。

評価関数は「SpecialPlanetまでの距離が近い星にできるだけ多くのユニットが配置されてれば良し」みたいな評価関数でした。

ヒューリスティック

あとは到るところに色々ヒューリスティック要素を入れてました。

  • 初動時に、前線が確定するまでは敵に近づいた分だけのボーナス点を与えた。
  • 前線が膠着した場合は、多少不利でも敵陣に無理やりユニットを送るように調整した。
  • 1つの星にユニットは5回しか送れないので、序盤は回数を節約するためにできるだけユニットまとめて送るようにした。

終盤はヒューリスティックを色々入れたり外したりが調整の中心だったので、ここには書ききれてないヒューリスティックも色々入ってます。

反省点

  • 1位になった後のモチベーション管理が難しい。(イキり)
  • もっと詰めるべき点があった気がするが、変更を加えても順位は上がらないので(終盤ずっと1位だったので)効果の測定が難しく詰めきれなかった気がする。

CODE OF KUTULU

CodinGameの10日間コンテスト。迷宮サバイバルゲーム(?)です。

f:id:y_kwn:20180625235257p:plain

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

世界3位/2092人、日本1位/67人でした。

ルール

4人対戦ゲームで最後まで生き残った人が勝利します。

敵と接触するとライフ(Sanity)が20減少します。ただ歩いているだけでも3-6減少していきます。2マス以内に他プレイヤーが居るとライフの減少が1~3に緩和されます。

敵はWandererとSlasherの2種類が存在します。Wandererはただ追跡するだけの敵で、Slasherは直線上のプレイヤーに狙いを定めて一足飛びで切りかかってきます。

プレイヤーは上下左右の移動の他にPlan・Light・Yellという行動が取れます。

ざっくり説明すると、Planはライフの回復・Lightは敵の追跡をかわす・Yellは他プレイヤーの動きを止めるという効果があります。

ゲーム性

他プレイヤーを見殺しにして最後まで自分が生き残れば勝ちですが、自分が生き残るためには他プレイヤーと協力しなければいけないというジレンマがあるゲームです。

基本的な勝ちパターンは、なるべく単独行動を取らず他プレイヤーと一緒に行動し被害を最小限に抑え、要所要所でYell等を使って他プレイヤーのライフを削っていく感じの動きになります。

アルゴリズム概要

chokudaiサーチで6手読みしてました。ただ、ほぼほぼ全パターン読み切れてたのでchokudaiサーチである意味はあんまりなかったと思います。

シミュレータ実装

Refereeは公開されていましたが、そんなに作業量は無いなと思ったので移植という形じゃなくてほぼほぼ自分で再実装しました。

デバッグに関しては、もうこれはシミュレータ実装の常套手段ですが、アリーナを全員自分にしてシミュレーション結果とリアルな結果の差分を見て、差分があったらエラーログを出すって方法でバグを潰していきました。

Slasherのstateの切り替えやtargetの取り方のデバッグで泣きそうになりましたが、1日半(土曜夕方~日曜夜)で完璧クオリティのシミュレータが完成しました。

45msecで大体10000~20000回シミュレーションできました。(ちなみに自分のAIのコメント出力の数字はシミュレーション回数です)

シミュレータ高速化

多分一番効いたのは経路探索の省略です。どう省略したかは単純で、任意の(x1,y1)から(x2,y2)まで何手でたどり着けるかを[w*h*w*h]のテーブルで持っていただけです。

同様に任意の(x1,y1)から(x2,y2)に進む場合、1手目はどの方向に進むかを[w*h*w*h][4]のテーブルで持っていました。

※[4]の意味 : 探索優先度がターン毎にRDLU→DLUR→LURD→URDL→RDLU→...と切り替わるので4つ持つ必要がある

ただ、LightEffectが存在する場合は大人しくBFSで検索してました。

chokudaiサーチ部

6手読みで、遷移は2手目までは「待機・上下左右・plan・light・yell」の8パターンで、3~6手目は「待機・上下左右」の5パターンでした。

遷移の間、他プレイヤーは待機上下左右の5パターンのうちから簡易評価関数が最も良くなる方向に行動します。

※敵の簡易評価関数 : ダメージ食らう位置だったら-1000 - 1番近くの味方までの距離 * 2.0 + 1番近くの敵までの距離 * 1.0

評価値は「1手目の評価値 * 1.0 + 2手目の評価値 * 0.98 + 3手目の評価値 * 0.96」みたいな感じで、各ターンの評価値を足し合わせた値を使いました。

遠いターンの盤面は他プレイヤーの行動によって予想と全然違う盤面になってるはずなので、6手目の評価値だけをみるのは微妙な気がしたので足し合わせることにしました。

同じような理由で、計算時間的に7手読み以上も余裕でできますが、あんまり遠いターンを読んでもしょうがないないなという理由で6手で打ち切ってます。(実際性能は上がらなかった)

評価関数

自分のSanity * 100
1番近くのWandererまでの距離 * 1.0
Wandererのターゲットが自分だったら-10
Wandererと隣り合っていたら-100
1番近くのSlasherの距離 * 0.5
Slashが直線上にいたら-10
Lightの個数 * 0.05 (ちょっとでも得するなら使うようにした)
Planの数 * (6-_sanity_loss_group)*5*100 (他に1人巻き込んでplanを使うと採算が取れるように調整)
1番近くのシェルターまでの距離 * 0.25

(以下1手目限定)
他プレイヤーのSanity * -20
他プレイヤーに対してYELLを使っていたら-200 (YELLの無駄打ち防止)
1番近くの他プレイヤーまでの距離 * -2.0 (3人以上生き残ってるときのみ有効)

※遠いターンの他プレイヤーの予測位置は当てにならないので、他プレイヤーに関する評価は1手目限定にしてます

反省

  • 終了後のチャット眺めてた感じblasterpoardさん・Agadeさんはminimaxを使っていたっぽいです。minimaxとBFSの組み合わせっぽい?自分もminimaxはありかなと軽くは思っていたんですが、軽く思っていただけでした。ビームサーチ系が当たり方針だという思い込みがあったので(まぁ当たりではあったと思うけど)、真面目に考察するフェーズまで行かなかったのが後悔ポイントです。

  • あと1手あれば1位だったけど、その1手はminimaxだったと思う。

  • パラメータ調整をやりすぎるのは悪手なんですが今回はやらなすぎた感がある。

  • 大局を見た上での調整を全く入れてなかったので、ちょっとは入れても良かったかも。初期位置が相手と離れすぎていたら序盤は合流を最優先にするみたいな。

  • (」・ω・)」うー!(/・ω・)/にゃー!をコメント芸でやればよかった。(今思いついた)

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の選び方とか嫌がらせの閾値調整とかに無駄に時間取られたので何とかしたいし、常に最強のパラメータを選んでるという安心感が欲しいです。

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