UCT探索とα-β法

モンテカルロ木探索についての疑問

コンピュータ囲碁界では，モンテカルロ木探索という手法が流行っている．しかし，このアルゴリズムがどうも怪しいと思えてならない．怪しいというのは理論的な根拠が希薄ではないかという点だ．

モンテカルロ木探索のアルゴリズムで代表的なものが，UCT (UCB applied to Trees)アルゴリズムである．UCTは，Malti-Armed Bandit問題の解法のUCBアルゴリズムを元にしている．UCT，UCBの詳細は参考文献[1][2]か他のページを参照されたい．

UCTアルゴリズムは，UCBという値を頼りにゲーム木を伸ばしていって，最適な手を探す．私の疑問は，UCBを元に木を伸ばしてゆくということは，Multi-Armed Bandit問題を解いていることには相当しないのではないかという点だ．ゲーム木を伸ばしていったら，試行している間にスロットマシンが変わっていくではないか．それでは最もよいスロットマシンを選ぶことは出来ない．

UCTアルゴリズムの問題

UCTでは確かに，無限大回数の試行を行えば，正解が得られる．しかし，UCTは試行を繰り返すと一直線に正解の手順に漸近していくわけではない．シチョウから逃げるような相手が正しい手を打たないことを期待する誤った手順を選択し始めると，その手順が正解に近いとみなし，その手順を重点的に探索する．そして，しばらく探索を進めるうち，その手順を誤りと気づいて別の手順を探索する．誤った手順の探索に計算時間を取られて，正しかろう手順の探索に入る前に計算時間が切れてしまう恐れがある．こういうのはTrapなどと呼ばれているようだ．

UCTを用いたプログラムを強くするためには，Trapから早く抜け出すか，Trapにはまらないような工夫が必要となる．

前者では，例えばAccelerated UCT（参考文献[3]）というアルゴリズムが提案されている．Accelerated UCTは実験によって効果があることが確認されているようだが，これも理論的根拠が乏しいと思える．（私の勉強不足のためかもしれない．自信がないので要検討．）少なくとも通常のUCTは無限大回数の試行を繰り返してすべてのTrapから抜け出せれば，正解に漸近していくはずだが，Accelerated UCTはそうならない気がする．Trapから抜け出しやすいということは，正解の手順に漸近していくルートからも抜け出しやすいということだ．

後者のTrapにはまらないような工夫という点では，Playoutでの着手確率を工夫するという手段が取られている．シチョウから逃げるような手ははじめから打たないということだ．現状では，この方法を採用しているプログラムがほとんどのようである．Playoutを工夫し，人間っぽい打ち方を予め教えておくことで，棋力を上げていくというのが，現在の流れのようだ．

シチョウから逃げるような明らかな誤りは，予め除外するべきと思うが，それ以外にも周囲の石の配置などによって着手確率を変更するといった工夫がされている．これは探索する手にバイアスを加えているということに他ならない．人間と異なり総当りで探索ができるということがコンピュータの強みのはずなのに，探索する手にバイアスを加えるというのは，（非常に主観的だが）アルゴリズムとして綺麗くないという印象を受ける．そして，場合によっては意図せずに，正解を除外してしまう恐れがないかと思えるのだ．

別のモンテカルロ法のアルゴリズムを考えた

さて，モンテカルロ木探索を勉強して思ったのが，これは要するにPlayoutによって得られた勝率を評価関数としているだけなのではないかということだ．特に，有限の試行で探索を打ち切る場合にはだ．コンピュータ囲碁の研究において，もっとも難題とされているのが適切な評価関数の作成であった．モンテカルロ法が画期的だったのは，確率的に良さそうな局面を良い局面とみなすという点だ．

ならば最初から双方が勝率を最大化する手を選ぶということを考慮して，minimax戦略で手を選ぶ方がアルゴリズムとしてシンプルではないのだろうか．そして，それならば本来のMulti-Armed Bandit問題に帰着できる．そして，minimax法はα-β法を用いることで計算を削減できる．

以下にこの考えで探索を行うアルゴリズム（alpha-beta ucb法？)を提案する．私が考えたが，ちゃんと調査していないので，すでに考えた人はいるかも知れない．ただ，UCB法とα-β法をくっつけただけなので特段新しいわけではない．擬似コードの書き方がわからないので，大体で．合っているかあまり自信がない．ちゃんとしたコードを作りテストできたらまた更新する．

ゲーム木の作成();

//初期化
for each terminal node
     while 各nodeが「最小プレイアウト数」を行うまで
          playout(terminal node);

while 「最大プレイアウト数」を行うまで
    {
     //minimax戦略でucbが最も良さそうなterminal nodeを選ぶ
     alpha-beta-ucb(root node, -infty, infty);
     playout(the terminal node);
    }
//minimax戦略で勝率が最もよい手を選ぶ．普通のalpha-beta pruning.
alpha-beta(root node, -infty, infty); 

function alpha-beta-ucb(node, alpha, beta)
     if (node is terminal node)
     {
          DCB = そのノードの勝率 ー 信頼幅;
          UCB = そのノードの勝率 ＋ 信頼幅;
          return (DCB, UCB);
     }
     for each child of node
     {
          //順序！！
          (UCB, DCB) = (1.0, 1.0) - alpha-beta-ucb(child node, 1.0 - beta, 1.0 - alpha);
         if (DCB >= beta)
              return (DCB, UCB)
         if (UCB >= alpha)
         {
              alpha  = UCB;
              alpha' = DCB;
         }
     }
 
     return (alpha, alpha');

minimax戦略で手を決定するので，Upper Confidence Bound (UCB)だけでなく，Downer Confidence Bound (DCB)という値も導入する．UCBの付加項の符号をマイナスにしただけの値である．意味はUCBと同じで，値の下限を表している．UCBには，UCB1-TUNED（文献[2]）がよいと思われる．

UCTと異なるのは予めゲーム木を作成している点だ．この際，探索深さは一定である必要はない．例えば定石に従って打つような所は，定石が終わるまでゲーム木を伸ばしておくと有効とだろう．UCTのように動的にゲーム木を生成しても良いが，計算時間は限られていて，読める限度は最初から分かっているのだから，予め展開して計算したほうが良さそうに思える．

また，すべての合法手を探索すると，せいぜい２手先までしか読めない．考慮すべき手は囲碁の知識から絞るのが良いと思われる．枝刈りする手を明確にできるのが，UCTと比較して良いところだと考えている．

Playoutに関しては，これまで研究されているように人間っぽく打つように工夫すると良いだろう．Playoutで打たれるランダムな手のみでもある程度筋の良いところに打ってくれれば，計算された勝率の信頼性が向上する．得られた勝率が局面の優劣を正確に表せているかどうかが，モンテカルロ法が正解をあたえるかどうかを決定する．

パラメータは３つだ．

1. 読みの幅
2. 読みの深さ
3. 読みの正しさ

読みの幅とはゲーム木の分岐の数，考慮する着手候補の数だ．読みの深さとはゲーム木の深さ，何手先まで読むかということ．読みの正しさとはPlayoutの回数．ある程度試行しなければ最善の手は得られない．それは確率的に評価可能である．次善の手まで認めるのであれば，試行回数はそれほど多くなくてよいと思われる．限られた計算時間で最もよい結果を得られるパラメータの組み合わせを選択する必要がある．

最後に

ダラダラと書いてきたが，現在この考えのもとで囲碁プログラムを開発している．今さらUCTアルゴリズムでやっても追いつけるわけないので，別のアプローチを取ってみようと思うのである．現状はルール通り石を打てるのみにとどまっているが，UCTを採用するより良いという結果が得られたら，うれしいと思う次第である．

参考文献

[1] 松原仁　編，美添一樹・山下宏　著，『コンピュータ囲碁 ―モンテカルロ法の理論と実践―』，共立出版
[2] Auer et al., Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, 47, 235-256, 2002  　　←これはインターネットで入手可．こちら．
[3]Hashimoto et al. , Accelerated UCT and Its Application to Two-Player Games, ACG 2011, LNCS 7168, pp.1-12, 2012

以上，囲碁プログラム開発の記録にしようと思ったブログからの転載．囲碁プログラム開発はしばらく手を着けなかったら，興味を失ってしまった．また，気が向いたらちょこちょこっとやり始めるかも．