2017年6月24日～7月3日に開かれた競技プログラミングコンテスト、codingame「wondev women」の備忘録です。
結果
世界47/2299位、日本4/58位でした。
今回のお題は陣取りゲー。シンプルなのに奥が深く、過去最高のゲームだったと思います。
考えたこと・やったこと
初日（数時間）
「探索が重要になりそうだな。いつも無理くりルールベースだから、ちゃんとアルゴ実装しよ。」
最低限の評価関数でBronze到達を目指しました。
・ポイント取得で＋
・より高い位置ならば＋
・周囲8マスで移動可能マスが多いほど＋
・移動不可は大幅－
2日目（丸一日）
「折角だし、流行りのアルゴで成果出したいな。」
バンディットアルゴリズムを作成しました。簡単なMCTSは書いたことがあったので、それをベースに膨らませました。
3～7日目（数時間）
「…（お仕事で死亡）」
数日かけて評価関数をひとつだけ追加しました。私のAIは強さは、ほぼほぼこの評価関数に依ります。
・相手より自分に近いマスの数を、将来的な取得ポイントとして扱う。
8日目
「switch売ってない…」
9日目（丸一日）
「とりあえず、やるだけのやつはやろう。」
・アルゴのバグ修正
・相手の位置予測 ←これも結構効いた
・パラメーター調整 ←もはや頭が働かずポチポチしてた
終了。
アルゴから取り組むと、無駄になることが少なくて効率的でした。
計30時間弱でTシャツ届いたので、いつも時間で殴ってしまう自分としてはちょっと成長です。
実装したアルゴリズムについて
バンディットアルゴリズムをベースに、ゲームAI特有のヒューリスティック評価を組み込みました。処理概要は下記を時間いっぱい繰り返します。
１． 大元のノードからバンディットアルゴリズムを用いて、未探索のノードまで潜る。
＃UCBを使用。選択肢となるノードの評価値は、選択時に0～1の間になるよう単位化。
２． 未探索のノードの次手をシミュレート、得られた子ノードの中から最も高い評価値をそのノードの評価値とする。
＃相手番の場合は、逆に最も低い評価値のものを選択。
＃相手番は、ユニットの位置が確定できる場合のみシミュレート。
３． ノードの選択数をカウントアップ、評価値の更新を大元のノードまで巻き戻す。
＃MCTSだと単純に勝率となる部分に評価値を当てはめることで、ゲーム終局までの探索を回避。
下記は簡易化したソース（アルゴリズムの本質とズレる部分は省略してます。）
/**
* codingame 2017/06/24 wondev women
*
* @author tsukammo
*/
class Player {
public static void main(String args[]) {
new Player().play();
}
void play() {
Scanner in = new Scanner(System.in);
size = in.nextInt();
units = in.nextInt();
Node now = new Node();
// game loop
while (true) {
startTime = System.nanoTime();
init(now);
input(in, now);
Node ans = search(now);
if (ans == null) {
System.out.println(DEFEAT);
} else {
System.out.println(ans.out.toString());
}
}
}
private Node search(Node root) {
while ((System.nanoTime() - startTime) < timeLimit) {
Node now = root;
while (now.children != null) {
Node tmp = now.selectChild();
now = tmp;
}
now.getChildren();
}
return root.choseChild();
}
public class Node {
Node parent = null;
byte field[] = new byte[size * size];
int[] uni = new int[units * 2];
List<Node> children = null;
Output out = new Output();
boolean myTurn = true;
int score = Integer.MIN_VALUE;
double visits = 1;
// 処理概要１
Node selectChild() {
Node ans = null;
// 自分or相手のターンで反転
int vec = getVec(myTurn);
// 単位化
int maxScore = Integer.MIN_VALUE;
int minScore = Integer.MAX_VALUE;
for (Node child : this.children) {
if (maxScore < child.score * vec) {
maxScore = child.score * vec;
}
if (minScore > child.score * vec) {
minScore = child.score * vec;
}
}
double calib = Math.abs(maxScore - minScore) + vec;
// バンディットアルゴリズム：UCB
double maxValue = Integer.MIN_VALUE;
for (Node child : this.children) {
double ubtValue = (child.score * vec - minScore) / calib
+ C * Math.sqrt(2 * Math.log(this.visits) / child.visits) * vec;
if (maxValue < ubtValue) {
maxValue = ubtValue;
ans = child;
}
}
return ans;
}
int getVec(boolean myTurn) {
if (myTurn) {
return 1;
} else {
return -1;
}
}
// 処理概要２
void getChildren() {
children = new ArrayList<>();
// 子ノード生成は省略
for (Node c : children) {
c.myTurn = !myTurn;
c.eval();
}
backpropagate();
}
void eval() {
// 省略
}
// 処理概要３
void backpropagate() {
Node n = this;
while (n != null) {
int vec = getVec(myTurn);
int maxScore = Integer.MIN_VALUE;
for (Node child : n.children) {
if (maxScore < child.score * vec) {
maxScore = child.score * vec;
}
}
n.score = maxScore;
n.visits += 1;
n = n.parent;
}
}
public Node choseChild() {
Node ret = null;
int maxScore = Integer.MIN_VALUE;
for (Node n : children) {
if (n.children != null && maxScore < n.score) {
ret = n;
maxScore = n.score;
}
}
return ret;
}
}
// 以下略
}
狙った効果
今回のゲームは、石を落とす場所によって評価値が変わらない場合がほとんどだったので、自分にとって有効な（逆に相手にされると嫌な）評価値の高い（低い）ノードに計算資源を集中投資できたんじゃないかと思います。
フィールドをbyte配列で保持する等高速化を施して、開けた場所で4ターン？くらい（自→相→自→相※ラストは数ノードだけ）、後半パターンが少なくなると相当深くまで探索できていたようです。時間管理も超楽。
反省点
アルゴが複雑なこともあり、最終日までバグ対応してました。結果、評価関数を練る時間はありませんでした。また、深さの違うノードの評価値を同列に扱うのは本質的に間違っている気がする、が、上手く工夫できませんでした。
最後に
ここまで読んで頂きありがとうございました。通期コンテスト化したら、アルゴリズム部分だけ貪欲探索とか2ターン全探索とかのものと入れ替えて、どれが一番強いかとか実験してみたいなぁと思ってます。
そして、この前創部した弊社競技プログラミング部についてですが、若手を中心にちょっとずつ参加者増えてきました。競プロ初経験のメンバーばかりですが、codingameはやはりウケがいいです。これから競プロ力をどんどん磨いてもらって、日本上位を占めていきます！
【定期】お客様も歓迎いたしますので、興味があればご一報を。
＃創部間もないのでまだ窓口がありません。御用の際は私のTwitterアカウントに連絡下さい。@tsukammo
以上