モンテカルロで二人ゲーム

この記事は、Competitive Programming Advent Calendar 2014 - PARTAKE 12/14のマラソン系の記事です。

 

 この記事では、二人ゲーム*1のAI向けのモンテカルロ法の使い方について説明します。

参考図書

松原 仁 編 美添一樹・山下 宏 著 「コンピュータ囲碁 モンテカルロ法の理論と実践」 共立出版

この記事よりこの本のほうがいいです。タイトルはコンピュータ囲碁ですがサブタイトルにもあるように、モンテカルロ法に関することも書かれている本です。

モンテカルロ法

モンテカルロ法とは、すごい簡単に言ってしまえば乱数を使ってシミュレーションする方法です。囲碁のAIによく使われていますが、将棋やオセロのようなゲームではあまり使われていません。モンテカルロ法はどちらかといえば評価関数が作りにくいゲーム向けの方法です。

○×ゲーム

ここから先、説明に○×ゲーム(三目並べ - Wikipedia)を使います(○×ゲームは状態数が非常に少なく、全探索してしまえば済むのでモンテカルロ法は不向きですが)。先攻が○、後攻が×を使うことにします。説明のために盤面のマスに番号をつけておきます。

f:id:ustimaw:20141212154315p:plain

Wikipediaにもあるとおり、このゲームは両者が最善を尽くすと引き分けになります。ここではルールを少し変え、引き分けも後攻の勝ちとします。

先攻が左上においてきた場面で後攻の手を考えることにします。次に後攻が置ける場所は、8マスあります(対称性を考えると考える必要のあるマスは減りますが、簡単のためここでは考えないことにします)。どのマスに置くかによって盤面は以下のように8通りに分岐します。

f:id:ustimaw:20141212104708p:plain

矢印の上の数字はマスの番号です。最初に先攻が左上に置いた盤面では、Wikipediaによると真ん中に置かなければ後攻は負けてしまうということです。置く事のできる8箇所について、それぞれ置いた後の盤面の状態を評価し、真ん中に置く場合の評価値をそれ以外の場所に置く場合の評価値よりも高くするのが目標です。

単純な方法

後攻が置いた後の各8通りの盤面について、ゲームが終わるまで先攻と後攻が取れる手を等確立で選ぶ場合での、後攻が勝つ確率を評価値にすることにします。モンテカルロ法ということで、計算で評価値を求めるのではなく、実際に勝負がつくまでランダムに手を進めてはその結果の勝敗を記録するということを繰り返すことによって評価値を求めます。勝負がつくまでランダムに手を進めていくことを、プレイアウトと呼びます。

この方法のプログラムでは、以下のような結果が得られました。

f:id:ustimaw:20141213111604p:plain

 

図の出力は、左の列から×を置いた場所、後攻が勝った数、試行回数、評価値(つまり、後攻が勝った数/試行回数)です。

一番評価値が高いのは5番に置いた場合なので、評価値が最高の手を選ぶというようにAIを組んでいれば正しく5番が選ばれることになります。この場合は偶然うまくいったといえますが、うまくいかないときのために話を続けます。

ゲーム木

以降の説明の前に簡単にゲーム木について触れます。先ほど、盤面が分岐するという説明のときに出した図のようなものがゲーム木の例になります。ゲーム木とは、ゲームの各状態を頂点、とることのできる手を辺とし、ある状態と、そこで着手した結果できた別の状態を結んだものです。

もうひとつ例となる図をあげておきます。これはある程度○×ゲームが進んだ盤面をあらわしています。

f:id:ustimaw:20141212161338p:plain

MCTS(モンテカルロ木探索)

MCTSの説明です。説明の前に動作のイメージを示しておくと以下のような感じです。

f:id:ustimaw:20141212151205g:plain

MCTSは以下の2つの特徴からなります。

1. 選ぶ手を工夫する
2. 節点を展開する

 

片方だけではほとんど効果はありません。

選ぶ手を工夫する

先ほどの例では最初の一手は試行回数がおおよそ平等になるように手を選んでいました。これを変更し、有効な手や、あまり選ばれていない手が多く選ばれるようにします。そのための方針として、以下のUCB1という基準を使ってその値の一番高いものを選ぶという方法があります。

f:id:ustimaw:20141212155615p:plain

各変数は、jは今評価しようとしている手の番号です。x_jは評価しようとしている手で何回中何回勝ったかの割合を、nは今評価しているものも含め、現在の盤面から取れる手全体の試行回数を、n_jには今評価しようとしている手の今までの試行回数を入れます。logの底はeです。Cはおおよそ0~1くらいの定数で、実際にプログラムで使うときは何種類か試して一番効果の出る値にします。

節点を展開する

節点を展開するとは、図にすれば以下のような感じです。

f:id:ustimaw:20141212163527p:plain

小さくて見にくいですが、5番を選んだ節点を展開した例になります。
節点とはゲーム木のノードのことで、各盤面に対応します。全ての節点を展開することは計算時間やメモリの制限上難しいので、ある程度の試行回数を経た節点のみを展開することにします。展開した節点においても、何回試行したか、何回勝ったかという情報を持っておきます。相手番の結果に対応する節点(つまり、自分の番の節点)では、何回試行したか、相手から見て何回勝ったかという情報を記録します。


シミュレーションの回数が増えてくると、木が段々成長していきます。

f:id:ustimaw:20141213111459p:plain

この図中の丸は節点を表しています。黒丸と白丸があるのは1手ごとに手番が入れ替わっていることをあらわしています。

2つをあわせる

先ほどの方法では2手目の後手番以降は手の選び方は完全にランダムになっています。節点を展開することで、展開された手はランダムに選ばれるのではなく、偏った選び方をすることができるようになります。UCBなどを使うことで、シミュレーションの中でランダムに選ばれた手よりも現実的な手が選ばれるようになります。

先ほどあげた図をもう一度示しておきます。

f:id:ustimaw:20141212151205g:plain

この図は先手番が次の手を評価しているところを示しています。この図中の丸の中にある分数のようなものは、分母がその節点の試行回数、分子が勝った回数を表しています。ただし、後手番の節点では先手から見ての勝利数が、先手番の節点では後手番から見ての勝利数が記録されています。これは二人ゲームのため、先手が着手した結果の盤面が後手番に、後手が着手した結果の盤面が先手番になるからです。

 

先ほどのプログラムをMCTSを使うように改良したものの結果は以下のようになります。

f:id:ustimaw:20141213111643p:plain

UCBの定数Cの値や節点を展開する閾値は適当です(C=1、節点は6回目に展開)。試行回数がおよそ10分の1になっていますが、5番に置いたときの評価値が上がって、次点との評価値の差が大きくなりました。

プレイアウトの改良

モンテカルロ法を使うAIをつくるときに一番労力を注がれるのが、プレイアウトの改良の部分と言われています(多分)。

明らかに良さそうな手は選ばれる可能性が高く、明らかに悪そうな手は選ばれる可能性は低いといえます。節点を展開していない部分であっても、ゲームの特性から手の良し悪しが分かるならば、プレイアウトの際に手をランダムに選ぶのではなく、良い手に偏った選び方をしたり手を決めうちにすることでシミュレーションの精度がよくなることがあります。

感想

思った以上に人に説明するの難しかったです。誰かもっとわかりやすく書いてください。

明日の担当は hasi_t さんと ichyo さんです。

*1:タイトルを含め「二人ゲーム」と書いてあるところは、「二人零和有限確定完全情報ゲーム」のことを指すものとします。