TSG live AI コンテストの内容と感想、盤面生成に関する妄想など

この記事はTSG Advent Calendar の11日目の記事として書かれました。昨日は、Misterさんの

misteer.hatenablog.com

でした。

live AI コンテストとは

簡単な対戦型のゲームに対する思考ルーチンを書いて戦わせるコンテストです。様子は、

www.youtube.com

で見られます。今回ぼくは、作問周りを担当しました。簡単にいうと、ゲームを考えて、適当にRustで実装したら、次の日にはhakatashi という人がJavaScriptのコードにして、ビジュアライザを書いていました。人間emscripten

お題について

お題そのものは 駒場祭2018 Live AI Contest からみることができると思います。以下引用をします

  • ゲームは、ターン制かつ攻撃側と防御側が存在する。
  • 各プレイヤーは同じ盤面から始めてそれぞれ攻撃側と防御側を一度ずつ行う。
  • 盤面の外周は壁で囲われているものとする。
  • 初期盤面では、大きさW x Hの盤面の上にはロボットといくつかの壁が配置されている。
  • ロボットの種類は、Beam, Targetであり、Beamが攻撃側、Targetが防御側に属する。
  • 各ターンごとに、プレイヤーは自分のロボットを選んで、四方の好きな方向を選び動かすことができる。
  • ロボットは、他のロボットか、壁に衝突するまで止まらずに真っ直ぐ進む。
  • ただし、Beamのロボットだけは、移動前に選んだ方向にビームを打ってから、移動をする。
  • このとき、ビームの先にTargetロボットが存在すればそのロボットは消滅する。
  • またこのビームの軌跡は盤面上に残りTargetロボットはこのBeamを超えることはできない。すなわち、Targetロボットにとっては、ビームの軌跡も壁になる。
  • また、ビーム自体は壁を突き破ることはない。
  • このビームによりすべてのTargetロボットが消滅したときに、ゲーム終了となり、攻守交代をして 同じ盤面で 再び対戦をする。
  • 300ターン後に決着がついていない場合、ゲームが終了する。
  • 自らが攻撃側の際にゲーム終了までにかかったターン数の合計がより少ないほうが勝ちである。

まぁつまり、やや雑な書き方をすれば「移動に制約がついたおいかけっこ」の攻撃側・防御側それぞれの思考ルーチンを書いて、「できるだけ速く相手を捕まえ、できるだけ相手から逃げろ」という話です。

例えば以下のような対戦がよくわかる例になります

https://raw.githubusercontent.com/moratorium08/static/master/output.gif

もととなったゲーム

実はこのロボットのうごき方は、「ハイパーロボット」 というゲームをもとにしています。もともとは、ロボットのうごきを組み合わせて「特定の場所」に移動させるゲームで、これもたのしいので、興味がある人は購入してみてください

簡単な思考ルーチン

このゲーム、ルールを見ると分かるように、攻撃側ロボットが動くと、盤面が狭まることを考えると、簡単に考えれば「攻撃側は相手の移動可能マスを狭めるように移動すればいい」ことが分かります。

すると、相手の動きはとりあえず無視して「相手の移動可能範囲」を狭めていくように探索していくとある程度勝つことができるようになります。この比較的雑な全探索があたりがコンテスト中は実装されればいいなあという気持ちがありましたが、冷静に考えて競技時間75分は短いという話があり、ややゲームが複雑過ぎた可能性があります。

また、逃げる側も「一手後に殺される数を最小化する」ようにするだけでも十分「ターン数を稼げる」ので、ここらへんを想定していました。

盤面生成

実はこのゲーム結構盤面生成が難しいです。というのも、「すべてのマスの上を攻撃側ロボットが通過可能」でなければ、安置ができてしまう可能性があるわけですが、これを保証できるようにするのは、比較的難しく、全探索できるような盤面サイズであれば攻撃側AIも全探索ができてしまうので面白くなく、また安置が無いと証明した盤面を自動で生成するのもそれなりに難しいと思われました。

例えば、雑にすべてのマスが連結(マス同士を一つ一つ移動していけばすべてのマスに移動できる)としても、例えば、初期盤面で

* *
.   
* *
x

のような盤面ができてしまうとxは.に到達ができません。

これを回避するには、次のような盤面を考え、それらをうまくつなぎ合わせるとおそらくランダムで適切な盤面の""良い近似""(雑な表現ですが)な盤面生成ができると考えられます。

  • 全探索可能な小さいサイズで、その盤面内のいくつかの点をハブとする。すなわち、ハブからその盤面内の任意の点へいけることを保証し、逆に盤面内の任意の点はハブにいけることを保証する
  • 上のルールで作った異なるサイズの盤面を組み合わせてより大きい盤面を作る。ただし、各盤面をつなぎあわせる際に盤面の少なくとも1つのハブの少なくとも一つのもう一方の盤面のそのハブとの接点となるマスが「壁」になっていない

実際のところ、盤面に傾向ができてしまうため、うまくやると、各盤面をHackして効率の良いルートが発見できるかもしれませんが、盤面の構成法を秘匿、すなわち、どれくらいのサイズのマス同士をどのように組み合わせたかを知らせなければ、Hackするのは難しいのではないかと雑に考えています。

まぁところで、盤面生成の問題を解決しなければいけないと思ったのが、コンテスト10時間前などであって、上を完全に実装するのがしんどかったため、コンテストの盤面生成に際しては、手動で目で見て「おそらく上を満たしていそうな盤面」を複数作って、それらを組み合わせて大きい盤面を作りました。悲しいですね。まぁ逆にいえば、もととなったハイパーロボットの盤面ってそうやって作られたんかな〜と妄想などをしたりしていました。

反省

おそらくライブですべての内容を完結させるには、ある程度「まとも」なゲームを考えると、普通にしんどいよなあという気持ちになりました。本質50~60行程度の思考ルーチンで、探索のしやすい構造をしたゲームないし、うまいヒューリスティクスが考えられそうなゲームで、完全に最良とは言えないが、多くの場合で最良になりそうなアルゴリズムを想定として持ったような状態で望むくらいがlive AIコンテスト的には正しい姿勢かもしれません。

感想

まぁしかし楽しかったです。気づいたらなんでも実装してくれる hakatashi さんと、catより強いAIを作ってさらに実況もしてくれたfiord くん、ありがとうございました。

明日(今日?)は、pizzacat83 さんの 「クラスSlackの話?」です。