こんにちは 
id:zekehamp (KMCid:zeke)です。この記事はKMCブログリレーの一環で書かれたものです。
皆さん、ゲームはお好きですか？自分は好きです。 Hoi4というゲームが好きでよくやってます。
そんなことはどうでもよくて、今回紹介したいのはゲームAIです。
なにかAIという言葉を聞くと難しそうに聞こえるかもしれませんが、プログラミング言語の一つや二つを触ったことがあるならば、思ったより簡単に作ることができます。競プロなどをやっている人向けですが、競プロのマラソンに近いものがあると感じました。明確な解法があるというよりかは、いくつかの手法を組み合わせて徐々に改善していくという感じです。僕自身、いくつかの手法を試すことで
上位1/4ぐらいの成績をとることができました。 この記事では、このゲームに対しての紹介と簡単な攻略を書いていきたいと思います。
Tron Game
今回ご紹介するのはCodinGameが提供しているTron battleです。CodinGameは初心者向けから上級者向けまでいろいろなプログラミング教材を提供しており、Tron Gameはこの教材の一つとなります。またC言語を始めとしてPython,Rustなどさまざまな言語に対応しているのもよいです。 簡単な登録を済ませれば、任意のゲームAIと試合を組ませることができたり、Submitすることで自動的に試合が組まれその成績によってランク付けがなされたりします。
今回紹介するゲームであるTron Battle のルールを説明していきます。
- フィールドは20×30でプレイヤー数は2~4人
- 各プレイヤーは手番になればフィールド上を動き回るが、今いるところから縦横4方向にしか進めない
- プレイヤーは自他プレイヤーがすでに通ったところに進むことはできない
- 進める場所がなくなったら負け、負けたプレイヤーの通った場所は再び通ることができる
- 最後まで残っていたら勝ち
- 各ターン100ms以内に次の手をうつこと
ルール自体はとてもシンプルです。
参考までに入出力は
入力 N P X0 Y0 X1 Y1 X0 Y0 X1 Y1 … N-プレイヤー数 P-自分のプレイヤー番号 以下各プレイヤーの情報が続く (X0,Y0)初期座標 (X1,Y1)今いる座標
出力 UP DOWN LEFT RIGHT のどれか
です。
競プロでいうインタラクティブ問題ですね。
それじゃ早速動くものを作ってみよう！
兎にも角にも、とりあえず動かしてみましょう！
まず最初のコードとしてこんなものがあります。
#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; int main() { // game loop while (1) { int N; // total number of players (2 to 4). int P; // your player number (0 to 3). cin >> N >> P; vector<int> X0(4),Y0(4),X1(4),Y1(4); for (int i = 0; i < N; i++) { cin >> X0[i] >> Y0[i] >> X1[i] >> Y1[i];//各プレイヤー情報 } cout<<"LEFT"<<endl;//ただ左に進むだけ } }
ただただ左に進むだけ…！こんなコードでもちゃんと動きます。ただめちゃくちゃ弱いですが。
まず気づくのが自殺してしまうことですね。
壁にぶつかったり、プレイヤーがすでに通った場所を通ったり…
とりあえず自殺しないコードを
int main() { vector<vector<bool>> have(20,vector<bool>(30,true)); while (1) { int N; int P; cin >> N >> P; vector<int> X0(4),Y0(4),X1(4),Y1(4); for (int i = 0; i < N; i++) { cin >> X0[i] >> Y0[i] >> X1[i] >> Y1[i]; have[Y1[i]][X1[i]]=false; } int dx[]={0,-1,0,1}; int dy[]={1,0,-1,0}; string order[]={"DOWN","LEFT","UP","RIGHT"}; for(int i=0;i<4;i++){ int nowx=X1[P]+dx[i]; int nowy=Y1[P]+dy[i]; if(nowx>=0&&nowx<30&&nowy>=0&&nowy<20&&have[nowy][nowx]){ cout<<order[i]<<endl; break; } } } }
書きました。
これで自殺しなくなりますね！
ちょっと先読みをしよう！
これだと以下のような場合でよく負けてしまいます。
このようにすることで、袋小路に突っ込むことがなくなります！
残り手数を数え上げるには、幅優先探索(BFS)や深さ優先探索(DFS)を実装してやります。この二つは所謂、全探索アルゴリズムでそこまで難しくはありません。
int bfs(int y, int x, vector<vector<bool>>& dis, vector<vector<int>>& inter) { //全探索用BFS中身 //開始座標ともう行ったかどうかの配列と開始座標からの距離を入れる配列を渡す int tempcnt = 0; dis[y][x] = false; inter[y][x] = 0; queue<vector<int>> q; q.push({y, x, 0});//開始地点を入れてあげます int path_cnt = 0; while (!q.empty()) { vector<int> temp = q.front(); q.pop(); path_cnt++; int nowy = temp[0]; int nowx = temp[1]; int depth = temp[2]; inter[nowy][nowx] = depth; tempcnt ++; for (int j = 0; j < 4; j++) { int disty = nowy + dy[j]; int distx = nowx + dx[j]; if (disty >= 0 && disty < 20 && distx >= 0 && distx < 30) { if (dis[disty][distx]) { dis[disty][distx] = false; q.push({disty, distx, depth + 1}); } } } } return tempcnt; }
このようにBFS関数を実装してあげます。
するとこれだけでもかなり順位を伸ばすことができました。
さらに改善する
正直ここまで実装した後、いろんな手法を試したのですが、実行制限時間に間に合わなかったり、それほど効果がみられなかったりと苦戦を強いられました。
結果いろいろ小細工をすることで少々記録を伸ばすことができたので下に方法を記します
死んだプレイヤーの通ったところを再び通れるようにする
ルールにある通り死んだプレイヤーの通ったところは通れるようにします。だれがどこを通ったかを記録しておけば容易に実装できるはずです。
ちなみにSilver League以上だとプレイヤー数が3人以上になります。
敵プレイヤーとフィールドを共有しているかどうか
もし敵とさえぎられていたら、余計なことはせず最大限今いけるところを塗るようにするのがよさそうです。
端っこは通らないようにする
対戦記録を見ると端っこで押しつぶされて負けいるのがよくあったので…
逆に相手をつぶしてみる
上のような状態だと、多少自分の行き場所が減っても相手を即死させられるほうが良い手と言えるでしょう。
そこで2手先ぐらい進めてやることで相手の行き場所が劇的に少なくなった手を優先的に取るようにします。
具体的には自分の手を2手先ほど進めながら、自分と敵プレイヤーの残り手数を数え上げ、もともとの手数との比率を計算してあげることにより、相手の行き場所をなくすような手を取ることができます。
これを実装すると順位が600ほど上がりました
やばそうなところにはいかないようにする
下のような場合はどうでしょう？
BFSしても残り手数は上に行っても左に行っても変わりませんが、明らかに左に行ったほうが敵につぶされる可能性が高そうです。
そこで、50手(この値は適当です)以内で行けるマスを数えてあげて、そのマスの数が多いほうを選んであげるということを実装しました。
すると順位が200~400ほど上がったりしました。
こんな感じで
実装を進めていくとSilver Leagueの186位につけることができました！
もっと順位をあげるためには？
こっちが知りたいぐらいですが、コンテストのフォーラムを眺めていると以下のような手法が有効らしいです。
これらをうまいこと実装してあげたら上のリーグへと行けそうです
感想
自分自身ゲームAIなどは作ったことはなかったのですが、いろんな知見を得ることができました。 Tron Gameは単純なルールのゲームなのに、すごく奥が深いです。
また、このゲームAIはヴィジュアル化されているので実装したアルゴリズムの効果が分かりやすかったり、対戦要素があるので知っている人とやることもできるので、すごく楽しいと思います。
最後に
ゲームAI楽しいよ！って話がしたかっただけです。自分自身プログラミングを始めて1年ぐらいということもあり、かなり拙いコードになっているので後半はコードをお見せすることができませんでした… ハードルは低いので、気になった方は気軽に始めてみてはいかがでしょうか？
ところで今度こんなイベントがあります！現在進行形で開催中です！自分はzeke8080で参戦しています。個人のほかに大学単位で順位なども出るそうです。是非参加してみませんか？対戦お待ちしています。
KMCM
KMCではパソコンで何かしたい人々を募集しています！！
