SPRING CHALLENGE 2020

CodinGameの10日間コンテスト。じゃんけんパックマンゲーム。

f:id:y_kwn:20200518230416p:plain

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

世界25位/4976人、日本5位/228人でした。個人的にはあまりぱっとしない成績。

ルール

同時に2~5体のパックマンを操作しペレットを集めるゲーム。
過半数のペレットを集めたほうが勝ち。
じゃんけんで勝っている敵のパックマンを食べることができる。
アビリティとして「加速」と「グーチョキパーどれかに変身」が使える。

アルゴリズム概要

10手読み幅200のビームサーチで各パックマンの動きを決定。
パックマン毎に200パターンの動きが求まるので、どれを組み合わせるかを山登りで決定。(この辺のパラメータ調整は甘い)

最初は相手の動きに合わせて如何に動くかが肝心と思って「すわっこれはMCTSか!?」と思ったんですけど、敵と絡むことはそんなにないので敵の動きはある程度無視して自分の動きを最適化するのがベストだと思い直しました。
さらに味方同士もそんなに絡むことはないから、パックマン毎にサーチして後でマージするって方式にしました。

ビームサーチ部

10手読み幅200でサーチ。
多様性確保のために最初の2手の動きが異なる物はビーム内に必ず入るようにした。
あいこか負ける敵は行き止まりとして扱ってサーチした。(これ勝つ相手も行き止まりにしてよかったかも)
来た道を戻るような動きにはペナルティをかけた。

山登り部

パックマンが10ターン分の動きを200パターン持ってるから、各パックマンはその中から動きを1つチョイスする。選んだ動きを元に10ターン分シミュレーションして評価する。シミュレーション中敵は動かさない。
その後どれか1つのパックマンの動きを変更するという遷移で山登りする。

評価関数

小ペレットを取った数 * 10
大ペレットを取った数 * 100
なくなってるかもしれないペレットを取った数 * 1
近くの小ペレットまでの距離 * -0.1
近くの大ペレットまでの距離 * -5.0
殺される相手の移動圏内にいると -10000

小手先テクニック

敵の動きの予測

各ターンの最初に、見えない敵は1手分動きを予測して予想位置を決定した。 動き方はこれ↓

  • アビリティを使える状態なら加速を撃つ
  • なるべく大ペレットに近づく
  • ペレットに接していたらペレットを食べる

見えない敵を再び見かけたときは、その地点にワープさせた。(適当)

通路

f:id:y_kwn:20200518230020p:plain

通路(画像の黄色い部分)の入り口をチェックして、入り口にペレットがあったら通路内のペレットはまだ存在すると仮定した。逆にペレットがなかったら存在しないものとして仮定した。

とられたかもしれないペレット

ペレットは、小ペレット・大ペレット・とられたかもしれないペレットの3つの状態を持つようにした。

かちあい時の動き

f:id:y_kwn:20200518230027p:plain

かちあいが発生したら、加速と相手に突っ込むのを禁止した。
(加速したらその瞬間に取られるし、変身した相手に突っ込んだら死ぬので)

殺し

アビリティを使えない敵が袋小路に追い込まれていた場合は殺すようにした。 逆に自分が袋小路に追い込まれていた場合は勝てる相手に変身するようにした。

反省

敵の動きの予測をもっと作り込むべきだったかなあ。

戦術をもっと真面目に考えるべきだった。

諸々検証不足でフィーリングで進めがちだった気がする。

山登りより優先度順にビームサーチの方が強そう。

CODE VS Reborn

2019/4/15~2019/5/10にあったゲームAIコンテスト。ぷよぷよみたいな落ち物パズルゲー。

f:id:y_kwn:20190521201613p:plain

決勝の様子(が見れる予定):https://live.nicovideo.jp/gate/lv320076507

予選3位/112人・決勝◯位でした。
参加人数は少ないですが参加面子を考えると日本最高峰のゲームAIコンテストだったでしょう。

ルール(適当説明)

基本ぷよぷよですが、4つ揃えるんじゃなくて数字の和を10に揃えたらブロックが消えるみたいなルールです。 連鎖すると敵の盤面にお邪魔ブロックを降らせます。相殺もぷよぷよと同じ仕様です。 ぷよぷよと大きく違うのはスキルがある点です。ブロックを消すとスキルゲージが溜まって、溜まると数字の5を爆発させて連鎖したときと同じように攻撃ができます。

アルゴリズム概要

目標連鎖数を決めてchokudaiサーチで探索して、発火が近くなったら色々考える感じです。

全体フローチャート

f:id:y_kwn:20190521201912p:plain

連鎖数決定

基本12連鎖を狙います。

敵がスキル型だったら15連鎖を狙います。敵が6連鎖以上組めてなかったらスキル型と判定してます。

敵を殺せそうだったら殺せるぐらいの連鎖を狙います。例えば敵が3行のお邪魔で死ぬなら大体11連鎖(お邪魔33個)を狙う感じです。

探索

心臓部です。

探索の重要性

単純な探索では絶対に負けないようにしました。敵が先に12連鎖撃ってきてるリプレイを発見したら、最低でも同じ速度で撃てるように徹底的に改良しました。 探索で負けていてもカウンター等の戦略で勝つことはできますが、それはじゃんけんに例えると「パーを出せないからグーとチョキと戦略で勝つ」みたいな発想です。 上位層で戦うにはグーチョキパーすべてと戦略を組み合わせないと話にならないと思ったので、妥協は絶対にしないようにしました。

探索の概要

10秒間のchokudaiサーチで探索しました。初手だけ18秒です。

MAX15ターンですが予定の連鎖数が見つかったら探索を打ち切ってるので15ターンまで読むことはほぼ無いです。(言い変えると15ターン以内に連鎖が見つかるように調整した)

こういうサーチ系を強くするのに重要なのは

  • 評価関数改良
  • 高速化
  • 探索の質を高める

ですが、評価関数はほぼ弄ってないので残り2つ中心の改良が中心でした。(評価関数を弄らないで正解だったかは不明)

評価関数

連鎖数 * 100
+ ブロック数 * 0.1
- 消えたブロックの数/連鎖数
- 15行積み上げていたらペナルティ
- 2ターン前から連鎖数が伸びてなかったら超ペナルティ

連鎖数は1ブロックを仮で落としてみての連鎖数です。

ブロックの落とし方ですが、最初は左端から右端まで落としてチェックしますが、1度連鎖を発見したら以降は発見ポイントから前後1マスだけ落とすように縛ってます。

高速化

多分皆やってたと思うんですが、1マスに4bitを割り当てて盤面をlong long[WIDTH]で表現して、ひたすらbit演算しました。

ざっくりすぎるのでいつもやってる高速化の手法を紹介します。これはどんなコンテストでも使える汎用的な方法です。

1. visual studioでパフォーマンスプロファイラーを起動します。

2. ボトルネックを見つけます

3. ボトルネックをカスカスになるまで高速化します。

f:id:y_kwn:20190521203149p:plain
ボトルネック

よくある話ですがボトルネック以外は高速化してもほぼ意味がないです。

実際にどう高速化するかはtomerunさんの高速化の記事を読みましょう。 https://topcoder.g.hatena.ne.jp/tomerun/20171216

探索の質を高める

基本は「無駄な探索を排除する」です。

まずはこんなツールを作ります。

f:id:y_kwn:20190521203405p:plain

これはchokudaiサーチの中身をダンプしたものを表示するツールです。これとにらめっこして改良していきました。

主にやったこと
1.ブロックを落とす場所を連鎖群に隣接する範囲に絞る

この縛りを入れないと、離れたとこにポツンと落とすパターンが生まれるので潰しました。

f:id:y_kwn:20190521203706p:plain

2.1ターン目は落とす場所を真ん中に固定する

この縛りを入れないと、形が横にずれただけみたいなパターンが生まれがちなので縛りました。 f:id:y_kwn:20190521211126p:plain

3.重複盤面除去

ダンプした結果を見ると重複盤面がそこそこあったので排除しました。

発火間際の諸々

発火1・2手前になると諸々考えて、前倒しで発火するか普通に発火するかさらに連鎖伸ばすかを判断します。

以下が入れた処理です。カッコ内は判定タイミングです。

・カウンター警戒(連鎖発動ターン)

カウンター戦術使ってくる人が多かったので入れました。

敵にお邪魔ブロックを降らしてみた上で敵の盤面を7手読みchokudaiサーチします。 で、こっちがかました連鎖数以上のカウンターが飛んでくるようだったら、連鎖を撃っても意味ないので連鎖さらに伸ばします(目標連鎖数はそのカウンターの連鎖数)。

・目標連鎖数に達していたら発火(連鎖発動ターン)

変にバグって発火しなかったら困るのでこの処理入れました。

・対ボマー対策1(連鎖発動2手前以内)

敵があと2手でスキルゲージが溜まる状態かつ、こちらが2手以内に12連鎖以上発動できる場合は発火します。

・対ボマー対策2(連鎖発動3手以上前)

敵があと3手でスキルゲージが溜まる状態かつ、こちらが3手以内に連鎖を発動しない場合3連鎖を狙います。

・連鎖潰され対策(連鎖発動1手前)

敵が連鎖を発動させたと仮定して自分の盤面にお邪魔ブロックを降らせます。で、次のターンの自分の連鎖数が激減する場合は前倒しで連鎖を発動します。

・まだ舞える(連鎖発動ターン)

敵の盤面を2手全探索してもしょぼい連鎖(11連鎖以下)しか見つからない場合、自分の盤面を2手全探索します。で、連鎖が伸ばせるなら自分の連鎖を伸ばします。

・敵の連鎖つぶし(毎ターン)

敵が次のターンに12連鎖以上発動させることが出来る場合、ためしに自分の連鎖を発火させてみます。で、お邪魔ブロックを降らした結果、敵が2手かけても5連鎖以下しかつくれない状態になるなら連鎖を発動します。

小ネタ

死亡間際のボマームーブ

基本は足掻いてもそのまま死ぬんですが、たまーに刺さるのでやり得でした。 雑に3手呼んで、スキル攻撃力を上げつつゲージ溜め優先といった感じです。

並列化はやってない

最後2日くらいでやろうと思ったんですが、やろうと思ったときには上位キープしてたし、決勝も1スレッドだろうからまあいいかなって感じでした。

反省点

余裕で決勝で行けたのでまあ満足です。

CODE A LA MODE

CodinGameの10日間コンテスト。味方と協力して料理を作るゲーム。

f:id:y_kwn:20190319070610p:plain

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

世界7位/1543人、日本2位/53人でした。もう日本2位は嫌なんじゃ・・。

ルール

一言で言うとovercookedです。2人で料理を作って配膳するとスコアが入るゲームです。
いつものと違って対戦相手と協力プレイをするってのが面白いです。

料理の作り方はそれぞれ↓みたいな感じです。

料理 作り方
アイス そのまま
ブルーベリー そのまま
イチゴ イチゴ→まな板→完成
クロワッサン パン生地→オーブン→完成
タルト パン生地→まな板→ブルーベリー→オーブン→完成

順位の付け方は、3人がマッチングしてA+B・B+C・A+Cで協力プレイをして、合計スコアが高い順で順位が付きます。 例を挙げると・・

A+B: 100点
A+C: 200点
B+C: 1000点

だったとすると

A: 300点
B: 1100点
C: 1200点

みたいなスコアがついて順位が付きます。こういう形式にすれば協力プレイでも順位がつくのでなるほどな~と思いました。

アルゴリズム

chokudaiサーチで7手読みでした。シミュレータは45msで100k~150kくらいの性能でした。
これ書いてて気付いたけど重複盤面除去やってねぇ。

サーチ部

枝刈り

  • 1~3歩の移動かつ外周を移動中かつ周囲になにもない場合の移動は無視してます。
  • 手に何か持ってる時、周囲に複数箇所置ける場所があっても置く場所は1箇所にとどめています。RAW_TARTならオーブンの近くに置くとかそんな感じで適当に決めてます。

相棒のシミュレーション

相棒の行動は以下のシミュレーションだけやって、それ以外は棒立ちです。

  • 1手目の時点でオーブンにTARTかCROISSANTが入っていて、オーブンに隣接している場合取る
  • 完成した料理を持っていたらwindowに近づいて配膳

評価関数

ゲームスコア  
+ (料理が揃っていたら)配膳する評価値  
+ タルト・クロワッサンの数(燃え尽き防止)  
+ 料理作る評価値  

基本的に上に書いてある方が値が大きくなるようになってます。
「配膳する評価値」と「材料作る評価値」は3つのオーダーそれぞれで評価値を出して、1番評価値が高い値を採用しています。
結果的に配膳できるものをさっさと作ってさっさと配膳する感じの評価関数になってます。

配膳する評価値

料理が皿に乗ってたら加点  
+ 料理が皿に乗ってなかったらその料理までの距離  
+ 皿を持ってなかったら皿までの距離  
+ 余計なものが皿に混じってたら大減点  

料理作る評価値

(必要な料理それぞれについて)  
既に料理ができていたら加点  
+ 料理の進捗度に応じて加点  

例:TARTの進捗度得点

状態 得点
オーブンにRAW_TARTを入ってたら 4点
RAW_TARTを持っていたら 3点+オーブンまでの距離で微小点
CHOPPED_DOUGHを持っていたら 2点+BLUEBERRIESまでの距離で微小点
DOUGHを持っていたら 1点+まな板までの距離で微小点
何も持っていなかったら DOUGHまでの距離で微小点

その他

bit表現

アイテムやらはこんな感じでbitで表現してました。

const int NONE                  = 0b000000000000000;
const int DISH                  = 0b000000000000001;
const int BLUEBERRIES           = 0b000000000000010;
const int ICE_CREAM             = 0b000000000000100;
const int STRAWBERRIES          = 0b000000000001000;
const int CHOPPED_STRAWBERRIES  = 0b000000000010000;
const int DOUGH                 = 0b000000000100000;
const int CROISSANT             = 0b000000001000000;
const int CHOPPED_DOUGH         = 0b000000010000000;
const int RAW_TART              = 0b000000100000000;
const int TART                  = 0b000001000000000;
const int MAP_EMPTY             = 0b000010000000000;
const int MAP_TABLE             = 0b000100000000000;
const int MAP_WINDOW            = 0b001000000000000;
const int MAP_CHOP              = 0b010000000000000;
const int MAP_OVEN              = 0b100000000000000;

メモリ使用量抑えたり、速度稼ぐためにやっとくかーって感じでしたが、普通に諸々の処理書くときに割と便利でした。

if(hand & DISH) //皿を持っているか
if(hand & (~order)) //オーダーにないものを持っているか
hand |= TART //タルトを拾う

みたいな

小ネタ

相棒が持っているものは基本無視しました。他人を信用しないスタンスです。

オーブンに入ってるRAW_TART・DOUGHはTART・CROISSANTとしてカウントしています。これで焼け上がるのをボーッと待ってるマンを防げました。

ローカルテスト環境

一応ローカルでもゲームを回せるようにしてました。プレイヤーは全員最新の自分で30戦くらい回して改善をチェックしてました。
ローカルテストでのスコアをベースで改善を進めるんじゃなくて、大きくスコアが下がってなければバグが仕込まれていないのでOKくらいなスタンスで運用していました。
ただまぁ、ローカルテストのスコアとsubmit後の順位は大体比例してた気もします。

反省点

  • やっぱりこれ書いているときにバグやら改善点を思いつくので、面倒臭がらずに終了1日前くらいにこれ書いた方がいいかも。
  • 評価関数の数字の大小関係の調整が超シビアだったので、予め理論的に評価関数を設計すべきだったかも。
  • 取れる行動の種類は多くても、シチュエーションの数は数えれる程なので(ホントか?)もっとヒューリスティックに寄せても良かったかも。
  • 何か見ながら作業するのはやめた方が良い(さく ゆい かわいい)

Xmas Rush

CodinGameの10日間コンテスト。アイテムを集めるゲーム。

f:id:y_kwn:20181217212006p:plain

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

世界29位/1229人、日本2位/40人でした。上位層に全然ついていけなかったので悔しい結果です。

ルール

大きく分けてPUSHターンとMOVEターンに別れていて、その2つのターンを繰り返します。

PUSHターン:いずれかの行列をPUSHして迷路をずらします。このときの行列の指定は敵味方同時に行います。敵味方で同じ行or列が指定されたら何も起きません。

MOVEターン:プレイヤーを20歩動かすことが出来ます。アイテムが3つ指定されるのでそのアイテムを回収するのが目的です。回収すると次のアイテムが指定されます。

最終的に12個のアイテムを回収したほうが勝利します。

アルゴリズム

minimaxっぽいことやりました。計算時間は余裕だったので枝刈りとかやってないです。

PUSHターン

自分のPUSH(max) → 敵のPUSH(min) → アイテム回収MOVE(一意に定まる) → 自分のMOVE(max)

という探索をやりました。2手読みとかやってみたんですけど性能落ちたので採用してないです。

MOVEターン

アイテム回収MOVE → 自分のMOVE(max) → 自分のPUSH(max) → 敵のPUSH(min) → アイテム回収MOVE → 自分のMOVE(max)

という探索をやりました。

評価関数

  • 回収したアイテムの個数がベース
  • 自分が端にいてNEXTに自分のアイテムがあったらそこそこプラス
  • 自分が動ける範囲が広かったらちょっとプラス
  • 指定アイテム周辺の道が繋がってたらほんのちょっとプラス
  • 相手を邪魔するより自分の得点を稼ぐムーブをしたかったので、自分に関する評価値はちょっと増やした

小手先テクニック

  • 行のPUSHが優先されるのでNEXTが自分のアイテムでかつ横端にいると100%アイテムを回収できる。
  • よく行列がかち合って数ターンロック状態になるけど、ロック状態のときは相手は自分と同じ行or列を指定しているはずなので、敵の動き予測が2パターンまで絞れる。
  • 敵がアイテム回収を先行している場合、敵の指定アイテムを記録しておくことで自分の次の指定アイテムを予測できる。

反省

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以下になったら)大減点、敵が自タワーの範囲に入っていたら加点するようにしました。

反省点

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

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

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

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