スライド 1

東京大学大学院
三木理斗 三輪誠 近山隆
1.
2.
3.
4.
5.
背景
関連研究
提案手法
実験
結論
1

麻雀
◦ 多人数
◦ 不完全情報
◦ 鳴き

Minimax探索の適用が困難
◦ 戦略が複雑
◦ 局面状態が不確定
◦ 手番の不規則な変化
2

麻雀の打ち手の探索
◦
◦
◦
◦
戦略の推定
不完全情報の推定
評価関数
手番の割り込み

これらの課題に対応したい

知識を用いずシミュレーションで手を求める
3
1.
2.
3.
4.
5.
背景
関連研究
提案手法
実験
結論
5

Minimax探索の拡張

UCT探索
◦ *-Minimax探索(不確定ゲームへの拡張)
◦ Maxn探索(多人数ゲームへの拡張)
◦ 多人数ゲームへの拡張
◦ 不完全情報ゲームへの拡張

麻雀に関する研究
◦ 牌譜を用いた評価関数の重み調整 [北川ら, 2007]
◦ 木カーネルを用いた打ち手の順位学習 [三木ら, 2008]
6



Chanceノードの評価値は子ノードの期待値
不完全情報ゲームでは探索空間が大きすぎる
鳴きがある麻雀では枝刈りが難しい
7

それぞれのプレイヤが自分
の評価値を最大にする

評価値最大の手が複数ある
場合には任意に選ぶ

戦略モデルが必要

評価関数が必要
8

UCB値が最大の子ノードを探索する(UCB1方策)
ln T
UCB i  X i  C
Ti
知識項

探索項
Xi
:子
i
の平均報酬
Ti
:子
i
の探索回数
T
:親の探索回数
C
:バランス定数
未探索ノードから先はプレイアウトを行う
◦ ランダムor知識利用
◦ 終局の結果を報酬として観測
9
ゲーム
ダイヤモンドゲーム
プレイアウト方策
ε-greedy (ε=0.05)
プレイアウト回数
50000
対戦相手
Maxn探索
勝率
73%
*プレイアウト方策とMaxn探索での評価関数は
敵の駒を無視したときのゴールまでの総距離
10
ゲーム
スカート
局面生成
持っていないスートを推定
プレイアウト方策
ヒューリスティック
プレイアウト回数
約4000 (1秒)
対戦相手
ヒューリスティックプレイヤ
人間
性能
やや及ばない
11
ゲーム
麻雀
評価関数
3層ニューラルネット
特徴要素
boolean
学習
Comparison training
(探索なし)
一致率
56%
12
ゲーム
麻雀
評価関数
SVMによる順位付け
特徴要素
木構造
学習
木カーネルSVM
一致率
53%
13
1.
2.
3.
4.
5.
背景
関連研究
提案手法
実験
結論
15

麻雀の打ち手をUCTアルゴリズムで探索する
◦ UCB1方策で手を決定
 高度な戦略の推定を必要としない
◦ 不完全情報はランダムシミュレーション
 膨大な探索を必要としない
◦ ランダムプレイアウト
 評価関数を必要としない
◦ 鳴きによる手番の割り込みにも適用できる
16
1.
局面の見えていない部分をランダム生成する
2.
UCTアルゴリズムを1ループ行う
3.
1,2を繰り返す
4.
最も平均報酬の高い手を選択する
17
相手の手牌と牌山をランダムに割り当てる
18
14牌ノード
13牌ノード

どの牌を切るか、またはカンするか

UCB1方策によって手を決定
19
13牌ノード
14牌ノード
対面がポン
下家がチー
誰も鳴かない
(下家がツモ)

ポンするか、鳴かないか
チーするか、鳴かないか

選択権の高いプレイヤ順にUCB1方策によって決定

20

終局までランダムプレイアウト
東
南
西
北

-4000
+8000
-2000
-2000
結果を報酬として経路上のノードを更新
21
1.
2.
3.
4.
5.
背景
関連研究
提案手法
実験
結論
22

実験環境

実装

実験方法
◦ Core2 Duo 3GHz
◦ 2GB RAM
◦ C++
◦ 約2000~数万プレイアウト/秒
◦ 一致率評価
◦ コンピュータおよび人間との対戦
23

牌譜との一致率評価

各種パラメータ
◦ 報酬は得点収支
◦ UCB値のC=1000
24
14牌ノード(ツモ局面)
100.0%
一致率
90.0%
3位以内率
80.0%
5位以内率
ランダム
70.0%
一致率

線形SVM
60.0%
50.0%
40.0%
30.0%
20.0%
10.0%
0.0%
100
1000
10000
プレイアウト回数
100000
27
13牌ノード(鳴き局面)
100.0%
90.0%
80.0%
70.0%
一致率

60.0%
50.0%
40.0%
30.0%
UCT
20.0%
ランダム
10.0%
SVM
0.0%
100
1000
10000
100000
プレイアウト回数
28

縦軸は一致率
100.0%
100.0%
90.0%
90.0%
80.0%
80.0%
70.0%
70.0%
60.0%
60.0%
50.0%
50.0%
40.0%
40.0%
30.0%
UCT
30.0%
UCT
20.0%
ランダム
20.0%
ランダム
10.0%
10.0%
SVM
0.0%
100
1000
10000
プレイアウト回数
牌譜で鳴いた局面
SVM
0.0%
100000
100
1000
10000
100000
プレイアウト回数
牌譜で鳴かなかった局面
29

プレイアウトを増やすととにかく鳴く

ランダムプレイアウト中にあがることはほとんどない
◦ 報酬のほとんどがノーテン罰符
◦ 流局テンパイを目指している
30

コンピュータプレイヤと対戦
◦ グリーディプレイヤ(シャンテン数最小化+ランダム)
◦ SVMによる評価関数のプレイヤ

人間と対戦
◦ 東風荘のRatingで評価
31
グリーディ対UCT(100試合400局)
プレイヤ
Greedy A
UCT A
Greedy B
UCT B
あがり率[%]
13
23
16.5
23.25
平均収支
-624.5
478.25
-269.25
402
SVM対UCT(100試合400局)
プレイヤ
SVM A
UCT A
SVM B
UCT B
あがり率[%]
16.75
19
22.5
21.5
平均収支
-458.5
399
118.75
-62.5
32








第一東風荘(東風戦 食いタンあり ノーテン親流れ)
1手5秒
123試合631局
R976 (安定R849)
あがり率 15.8%
放銃率 22.0%
2鳴き率 30.3%
平均収支 -716
33
1.
2.
3.
4.
5.
背景
関連研究
提案手法
実験
結論
34

麻雀の打ち手をUCT探索によって求めた

ツモ局面で 46% の最善手一致率
◦ 知識を用いなくてもSVMなどに匹敵する性能

問題点
◦ プレイアウトではほとんどあがれていない
◦ 流局テンパイを目指す打法
◦ 無駄な鳴きが増えてしまい、振り込みも多い
35

知識の導入
◦ 不完全情報の推定
 相手の手牌をそれらしく推定する
◦ プレイアウト
 ヒューリスティックを用いてあがれるように打つ

UCT探索の効率化
◦ FPU・・・未探索ノードのUCB値を下げて木の成長を加速
◦ UCB1-TUNED・・・パラメータCの動的制御
◦ 残り時間を考慮した枝刈り
36