概要

国際学会で開催されるFPGA Design Contestに出場するためのゲームAIを研究，実装しています． 2013-2015年まではBlokus Duoと呼ばれるゲームがお題とされ，2015年からはTraxというゲームがコンテストのお題となっています． 基本的にASAPグループ全員が協力して実装を行います． 今回のお題であるTraxには最近話題のディープラーニングを用いて挑む予定です．

TRAX (2015 ~ )

ルール

Traxは二人対戦型のボードゲームで2種類のタイルを交互に置いていきます． そして先に自分の色でループまたはビクトリーラインを作ったプレイヤーの勝利となります． タイルを置く際の制約は次の通りです．

1. タイルを置くときは場にすでに置かれたタイルにつなげること
2. 接しているタイルの線の色がつながっていること(赤色と赤色，白色と白色)
3. 自分の色の線を伸ばしてもいいし、相手の色の線につなげてもいい

また連鎖ルールというものがあり，タイルを置いたあとに連鎖が適応されるかどうかの確認もしなくてはなりません． 詳しいルールはこちらで確認してください． デザインコンテストでは，Blokus Duoのときと同様に1秒以内で置く手を決めなくてはならないという 制約が追加されます． Traxは盤面サイズに制限がないため，ゲーム終盤になればなるほど計算量が増え，1秒以内に手を決めるのが難しくなります．

戦略

Blokus Duoに参加した経験から，盤面を評価する評価関数が非常に重要で，この評価関数のチューニング(様々なパラメタの調整)には 多大な時間を要する上に対象とするゲームに対して精通していなくてはならないということがわかりました． そこで我々は機会学習に着目し， Deep Neural NetworkとQ-学習を組み合わせたDeep Q-Network (DQN)を評価関数に採用しました． DQNを評価関数に用いたことで，学習を重ねていくにつれて評価関数の最適化が自動的に行われていきます． そしてこの評価関数を用いて，Blokus Duoのときと同様，ゲーム木をalpha-beta法で探索していき，2-3手先を読んでいきます． 下記に学習で用いるネットワーク構成を記します． また大会にはZedBoardを用いて出場する予定ですが，事前の学習はGPUを用いて行います． つまり，GPUで学習した学習データ・セットをZedBoard上のニューラルネットワークにロードして対戦を行う予定です．

BLOKUS DUO (2013 ~ 2015)

ルール

Blokus Duoは二人対戦型のボードゲームで21種類のタイルを交互に置いていきます． そしてタイルがこれ以上置けなくなった時に，より多くのマスを専有しているプレイヤーの勝利となります． タイルを置くときの制約は次の通りです．

1. すでに置いてある自分のピースと角をつなげて置く．
2. すでに置いてある自分のピースの辺と接してはならない．
3. 最初は図の○印の書いてあるマスを埋めるように置かなくてはならない．

これらに加えて，デザインコンテストでは1秒以内に置く手を決めなくてはならないという制約が追加されます． したがって1秒以内にどれだけ先を読むことができるかが勝敗の鍵を握ります．

戦略

ゲームの状態をゲーム木で表現し，ゲーム木を探索することでゲームの先読みを行っていきます． ゲーム木を探索する際にalpha-beta法を適応して，探索するノードの数を削減し高速化をしました． 盤面の評価方法を下図に記します． 盤面にある自分のタイルの角から距離5以内に存在するマスをインフルエンスエリアとして， このマスの合計値を評価値として用いました． インフルエンスエリアが多ければ多いほど，有利であると判定します． 逆に相手のタイルの角から距離5以内の範囲は相手のインフルエンスエリアとなります．