数理解析研究所講究録
第 1744 巻 2011 年 56-59

56

2010 年度冬の LA シンポジウム [11]確率的評価値をもつゲーム木における最善手探索
奥山 洋平 *

瀧本 英二 \dag er

畑埜 晃平 \dag er

竹田 正幸 \dag er

2011 年 2 月 2 日

1

ンテカルロシミュレーションにおけるプレイアウト

はじめに数を小さくすることができる．
近年，モンテカルロシミュレーションを囲碁に取特にゲーム木上での探索手法 UCT アルゴリズム

り入れることにより，コンピュータ囲碁が急速に強[3] は，葉ごとの勝率の推定精度を動的に調整できるくなっている．中でも特に $MoGo[2]$ は，一般的な囲という性質を持つ．したがって，葉の勝率に差があ

碁の 19 $\cross 19$ という盤面のサイズより小さいる場合，より少ないプレイアウト数でミニマックス$9\cross$9 の盤面であるが，プロに勝てるほどである．これ$MoGo$ をはじめ，近年のモ解を近似できる．実際，

らモンテカルロシミュレーションに基づく手法は，与ンテカルロ囲碁の多くに UCT が採用されている．しえられた局面における自プレイヤーの「勝率」をモかし，UCT の性能の解析において， 近似の概念を$\epsilon$

ンテカルロシミュレーションにより推定し，得られ用いた厳密な定式化がされておらず，また，理論保た推定値をその局面の評価値とする．ここで，「勝率」 証の部分で強い仮定を用いており，何回プレイアウとは，その局面から両プレイヤーがランダムに手を トすれば求めたい解に収束するのか解析がされてい打ち続けたときに，自プレイヤーの勝ち局面に至るない．

確率である．また，現局面から終局面に至る両プレ

そこで本研究では，問題を簡単にするために 2 手イヤーのランダムな一連の試行をプレイアウトと呼先まで展開した部分ゲーム木において，最適解であぶ．モンテカルロシミュレーションにおいては，プるミニマックス解の近似解を求めるというオフライ

レイアウトを何回も繰り返すことにより，勝率を推ン問題を設定する．その問題に対し，強い仮定を用い定するのである．

ない RUCT アルゴリズム (Robust UCT Algorithm)

実際の対戦においては，現局面を根として数手先まで展開したゲーム木 (部分ゲーム木) 上でミニマックス探索を行い，ミニマックスの意味で最も評価値の高い次局面を次の 1 手として選択する．このとき選ばれた手は，局面の評価値として勝率そのものをを提案し，プレイアウト数の評価を行う．結果として，素朴な方法では，$\tilde{O}(_{\tau_{\epsilon}^{1}})$のプレイアウト数は誤差のパラメータ) かかるのに対し，RUCT では，葉の勝率の差が大きい場合に，$\tilde{O}(\frac{1}{\epsilon})$のプレイアウト数で済むことを示す．

用いた場合のミニマックス解の良い近似解となって欲しい．これを実現する素朴な方法は，部分ゲーム

木のすべての葉における勝率を十分高い精度で推定2問題設定した後，ミニマックス探索を行うことである．しかし，葉の勝率に著しい差がある場合には，いくつかの葉における勝率の推定精度は低くてもよいため，モ
九州大学大学院システム情報科学府\dagger 九州大学大学院システム情報科学研究院$*$$(\epsilon$

本節では，本研究の問題設定を行う．

57
2.1

ゲーム木となる値を求め，$\{\hat{\mu}_{i,j}\}$$\hat{\mu}_{i,j}$に基づくミニマックス解$i^{*}=$ argを最善手として出力max
本研究では 2 手先まで展開した部分ゲーム木を，$P_{i^{*=}}1,$ $P_{j}=0(j\neq i^{*})$することである．(厳密には，葉にオラクルがついた深さ 2 のゲーム木 として次$i \in[K]\min j\in[K_{i}]\hat{\mu}i,j$$T$となる分布 $P=$ $(P_{I}, ..., P_{K})$ を出力する．) よって，のようにモデル化する．ゲーム木の根は $K$ 個の子ノードをもち，それぞれ 1, 2, ..., $K$ のラベルを付ける．ノード $i\in[K]$ には葉がぞれ $(i, 1),$ $(i, 2),$$(i, j),$$(i, K_{i})$$\ldots,$$i\in[K],j\in[K_{i}]$が存在する．オラクル$K_{i}$のオラクル呼び出し

で，ゲーム木の最善手探索問題を解くことができる．

個ついており，それただし，size $(T)$ は，ゲーム木の葉の数を表す．のラベルを付ける．各葉には対応するオラクル$O_{i,J}$$m \cross size(T)=\tilde{O}(\frac{size(\mathcal{T})}{\epsilon^{2}})$$O_{i,j}$は，(引数なしで) 呼び出されると，アルゴリズムにとっては未知の期待値

3

提案手法

$\mu_{i,j}$のベルヌーイ分布にしたがって 0 または 1 の報酬をゲーム木の最善手探索問題をゲーム木の下段 (ノーは元のゲーム木において，2 手ド $i\in[K])$ と上段 (ゲーム木の根) に分けて考える．

返す．オラクル$O_{i,g}$先のノード $(i, j)$ を起点とするモンテカルロシミュレーションのプレイアウトに対応し，期待値$\mu_{i,j}$は3.1

ノード $(i$ , のの勝率を表す．

ゲーム木の下段

ゲーム木の下段では，各ノード $i\in[K]$ において，2.2

葉のオラクルゲーム木の最善手探索問題$O_{i,1},$$\ldots,$の中から報酬の期待値$O_{i,K_{?}}$が最小のオラクルと似た振る舞いをする，仮想的なオラクルを作る問題を考える．この問題は，多腕バゲーム木の最善手探索問題を以下のように定義すンディット問題に帰着でき，多腕バンディット問題をる．

解く UCB アルゴリズム [1] を利用することができ

定義 2.1(ゲーム木の最善手探索問題). ゲーム木る．このようにして構成したノードの最善手探索問題とは，入力として葉にオラクルをもったゲーム木 $T$ と，誤差に関するパラメータ$\epsilon(>0)$

ノード/レ

$\{$

1,$\ldots,$$K\}$

上の分布 $P=(P_{1},$$P$$\ldots,$に返される値をを出力の疑似オラク

UCB-oracle(i) を Algorithm 1 に示す．

定理 3.1. UCB-oracle(i) をが与えられるとき，以下の不等式を満たす$i$$X_{8}$$s$

回目に呼び出したときとする．このとき，することである．
$E(X_{s})\in[\mu_{i},$ $\mu_{i}+(1+o(1))4\sqrt{\frac{2K_{i}\ln s}{s}}]$$\max_{i\in[K]}\min_{j\in[K_{i}]}\mu_{i,j}-E[\sum_{i=1}^{K}\{P_{i}\min_{j\in[K_{i}]}\mu_{i,j}\}]\leq\epsilon$

が成り立っ．ただし，$\mu_{i}=\min_{j\in[K_{i}]\mu_{i,j}}$定理 3.1 より，ノード

ここで，P はオラクルの返す値によって決まる確率変数であり，不等式中の期待値はその確率空間の下 oracle$|$$(\dot{v})$が$s$$i$回目に返す値.の疑似オラクル UCB$X_{s}$は，で平均をとったものである．
$\max_{i\in[K]}\min_{j\in[K_{i}]}\mu_{i,j}$$\mu_{i}\leq\hat{\mu}_{i,s}\leq\mu_{i}+O(\sqrt{\frac{K_{i}\ln s}{s}})$をゲーム木 $T$ のミニマッ

クス値と呼び， と表す．また，ミニマックス値を与えるノード $i=$ arg max $i \in[K]\min j\in[K_{i}]\mu i,j$ をミニ$\mu^{*}$$\hat{\mu}_{i,s}$のベルヌーイ分布に従うことがより，UCB-oracle(i) は十分大きい回数呼び出された後は，報酬の期待値が分かる．

$\hat{\mu}_{is}arrow\mu_{i}(sarrow\infty)$

マックス解と呼ぶ．

この問題を解く素朴な方法は，各オラクル$\tilde{O}(\tau_{\in}^{1})$を満たす期待値回ずっ呼び出すことにより，$\mu_{i,j}$$O_{i,j}$

をの $O(\epsilon)$ 近似

最小のオラク$\uparrow_{F}^{m}$$0$$\ovalbox{\tt\small REJECT}$

レ $O_{i,j}( \mu_{i},j=\mu_{i}=\min_{j}\in[K_{i}]\mu_{i,j})$倣するとみなすことができる．

を

58
張版 UCB の提案と解析を行う．拡張版の Hoeffding$\frac{A1gorithm1UCB-orac1e(i)}{z_{j}=0,s_{j}=0,t=0(j=1,2,\ldots,K_{i})}$: オラクル$Zj$$O_{i,j}$が返した報酬の和を表す静的: オラクル

$O_{i,j}$を選んだ回数を表す静的変数:UCB-oracle(i) が呼び出された回数を表す静$t$

込んだ拡張版 UCB である RUCT(Robust UCT) アルゴリズムを Algorithm2 に示す．

変数 1
$Sj$の不等式を付録の定理 A.1 に，UCB-oracle を組み的変数

gllori{tbhm: 初期化–
Al$s_{i}=02RUCT(i=1,2, \ldots, K)$$z_{i}=0,$$\ovalbox{\tt\small REJECT}$$z_{i}$

if ョ$j,$$s_{j}=0$

then$s_{i}$$s_{j}=0$ を満たす $j$

を選ぶ

$i$

$T$

$j,$

$j= \arg\min_{j=l,2,\ldots,K_{i}}(s_{j^{-\cap\frac{2\ln t}{s_{j}}}}\lrcorner^{z}$$Sj=0$ を満たす

end if$O_{i,j}$を呼び出し，報酬$r$を選ぶを得る$z_{j}arrow z_{j}+r$

end if
UCB-oracle(j) を呼び出し，報酬$s_{j}arrow s_{j}+1$$tarrow t+1$

1, 2,$i$else

オラクル$r$を得る$z_{j}arrow z_{j}+r$$K_{i}\}$$\ldots,$

上の確率分布$\frac{s_{K_{i}}}{t})$$(_{t}\lrcorner^{S},$$\ldots,$に従いオ

ラクル $j$ を選ぶ

オラクル

return32$i$for $t=1$ to do
if ョ $s_{j}=0$ thenelse$\{$: ノード での累積報酬: ノード を選んだ回数$O_{i,j}$を呼び出し，報酬$r$$s_{j}arrow s_{j}+1$

end forを得る$P=(\frac{s_{1}}{T}, \ldots, \underline{s}_{T}\kappa)$$r$

return $P=(P_{1}, \ldots, P_{K})$

ゲーム木の上段

RUCT において，一回の UCB-oracle の呼び出し$K$ 個の疑似オラクル UCBゲーム木の上段では，に対し，葉のオラクル$\{O_{i,j}\}$のどれかがちょうど一$T$ がオラクル呼び出し回数を回呼び出されるので，oracle(1),...,UCB-oracle $(K)$ の中から，真の期待値がが最大となるノード を探す問題を考える．ここ表す．

で，UCB 用いてこの問題を解くことを考える．UCB定理 3.2. $\mu_{i}=\min_{J\in[K_{i}]^{\mu_{i,j}}},$ $\mu^{*}=\max_{i\in[K]}\mu_{i}$ と$i$$\mu_{i}$の解析には Hoeffding の不等式を用いているが，この不等式は，報酬の系列が独立で，報酬の期待値はすると，RUCT の返す分布 $P=(P_{1}, \ldots, P_{K})$ は以下の不等式を満たす．

固定の場合に用いることができる．しかし，ゲーム木の下段で作った疑似オラクルが返す報酬の系列は$\mu^{*}-E[\sum_{i=1}^{K}P_{i}\mu_{i}]$独立ではなく，疑似オラクルの持つ報酬の期待値は呼び出しごとに変動する．したがって，UCB の解析結果をそのまま今回の問題の解析に用いることはで$\leq 2312[\sum_{i:\mu>\mu},$$\frac{K_{i}\ln T}{(\mu^{*}-\mu_{i})T}]+o(1)$きない．そこで，新たに報酬の系列が独立でなく，報酬の期待値が変動する場合に用いることができる拡張版の Hoeffding の不等式を提案する．これを用い定理 32 により，深さ 2 のゲーム木に対して，RUCT を用いたとき，オラクル呼び出し回数て，今回の問題のために UCB-oracle を組み込んだ拡$T= \tilde{O}(\frac{size(\mathcal{T})}{\epsilon\min_{i.\mu>\mu_{i}}(\mu^{*}-\mu_{i})})$

1 アルゴ) ズムが終了しても値を保持しておく変数$|$

59で最善手探索問題を解くことができる．また，$\epsilon\geq$$\mu^{*}-\mu_{i}$の場合，RUCT

は$\tilde{O}(\frac{size(\mathcal{T})}{\epsilon^{2}})$

オラクル呼び出し回数で最善手探索問題を解けることを示せる．

3.3

深さ$d$

参考文献

を越えないのゲーム木への拡張

深さ 2 のゲーム木と同様の考え方で，ゲーム木の葉から順に疑似オラクルを作っていく．今回の提案
した RUCT アルゴリズムは深さ 2 の部分ゲーム木に対するアルゴリズムであるので，深さが の場合は

[1] Peter Auer, Nicol\‘o Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmedbandit problem. Machine Leaming, Vol. 47, pp.
235-256, 2002.
[2] Sylvain Gelly, Yizao Wang, R\’emi Munos, andOlivier Teytaud. Modification of UCT withPatterns in Monte-Carlo Go. Research Report
RR-6062, INRIA, 2006.

$d$

アルゴリズム内のオラクルを選ぶ式を，疑似オラク
ルの報酬の期待値が最大のものを選ぶ場合は，最小のオラクルを選ぶ場合は，[3] Levente Kocsis and Csaba Szepesv\’ari. Bandit based monte-carlo planning. In ECML-06,2006.

付録A

拡張版 Hoeffding の不等式

定理 A.l (拡張版 Hoeffding の不等式).に変更する．ただし，size$(T_{j})$はノード $j$ を部分ゲー

ム木の根としたときの葉の数とする．
定理 3.3. 深さが$d$の部分ゲーム木に対して $RUCT$アルゴリズムを用いる．RUCT の返す分布 $P=$$(P_{1}, \ldots, P_{K})$4は以下の不等式を満たす．

を $\{0,1\}$ を値に持つ$T$$X_{1},$$\ldots,$$X_{T}$個の確率変数とする．ただに対し，実数 $\mu_{L,t}<\mu_{H,t}$

し，任意の 1が存在して，任意の $a_{1}\ldots a_{t-1}\in\{0,1\}^{t-1}$ に対し，$\leq t\leq T$$\mu_{L,t}\leq E[X_{t}|X_{1}=a_{1}, \ldots, X_{t-1}=a_{t-1}]\leq\mu H,t$を満たす．このとき，すべての $c>0$ に対して以下の不等式が成り立っ．

$| \mu^{*}-E[\sum_{i=1}^{K}P_{i}\mu_{i}]|\leq$$P[\frac{1}{T}\sum_{t=1}^{T}X_{t}>\frac{1}{T}\sum_{t=1}^{T}\mu_{H,t}+c]$$\leq$$\exp(-2c^{2}T)$$\frac{8(16^{d}-1)^{2}}{225}[\sum_{i:|\mu^{*}-\mu_{i}|>0}\frac{size(T_{i})\ln T}{|\mu^{*}-\mu_{i}|T}]+o(1)$$P[\frac{1}{T}\sum_{t=1}^{T}X_{t}<\frac{1}{T}\sum_{t=1}^{T}\mu_{L,t}-c]$$\leq$$\exp(-2c^{2}T)$

今後の課題
UCB アルゴリズムの評価の改善により，RUCT ア

ルゴリズムの評価も改善が期待できる．これにより，オラクルの呼び出し回数をさらに減らすことができると考えられる．