終点枕崎

プログラミングとvimと音楽と地理

モンテカルロ木探索でBlokusのAIを作った

タイトルの通りです。モンテカルロ木探索と呼ばれるアルゴリズムの習作として、blokusというボードゲームの対戦AIを作りました。

Blokus

まずはBlokusについてご説明。4人のプレイヤーはそれぞれ自分の色(赤・黄・青・緑)のピースを持ち駒として持ち、4人で順番に持ち駒を20x20のマス目状のボードの上に配置していく。ピースは正方形が1〜5個繋がったもので、全部で21個ある。(余談だが、このように正方形を辺でつなげた図形をポリオミノといい、特にn個の正方形をつなげた図形をn-オミノと呼ぶ。blokusのピースはモノミオ、ドミノ、トリオミノ、テトロミノ、ペントミノからなる。)

ピースを置く際には、以下の制約に従う。

  • 初めの順番が来たら、ボードの角のマスを埋めるようにピースを置く。
  • それ以降は、自分のすでに置いたピースと角で接するように、そして辺で接しないようにピースを置いていく。色の違うピースは辺で接していても構わない。

f:id:uchifuji:20170914235542j:plainf:id:uchifuji:20170914235546j:plain

全員がピースを置けなくなったらゲーム終了。

f:id:uchifuji:20170914235548j:plain

勝ち負けの計算方法は2通りあって、単純に残りの手持ちピースのマス目の総数が少ない人が勝者という方法と、前者に付け加えて全部置けた時にボーナス得点が入るような方法があります。今回は前者の方法を採用しました。

モンテカルロ木探索

囲碁などによく使われるゲーム木探索のアルゴリズムであるモンテカルロ木探索について軽く説明します。

ある程度までゲーム木を展開したら、残りは終局までランダムに手を打って(これをプレイアウトと呼ぶ)勝率を計算し、最善手を近似的に導き出す探索方法を原始モンテカルロ法と言います。この探索方法は囲碁と相性がいいです。理由は2つあって、

  • ランダムに打っても必ず終局を迎える。(将棋などはランダムに打っても終局に向かう確率はほぼ0に等しい)
  • 囲碁の評価関数を作るのは困難である。

評価関数とは、盤面が自分にとってどれくらい有利な状況であるかを評価する関数です。ミニマックス法などの有名な戦略アルゴリズムに必要となります。囲碁は他のゲームと違って優劣を決める決定的ものが全くありません。プロでさえ経験から生まれる第六感で判断するほどです。それに対し、原始モンテカルロ法は終局で勝ち負けを判断するだけでいいので、評価関数が不要です。

ただ当然この原始モンテカルロ法は弱いです。特にハメ技に弱い。多くの場合有利な状況になるが、相手がうまい手を打てば一気に不利になるといった状況で逆転されやすいのです。それを防ぐにはより深くゲーム木を展開できるようにする必要があります。

この欠点を解消したのがモンテカルロ木探索です。説明は下記のページに任せます。簡単に言えば、有望な手(=暫定の勝率が高い手)を優先的に深読みしつつ、まだ未探索の手もバランスよく探索する仕組みになっています。時間をかければいつか最善手に収束するらしいです。今回は、ゲーム木を展開する優先度としてUCB値を利用したUCTアルゴリズムを使うことにします。

参考にしたページ:
http://repository.essex.ac.uk/4117/1/MCTS-Survey.pdf
http://ustimaw.hatenablog.com/entry/2014/12/14/081423
モンテカルロ木探索についての文献をいくつか見ましたが、文献によって言ってることが違って非常に困りました。最終的に上の2つを参考に実装することにしました。)

モンテカルロ木探索のBlokusへの適応

Blokus囲碁は共通点が多いです。

  • 陣取りゲームである。
  • ランダムに手を打って終局に向かう。
  • 評価関数を作るのが難しい。
  • 将棋のように「勝ち筋」を見極めるよりかは、大局的な判断が重要になる。

なのでBlokusにもモンテカルロ木探索が有効なのではないかと考えました。

問題点は、Blokusが4人対戦ゲームであることです。これは、1位を1.0勝、2位を0.75勝、3位を0.5勝、4位を0.25勝として扱うことで対応しました。

実装

プログラミング言語C++を採用しました。

Blokusの対戦AIを実装するにあたって難点が一つあって、Blokusは合法手(ゲーム違反にならない手)を列挙するのが大変です。なぜかというと、まず合法手の数が多い。そして、2つ目は合法手を列挙する処理に工夫が必要なことです。

事前にテストした結果、一番最初のプレイヤーの合法手は232通り、ゲーム序盤〜中盤には合法手は800手を超えてくるようです。囲碁は盤面の大きさから高々400通り、将棋は最大593通りです。単純計算では、多いときは2手先を全て読むのに640000通り、3手先は512000000通りの盤面を展開しなければならないわけです。

囲碁の合法手の列挙は楽です。ルール違反のマスを除いて、空いているマスのほとんどの場所に駒が置けます。それに対して、Blokusの合法手の条件は些か複雑です。ピースの種類と向き、そしてピースを置く位置によってピースの置き方を区別するとおよそ15万通りあるため、ナイーブに実装すると時間がかかりすぎます。

なので、今回は合法手の列挙の処理の記述が作業の大部分でした。約0.1msで全手列挙できるまで削りました。ゲーム開始から終局までのプレイアウトは約6msです。時間があればもう少し高速化したいです。

ソースコードは後日一週間以内にアップします。

結果

AIの思考時間は15秒以内に絞りました。
単純に僕がクソ弱いのもありますが、僕が先手でも最下位になってしまうくらいには強かったです。2位は一度だけとれました。1位は…いつかとりたいです。

f:id:uchifuji:20170915012122p:plainf:id:uchifuji:20170915012118p:plain(赤が僕)

ただゲーム序盤はやはり弱いです。合法手が多いからでしょうか。UCB値の定数の設定にもよりますが、どうやら最大で3手先くらいまでしかゲーム木を展開していないようです。

なので今後の課題は、序盤の定石を学習させることでしょうか。機械学習のこと全然わからないので、実現はまだまだ先になりそうです。