15B / 19M の @nari です。

2019年12月21日(土) と 2019年12月22日(日) に開催された SECCON CTF 2019 International に、traP からチーム NaruseJunとして出て 優勝 しました 🎉

この記事は、SECCON CTF 2019 International の問題伍(5)の writeup です。

参加記は こちら です。

この記事の内容

SECCON 2019 International の伍の writeup として、出題された問題と実際に使った解法を紹介します。

また、解法に使用したモンテカルロ木探索 (Monte Carlo Tree Search; MCTS) の解説にも取り組んでいます。

問題概要

いくつかの Python ファイル^[1]と、サーバの IP アドレスとユーザ名とパスワードが与えられます。
各チームが用意されたサーバ内でゲーム AI サーバを起動すると、運営のシステムがその AI サーバにアクセスして参加チーム間で対戦が行われます。
対戦によって Elo Rating 値^[2]が変動し、5 分ごとにレートが一番高かったチームに 20pts が加算されます。

図で書くと次のようになっています。

client.py は内部で snake.py で定義されるゲームを、各サーバの server.py に接続して実行される AI を元に動かしていきます。
各チームはこの server.py 以下をいじることで AI を変更することが出来ます。
デフォルトでは Python プログラムとして AI が書かれており、それを server.py から呼び出すことで AI が実装されています。

ゲーム概要

ゲームは二人対戦版スネークゲームと形容できるもので、おおよそ次のようなルールです。

• 盤面は高さ H 幅 W のグリッドマップで表される。
  • サンプルでは H=10, W=11
• 盤面の各マスは次の 5 つの状態のどれかである。
  • 空: 蛇が通ることが出来る。なにもない。上図の青色。
  • 林檎: 蛇が通ることが出来る。通りかかると林檎を食べることが出来る。上図の肌色。
  • 穴: 蛇が通ることが出来ない。上図の黒色。
  • 胴体: 蛇が通ることが出来ない。蛇の胴体が存在する。上図の薄い赤/緑色。
  • 頭: 蛇が通ることが出来ない。蛇の頭が存在する。上図の濃い赤/緑色。
• 盤面には林檎が常に一定数存在する。
  • 蛇が林檎を食べた時に、空のマスのどれか 1 つが新しく林檎マスになる。
  • サンプルでは林檎は常に 10 個存在するように設定されている。
• プレイヤーは 2 人であり、それぞれのコントロールする蛇が盤面上に存在する。
• 初期状態での蛇の長さは 1 である。
  • 初期盤面には胴体マスが存在せず、頭マスが 1 マスずつ存在する。
• プレイヤーは交互にターンが回ってくる。
  • 各プレイヤーのターン数は限られている。
  • サンプルでは各々が 40 ターン (合計 80 ターン) するとゲームが終了する。
• 各プレイヤーは 1 ターンで蛇を 1 マス進める必要がある。
  • プレイヤーがコントロールしている蛇の頭を上下左右のいずれかに動かす。
  • 胴体は蛇の頭が通った道をなぞるように動く。
• 蛇の頭が林檎マスと重なった時、蛇は林檎を食べ、蛇の長さが 1 伸びる。
  • 胴体マスが 1 マス増える。
• 蛇が通れないマスに移動しようとすると蛇は死亡し、相手プレイヤーが勝利する。
• 両者の蛇が死なずに全ターンが終了した場合、蛇の長さで勝敗を決める。
  • 蛇の長さが同じ場合は引き分けで終了する。

いくつかパラメータ (盤面の幅、高さ、林檎の数、ターン数) が不定ですが、これらに制約があったかどうかは読み取れませんでした。基本的にはこれらは可変としてプログラムを書いたほうが良かったのだと思われます。

AI 概要

詳細は割愛しますが、snake.py の 155 行目と 156 行目に次のような記述があります。

_input = self.players[k]["module"].main(
	{ "map": self.draw_map(False), "snakes": snakes, "turn": my_turn })

ここで main に与えられている情報が、AI プログラムに渡されている情報です。
map は現在の盤面、snakes は各プレイヤーの蛇の形、turn はプレイヤーの残りターン数です。
なお、サンプルの AI プログラムでは turn の値は利用されていません。これは snake.py を読まないとわからない情報なので、ちゃんと読んだかどうかで使える情報に差が出たものと思われます。
また、プレイヤーの残りターン数はわかりますが、どちらが先行かという情報はわかりません。これは多分どうしようもないと思うので、AI プログラム側で工夫が必要になるものと考えられます。

AI プログラムはこれらの情報から、次にどの方向に蛇を動かすかを、上下右左を 0123 に対応させて、整数 1 つを返す関数として実装します。

なお、client.py から server.py への接続部分で、タイムアウトまでの時間が 1.5 秒に設定されているため、AI プログラムが使える計算時間もおよそ 1.5 秒となります。

モンテカルロ木探索

私が最終的に実装した AI アルゴリズムはモンテカルロ木探索 (Monte Carlo Tree Search; MCTS) と呼ばれるもので、二人対戦ゲームにおいて 盤面の評価関数無しに 強力な AI を構成出来るものです。有名なものとして囲碁の AI である Alpha Go などが MCTS をベースとしています。

もちろん、今回のような規模が小さめのゲームにおいては、盤面の評価関数を設計できればより強い AI を作れると思いますが、たった 2 日未満で実質 1 人では調べられることが少ないため、ドメイン知識が少なくてもなんとかなる MCTS に頼ることにしました。

MCTS は簡単に言えば動的なゲーム木探索で、有望な選択肢は深く探索を行うことで、その選択肢が本当に価値のあるものなのかを探る、ということを何度も繰り返すアルゴリズムです。ただし一番有望なものだけを調べると、一回も調べてない選択肢を調べる動機が無くなってしまうので、あまり調べてない選択肢も調べるように適切に仕向けます。また「有望さ」はその選択肢を取った時の勝率なのですが、これを評価するためにゲームをランダムに最後までプレイすることで擬似的な勝率を記録します(プレイアウト)。

例えば上図のように選択肢が A/B/C の 3 つあり、探索度と勝率がそれぞれ記録されていたとします。この時、選択肢 A/B の二者択一ならば A を選んだほうが良いため、A の方を探索します。一方で、選択肢 A/C の比較は単純には出来ません。というのは選択肢 C は探索度が低く、潜在的に高い勝率を持っているかもしれない からです。

また、各ノードについて一定の回数探索を行った場合、上図のようにそのノードを展開します。こうすることで 良い選択肢についてはより詳細に勝率を調べることが出来、正確な勝率推定に近づきます。

なお、ノードが無くなった先の勝率推定は、ランダムなプレイアウト で行います。これには完全にランダムにゲームをプレイする方法や、ある程度賢いヒューリスティックを実装する方法などがあります。

モンテカルロ木探索自体は比較的古くからある手法のため、より詳細な情報や実装方法については Wikipedia や Google 検索、適切な書籍が参考になると思います。

モンテカルロ木探索 - Wikipedia

今回のゲームへの適用

今回のゲームは二人対戦で、ターン数が決まっていて最後までプレイすれば勝敗もわかるので、MCTS を適用出来る条件は整っています。……と言いたいところですが、新しい林檎が発生するマスの選択に乱数が関わっています。これは不確定ゲームと呼ばれるジャンルになり、扱いが非常に面倒です。

これを解決する手法の一つに、本来の双方のプレイヤーの選択以外に、林檎がどこに発生するかを(ランダムに)定める選択肢が仮想的に存在する、とする方法があります。これは「自然手番 (Move by nature - Wikipedia)」と呼ばれる考え方で、乱数の関わる不確定ゲームを扱いやすい確定ゲームへと変換します。MCTS ならば適切に自然手番を挟み、自然手番では等確率で林檎が発生するマスが選ばれるとすれば表現できると思います。

上述の問題点として、自然手番で分岐する分メモリ効率が悪くなる上、学習すべきノード数が増えてしまうというものがあります。例えば林檎の発生する可能性のあるマスが 20 マスあるとすると、ゲーム木が 20 分岐し、しかもそれぞれが完全にランダムに選ばれて探索されるため、そのノードの学習に 20 倍のメモリ/探索回数が必要となります。

今回はこの問題を回避するため(または実装する気力が無かったため)、自然手番は排し、MCTS の 1 プレイ(探索)ごとに林檎の発生の仕方がランダムになる ような実装を行いました。つまり、プレイごとに林檎の配置が変わり、それに伴い蛇の長さも変わるので、プレイごとに取れる選択肢が変わる可能性があり、表現の正確性では劣ります。

またプレイアウトについては、より正確な確率評価のため、完全にランダムなプレイではなく、自滅しにくいヒューリスティックを導入したランダムなプレイを行っています。

実際にサーバに置いた AI の実装は以下の gist のとおりです。C++ 言語で実装しており、これを python から呼び出すことで実行していました。競技プログラミングをする際の手癖が大量で非常に読みづらいですが参考程度にお読みください。

https://gist.github.com/n-ari/7771d6450d1098d18e9e91ee77895767

コンテストでの結果

実際に問題伍で獲得したポイントの推移は以下の写真のとおりです。1 日目の深夜に上述 AI を実装し、2 日目開始後にサーバに置いたため、2 日目の開始 20 分頃から ポイントを独占 出来ていることが分かります。

また、2 日目の AI のレーティング値の推移は以下の図のとおりです。赤いラインが私の AI のレーティングです。レーティングのログを自動で取るようにしていなかったため中盤は曲線が粗いですが、レーティングが安定してからは 2000~2150 ぐらいのレートを取り続け、2 位の AI と 100~300 ほどのレーティング差をキープ していました。

まとめ

MCTS をマスターして最強のゲーム AI エンジニアになろう！

ところで、不確定ゲームや不完全情報ゲームでは不確定な要素が入るため、やはりそのままでは MCTS の適用が難しいという話があります(例: 麻雀 AI)。この辺りは今後調べられたら調べたいですね。