大貧民のモンテカルロ法プレイヤにおける シミュレーション精度向上

平成 25 年度
修士学位論文
大貧民のモンテカルロ法プレイヤにおける
シミュレーション精度向上に関する研究
Improvement of Simulation Accuracy
in Monte Carlo Daihinmin Players
1165064
地曳 隆将
指導教員
松崎 公紀
2014 年 2 月 28 日
高知工科大学大学院 工学研究科 基盤工学専攻
情報システム工学コース
要 旨
大貧民のモンテカルロ法プレイヤにおける
シミュレーション精度向上に関する研究
地曳 隆将
近年，大貧民の研究においてモンテカルロ法を適用したプレイヤの研究が行われている．
モンテカルロ法プレイヤは，現在の盤面からゲーム終了までのシミュレーション（プレイア
ウト）を複数回行うことで各手役の評価値を算出する．プレイヤの強さはプレイアウトの精
度を向上させることで強化できる．
本研究では，大貧民モンテカルロ法プレイヤのプレイアウトの精度を向上させるために 2
つの手法を取った．
1 つめの手法は，プレイアウト開始時に生成する相手手札を実際の盤面に近づけることで
ある．大貧民は不完全情報ゲームであるため，相手プレイヤの手札を知ることができない．
そのため，プレイアウト開始時に生成した相手プレイヤの手札と，実際の盤面の相手プレイ
ヤの手札の差がプレイアウト精度を下げる要因となる．プレイアウト開始時に生成した相手
プレイヤの手札を実際の盤面に近づけることでプレイアウト精度が向上する．
2 つめの手法は，プレイアウト中の各プレイヤのプレイ方策を，実際のプレイヤのプレイ
方策に近づけることである．最も単純なモンテカルロ法である原始モンテカルロでは，プレ
イアウト中の各プレイヤのプレイは乱数によってランダムに行われる．そのため，各プレイ
ヤのプレイとは提出手役に差ができる．各プレイヤが提出する手役を真似できるようになれ
ばプレイアウト精度が向上する．
本研究では，この 2 つの手法が大貧民モンテカルロ法プレイヤに与える影響を調査した．
1 つめの手法では，モンテカルロ木探索プレイヤによって「最善手」を算出し，手札情報
–i–
の異なるモンテカルロ法プレイヤが算出した「最善手と判断した手」と比較した．これに
よって，手札情報の精度がモンテカルロ法プレイヤに与える影響を調査した．調査の結果，
手札推定を行うことでモンテカルロ木探索プレイヤの「最善手」の評価値にモンテカルロ法
プレイヤの評価値（モンテカルロ木探索プレイヤの「最善手」と同じ手の評価値）は近づく
ことがわかった．一方，モンテカルロ法プレイヤが「最善手と判断した手」にはほとんど影
響は無く，
「最善手」の推定には寄与していないことがわかった．
2 つめの手法では 2 つの実験を行った．1 つめの実験では，3 層ニューラルネットワークを
用いた評価関数の性能を調査した．棋譜でプレイヤが提出した手役と，評価関数を用いて得
られる手役の一致度を調査した．調査の結果，学習に使用する盤面データを増やすことで提
出手役の一致率が上昇し，盤面データ数 15,000 程度で一致率が頭打ちになることが確認で
きた．盤面データ数 15,000 の評価関数では，未知の盤面に対する提出手役一致率がおよそ
69%となった．2 つめ実験では，評価関数を適用したモンテカルロ法プレイヤの性能を調査
した．モンテカルロ法プレイヤのプレイアウト中の提出手役を，3 層ニューラルネットワー
クを用いた評価関数によって選択するプレイヤを提案し，原始モンテカルロプレイヤと比較
実験を行った．調査の結果，原始モンテカルロプレイヤよりも評価関数を適用したモンテカ
ルロ法プレイヤの方が強いことが確認できた．
キーワード
大貧民，モンテカルロ法，モンテカルロ木探索，3 層ニューラルネットワーク
– ii –
Abstract
Improvement of Simulation Accuracy
in Monte Carlo Daihinmin Players
Takamasa ZIBIKI
In recent studies of Daihinmin, the Monte-Carlo method has been applied to Daihinmin players. Monte-Carlo player calculates an evaluation value of each meld by
performing a lot of playouts, which are random simulations to the end of the game. The
strength of Monte-Corlo players depends on the accuracy of the playouts.
In this study, we took two approaches in order to improve the accuracy of the
playouts of Daihinmin Monte-Carlo players.
In the first approach, we estimate the opponents’ hands, from which playouts are
performed, as close to the real ones as possible. Since Daihinmin is a game with imperfect information, it is impossible to know the opponents’ hands. The difference between
the estimated hands and the real ones would become a factor that reduces the accuracy
of playouts. If we can estimate the opponents’ hands more precisely, we can improve
the accuracy of playouts.
The second method is to approximate the play strategies in the playouts. The
simplest Monte-Carlo method, called primitive Monte-Carlo, performs playouts just
with random numbers. The difference between the random plays and the real ones
would become a factor that reduces the accuracy of playouts. If we can mimic the play
strategies of the players, we can improve the accuracy of playouts.
In this study, we investigated the effects of these two approaches on Daihinmin
– iii –
Monte-Carlo players.
For the first approach, we compared the melds computed by Monte-Carlo players
with different hand informations with the best hand computed by Monte-Carlo Tree
Search player with perfect information. We found after this experiments that partial
information of opponents’ hands may improve evaluation values but the effects on selecting the best hand are small.
The two experiments were performed for the second approach. The first experiment
investigated the performance of the evaluation function developed with a three-layer
neural network. We investigated how often we can select the real melds played in the
game records using the evaluation function. It was confirmed that the concordance rate
of submission hand combination increases by increasing the training data to be used for
learning, and concordance rate saturates over 15,000 training data. In the evaluation
function learned from 15,000 training data, submitted hand role concordance rate for
the unknown boards has become approximately 69%. The second experiment investigated the performance of the Monte-Carlo player applying the evaluation function. The
proposed player selected the meld computed with the three-layer neural network in the
playouts. We compared the proposed Monte-Carlo player with the primitive MonteCarlo player. After the experiments, we confirmed that the Monte-Carlo player with
the evaluation function is stronger than the primitive Monte-Carlo player.
key words
Daihinmin, Monte-Carlo Method, Monte-Carlo Tree Search,
Three-Layer Neural Networks
– iv –
目次
第1章
はじめに
1
1.1
背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3.1
大貧民に関する研究 . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3.2
モンテカルロ木探索に関する研究 . . . . . . . . . . . . . . . . . . .
3
1.3.3
棋譜を利用した評価関数の学習に関する研究 . . . . . . . . . . . . .
4
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
大貧民とその盤面データ
6
2.1
大貧民のルール . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
盤面データ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
モンテカルロ法とモンテカルロ木探索
8
モンテカルロ法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.4
第2章
第3章
3.1
3.2
第4章
4.1
3.1.1
モンテカルロ法のアルゴリズム . . . . . . . . . . . . . . . . . . . .
8
3.1.2
モンテカルロ法プレイヤ
. . . . . . . . . . . . . . . . . . . . . . .
9
3.1.3
モンテカルロ法プレイヤの収束 . . . . . . . . . . . . . . . . . . . .
10
モンテカルロ木探索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.1
モンテカルロ木探索のアルゴリズム
. . . . . . . . . . . . . . . . .
12
3.2.2
モンテカルロ木探索プレイヤ . . . . . . . . . . . . . . . . . . . . .
13
3.2.3
モンテカルロ木探索プレイヤの収束
. . . . . . . . . . . . . . . . .
13
3 層ニューラルネットワーク
16
3 層ニューラルネットワークにおける出力値の計算 . . . . . . . . . . . . .
16
–v–
目次
4.2
誤差逆伝播法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
第5章
手札情報の精度がモンテカルロ法プレイヤに与える影響の調査
20
第6章
3 層ニューラルネットワークを用いた提出手役評価関数の性能調査
24
6.1
提出手役評価関数の性能調査
. . . . . . . . . . . . . . . . . . . . . . . .
24
6.2
モンテカルロ法に提出手役評価関数を適用したプレイヤの性能調査 . . . .
27
第7章
6.2.1
対戦プレイヤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
6.2.2
対戦実験 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
おわりに
31
謝辞
33
参考文献
34
– vi –
図目次
2.1
盤面データ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.1
モンテカルロ法のアルゴリズム . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2
モンテカルロ法プレイヤの評価値の推移 . . . . . . . . . . . . . . . . . . .
11
3.3
モンテカルロ木探索のアルゴリズム . . . . . . . . . . . . . . . . . . . . . .
12
3.4
モンテカルロ木探索プレイヤの動作 . . . . . . . . . . . . . . . . . . . . . .
14
3.5
モンテカルロ木探索プレイヤの評価値の推移の一例 . . . . . . . . . . . . .
15
4.1
3 層ニューラルネットワーク . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.2
シグモイド関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
6.1
提出手役一致数（MCMP の棋譜 中間層数 15） . . . . . . . . . . . . . . .
26
6.2
提出手役一致数（MCMP の棋譜 中間層数 50） . . . . . . . . . . . . . . .
26
– vii –
表目次
3.1
モンテカルロ法プレイヤの各盤面における最小値と最大値の差の幾何平均
.
3.2
モンテカルロ木探索プレイヤの各盤面における最善手の最小値と最大値の差
10
の幾何平均 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.1
各盤面における最善手の評価値の幾何平均誤差 . . . . . . . . . . . . . . . .
22
5.2
最善手の的中数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
6.1
評価項目に使用した盤面情報 . . . . . . . . . . . . . . . . . . . . . . . . .
25
6.2
提出手役一致数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
6.3
1 対 1 の対戦結果（VS Nakanaka） . . . . . . . . . . . . . . . . . . . . .
30
6.4
2 対 2 の対戦結果（VS Nakanaka） . . . . . . . . . . . . . . . . . . . . .
30
6.5
1 対 1 の対戦結果（VS paoonR2） . . . . . . . . . . . . . . . . . . . . . .
30
6.6
2 対 2 の対戦結果（VS paoonR2） . . . . . . . . . . . . . . . . . . . . . .
30
– viii –
第1章
はじめに
1.1
背景
ゲームはルールが明確に定められており勝ち負けによって評価を行うことができるため，
探索アルゴリズムの性能評価に用いられてきた．またこれまでに，ゲームにおいてプレイヤ
を強化する過程の中で，新たな探索アルゴリズムも発見されている．
2 人零和確定完全情報ゲームにおいては，ゲーム木探索手法や評価関数を適用したプレイ
ヤが人間のトップレベルのプレイヤに対して勝利しその実力を示している．オセロやチェ
スにおいては 1990 年代に当時の世界チャンピオンに勝利している [21]．将棋においては，
ゲーム木探索手法と棋譜による学習を行った評価関数を組み合わせた手法によって，プロ棋
士に勝利するレベルのプレイヤが複数作成されている [17, 20, 22]．囲碁においては，モン
テカルロ木探索をプレイヤに適用することで，プレイヤの棋力がアマチュア有段者レベルま
で向上した [19]．
一方，多人数不完全情報ゲームにおいては，2 人零和確定完全情報ゲームと比較すると良
い結果は得られていない．モンテカルロ木探索を多人数不完全情報ゲームに適用する場合，
探索を開始する初期盤面の情報が確定しないことが多いため，モンテカルロ木探索を効果的
に適用することが困難である．一方，ゲーム木探索手法を用いないモンテカルロ法や評価関
数をプレイヤに適用する研究が行われている．大貧民においては，モンテカルロ法をプレイ
ヤに適用することでプレイヤの強化が確認されている [10]．
–1–
1.2 目的
1.2
目的
本研究では，多人数不完全情報ゲームである大貧民を研究の対象とし，主にモンテカルロ
法プレイヤの強化手法について調査を行った．モンテカルロ法およびモンテカルロ木探索
は，ある局面から乱数を用いて終局までのシミュレーション（プレイアウト）を繰り返し，
合法手の評価値を算出する探索手法である．大貧民においてプレイヤを強化するためには，
プレイアウト回数を増やすだけでなく，プレイアウトの精度を高める必要がある．そこでま
ず大貧民においてプレイアウトの精度を下げる要因をここで明らかにする．
大貧民においてプレイアウトの精度を下げる要因は大きく分けて 2 つある．1 つめの要因
は，プレイアウト開始時に生成する相手プレイヤの手札と実際のプレイヤの手札の差であ
る．大貧民では相手プレイヤの持つ手札は分からないので，プレイアウトを行う前に相手プ
レイヤの持つ手札を仮想的に生成する必要がある．ここで生じる実際の相手プレイヤの手札
と仮想的に生成した手札の差は，プレイアウトの精度を下げる要因となる．2 つめの要因は，
プレイアウト中の各プレイヤのプレイ方策と，実際にプレイしている各プレイヤのプレイ方
策が異なることで生じる提出手役の差である．原始モンテカルロ法と呼ばれる最も単純なモ
ンテカルロ法では，プレイアウト中の各プレイヤのプレイは乱数によってランダムに行われ
る．そのため，実際にプレイしているプレイヤとプレイアウト中のプレイヤの提出手役の差
は，プレイアウトの精度を下げる要因となる．
そこで本研究では，これらのプレイアウトの精度を下げる要因がモンテカルロ法プレイヤ
に与える影響について調査した．本研究の目的は，多人数不完全情報ゲームである大貧民に
おいて強いプレイヤを作成するために必要な情報を調査し，実際に強いプレイヤを作成する
ことである．
1 つめの要因である手札情報の精度に関しては，手札情報が異なるプレイヤにモンテカル
ロ法による評価値の算出を行わせ，モンテカルロ木探索で得られた最善手の評価値と比較を
行い，最善手の的中率と評価値の誤差について調査した．この実験を行うにあたり「次の一
手問題」を複数個用意し，それに対して実験を行う手法を用いた．
–2–
1.3 関連研究
2 つめの要因であるプレイアウト中のプレイ方策の精度に関しては，プレイアウト部分に
3 層ニューラルネットワークを用いた提出手役評価関数を適用し，性能を調査した．対戦実
験では提出手役評価関数とモンテカルロ法を組み合わせたプレイヤの性能を調査した．
1.3
1.3.1
関連研究
大貧民に関する研究
本研究の対象とする大貧民においては，モンテカルロ法をプレイヤに適用することで，
UEC コンピュータ大貧民大会（UECda）[23] で優勝するレベルのプレイヤが得られた
[10, 13, 14]．
大貧民は不完全情報ゲームであり相手手札を知ることはできないため，相手プレイヤの手
札を推定する研究も行われている．須藤ら [13]，および，西野ら [16] は，相手プレイヤが場
に提出した手役の情報から，相手プレイヤの手札を推定する手法を提案し，手札推定を用い
ることでより強いモンテカルロプレイヤが得られることが報告されている．一方で西野ら
は，相手プレイヤの手札を推定することの重要性について，手札の集合を同値類に分類した
結果から得られる考察により，大貧民においては手札推定があまり重要でないと述べている
[15]．
プレイヤ強化の一環として，プレイアウト中の提出手役を実際のプレイヤに近づける研究
も行われている．伊藤ら [5] は，実際のプレイヤの提出手役を模倣する手法としてナイーブ
ベイズを用い，過去の UECda 優勝クライアントである snowl に対して提出手役一致率がお
よそ 4 割であったと報告している．
1.3.2
モンテカルロ木探索に関する研究
ゲームのプレイヤに対してモンテカルロ木探索を適用する研究も行われている．
2006 年にモンテカルロ木探索を適用した囲碁のプレイヤが初めて開発された [19]．19 路
盤の囲碁においてはそれまでのコンピュータプレイヤは非常に弱かったが [19]，モンテカル
–3–
1.4 本論文の構成
ロ木探索と UCB1[3] を組み合わせることで，プレイヤの棋力がアマ有段者レベルまで向上
した [1, 19]．将棋においては，モンテカルロ木探索だけでは強力なプレイヤを作り出すこと
は難しいが，従来の手法と組み合わせて部分的にモンテカルロ木探索を用いることでプレイ
ヤの強化が可能であると示唆されている [11]．その他のゲームにおいても，オセロやパック
マンなどでモンテカルロ木探索を適用することでプレイヤを強化できることが明らかになっ
ている [4, 18]．
1.3.3
棋譜を利用した評価関数の学習に関する研究
棋譜を利用して，ゲームの行動選択に使用する評価関数の学習を行う研究も行われている．
1950 年代にオセロにおいて，ゲームの棋譜を利用して線形和で表現された評価関数の重
みを調整する方法が提案された [2]．
将棋においては，棋譜で指された手を出すように重みを調整することで 10,000 を超える
重みの調整に成功し，コンピュータ将棋選手権で優勝するレベルのプレイヤが得られた [17]．
2013 年に行われた第 2 回将棋電王戦 [22] においては，A 級棋士（日本で 10 名が在籍）で
ある三浦弘行九段に勝利するレベルのプレイヤが作成されている [20]．
また，大貧民と同じ多人数不完全情報ゲームである麻雀においても，棋譜（牌譜）を利用
して評価関数の重みを調整している [9]．結果として評価関数を用いたプレイヤのレーティ
ングは 1318 と弱かったが，棋譜と評価関数の打牌・行動一致率はツモ局面でおよそ 56%と
なり，鳴き局面においておよそ 89%となった．
1.4
本論文の構成
本論文の構成を以下に示す．第 2 章では，大貧民のルールについて説明し，本研究に使用
した次の一手問題と教師データについて説明する．第 3 章では，モンテカルロ法とモンテカ
ルロ木探索について説明する．第 4 章では，3 層ニューラルネットワークについて説明する．
第 5 章では，手札情報の差がモンテカルロ法プレイヤに与える影響を調査する．第 6 章で
–4–
1.4 本論文の構成
は，3 層ニューラルネットワークを用いた提出手役評価関数の性能を調査する．最後に，第
7 章で本論文をまとめる．
–5–
第2章
大貧民とその盤面データ
2.1
大貧民のルール
本研究では，大貧民のルールには UEC コンピュータ大貧民大会 (UECda) の標準ルール
を使用した [23]．そのうち本研究に大きな影響を与える重要なルールを以下に示す．
あがり時の制約 プレイヤの手札枚数が 0 になった状態をあがりと呼ぶ．あがり時にはどの
ような手役を提出してもよい．あがり時に出す手役の制約がないことにより，モンテカ
ルロ法やモンテカルロ木探索においてプレイアウトを単純に実装することができる．
8 切り ランクが 8 のカードを含む手役が場に提出されると 8 切りが発生する．8 切りが発
生すると場が流れ，8 切りを発生させたプレイヤが次の手役を出せる．ランクが 8 の
カードのランク自体はそれほど強くないが，プレイにおいて適切に使用すると強力な
カードにもなるため，モンテカルロ法とモンテカルロ木探索での差が生じる可能性が
ある．
しばり 場に同じスート（複数枚の手役のときには，全てが同じスート）の手役が連続して
提出されるとしばりが発生する．しばりが発生すると，場が流れるまで，同じスート
（の組み合わせ）の手役しか場に提出できなくなる．このルールにより，特定スートの
カードを持つかどうかに意味があり，相手手札の不完全情報性の一要素となる．
獲得点数
1 ゲームにおける獲得点数は，大富豪であれば 5 点，富豪であれば 4 点，平民で
あれば 3 点，貧民であれば 2 点，大貧民であれば 1 点である．
–6–
2.2 盤面データ
Order Normal
Lock_Suits H
Last_Meld Single:H5
Put_Meld Single:H8
Player0 Yes C3 S7 H7 D7 H8 C8 SJ HQ DQ
Player1 Yes S3 S4 H4 S5 S6 S8 S9 S10 CQ HA D2
Player2 Yes H6 HJ CJ SQ SK HK
Player3 No C7 D8 H10 DK CA C2
Player4 No C9 DJ CK S2 H2
図 2.1 盤面データ
2.2
盤面データ
本研究では，盤面データを用いて「次の一手問題」と「教師データ」を作成した．次の一
手問題は，第 5 章の手札情報の精度がモンテカルロ法プレイヤに与える影響の調査に用い
る．教師データは，第 6 章の 3 層ニューラルネットワークを用いた提出手役評価関数の性能
調査に用いる．
盤面データの例を図 2.1 に示す．盤面データは以下の情報からなる．
• プレイヤに関する情報（次にプレイするプレイヤを Player0 とする）
– プレイヤが持つカードの集合
– プレイヤがそのターンでプレイ可能かどうか（パスしているか，すでにあがりであ
る場合にはプレイできない）
• 場に関する情報
– 強さの順番（革命の有無）
– しばりがある場合にはそのスート
– 最後に場に出された役（場が新しい場合には空とする）
• 提出手役に関する情報
– Player0 が実際に出した手役
–7–
第3章
モンテカルロ法と
モンテカルロ木探索
3.1
3.1.1
モンテカルロ法
モンテカルロ法のアルゴリズム
モンテカルロ法は，乱数によるシミュレーションを複数回行うことで近似解を算出するア
ルゴリズムである．モンテカルロ法の特長のひとつに，解析的に解を算出しにくい問題を含
む広範囲の問題に対して適用可能であることが挙げられる．一般に，モンテカルロ法の解の
精度はシミュレーション回数の平方根に比例する [12]．
ゲームのプレイヤに適用したモンテカルロ法の動作を図 3.1 に示す．モンテカルロ法のシ
ミュレーションでは，ある盤面のある合法手から始め，乱数によって各プレイヤのプレイを
図 3.1 モンテカルロ法のアルゴリズム
–8–
3.1 モンテカルロ法
行い，終局までプレイすることに対応する．この乱数による終局までのプレイをプレイアウ
トと呼ぶ．複数回のプレイアウトを行いプレイアウトの結果それぞれに点数をつけ，その点
数の平均などを求めることで評価値を計算する．
限られた回数のプレイアウトでより良い結果を得るためには，有望そうな手に対して多く
のプレイアウトを行う手法が有効である．どの手をプレイアウトすると最も高い期待値を得
られるかという問題は「多腕バンディット問題」と呼ばれ，これを効率良く解くアルゴリズ
ムが複数提案されている．そのひとつである UCB1（Upper Confidence Bound）[3] では，
手 j の評価値 Xj ，全体のプレイアウト回数 n，手 j に対するプレイアウト回数 nj ，および
ある定数 c に対して，以下の式で示される UCB1 値
√
Xj + c
2 log n
nj
(3.1)
が最も大きいものに対してプレイアウトする．定数 c はバランスパラメータと呼ばれ，プレ
イアウト回数を評価する式の調整に用いる．
モンテカルロ法では，プレイアウト回数だけでなくプレイアウトの精度が結果に大きく影
響する．すなわち，乱数によるプレイが実際で行われるプレイと大きく異なる場合には正し
い結果に収束しない．さらに，探索する木の深さが 2 以上の場合には，プレイアウト回数を
無限に増やしても正しい結果に収束しない可能性がある [1]．
3.1.2
モンテカルロ法プレイヤ
モンテカルロ法プレイヤは，合法手に対して指定回数のプレイアウトを行い，最終的に最
も評価値の高い手役を場に提出する．プレイアウトの対象となる合法手には（全く意味のな
い，場が新しい場合を除き）パスも含める．プレイアウトでは，各プレイヤは以下のように
動作する．
1. 合法手のうち，それを出すことであがりとなるような手があれば，それを選択する．
2. パス以外の合法手が存在する場合には，パス以外の合法手の中から等確率に選択する．
–9–
3.1 モンテカルロ法
表 3.1
モンテカルロ法プレイヤの各盤面における最小値と最大値の差の幾何平均
測定範囲
序盤
中盤
終盤
100∼1,000
0.1474
0.1097
0.0864
1,001∼2,000
0.0351
0.0266
0.0224
2,001∼3,000
0.0214
0.0132
0.0121
3,001∼4,000
0.0152
0.0101
0.0098
4,001∼6,000
0.0150
0.0111
0.0090
6,001∼8,000
0.0103
0.0071
0.0063
8,001∼10,000
0.0085
0.0058
0.0049
3. 合法手がパスのみである場合には，パスを選択する．
上記のとおり，プレイアウトの対象となる最初の 1 手のみパスを含み，プレイアウト中では
意図的なパスはしないとする．
1 回のプレイアウトが終了すると，選択した手役に対して点数を割り当てる．このときに
割り当てる点数は UECda の標準ルールにならって，大富豪であれば 5 点，富豪であれば 4
点，平民であれば 3 点，貧民であれば 2 点，大貧民であれば 1 点とした．UCB1 値のバラ
ンスパラメータ c は 1 回のプレイアウトで得られる報酬の最大値と最小値の差，すなわち 4
とした．
3.1.3
モンテカルロ法プレイヤの収束
モンテカルロ法プレイヤの収束について調査するため，各手役に対して 10,000 回のプレ
イアウトを行った．調査には 30 問（序盤 10 問，中盤 10 問，終盤 10 問）の次の一手問題を
使用し，相手プレイヤの手札をすべてわかっている状態とした．図 3.2 は，モンテカルロ法
プレイヤを用いてプレイアウトを行ったときの各手役の評価値の推移の一例である．図 3.2
を見ると，プレイアウト回数が増加するにつれて評価値の変化の幅が小さくなっていること
がわかる．
表 3.1 は各手役の評価値の測定範囲をプレイアウト回数で区切り，その範囲内の最小値と
最大値の差の幾何平均を示した図である．表 3.1 を見ると，モンテカルロ法プレイヤの評価
– 10 –
3.1 モンテカルロ法
図 3.2
モンテカルロ法プレイヤの評価値の推移
値はプレイアウト回数が増加するにつれて変化の幅が小さくなっていることがわかる．ま
た，序盤，中盤，終盤となるにつれて評価値の変化の幅が小さくなっていることがわかる．
測定範囲が 100∼1,000 の範囲での各手役の評価値は，序盤で 0.15，中盤で 0.11，中盤で
0.09 程度の変化の幅がある．それ以降の測定範囲を見ると，徐々に変化の幅が小さくなって
いるのがわかるが，3,001∼4,000，4,001∼6,000 の測定範囲の変化の幅は大差ないことがわ
かる．3,001∼4,000，4,001∼6,000 の測定範囲では評価値の変化の幅が 0.01 程度に収まっ
ているため，評価値が収束しているのではないかと考える．このことから，モンテカルロ法
プレイヤが各手役に対して行うプレイアウト回数は 4,000 回程度が適当であると考える．
– 11 –
3.2 モンテカルロ木探索
MCT(root) {
loop until end_flag {
leaf <- select_downwards(root)
leaf.n <- leaf.n + 1
if (expand_flag(leaf)) {
leaf <- expand(leaf).first_child
}
board = playout(leaf.board)
update_upwards(leaf, getvalue(board))
}
return select_best_child(root)
}
図 3.3 モンテカルロ木探索のアルゴリズム
3.2
3.2.1
モンテカルロ木探索
モンテカルロ木探索のアルゴリズム
モンテカルロ木探索 [1] は，モンテカルロ法とゲーム木探索手法を組み合わせたアルゴリ
ズムである．基本的な考え方は，プレイアウトによってある盤面のある合法手に対する評価
値を計算し（モンテカルロ法），そこで得られた有望そうな手についてその先の探索をより
深くする（ゲーム木探索手法）というものである．モンテカルロ法とは異なり，モンテカル
ロ木探索ではプレイアウト回数を十分に増やすと最善手が得られる [1]．
モンテカルロ木探索の疑似コードを図 3.3 に示す．モンテカルロ木探索では，終了条
件（end_flag）を満たすまでプレイアウトを行い，合法手の評価値を算出する．終了条
件は，探索回数や探索時間によって与えられる．モンテカルロ木探索では，それまでに
得られている評価値を利用して木を探索する．根ノードからある葉ノードに到達すると
（select_downwards），その葉ノードに対応する盤面を開始盤面としてプレイアウトを行
う（playout）．ここで，ある葉ノードにおけるプレイアウト回数がある閾値に達した場合
は（expand_flag），そのノードを展開し（expand），その盤面の 1 手先からプレイアウト
するようにする．プレイアウトの結果から合法手の評価値を算出し（evaluate），葉ノード
– 12 –
3.2 モンテカルロ木探索
から根ノードまでの値を更新する（update_upwards）．UCB1 などの手法を用いると，有
望そうな手にはプレイアウトが多く実行され，プレイアウトが集中するところはより深く木
を探索できることになる．
3.2.2
モンテカルロ木探索プレイヤ
モンテカルロ木探索プレイヤの動作を図 3.4 に示す．モンテカルロ木探索プレイヤにおい
て，場に提出する手役，プレイアウト中の動作，割り当てる点数はモンテカルロ法プレイヤ
と同じとする．木の探索においてどの子ノードを選択するかは，式 3.1 の UCB1 値によっ
て決定した．また，葉ノードのプレイアウト回数が 100 回を越えるときにそのノードを展開
するものとした．
プレイアウトでは，ルートノードのプレイヤだけでなく全てのプレイヤに点数を割り
当てる．葉ノードにおいては，割り当てられた点数の相加平均により，各プレイヤの評
価値を求める．その他のノードについては，maxn アルゴリズムにより，各プレイヤが
その子ノードの評価値のうちそのプレイヤにとって最大となるものをローカルに選択す
るようにした．例えば，図 3.4 でルートからハートの A を選んだ先のノードでは，その
子ノード（いずれも葉ノードである）のうちプレイヤ P3 にとって評価値の高い PASS
（[P 0 → 3.21, P 1 → 4.25, P 2 → 1.52, P 3 → 2.88, P 4 → 2.97]）がその評価値となる．
3.2.3
モンテカルロ木探索プレイヤの収束
モンテカルロ木探索プレイヤの収束について調査するため，合法手全体で 100,000 回のプ
レイアウトを行った．モンテカルロ法プレイヤと同様に，調査には 30 問（序盤 10 問，中盤
10 問，終盤 10 問）の次の一手問題を使用し，相手プレイヤの手札をすべてわかっている状
態とした．図 3.5 は，モンテカルロ木探索プレイヤを用いてプレイアウトを行ったときの各
手役の評価値の推移の一例である．図 3.5 を見ると，各手役の評価値が大きく変動している
箇所が多数あることがわかる．これは，プレイアウトをしている手役の葉ノードを展開した
– 13 –
3.2 モンテカルロ木探索
図 3.4 モンテカルロ木探索プレイヤの動作
表 3.2 モンテカルロ木探索プレイヤの各盤面における最善手の最小値と最大値の差の幾何平均
測定範囲
序盤
中盤
終盤
100∼10,000
1.5394
0.7868
0.5031
10,001∼20,000
0.3550
0.4027
0.3729
20,001∼30,000
0.4806
0.4373
0.4129
30,001∼40,000
0.4723
0.3703
0.4429
40,001∼50,000
0.4412
0.1111
0.3695
50,001∼60,000
0.3794
0.3164
0.2461
60,001∼70,000
0.3756
0.6482
0.3521
70,001∼80,000
0.4322
0.5886
0.4239
80,001∼90,000
0.4402
0.5886
0.4239
90,001∼100,000
0.5151
0.5518
0.1515
ときに，その 1 つ下のプレイヤがベストな手役を提出したことでおこる現象であると考え
る．このことから，多人数ゲームにおいてモンテカルロ木探索を行った場合には，木の深さ
を 1 つ深くするだけで各手役の評価値が大きく変動することが確認される．
表 3.2 は最善手の評価値の測定範囲をプレイアウト回数で区切り，その範囲内の最小値と
最大値の差の幾何平均を示した図である．なお，測定範囲内で評価値が全く変化していない
ものは無視して測定した．表 3.2 を見ると，モンテカルロ木探索プレイヤの評価値は，全体
– 14 –
3.2 モンテカルロ木探索
図 3.5 モンテカルロ木探索プレイヤの評価値の推移の一例
のプレイアウト回数が増加しても変化の幅があまり変わらないことがわかる．これは，図
3.5 のように評価値が大きく変動しながら推移するためであると考える．このことから，モ
ンテカルロ木探索プレイヤを用いて正しい評価値を算出するためには，100,000 回よりも多
くプレイアウトが必要になることがわかる．
– 15 –
第4章
3 層ニューラルネットワーク
4.1
3 層ニューラルネットワークにおける出力値の計算
図 4.1 に 3 層ニューラルネットワークの構成を示す．3 層ニューラルネットワークは，入
力層，中間層，出力層の 3 層からなる．入力層に値を与えることで中間層を経て出力層から
値が得られる．
入力層のユニット i から中間層のユニット j への遷移に対する重みを ωi,j ，中間層のユ
ニット j から出力層のユニットへの遷移に対する重みを υj とする．ωi,j の総数は，入力層
のユニット数 I に中間層のユニット数 J を掛けた数に等しく，υj の総数は中間層のユニッ
ト数 J に等しい．ωi,j (1 ≤ i ≤ I, 1 ≤ j ≤ J) をまとめて ω と表す．同様に υj (1 ≤ j ≤ J)
図 4.1 3 層ニューラルネットワーク
– 16 –
4.1 3 層ニューラルネットワークにおける出力値の計算
図 4.2 シグモイド関数
をまとめて υ と表す．関数 S(x) をシグモイド関数
S(x) =
1
1 + e−x
とする．シグモイド関数は図 4.2 のように (−∞, ∞) を (0, 1) に変換する関数であり，
S(x) = 0 と S(x) = 1 に漸近線を持つ．また，関数 D(x) を
D(x) = x(1 − x)
とする．ここで，S 0 (x) = D(S(x)) が成り立つ．
各層の計算について以下に示す．入力層の各ユニットでは入力 p によって値が計算され
る．入力層のユニット i で計算される値を fi (p) とする．中間層の各ユニットでは入力層の
値 fi (p) と ωi,j によって値が計算される．中間層のユニット j で計算される値 gj (p, ω) は
gj (p, ω) = S
( I
∑
)
fi (p)ωi,j
i=1
である．出力層では中間層の値 gj (p, ω) と υj によって値が計算される．3 層ニューラルネッ
– 17 –
4.2 誤差逆伝播法
トワークの出力値 h(p, υ, ω) は

h(p, υ, ω) = S 
J
∑

gj (p, ω)υj 
j=1
となる．
4.2
誤差逆伝播法
各層の重みの調整は，多数の教師データを用いて誤差逆伝播法によって行う．教師データ
は正解の入力 qm と不正解の入力 pm の組であり，教師データの数を M とする．教師データ
の集合を P と表す．ここで，正解の出力と不正解の出力の差の度合いを示す関数 E(P, υ, ω)
を
E(P, υ, ω) =
M
∑
S (h(pm , υ, ω) − h(qm , υ, ω))
m=1
と定める．誤差逆伝播法による重み調整では，E(P, υ, ω) を最小化することを目標とする．
誤差逆伝播法による重み調整を以下に示す．あるときの調整前の重みを υ ，ω ，調整後の
重みを υ 0 ，ω 0 とする．学習率 η を用いて，υ ，ω の重みを
(υ 0 , ω 0 ) = (υ, ω) − η
∂E(P, υ, ω)
∂(υ, ω)
によって調整する．ここで，υj の重みを調整するための勾配は
αi,j (p, υ, ω) = D(h(p, υ, ω))gj (p, ω)
を用いて
M
∑
∂E(P, υ, ω)
= D(E(P, υ, ω))
(αi,j (pm , υ, ω) − αi,j (qm , υ, ω))
∂υj
m=1
– 18 –
4.2 誤差逆伝播法
によって計算される．ωi,j の重みを調整するための勾配は
βi,j (p, υ, ω) = D(h(p, υ, ω))υj D(gj (p, ω))fi (p)
を用いて
M
∑
∂E(P, υ, ω)
= D(E(P, υ, ω))
(βi,j (pm , υ, ω) − βi,j (qm , υ, ω))
∂ωi,j
m=1
によって計算される．
– 19 –
第5章
手札情報の精度がモンテカルロ法
プレイヤに与える影響の調査
本研究では，1,500 問の次の一手問題を「手札情報の異なるモンテカルロ法プレイヤ」と
「モンテカルロ木探索プレイヤ」に解かせ，手札情報の精度が大貧民モンテカルロ法プレイ
ヤに与える影響を調査した．次の一手問題には図 2.1 のような盤面データの中から，勝ち抜
けが確定していないものを用いた次の一手問題の内訳は，枚数を基準として序盤を 500 個，
中盤を 500 個，終盤を 500 個とした．序盤・中盤・終盤を区別する枚数の基準は以下の通り
とした．
序盤 まだ使用されていないカードが 36 枚以上
中盤 まだ使用されていないカードが 21 枚以上 35 枚以下
終盤 まだ使用されていないカードが 20 枚以下
各 1,500 盤面に対して 6 種類のシミュレーションを行い，そのときの各手役の評価値を調
査した．6 種類のシミュレーションは以下の通りである．
M 全ランダム 相手プレイヤの全てのカードをランダムに割り当て，モンテカルロ法プレ
イヤでプレイアウトを行う．
M 強固定 各相手プレイヤの最強のカードを 1 枚固定し，その他のカードをランダムに割
り当て，モンテカルロ法プレイヤでプレイアウトを行う．
M 弱固定 各相手プレイヤの最弱のカードを 1 枚固定し，その他のカードをランダムに割
– 20 –
り当て，モンテカルロ法プレイヤでプレイアウトを行う．
M 強弱固定 各相手プレイヤの最強と最弱のカードを 1 枚固定し，その他のカードをラン
ダムに割り当て，モンテカルロ法プレイヤでプレイアウトを行う．
M 全固定 相手プレイヤの全てのカードを固定し，モンテカルロ法プレイヤでプレイアウ
トを行う．
T 全固定 相手プレイヤの全てのカードを固定し，モンテカルロ木探索プレイヤでプレイア
ウトを行う．
各シミュレーションについて図 2.1 を例に補足する．全ランダムは相手の手札が一枚もわ
かっていない（通常の大貧民と同じ）状態である．強固定は Player1 の D2，Player2 の
HK，Player3 の C2，Player4 の H2 がわかっており，そのカードよりも強いランクのカー
ドを持っていないことがわかっている状態である．弱固定は Player1 の S3，Player2 の H6，
Player3 の C7，Player4 の C9 がわかっており，そのカードよりも弱いランクのカードを
持っていないことがわかっている状態である．強弱固定は，Player1 の S3 と D2，Player2
の H6 と HK，Player3 の C7 と C2，Player4 の 9 と H2 がわかっており，各プレイヤの手
札はそれらの最弱カードと最強カードの間のカードから構成されていることがわかっている
状態である，全固定は完全情報ゲームになっている状態である．
T 全固定は合計 100,000 回のプレイアウトを行い，それ以外の 5 つのシミュレーションは
各手役に対して 10,000 回のプレイアウトを行った．T 全固定時に最も評価値が高い手役を
その盤面における「最善手」とし，最善手の評価値とそれ以外の 5 つのシミュレーションの
最善手の評価値の幾何平均誤差と，最善手の的中数について調査した．
各盤面における最善手の評価値の幾何平均誤差を表 5.1 に示し，最善手の的中率を表 5.2
に示す．表 5.2 中のスラッシュの左の数値は各シュミレーションで最も評価値が高い手役が
最善手と一致した数を表し，スラッシュの右の数値は各シミュレーションで二番目に評価値
が高い手役が最善手と一致した数を表している．表 5.1 を見ると，すべての盤面において全
固定の最善手の評価値の誤差は，他のシミュレーション手法と比較して小さいことがわかる．
– 21 –
表 5.1 各盤面における最善手の評価値の幾何平均誤差
シミュレーション手法
序盤
中盤
終盤
M 全ランダム
0.2934
0.3367
0.2844
M 強固定
0.2816
0.2623
0.3085
M 弱固定
0.2745
0.2606
0.2999
M 強弱固定
0.2758
0.2628
0.2627
M 全固定
0.2422
0.2066
0.2605
表 5.2 最善手の的中数
シミュレーション手法
序盤
中盤
終盤
M 全ランダム
129 / 100
181 / 125
256 / 126
M 強固定
133 / 95
187 / 120
246 / 145
M 弱固定
127 / 99
178 / 122
254 / 137
M 強弱固定
131 / 101
179 / 120
239 / 146
M 全固定
135 / 96
180 / 123
254 / 136
合法手数の幾何平均
10.66
6.67
4.45
また，全ランダムの序盤・中盤の最善手の評価値の誤差は他のシミュレーション手法と比較
して大きいことがわかる．そのため序盤・中盤においては，相手手札を推定することで最善
手の評価値の誤差を小さくできることがわかる．終盤における最善手の評価値の誤差は，全
ランダムよりも，強固定や弱固定の方が大きく，強・弱固定や全固定の方が小さい．そのた
め，終盤においては，相手手札を全体的に推定しなければ意味がないことがわかる．
表 5.2 について見ると，序盤，中盤，終盤となるにつれて，幾何平均合法手数が減少し，
最善手の的中数が多くなっていることがわかる. つまり，残りカード枚数が多く合法手数が
多い序盤では最善手の推定が難しく，その逆の終盤では最善手の推定がしやすいことが確認
できる．
各盤面で各盤面で最も的中率が低い手法とその的中数は，序盤は弱固定で 127 盤面，中盤
は弱固定で 178 盤面，終盤は強・弱固定で 239 盤面であり，最も的中率が高い手法とその的
中数は，序盤は全固定で 135 盤面，中盤は強固定で 187 盤面，終盤は全ランダムで 256 盤
面である．この結果から，最も高い的中数を出したシミュレーション手法は，序盤・中盤・
– 22 –
終盤で異なることがわかる．また，序盤と中盤では最も高い的中数と最も低い的中数の差が
10 盤面もなく，終盤でも的中数の差は 17 盤面である．この的中数の差は調査に使用した盤
面の 2∼3%程度の数であり，各シミュレーション手法の的中数に大きな差はないと考える．
表 5.1 と表 5.2 の結果から，手札情報を推定することで最善手の評価値に近づくことはで
きるが，最善手の推定には寄与していないことがわかる．
– 23 –
第6章
3 層ニューラルネットワークを
用いた提出手役評価関数の性能調査
3 層ニューラルネットワークを用いた提出手役評価関数の性能調査では，モンテカルロ法
に提出手役評価関数を適用したプレイヤの性能調査を，他のプレイヤとの対戦により行った．
6.1
提出手役評価関数の性能調査
本研究では，3 層ニューラルネットワークを用いた提出手役関数を作成し性能を評価し
た．教師データには，大貧民の棋譜を図 2.1 のような盤面データに切り出したもの使用した．
図 2.1 の盤面データでは相手プレイヤの手札がわかっているように表現されているが，教
師データでは相手プレイヤの手札枚数だけがわかっている状態とした（Player1，Player2，
Player3，Player4，の手札の集合が場の残存カードに対応する）．教師データにおける正解
の入力は，Player0 が実際に出した手役であり，不正解の入力は，それ以外の合法手である．
図 2.1 であれば正解の入力は H8，不正解の入力は H7,HQ,PASS となり，この盤面データ
からは 4 個の教師データが作成される．多数の教師データを用いて，提出手役評価関数の重
みを Player0 が実際に出した手役を提出するように調整することで，Player0 のプレイ方策
を模倣した提出手役評価関数が作成されることが期待される．
教師データの作成には 2 種類の大貧民の棋譜を用いた．1 つは「各合法手に対して 500 回
のプレイアウトを行う原始モンテカルロ法プレイヤ 5 名」の対戦を棋譜にしたものである．
もう 1 つは「人間のプレイヤ 1 名と各合法手に対して 500 回のプレイアウトを行う原始モ
– 24 –
6.1 提出手役評価関数の性能調査
表 6.1
盤面情報の種類
場の情報
提出役の情報
プレイヤの情報
評価項目に使用した盤面情報
評価項目
場のオーダ
場の役と提出役のランク差
場の残存カードのランク
手役のランク
手役のタイプ
手役のサイズ
革命が発生するか
しばりが発生するか
8 切りが発生するか
JOKER を含むか
自プレイヤの手札のランク
他プレイヤのカード枚数
評価項目数
1
5
41
17
2
5
1
1
1
1
41
4
ンテカルロ法プレイヤ 4 名」の対戦を棋譜にしたものである．すべての教師データに対し
て 1 回だけ学習を行うことを 1 イテレーションとし，1,000 イテレーションの学習を行った．
提出手役評価関数の中間層数は 15 と 50 の 2 通りを用意した．学習率は初期値を 0.9 とし，
1 イテレーションごとに 0.99 を掛けて使用した．評価項目に使用した盤面情報を表 6.1 に
示す．
以上の条件で提出手役評価関数の学習を行った．また，重みの初期値によって提出手役評
価関数の性能が変動することが考えられるため，初期値が異なるものを 100 個用意しそれぞ
れ学習した．
性能調査実験では，提出手役評価関数の性能を調査するため「棋譜で提出された手役」と
「提出手役評価関数によって得られた評価値が最も大きい手役」がどの程度一致するか調査
した．調査に使用する盤面には，学習時に使用していないものを 1,000 盤面用意した．学習
時に使用していない盤面に対して調査を行うことで，未知の盤面に対して調査を行ったこと
になり，実戦時の性能が評価できる．
実験結果を図 6.1，6.2 と表 6.2 に示す．図中と表中では原始モンテカルロ法プレイヤを
MCMP と表記する．Ave は平均的中数，Max は最大的中数，Min は最小的中数，エラー
バーは標準偏差における 95%信頼区間を表している．
– 25 –
6.1 提出手役評価関数の性能調査
図 6.1
提出手役一致数（MCMP の棋譜 中間層数 15）
図 6.2
提出手役一致数（MCMP の棋譜 中間層数 50）
図 6.1，6.2 を見ると，中間層の数に限らず，学習に使用する盤面データを増やすことで提
出手役の一致率が上昇していることがわかる．
図 6.1 の平均最善手的中数を見ると，盤面データ数 15,000 付近で最善手的中数が頭打ち
になっており，そのときの最善手一致率はおよそ 69%である．盤面データ数 1,000 の場合と
表 6.2 提出手役一致数
棋譜
MCMP
MCMP
MCMP
MCMP
人間
中間層数
盤面データ数
15
15
50
50
15
3,000
19,000
3,000
27,000
2,245
平均
最大
最小
標準偏差
653.22
691.29
670.27
705.97
420.65
694
737
714
742
469
603
647
635
666
362
16.17
16.07
14.81
14.86
29.45
– 26 –
6.2 モンテカルロ法に提出手役評価関数を適用したプレイヤの性能調査
比較すると，およそ 4%最善手一致率が向上していることがわかる．
図 6.2 の平均最善手的中数を見ると，盤面データ数 27,000 まで最善手的中数がゆるやか
に上昇し続けており，盤面データ数 27,000 での最善手一致率はおよそ 71%である．中間層
数 50 の場合では最善手一致数が頭打ちになっていないため，盤面データ数をさらに増やす
ことで最善手一致率が上昇する可能性がある．
表 6.2 を見ると，人間の棋譜を用いた学習は，原始モンテカルロ法プレイヤの棋譜を用い
て学習した場合に比べて平均一致率が低くなっている．そのため，人間の棋譜を用いて充分
に学習を行うためには，原始モンテカルロ法プレイヤの棋譜よりも多くの棋譜が必要になる
ことがわかる．
6.2
モンテカルロ法に提出手役評価関数を適用したプレイヤ
の性能調査
6.2.1
対戦プレイヤ
対戦に使用するプレイヤは，比較用に作成したプレイヤを 5 つ，UECda ホームページ
（プレイヤが入手可能な 2012 年度版）で公開されているプレイヤから 3 つの計 8 プレイヤ
を使用した．対戦に使用したプレイヤは以下の通りである．
• Monte
原始モンテカルロ法プレイヤ
• EVM
提出手役評価関数プレイヤ（コンピュータの棋譜）
• EVH
提出手役評価関数プレイヤ（人間の棋譜）
• MonteEVM 提出手役評価関数を適用したモンテカルロ法プレイヤ（コンピュータ
の棋譜）
• MonteEVH
提出手役評価関数を適用したモンテカルロ法プレイヤ（人間の棋譜）
• Sample
UECda サンプルプレイヤ
• Nakanaka
UECda ライト級基準プレイヤ
– 27 –
6.2 モンテカルロ法に提出手役評価関数を適用したプレイヤの性能調査
• paoonR2
2012 年度 UECda 無差別級優勝プレイヤ
比較用に作成した 5 つのプレイヤの詳細を以下に示す．
■Monte プレイアウト中はパス以外の合法手の中から等確率に選択した手役を提出する
ようにした．プレイアウト回数は全体で 1,000 回とし，プレイアウトを行う手役は UCB1
値によって決定した．場に提出する手役は，1,000 回のプレイアウト終了後に最も評価値の
高い手役である．
■EVM 教師データの作成には，各合法手に対して 500 回のプレイアウトを行う原始モン
テカルロ法プレイヤ 5 名の対戦の棋譜を用いた．提出手役評価関数は，中間層数が 15，盤
面データ数が 19,000，イテレーション数が 1,000 のものである．場に提出する手役は，提出
手役評価関数によって得られる評価値が最も大きい手役である．
■EVH
教師データの作成には，人間のプレイヤ 1 名と，各合法手に対して 500 回のプレ
イアウトを行う原始モンテカルロ法プレイヤ 4 名の対戦の棋譜を用い，人間のプレイヤの
プレイ方策を学習した．提出手役評価関数は，中間層数が 15，盤面データ数が 3,245，イテ
レーション数が 1,000 のものである．場に提出する手役は，提出手役評価関数によって得ら
れる評価値が最も大きい手役である．
■MonteEVM 教師データの作成には，各合法手に対して 500 回のプレイアウトを行う
原始モンテカルロ法プレイヤ 5 名の対戦の棋譜を用いた．プレイアウトに用いる提出手役評
価関数は，中間層数が 15，盤面データ数が 19,000，イテレーション数が 1,000 のものを使
用し，プレイアウト中は提出評価関数によって得られる評価値が最も大きい手役を提出する
ようにした．プレイアウト回数，プレイアウトを行う手役の決定手法，場に提出する手役は
Monte と同様である．
■MonteEVH 教師データの作成には，人間のプレイヤ 1 名と，各合法手に対して 500
回のプレイアウトを行う原始モンテカルロ法プレイヤ 4 名の対戦の棋譜を用い，人間のプレ
イヤのプレイ方策を学習した．プレイアウトに用いる提出手役評価関数は，中間層数が 15，
– 28 –
6.2 モンテカルロ法に提出手役評価関数を適用したプレイヤの性能調査
盤面データ数が 3,245，イテレーション数が 1,000 のものを使用し，プレイアウト中は提出
評価関数によって得られる評価値が最も大きい手役を提出するようにした．プレイアウト回
数，プレイアウトを行う手役の決定手法，場に提出する手役は Monte と同様である．
MonteEVM，MonteEVH はプレイアウト中でも合法手にパスを含むようにした．Monte，
EVM，EVH，MonteEVM，MonteEVH の手札交換のアルゴリズムは Nakanaka と同じも
のを使用した．
6.2.2
対戦実験
対戦実験では，比較用に作成した 5 つのプレイヤと UECda ライト級基準プレイヤの
Nakanaka を対戦させた．対戦は 5 人対戦で行い，その組み合わせは，
「比較するプレイヤ
の数」と「Nakanaka の数」が 1 対 1 もしくは 2 対 2 となるようにし，残りのプレイヤは
Sample とした．
対戦結果を表 6.3，6.4 に示す．表中の点数は，平民を 0 点として，大富豪を +2 点，富豪
を +1 点，大貧民を −2 点，貧民を −1 点としたときの総獲得点数である．試合数は 2012
年度の大会試合数と同じ 400 である．
表 6.3，6.4 を見ると，いずれの対戦でも Monte，EVM，EVH は Nakanaka に獲得点数
で負けている．一方，表 6.3 の MonteEVM と Nakanaka の対戦結果を見ると，MonteEVM
は Nakanaka に獲得点数で勝っている．この結果から，モンテカルロ法に提出手役評価関数
を適用することでプレイヤが強化されたことがわかる．
また参考として，対 Nakanaka 戦において最も獲得点数が多い MonteEVM と 2012 年度
UECda 優勝プログラムの paoonR2 を対戦させた．対戦結果を表 6.5，6.6 に示す．
表 6.5，6.6 を見ると，どちらの対戦においても MonteEVM は Nakanaka と paoonR2 に
獲得点数で負けている．また，表 6.4 の MonteEVM と Nakanaka の対戦を見ると，1 対 1
の対戦では MonteEVM の方が獲得点数が多かったが，2 対 2 の対戦では Nakanaka の方が
獲得点数が多くなっている．
表 6.3，6.4 の MonteEVM について見ると，Monte よりも獲得点数が少なくなっている
– 29 –
6.2 モンテカルロ法に提出手役評価関数を適用したプレイヤの性能調査
表 6.3 1 対 1 の対戦結果（VS Nakanaka）
プレイヤ名
プレイヤ
Nakanaka
Sample
Sample
Sample
プレイヤと Nakanaka の差
Monte
+182
+395
−134
−168
−275
−213
EVM
−191
+468
−87
−120
−70
−659
EVH
−537
+434
+86
+42
−25
−971
MonteEVM
+346
+239
−154
−190
−241
+107
MonteEVH
−18
+428
−56
−173
−181
−446
表 6.4 2 対 2 の対戦結果（VS Nakanaka）
プレイヤ名
プレイヤ
プレイヤ
Nakanaka
Nakanaka
Sample
プレイヤと Nakanaka の差
Monte
+24
−23
+157
+116
−274
−272
EVM
−284
−306
+430
+312
−152
−1332
EVH
−468
−479
+463
+396
+88
−1806
MonteEVM
+85
−56
+240
+99
−368
−310
MonteEVH
−102
−223
+323
+225
−223
−873
表 6.5 1 対 1 の対戦結果（VS paoonR2）
プレイヤ名
プレイヤ
paoonR2
Sample
Sample
Sample
MonteEVM
+243
+533
−202
−273
−301
表 6.6 2 対 2 の対戦結果（VS paoonR2）
プレイヤ名
プレイヤ
MonteEVM
paoonR2
paoonR2
Sample
MonteEVM
−61
−61
+314
+290
−482
ため，人間の棋譜から学習した提出手役評価関数をモンテカルロ法に適用してもプレイヤが
強化されていないことが分かる．これは盤面データ数が 3,245 と少ないことや，盤面データ
の中に人間が明らかなミスをしたものも含まれている可能性があることなどが原因であると
考える．人間の棋譜から学習した提出手役評価関数の性能は，棋譜を充実化することで改善
できると考える．
– 30 –
第7章
おわりに
モンテカルロ法プレイヤにおいて，プレイアウトの精度は重要である．本研究では，手札
情報の精度がモンテカルロ法プレイヤに与える影響と，3 層ニューラルネットワークを用い
た提出手役評価関数の性能の調査を行った．
手札情報の精度がモンテカルロ法プレイヤに与える影響の調査では，モンテカルロ法プレ
イヤは，与えられる手札情報が多くなるにつれて正しい手役の評価値に近い値を得られる傾
向が見られた．しかし，最善手の推定には至らず，手札情報の推定だけでは強いプレイヤに
ならないことが確認できた．
3 層ニューラルネットワークを用いた提出手役評価関数の性能調査では，モンテカルロ法
プレイヤのプレイアウト部分に提出手役評価関数を適用することでプレイヤの強化を図っ
た．提出手役評価関数の性能を評価した結果，学習に使用する盤面データを増やすことで
提出手役の一致率が上昇し，盤面データ数 15,000 程度で充分に学習できていることが確認
できた．盤面データ数 15,000 の提出手役評価関数では，未知の盤面に対する提出手役一致
率がおよそ 69%となった．また，中間層数 50 の場合でも同様に，盤面データを増やすこと
で提出手役の一致率が上昇した．盤面データ数 27,000 までの提出手役一致率を調査したが，
一致率が頭打ちになっておらず，充分な学習にはこれ以上の盤面データが必要であることが
確認できた．対戦実験では，2012 年度のコンピュータ大貧民大会優勝プレイヤには勝てな
かったが，モンテカルロ法に対して提出手役評価関数を適用することでプレイヤが強化さ
れた．
今後の課題として，提出手役評価関数の改良と，棋譜の充実化が挙げられる．提出手役評
価関数の改良では，評価項目の設計を改良することや，序盤・中盤・終盤で使用する評価関
– 31 –
数を分ける，などの方法が考えられる．また，棋譜を充実化させることで，学習によって得
られたプレイヤの棋譜による再学習や，強い人間の棋譜による学習などを行えるようにな
る．改良された提出手役評価関数を用いて，充実化した棋譜からの学習を行うことで，強い
プレイヤを作り出すことができると考える．
– 32 –
謝辞
本研究の完遂にあたって，丁寧な御指導と的確なアドバイスをしていただいた高知工科大
学情報学群准教授松崎公紀先生に心より感謝し厚く御礼申し上げます．松崎先生には研究室
に所属してからの 4 年間本当にいろいろとお世話になりました．私自身，学生の研究という
ものはもっと孤独なものであると勝手に想像していたのですが，松崎先生には想像をはるか
に超えるレベルで親身になってサポートしていただきました．おいしい食べ物やお酒に対し
て経験的な知見を得られたことも，とてもありがたく感じています．
また，副査として本研究を支援して頂いた同学群教授福本昌弘先生，並びに，同学群准教
授吉田真一先生に深く感謝いたします．福本先生には，コンピュータリテラシーの TA でも
2 年間お世話になりました．おかげさまで，
「他人に対する物事の教え方」の良い勉強になり
ました．吉田先生には，学部時代にも私の卒業論文の副査を担当していただきました．学部
時代にいただいたアドバイスはその後の研究にも役立てることができたと思います．
また，日頃より本研究について熱心な討論と有益なアドバイスをしていただいた松崎研究
室の皆さまに感謝いたします．皆さまのおかげで，松崎研究室は実家のように居心地の良い
場所となりました．私の 4 年間の研究室生活はとてもとても有意義なものでした（ここには
書ききれないほどに）．
最後に，6 年間の学生生活を精神的にも経済的にも支えていただいた両親と両祖父母に対
して深く感謝し，謝辞とさせていただきます．
– 33 –
参考文献
[1] L. Kocsis and C. Szepesvári. Bandit Based Monte-Carlo Planning, 17th European
Conference on Machine Learning (ECML 2006), Lecture Notes in Computer Science 4212, pp. 282-293 (2006).
[2] M. Buro. Improving heuristic mini-max search by supervised learning. Artificial
Intelligence, Artificial Intelligence 134(1–2), pp. 85–99 (2002).
[3] P. Auer, N. Cesa-Bianchi and P. Fischer. Finite-time Analysis of the Multi-armed
Bandit problem. Machine Learning, Vol. 47, pp. 235–256 (2002).
[4] 池畑 望, 伊藤 毅志. Ms. Pac-Man におけるモンテカルロ木探索. 情報処理学会論文誌,
Vol. 52, No. 12, pp. 3817–3827 (2011).
[5] 伊藤 祥平, 但馬 康宏, 菊井 玄一郎. コンピュータ大貧民における高速な相手モデル作
成と精度向上. 数理モデル化と問題解決研究会報告, Vol. 2013-MPS-96, No. 4, pp.1–3
(2013).
[6] 金子 知適. 兄弟節点の比較に基づく評価関数の調整. 第 12 回ゲームプログラミング
ワークショップ, pp. 9–16 (2007).
[7] 金子 知適, 田中 哲朗, 山口 和紀, 川合 慧. 駒の関係を利用した将棋の評価関数. 第 8 回
ゲームプログラミングワークショップ, pp. 14–21 (2003).
[8] 金子 知適, 山口 和紀. 将棋の棋譜を利用した，大規模な評価関数の調整. 第 13 回ゲー
ムプログラミングワークショップ, pp. 152–159 (2008).
[9] 北川 竜平, 三輪 誠, 近山 隆. 麻雀の牌譜からの打ち手評価関数の学習. 第 12 回ゲーム
プログラミングワークショップ, pp. 76–83 (2007).
[10] 小沼 啓, 西野 哲朗. コンピュータ大貧民に対するモンテカルロ法の適用. 研究報告ゲー
ム情報学 (GI), Vol. 2011-GI-25, No. 3, pp.1–4 (2010).
[11] 佐藤 佳州, 高橋 大介. モンテカルロ木探索によるコンピュータ将棋. 情報処理学会論文
– 34 –
参考文献
誌, Vol. 50, No. 11, pp. 2740–2751 (2009).
[12] 島内 剛一, 有澤 誠, 野下 浩平, 浜田 穂積, 伏見 正則. アルゴリズム辞典. 共立出版株式
会社, pp. 804–806 (1998).
[13] 須藤 郁弥, 成澤 和志, 篠原 歩. UEC コンピュータ大貧民大会向けクライアント「snowl」
の開発. 第 2 回 UEC コンピュータ大貧民シンポジウム (2011).
[14] 須藤 郁弥, 篠原 歩. モンテカルロ法を用いたコンピュータ大貧民の思考ルーチン設計.
第 1 回 UEC コンピュータ大貧民シンポジウム (2010).
[15] 西野 順二, 西野 哲朗. 多人数不完全情報ゲームのモンテカルロ木探索における推定の
効果. 研究報告バイオ情報学 (BIO), Vol. 2011-BIO-27, No. 31, pp. 1–4 (2011).
[16] 西野 順二, 西野 哲朗. 大貧民における相手手札推定. 研究報告数理モデル化と問題解決
(MPS), Vol. 2011-MPS-85, No. 9, pp. 1–6 (2011).
[17] 保木 邦人. 局面評価の学習を目指した探索結果の最適制御. 第 11 回ゲームプログラミ
ングワークショップ, pp. 78–83 (2006).
[18] 前原 彰太, 橋本 剛, 小林 康幸. 局面評価関数を使う新たな UCT 探索法の提案とオセロ
による評価. 研究報告ゲーム情報学 (GI), Vol. 2010-GI-24, No. 5, pp. 1–5 (2010).
[19] 美添 一樹. モンテカルロ木探索:コンピュータ囲碁に革命を起こした新手法. 情報処理,
Vol. 49, No. 6, pp. 688–693 (2008).
[20] 竹内 聖悟. コンピュータ将棋の技術と GPS 将棋について. http://www.cybernet.
co.jp/avs/documents/pdf/seminar\ event/conf/19/1-3.pdf (2013).
[21] 美添 一樹. コンピュータ囲碁におけるモンテカルロ法 ∼ 理論法 ∼. http://entcog.
c.ooco.jp/entcog/contents/lecture/date/5-yoshizoe.pdf (2008).
[22] 第 2 回 将 棋 電 王 戦 HUMAN VS COMPUTER, http://ex.nicovideo.jp/
denousen2013/ (2013).
[23] 電 気 通 信 大 学. UEC コ ン ピュー タ 大 貧 民 大 会, http://uecda.nishino-lab.jp/
2012/ (2012).
– 35 –