ACM-ICPC2011 アジア地区予選福岡大会の JavaChallenge で優勝してきました
最近競技のネタばかりです。 methane です。
ACM-ICPC のアジア地区予選の1つが毎年日本で開催されており、KLabは3年前から そのスポンサーをしています。今年も 11/12-14 に福岡で大会があり、13日に観戦に行きました。
この大会の余興としてJavaChallengeというJavaでAIを作って戦わせるミニプロコンがあります。 昨年からこのJavaChallengeにOBやスポンサー企業も参加できる Special Leagueというイベントも 開催されるようになりました。 ( 今年のJavaチャレンジの問題)
去年は残念ながら3位だったので、リベンジだとばかり前日に問題が公開されてから当日の 午前4時までかかってプログラムを書き上げ、満を持して参加したのですが、、、去年は たくさんいたOBが福岡大会ということであまりおらず、コーチ等で来られていた方も 時間がとれず、結局 Special League は僕とあまり時間がかけられなかったコーチが一人の 2人だけでした。
それに勝つと今度は学生の優勝チームとの対戦になるのですが、学生は1時間の時間枠で 実装していて、今年は問題が去年よりも複雑だったのでかけられた時間の差が圧倒的な 差になってしまい、やはり圧勝でした。みんながルールを読んだりAIを実装するための APIを調べてる間に時間切れになったのに対し、一人だけ時間をかけてまともな AIを実装して俺TUEEEEしてる様はどう見てもチートでした。
せっかく実装したので、ソースを公開して簡単に解説ていきます。 （以下、上記リンク先の問題を知っていることを前提にしています）
アルゴリズムは、深さを限定した深さ優先探索で、葉の評価が一番良い選択肢を選びます。 探索部分は何も特別なことは無いので、評価部分を解説して行きます。
まず、コースレイアウトを取得したいのですが、その前に全体の幅と高さを取得するAPIが用意されていません。 しかし、座標ごとの状態を取得するためのAPIを叩いて結果を調べていたところ、コースの大きさを 超えたところで ArrayIndexOutOfBoundsException が発生することが解りました。なので、 最初に次のようにして全体のサイズを取得します。
// calc stage size.
private void _checkStageSize(GameInfo info) {
int i=0;
try {
for (i = 0;; ++i) info.getGoalDistance(i, 0, 0);
} catch (ArrayIndexOutOfBoundsException e) {
_width = i;
}
try {
for (i = 0;; ++i) info.getGoalDistance(0, i, 0);
} catch (ArrayIndexOutOfBoundsException e) {
_height = i;
}
}
次にコースレイアウトを取得します。各座標の状態を取得するAPIが用意されているのですが、 壁、道、ゴール以外にも味方の車、敵の車、攻撃エフェクトなど余計なデータが返ってくる代わりに、 どっちが順走でどっちが逆走なのかを知る方法がありません。ゴールまでの距離を返すAPIが別に あって、こちらを使うのが正解です。壁は -1, 道は正の整数, ゴールは 0, ゴールまでの距離が 小さくなる方向が順送になります。
for (y=0; y<h; ++y) {
for (x=0; x<w; ++x) {
_stage[y][x] = info.getGoalDistance(x, y, lap);
System.out.printf("%3d ", _stage[y][x]);
}
System.out.println();
}
このゴールからの距離をそのままコストにしても良いのですが、最短ルートに幅が1しかない道を選んでしまうので、 2方向で壁に隣接しているマスは高コストになるように再計算しています (_adjustCostメソッド)
次に、各マスで車が向いていて欲しい方向を決めて行きます。純粋にコストが小さくなる方向でも良いのですが、 次のようなケースで無駄に方向転換が多くなってしまう場合があります。
コスト 方向
########### ###########
####789ABCD ####vvvvvvv
#3456789ABC #vvvvvvvvvv
123456789AB <<<<<<<<<<<
1234####### <<<<#######
########### ###########
できれば、ストレートはまっすぐ走って欲しいところです。いくつか方法はあるのですが、コストを下げ続けながら 壁にぶつからずまっすぐに何マス進めるかを基準に方向を決めることにしました。
Direction d = Direction.NORTH;
int xx=x, yy=y, max_st=0, st=0;
while (!isWall(xx,yy-1) && _stage[yy-1][xx] < _stage[y][x]) {
yy--;
st++;
}
if (st > max_st) {
max_st = st; d = Direction.NORTH;
}
xx=x; yy=y; st=0;
while (!isWall(xx,yy+1) && _stage[yy+1][xx] < _stage[y][x]) {
yy++;
st++;
}
if (st > max_st) {
max_st = st;
d = Direction.SOUTH;
}
....
これで上の例は次のように改善されます。
コスト 方向
########### ###########
####789ABCD ####vvv<<<<
#3456789ABC #vvv<<<<<<<
123456789AB <<<<<<<<<<<
1234####### <<<<#######
########### ###########
ここまで来たら、評価するときは、各マスのコストに、車の方向が理想と異なった場合のペナルティを足したもので表現できます。 ゴールを過ぎて次のラップに入るときにコストが増えてしまう等の問題が残っていますが、一気に大きくコストが上がったら次のラップに 入ったことにして評価を良くするなどアドホックに対処しています。
また、速度制限もしています。深さ優先探索の葉の状態の次の状態で、どうやってもコースアウトするケースがあるからです。 速度が1なら真横にだって進めるので、探索の深さを n のときに最大速度を n-1 程度に制限すれば、あまり壁にぶつからずに 速度を出せるはずです。ただし、ガンガン壁にぶつかりながらでも速度を出したほうが、大きなタイムロスをするリスクがあるものの 早くゴールできる可能性が高くなります。今回は3台分のAIを用意できるので、探索の深さは時間の関係で 7 に固定したまま、 制限速度を 5, 7, 9 で走らせています。
今回の問題を短時間で解く方法を考えてみたのですが、実は走るコースは固定なので、APIの使い方を調べるよりも JARファイルを展開して中に入っているコースレイアウトを直接取り出すほうが早かったはずです。 コースレイアウトを固定でAIに埋め込むのなら、場所ごとの方向も最高速度も人間がそこそこ適切な値を 埋めていけば、上記の評価で使った値を15分程度で用意できるでしょう。 ただし、そんなちょっとズルい方法を使ったとしても、やっぱりドキュメントやAPIを読み解く時間を含めると、 1時間で探索まで実装するのはかなり難しいと思います。去年のTRONのようにルールがシンプルだけど奥が深くて 1時間でも1週間でも楽しめる問題が理想なのですが、難しいですね。
去年も今年も、スポンサー企業で参加しているのが僕一人なのですが、他のスポンサー企業の方も、 （例えば同じビルにある2つのG社さんとか）来年もSpecial Leagueがあれば一緒に参加しませんか？
