数理解析研究所講究録
第 1894 巻 2014 年 84-88

84

多人数不完全情報ゲームに対する局面評価値を用いたモンテカルロ法中央大学大学院理工学研究科漆畑雅士
Masashi Urushibata
Faculty of Science and Engineering, Chuo University

1

試合を始める．本研究でのルールは UEC 標準ルール [1] に則っている．

序論

近年，モンテカルロ法によりコンピュータ囲碁のは急激に強くなっている．囲碁は，将棋やチェスのようなボードゲームとは違い，合法手をランダム$AI$に打ち合っても終局させられるという点においてモンテカルロ法に都合がよかったためである．モンテ
カルロ法はさまざまなゲーム $AI$ の研究において注目

3

モンテカルロ法

3.1

大貧民におけるモンテカルロ法

以下で説明するアルゴリズムは「各候補手に対して，プレイアウトを何回も行 ’ 勝率の最も高い候補されている．その中で，多人数不完全情報ゲームであるトランプゲーム “大貧民” においても，プレイヤー手を選択する」というモンテカルロ法をもとにしてプログラムの強さを競う UEC コンピュータ大貧民いる．プレイアウトとは，乱数を用いてゲームを終局大会 (UECda) が毎年開催され，モンテカルロ法を用いたプレイヤープログラムが活躍している [1]. 本までプレイすることをいう．大貧民におけるモンテ研究では，大貧民を題材とし，モンテカルロ法に利用される UCBI に局面評価値を実装することによって，精度の向上を図るとともにより強いプログラムを構築することを目指す．

2$\iota\backslash$

カルロ法は以下のような手順で行う．

1. 合法手の列挙
自身が選択可能な合法手を列挙する．

2. プレイアウトを指定回数行う．
ここで，合法手の選択，手札の配布，乱数によるシミュレーション，報酬値のフイードバック

大貧民を行う．報酬値として，プレイアウトの結果が大貧民はトランプを用いて遊ぶゲームの一つで，多人数不完全情報ゲームに分類される．トランプを全参加者に配り，それぞれが手持ちのカードを順番に場に出して早く手札をなくすことを競うゲームである．1 試合のみで終了することはほとんどなく，複数回試合を行うことが多 . 大きな特徴として，1 試合終了時の順位が次試合開始時の有利不利に影響す

大富豪ならば 5, 富豪は 4, 平民は 3, 貧民は 2,大貧民は 1 を返す．これを指定回数繰り返す．
3. 報酬値の比較
全プレイアウト終了後，各合法手に対する報酬値の平均を比較し，それが最大の合法手を最善$\iota\backslash$るという点が挙げられ，勝者が有利な状況から次の手として出力する．

85
3.1.1

UCBI-TUNED

多腕バンディット問題は，複数のマシンを多数回プレイする中で，一番利益を得るには，どのマシンをプレイするのがいいか，ということを決定する問題である．この問題に対して，UCBI(Upper ConfidenceBounds) というアルゴリズムが提案されている [2].

これは，結果が悪かったマシンで施行回数が多いもる方法が提案されている [3]. 例えば，差分学習法に基づいて報酬値を変化させたものが$V= \sum_{t=0}^{N-1}r_{t}\omega_{t}$である．すなわち，プレイアウト中に生成された盤面状態において，盤面の評価値してその盤面における評価の重み$t$$r_{t}$を算出する．そに従って最初にのはプレイせず，逆に施行回数が少ないマシンはプ選択した合法手 に逐次的なフィードバックを行う．
レイするアルゴリズムである．具体的には UCBI 値によってマシンの選択を行う．ここで，総プレイ回数$\omega_{t}$$i$を $n$ としたとき，その $n$ 回のうち，マシン$i$された回数を $T_{i}(n),$$(n)$がプレイ3.3回プレが銑イされた時の利益の平均とすると，UCBI 値は$\overline{X}_{i}$をマシン$i$

局面評価値の導入

UCBI-TUNED は，最初に選択する合法手の評価を全て均一のものとしてシミュレーションを行う．そ$\overline{X}_{i}+\sqrt{\frac{2\ln n}{T_{i}(n)}}$こで，UCBI-TUNED に局面評価値を導入することで局面評価値が良いと思われる手を優先して探索すによって表される．UCBI アルゴリズムは上記の値る．この手法は，中華圏で人気のゲーム “Big Two”が最も高いマシンにおいて性能向上を示し，その有効性が示されてい$i$に対してプレイアウトを行う．更に，この UCBI アルゴリズムにおいて，各マシンの経験値の分散を考慮したものが UCBI-TUNED[2] でる[4]. 実際に UCBI-TUNED に局面評価値を導入したものがあり，具体的には$\overline{X}_{\iota’}+\sqrt{}\frac{V\cross\ln n+C_{E}xE_{i}}{T_{i}(n)}$$\overline{X}_{i}+\sqrt{\frac{V\cross\ln n}{T_{i}(n)}}$$V= \min(0.25,\overline{X_{i}^{2}}-(\overline{X_{i}})^{2}+\sqrt{\frac{2\ln n}{T_{i}(n)}})$$V= \min(0.25,\overline{X_{i}^{2}}-(\overline{X_{i}})^{2}+\sqrt{\frac{2\ln n}{T_{i}(n)}})$

である．ただしは定数であり，計算機実験の項で詳述する．また，瓦は局面 における局面評価値となるにつれである．上式より明らかに，て勝率瓦が重視されるようになる．
局面評価値の作成に当たって，“Big Two” のゲー
ム $AI$ , $(coffeeAI$” を参考にした [5]. 実際に coffee$AI$ を参考に作成した局面評価値
は$C_{E}$を用いるものである．本研究では，UCBI-TUNEDを利用して，勝率の高い候補手に，より多くのプレイアウトを割り当てる．ここで，前述のマシンは候補手に対応し，利益は報酬値に対応する．大貧民における報酬値は，結果が大富豪ならば 5, 富豪ならば4,. .. , 大貧民なら 1 の値を取る．

$i$$n_{i}arrow\infty$($E_{i}$$E_{i}=E_{sp}+ \frac{E_{8Z}}{1000}+\frac{1000-E_{sum}}{1000^{2}}+E_{p}$3.2

差分学習法の応用である．ただし各記号は以下の通りである．

モンテカルロ法は，プレイアウト途中における盤面を評価せずに報酬値のフィードバックを行っている．そこで，途中経過も含めて強化学習を行うこと$E_{sz}$により，モンテカルロ法よりも適切な行動を選択す$E_{p}$

$E$

。
$p$

: 残り手札を全て提出するための最小手番数: 残り手札の枚数$E_{sum}$: 残り手札中のカードの強さの総和．

: 強いカードを使っているか，次の手番でカード

86を出せるか，よく多くの枚数を使うカードの組合せを崩していないか，パスを選択しているか，しばり手かどうかをそれぞれを考慮した評価値．
coffee $AI$ の評価関数を利用するに当たり，力一4計算機実験
モンテカルロ法のプレイアウトにおいて UCBI-TUNED を利用するクライアントを ‘UCBIに局面評価値を導入しドの強さの調整，Big Two には存在しないルールで TUNED.” UCBI-TUNED

あるしばり手を考慮した評価値，そしてより強い手を崩さないようにする評価値を追加した．導入に際し，局面評価値は 0.0 1.0 の値を取るように調整を$\sim$

3.4

手札交換における手札分割差分学習法を応用した

モンテカルロ法を UCBI-TUNED に導入したクライアントを “ $TD$ .”$TD$に局面評価値を導入したク$UCB+TD.$ ”

UCB $+TD$ に手札分割を実装したクライアントを$UCB+TDhand$ ” と呼ライアントを行った．

$UCB+.$ ”

たクライアントをぶ．それぞれを用いた実験をして比較する．実験で記述する 1 ゲームは 1000 試合とする．

計算機実験 1
ゲーム開始前に大富豪，富豪は，大貧民，貧民に$UCB+$ と UCBI-TUNED の強計算機実験 1 では，カードを渡す必要がある．原口は，提出することが可さを比較する．UCB $+1$ つ，UCBI-TUNEDI つ，能な手に応じて手札を分割する手法を提案した [6].
そして過去に UECda にて優勝したクライアント 3
例えば図 1 のような手札分割を行うと，手数が 4 のつの計 5 つを戦わせる．1 ゲーム終了後，UCB組合せと，手数が 3 の組合せができる．階段，トリと UCBI-TUNED のポイント合計を比較し，点数プル，8 を切札とすると，それぞれの切札の枚数はの高い方を勝ちとして結果を出す．UCB の局面評2 枚となる．手数一切札の数が 1 となった時，手札の値は 0.2 2.2 で変化させ，そ価値における提出における読み切りが可能となるため，良いとされぞれ 40 ゲーム行う．プレイアウト数は UCB $+,$れるものは右の組合せとなる．このようにして，手UCBI-TUNED 共に 2000 回とした．図 2 は $UCB+$
数一切札の数がより小さい分割を，良い分割と考えの勝利数と敗北数を定数別にまとめている．値る．実際の運用は切札数ではなく，各手の切札度の総和で行う．この手札分割を手札交換において利用する．最適な組合せを見つけた後に，ソロのカードの中で最も弱いカードを交換する．最小値探索には$|$ $|$$+$$+$$\sim$$C_{E}$$C_{E}$$4035202530151050$$|-f|_{-}^{-}-|_{-}|_{-}^{-}----|^{-}-|_{-}^{-}---|\begin{array}{ll}-- -- -\end{array}|$

分枝限定法を用いる．
自分の手札. .

相手の手札

0.2 0.4 0.6 0.8$\cup$

1

C8 勝利$+$

1.2 1.4 1.6 1.82

2.2
$C_{E}$$UC$

8 敗北$+$

図 2: UCB $+$ と UCBI-TUNED の対戦結果$C_{E}=1.2$ の時，UCBI-TUNED に対して 25 勝 15敗という最も良い結果が得られたため，この定数を使って計算機実験 2 以降の実験を行っている．また，$C_{E}$

図 1: 手札分割の例が 1.6 より大きくなると，敗北数が勝利数を上回ってしまう．すなわち局面評価値への依存度が高過ぎると性能が下がってしまうことが分かる．

87
計算機実験 2計算機実験 2 では，UCB $+TD$ と $TD$ の強さを比較$T6.$ $UCB+TD1-\supset,$ $TD1-\supset$ , UCBI-TUNED3つの計 5 つを戦わせる．1 ゲーム終了後，UCB と鴎$+$

UCBI-TUNED のポイント合計を比較し，点数の高い方を勝ちとして，100 ゲーム行う．プレイアウ
ト数は全てのクライアントにおいて 2OOO 回とした．

$0$

図 3 に，それぞれのクライアントの勝利数をまとめ.

20

40

大富豪

富豪

60
平民

$\alpha$$\blacksquare$

80
貧民

$*$

100

大貧民

$UCB+$ に対る．結果は $UCB+TD$ の 61 勝 39 敗で，

図 4: UCB $+$ TDhand と UCB $+TD$ の対戦結果

70

5$UCB+TD TD$
図 3: UCB $+TD$ と $TD$ の対戦結果

して 6 割程度の勝率となった．計算機実験 1 と合わせて，局面評価値を UCBI-TUNED に導入することで，精度が向上している．
・計算機実験 3

結論

多人数不完全情報ゲームである大貧民に対し，局面評価値を UCBI 値に導入することによって，精度の向上を図り，より強いプログラムを作成することができた．今回作成した局面評価値は，各プレイヤーの手札の状況のみを見ているだけで，盤面の状態を見てはいないが，それでも一定の効果が得られた．より強い局面評価値が作成できれば，性能を更に向上させることも可能であると考えられる．加えて，手, 交換のプログラムを実装するだけで，強くなった$\ddagger b$

ことから，手札提出のみでなく，手札交換においても今後は注目していく必要があるだろう．

計算機実験 3 では，UCB TDhand と UCB $+TD$ の強さを比較する．UCB TDhandl つと UCB $+TD4$つの計 5 つを同時に戦わせて比較を行う．プ参 考文献
レイアウト数は 2000 回とし，100 ゲーム行う．
[1] 電気通信大学，“UEC コンピュータ大貧民大会”
図 4 は UCB $+TD$ の 100 ゲームの結果である．
(available at http: //uecda.nishino-lab.jp/).
UCB TDhand は，大富豪 39 回，富豪 24 回，平民16 回，貧民 14 回，大貧民 7 回という結果を出した． [2] P. Auer, N. Cesa-Bianchi, P. Fischer, “Finitetime analysis of the multiarmed bandit prob手札交換のプログラムが作用するのは，大富豪，富豪の時のみではあるが，それでも良い結果を残してlem,” Machine Learning, 47 (2002), pp. 235いる．従来の手札交換プログラムは，手札を探索し256.て単に弱いものをカード交換していたが，その交換[3] 小沼啓，本多武尊，保木邦仁，西野哲朗，‘(コによって手札を弱くしてしまっていると思われる．
ンピュータ大貧民に対する差分学習法の応用，”情報処理学会ゲーム情報学研究会 (SIGGI) 研究
報告，1(2012), pp. 1-4.
$+$$+$$*_{z\vee}$$+$

88$(UCB+$ を用いた Big Two[4] 万代悠作，橋本剛，$AI$ の研究，” ゲームプログラミングワークショッ

プ 2012 論文集，6 (2012), $pp.205-210.$[5] SourceForge.net: bigtwo, “Project Web HostOpen Source Software” (available ating
http: $//$ bigtwo. sourceforge. net/).
-[6] 原口和也，私信，2013.