スライド 1

Chikayama & Taura Lab.
M1 Ayato Miki
1
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
2

Features = elements to evaluate positions in
games
◦ e.g. Numbers and arrangements of pieces in Shogi

Difficulty in creating features
◦ Require expert knowledge for the game
◦ Simple linear combinations are insufficient
 e.g. XOR
3

Use kernels for evaluation features in games
◦ Simple inputs
 Tree structure
◦ Expect to work as non-linear features
 Implicit classification in high level feature space
4

Classification of moves in mahjong using SVM
with kernels
◦ “Evaluation functions > search” in mahjong
 Kernel method is effective
◦ Tree kernels for tree structures of mahjong hands
 Similarity representation by kernel functions
◦ Use expert game records
 Learn “expert moves > other moves” with SVM
5
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
6

Machine learning using simple features
◦ TD-Gammon [Tesauro, 1992]

Research about mahjong
◦ Learning from expert records [Kitagawa, 2007]
7
Game
Mahjong
Features
Manually picked
Method
Bonanza method
(without search)
Accuracy
56%
9
面前の持ち牌
面前の持ち牌2枚の組み合わせ
面前の持ち牌3枚の組み合わせ
鳴いた牌の構成と状態
面子数
リャンメン数
Features of player
カンチャン数とペンチャン数の和
トイツ数
テンパイしているかどうか
ドラの枚数
面前であるかどうか
親であるかどうか
リーチしているかどうか
自分が捨てたことのある牌
鳴いた牌の構成と状態
鳴いた回数
Features of
opponents
鳴いた牌の中で見えているドラの数
親であるかどうか
リーチしているかどうか
そのプレイヤに対する完全安牌
筋や壁などによって安全度が高い牌
自分との点差
Features of field
オーラスかどうか
見えていない牌の残り枚数
10
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
11
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
12

2-class linear classifier

 
g ( x)  w  x  b

g ( x)  1

g ( x)  0
1

w
2
Maxmize margin 
w
1

w

g ( x )  1
13

Method for non-linear classification


x   (x )


 ( x1 )   ( x2 )
 
K ( x1 , x2 )
Explicit
Replace
14
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
15
手牌
孤立牌
面子候補
面子
暗刻
リャンメン
カンチャン
ペンチャン
明刻
暗順 …
トイツ
Specific cards as leaves
16
孤立牌
リャンメン
カンチャン
ペンチャン
トイツ
暗刻
暗順
17
手牌
孤立牌
手牌
面子候補
リャンメン
面子
カンチャン
孤立牌
暗順
面子候補
リャンメン
面子
カンチャン
Count common subtrees
暗順
SST
手牌
…
…
…
リャンメン
…
リャンメン
…
面子候補
面子
リャンメン
暗順
…
面子候補
リャンメン
18

Deep subtrees are not very important
面子
暗順
暗順
暗刻

depth (0    1)
19
K t (t1 , t 2 ) 
  (n , n )
n1N t1 n2 N t2
1
2
F
(n1 , n2 )   
l ( fi )
i 1
I i (n1 ) I i (n2 )
Nt
Set of nodes in tree t
F  { f1, f 2 ,, f F }
Subtree set
l ( fi )
Depth of subtree fi
1
I i (n)  
0
If fi is rooted at node n
otherwise
20
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
21

SVM is just a 2-class classifier

If you want to know ranks of three moves…
◦ How learn to rank
( m1 , m2 )
m1  m2
( m1 , m3 )
m1  m3
( m2 , m3 )
m2  m3
Rank
m3  m1  m2
Order classifier ( > or < )
Input data -> Pairs of moves
22

One training example has two tree instances
ei  t , t
l
i

r
i
Label +1 when tl > tr
Label -1 when tl < tr
Define kernel function for relative order
Ktr (e1, e2 )  Kt (t1l , t2l )  Kt (t1r , t2r )  Kt (t1l , t2r )  Kt (t1r , t2l )
Classify “tl > tr” and “ tl< tr”
24
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
25
1.
Experiment of proposed method
2.
Error analysis
3.
Comparison with related work
4.
Practical player
26

Machine spec
◦ Dual-Core AMD Opteron 2.4GHz
◦ 32GB RAM

Implementation
◦ SVM-Light-TK [Moschitti, 2004]
 Soft margin trade-off parameter C=0.1
 Optimization threshold ε=0.1
27

Learn from tsumo positions in expert records
◦ “Offensive” positions only
 Nobody declares “li-zhi”
 Nobody calls 3 or more “chi”, “pon” or “kan”
◦ Using records of Totugeki Tohoku
 ~285 games (~13,000 training positions)

Evaluation
◦ Accuracy rates of trained classifiers
 Are expert moves ranked as the bests ?
◦ 4-fold cross validation
28
100%
90%
Accuracy rates
80%
70%
rank 1
rank 1-2
60%
rank 1-3
rank 1-5
50%
40%
30%
0
2000
4000
6000
8000
10000
12000
14000
Training positions
29

“Defensive” positions
31

Positions require “yaku”(=poker hands) knowledge
32

Using features designed in [Kitagawa, 2007]
◦ Including board status information

Implementation
◦ Ranking SVM in SVM-Light [Joachims, 2002]
34
100%
90%
Accuracy rates
80%
70%
rank 1
rank 1-2
60%
rank 1-3
rank 1-5
50%
40%
30%
0
5000
10000
15000
Training positions
35

Core2 Duo 1.06GHz
91819 support vectors
700ms for classification of one tree pair

7 seconds for deciding one move


◦ 4 seconds in dual threading
◦ Good enough for playing against human players
36
Introduction
Related work
Proposed method
1.
2.
3.
◦
◦
◦
4.
5.
SVM with kernels
Tree kernels in mahjong
Learning to rank using SVM
Experiment
Conclusion
37

Classified ranks of moves with tree kernels
◦ Possible with simple input

57% accuracy
◦ Despite the lack of information of field and
opponents
◦ Increasing…

Fine accuracy with permissible cost
38

Classification analysis

Refine tree structure

Other information
◦ Positions that linear combinations cannot classify
◦ Hands information with other kernels
 String kernels
◦ Information of field and opponents
 Add as linear combinations or other kernels

Heavy computing cost
◦ Classification time increases with a number of training
positions
◦ Indispensable in other games
39

Download Report