UCTを利用したモンテカルロ法とミスに着目したゲームの特性

コンピュータ将棋協会のブログで知ったのですが、ゲームプログラミングの学会GPW2007の話題の中心はボナンザタイプの機械学習による評価関数のデザインと、UCTらしい。

機械学習については、以前調べて、大体のどんな感じのものかおぼろげに理解したけれど、UCTってなんなのか、まったく言葉すら知らなかったのでちょっと調べてみた。

ついでにプログラムを組んでみた。

UCTって何か？

これは、モンテカルロ囲碁で最近流行の手法で、UCB1を使ってゲームの木のノードを下ってからモンテカルロシミュレーションする手法のことらしい。

UCB1ってなにか？

ぶっちゃた言い方をすると、パチンコの台選びを想像するのが理解しやすいかも。
釘が読めない前提でパチンコで台を選ぶとき、それぞれの台を試し打ちして、スタートチャッカーへの入賞率が高い台（いわゆる良く回る台）を探す。

そのとき、「そこそこ回るパチンコ台を見つけたけど、まだもっと回る台があるかもしれない。まだ試してない台を打ってみるか？」とか、「この台は異常に良く回るけどまだ試し打ちの回数が少ないので回転ムラで回ってるだけかもしれない、さっき打ったあっちの台はたくさん試し打ちしてそこそこ良く回ったのであっちのほうが本当は良い台なのかも？」とか案外迷うことがある。すべての台を十分な回数試し打ち出来れば良いけれど、そんなことしていたらけっこう金を損してしまう。UCB1ってのはそこらへんの立ち回りをゲーム理論的に数式化したものと思っていいらしい。

UCTやUCB1については以下の日本語訳してくれた論文を読むのがわかりやすそう。
http://www.geocities.jp/hideki_katoh/RR-6062-v3-jp.pdf

論文読んでみたけれど、数式の導出過程など理論的に深いところまで追求しないで、単純にアルゴリズムを使うだけなら割りと簡単っぽい感じ。

実際最強を目指して強くするためには色々工夫が必要だろうけれど、そこそこ遊べればで良いのであれば、単純に、
１）この局面から次にさせる手をリストアップする
２）ゲームの終了を認識して勝ち負けを判定する。

この２つさえ書けばあとは、あとは、定型的な処理でいろんなゲームの思考ＡＩが出来るみたい。

ほんとにこんなお手軽な方法で強くなるのか！？と思って試しに作ってみた。

選んだゲームは私の地方では「753」って呼んでいた線消しゲーム。

紙に以下のような３本，５本，７本の線を描いて2人で交互に線を消して行き、最後に残った線を消したほうが負け。

こんな風に連続した線を消すのはありだけれど、

このように、消した線をまたいだり、斜めに消すのはダメというルール。

ソースコードはこちらからどうぞ。
(Ｃに限りなく近いC++。Visual Studio2005でコンパイルして動作確認している)
(ゲームの局面数が少ないんで考えうる局面は全部配列に持ってるし、ノードの下り方なども、もっと工夫がいると思う。)

初手の最善手を100万回の試験数で試してみた結果が以下。

どうやら、このゲームは先手必勝で、初手は5本の線の端１本を消すことがベストの模様。

しかし、これ、あまり、このＵＣＴの効用を示すのには良くなかった。
というのは、７５３ゲームの場合、１００万回のシミュレートってのは結局のところ、全数探索をしてしまっていてることになっているから。

これが、全数探索するまでには至らない0万回程度のシミュレート結果だと、どの選択でもほぼ５割に近い数字になってしまって差がつかなかった。

どうしてこうなってしまうのか、ちょっと考えてみた。

＊　＊　＊　＊　＊

これは、７５３というゲームの特性がＵＣＴに向いていないために起きてしまうのだろう。
ここでいうゲームの特性とは、ミスと勝敗の関係についてのこと。
ゲームにはミスが付き物で、ミスが勝敗を分ける要因になるのだけど、実はこれには3つのタイプがあると私は思う。

タイプＡ）ミスした回数が多いほうが負けるゲーム
ゲーム中に着実にポイントを稼いでいったほうが勝つタイプのゲーム。
例：囲碁、はさみ将棋、タクティカルウォーゲーム

タイプＢ）最初にミスしたほうが負けるゲーム
タイプＢ－１）
最初にリードしたほうが小さなミスをしても逆転されにくいタイプ
タイプＢ－２）
最初に築いたアドバンテージにより、その後お互いが無難に
行動していてもドンドン差がついていってしまうタイプ
例：　競艇などのレース（Ｂ－１）、ポーカーの大会（Ｂ－２）、格差社会

タイプＣ）最後にミスしたほうが負けるゲーム
いくら途中まで有利に局面を進めていても一度の小さなミスで形勢が逆転してしまうタイプ。
例：７５３ゲーム、石取りゲーム、将棋（プロレベル）

もちろん、完全に３つに区別できるわけではない。
はさみ将棋などはタイプＢの要素もあるし、素人レベルの将棋は、ＡＢＣのどれにも当てはまる。
マージャンは基本的にはタイプＡだけれど、タイプＢの要素も含んでいる。
ただ、７５３は典型的なタイプＣ。

そして、ＵＣＴは以下のように、ゲームの木を途中まではまじめに下っていくが、そこから先はモンテカルロでシミュレートする。（図は先ほど紹介した論文から引用）

だから、途中で築いた形勢有利な局面が、モンテカルロのランダムさで無意味になってしまうので、タイプＣのゲームとはすこぶる相性が悪いということなのだろう。

ほかにもUCT+モンテカルロとの相性に関連するゲームの特性があると思う。

合うタイプは以下のようなタイプではないかな。

１）　ランダムに打っていても一定の手数でゲームの決着が付くタイプ
○囲碁、オセロ　×将棋、マージャン

２）　途中の局面での静的な評価関数を作るのが困難なタイプ
○囲碁、△マージャン、オセロ、将棋

３）　（仮に前方枝狩りをしたとしても）着手数が多くて探索が困難なタイプ
○囲碁　△将棋　×マージャン、オセロ

こう見てみると、囲碁は実に相性が良い感じがするけれど、将棋は相性が悪いのではないかと思う。
マージャンの場合は、前方枝狩りを入れれば使えないことは無いけれど、枝狩り前提ならそもそも着手数が少ないのと、マージャンでは、許される思考時間が短いため、どちらかといえば相性が悪い部類になるだろうと思う。

追記：
似て非なる将棋と囲碁のゲームの特性の違いについては、毎日コミュニケーションの週間将棋のコラムが結構面白いです。おすすめ。