Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

TSG LIVE! 2 ライブAIプログラミング反省

この記事はTSG Advent Calendar 201820日目として書かれた記事です。昨日はつばめ氏の「Java の Deserialization 経由の RCE について?」の予定です。


初めましての方は初めまして、Misterです。東京大学TSGというプログラミングサークルに所属しています。

10日前にこのAdvent Calendarで「TSG LIVE! 2 ライブ競技プログラミング反省」という記事を書きました。今回はその続きとして、私がプレイヤーとして参加したもう1つの企画「ライブAIプログラミング」について書きます。


簡単に説明すると、「ライブAIプログラミング」は「75分間でできるだけ強いゲームAIを作る」という企画です。「ゲームAI」と言ってもそこまで大それたものではなく、ゲームをプレイするプログラム全般を指します。

ちなみに本コンテストの作問者であるmoratorium氏も、Advent Calendarで「TSG live AI コンテストの内容と感想、盤面生成に関する妄想など」という記事を投稿しています。裏の話が見られて面白いので、ぜひこちらも読んでみてください。

ゲーム概要

まずこのゲームは攻守に分かれてのターン制で行われる。

 H \times Wのまばらに壁が配置され、外周が壁で囲まれた2次元グリッドがある。グリッド上にはBeamTargetと呼ばれるロボットがそれぞれ最初 N台、 M台配置されている。

各ターン、攻撃側はBeam、守備側はTargetのうち1台を、4方向のうちいずれかに動かすことができる。このとき各ロボットは壁か他のロボットに接触するまで、止まることなく直進し続ける。

さらにBeamは移動の際、移動する方向にビームを打つことができる。ビームは壁によって遮蔽されるが、ビーム上にいたTargetは消滅する。さらにビームは盤面上に残り続け、Targetにとっては壁となる(接触しても消滅はしない)。

スコアと制約

各ケースについて攻守を交代し、共通の盤面にてゲームを行う。そして攻撃時にTargetをより早く全滅させたプレイヤーに所定のスコアが入る。なおゲームは最大300ターンまで行われる。

制約、スコア、ケース数は以下の通り。

  •  (H = W = 10, N = 3, M = 2, Score = 40) \times 10
  •  (H = W = 20, N = 10, M = 3, Score = 100) \times 3
  •  (H = W = 30, N = 20, M = 5, Score = 200) \times 1


大体上の通りですが、文で言われてもイメージが湧かないと思います。先に上げたmoratorium氏の記事にゲーム動画が載っているので、そちらも参照していただけると良いかと。

本番の流れ

環境整備

それでは早速乱択を、とやりたくなりますがここで思い留まります。

過去に何度か長めの実装をした経験1から、適当に実装したら後でコードが壊滅することは目に見えていました。かといって、十分丁寧に実装するには75分は短いかも分かりません。

少し悩んだ結果、自分の実装スピードを信じてクラスから実装することにしました。結果としては実装が幾分楽になったので、この判断は正しかったように思います。

初期段階では、クラスの構造は以下のような感じでした。

class Robot {
public:
    explicit Robot(int _x, int _y, int _id);

    int x, y, id;
};

class Board {
public:
    explicit Board(int _H, int _W);
    
    // 標準入力を元に初期化する
    void load();
    
    // (x, y)が盤面内にあるか判定する
    bool inarea(int x, int y);

    int H, W;
    vector<vector<string>> brd;
    vector<Robot> beams, targets;
};

一番懸念していたBoard::load()の実装もそれほど複雑ではなく、各メンバ関数の具体的な実装は20分くらいで終わりました。

ちなみにこれは競プロの癖ですが、わざわざメンバ変数をprivateにはしません。普段のプログラミングでやったらアウトですが、どのみち使い捨てるコードなので。

壁のない方へ

そして乱択の実装に移るわけですが、この際少し動きを工夫しました。

隣接マスが壁であるような方向に移動すると、そのターンロボットは移動できません。これは基本的に不利です。というのも攻撃側なら全然Targetを探せないし、守備側ならBeamにとって格好の的になってしまうからです。

ということで、少しだけコードをイジって「1マス先が壁でない方向へ移動する」ようにして、乱択を提出しました。この時点で大体30分です。

しかしこのコード、

  • 二重for文で同じ変数名を使っている。
  • 遷移をミスって、forで無限ループが起きる2
  • 誤読して間違えたRobot idを出力する。
  • 壁を表す文字を勘違いする3

といった酷いミスを連発しており、これらの対処に20分ほど費やしてしまいました。

Beamの改良

次に目指したのは「攻撃時にBeamと同じ列か行にいるTargetを確実に潰す」という動きの実装です。

そのために、「指定された方向の先にTargetがいるか判定する」Robotのメンバ関数を実装しました。具体的には「壁にぶつかるまで移動して、途中でどれかのTargetの座標と一致したらtrueを返す」という簡単なものです。

これを提出したのが60分頃。しかしビジュアライザを見るとたまに上手く動いていないときがあり、その原因を探っていたらコンテスト終了になりました。

ちなみに以下が最後までバグらせていた箇所です。どこがバグの原因か分かりますか?

bool Robot::beam_search(const Board& board, int d) const {
    int nx = x, ny = y;
    while (board.inarea(nx, ny) && board.brd[nx][ny] != "*") {
        nx += dx[d];
        ny += dy[d];

        for (const Robot& target : board.targets) {
            if (target.x == nx && target.x == ny) {
                return true;
            }
        }
    }

    return false;
}



答えは8行目のtarget.x == nyです。コンテスト後、ここを修正したらちゃんとTargetを潰してくれました。

Beamを避ける

コンテスト中は時間がなかったので、Targetの動きは最後まで乱択でした。それでは物足りなかったので、コンテスト後に延長戦として「Beamと同じ行、列になるような箇所に移動しない」という動きも実装しました。

ちゃんと実装できて理想通りの動きをしてくれたのですが、なぜかこれがrandomに負けるという始末4。ゲームAIって難しいですね。

ちなみに最終的にクラスの構造は以下のように変わりました。

class Robot {
public:
    explicit Robot(int _x, int _y, int _id);

    // メンバ変数を出力
    void print();

    // 方向dの先にtargetがいればtargets内でのindexを返す
    // targetがいなければ-1を返す
    int beam_search(const Board& board, int d) const;

    // targetをdの方向へ動かしたときの動きをシミュレートする
    void target_move(const Board& board, int d);

    int x, y, id;
};

class Board {
public:
    explicit Board(int _H, int _W);

    // 標準入力からマップを読み込み、ロボットをふるい分け
    void load();

    // ロボットの情報を出力
    void print();

    // マス(x, y)がボード内にあるか
    bool inarea(int x, int y) const;

    // beamsの各Robotからビームを四方へ拡散させる
    void beam_diffusion();

    int H, W;
    vector<string> brd;
    vector<Robot> beams, targets;
};

やりたかったこと

今回はコードのテスト用に、運営側で「random」「cat」という2つの対戦用AIを用意していただきました。しかしむちゃくちゃ強いcatはおろか、上に述べた通りrandomにも安定して勝てるAIは作れませんでした。

さらに強くするためにやりたいこととしては、

  • 数手掛けてTargetを潰すようなムーブを探索する。
  • Targetを極力スペースが広い、かつBeamから遠い箇所に逃がす。

などが考えられますが、上手い実装が思い浮かびません。

あるいは機械学習ゲーム理論を学べばもっと強いのが作れるかも知れませんが、当然ながら知識及ばず。なんとかしてcatに勝ちたいですね。

感想

1つ言わせてもらうとすれば、75分は非常に短いです。いっそのこと1週間ほど用意して、当日に複数人のAIを戦わせるのもありかもしれません(それはライブプログラミングではありませんが)。少なくとももっとハイレベルな戦いが見れると思います。

それとやはりゲームAI実装は難しいです。競プロ以上に複雑な実装もこなせるようになりたいですね。


本記事は以上になります。ここまで読んでいただきありがとうございました。

明日は(も)つばめ氏による「5文字 or 6文字でJSを書く話」です。JSはJavaScriptとして、5、6文字とは......?楽しみですね。


  1. HTTF2019Codefestival AI Challenge 2018等。

  2. for(int i = 0; i < 4; d = (d + 1) % 4)のように、ループ回数を制御するiをインクリメントし忘れました。

  3. 競プロで壁と言えば#なのですが、今回は*でした。思い込みダメ、絶対。

  4. 実はBeamを避ける機能を実装する前後で、randomに対する勝率が落ちました。おそらくTargetの動きが狭まったことが原因でしょう。