2017-11-28

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手読みくらいなら評価関数でカバーできるやろの精神でした。

シミュレータ

まず１・２日目に完璧なシミュレータを作りました。シミュレータ部分に関しては公式で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止めたんですがやっぱりやればよかった。（収束早めるには行動数削ればいいし、敵は無視しても良さそうだった）

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

2017-07-03

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マス(ただし移動可能なマス限定)の値を足し合わせると影響マップになります。

これを	足し合わせる

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

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

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

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

これが	こうじゃ

敵位置予測

今の盤面と直前の盤面を比較して、敵の位置としてありうる位置を全て算出しました。予測位置が複数ある場合は、一番評価値が高くなる場所に敵が居ると決め打ちして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位を取るくらいの復習をしないともう上には上がれないかも

2017-05-23

CODE4LIFE

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

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

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

ルール

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

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

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

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

アルゴリズム

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

↑の戦略

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

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

←の戦略

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

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

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

↓の戦略

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

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

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

→の戦略

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

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

反省

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

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

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

2017-04-24

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手が5³=125パターン）

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

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

機雷の置き方

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

砲撃地点の選び方

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

評価関数

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

シミュレータのデバッグ

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

反省

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

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

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