ゲーム構成要素を組み合わせた特徴の最適化

ゲーム構成要素を
組み合わせた特徴の最適化
東京大学
矢野友貴, 三輪誠
横山大作, 近山隆
1
評価関数の設計
• 評価関数の設計
– 従来：手作業による設計
• ゲームに対する深い知識が必要
• 特徴の選択や重みの調整に膨大な時間と手間
– 近年：組み合わせ特徴の利用
• 知識に依らないシンプルな特徴
• 機械学習を利用した自動調整
2
組み合わせ特徴
• ゲーム構成要素を組み合わせた特徴
– 将棋では, [駒の種類]×[絶対位置]
• これを複数駒間で組み合わせる
– Ex) Bonanza (玉を含む3駒間の組み合わせ)
６
５
４
角
歩
三
銀
金
二
四
▲５三歩
▲６三金
▲５三歩
△４二角
▲５三歩
△５四銀
▲６三金
△４二角
▲６三金
△５四銀
△４二角
△５四銀
2駒間の組み合わせ特徴
3
組み合わせ特徴
• 組み合わせ特徴の問題点
– 組み合わせ爆発, 冗長性
– 計算資源による制約
限定的な利用
• 提案：ゲーム構成要素間の関連性に注目し
た組み合わせ特徴の絞り込み
– 局面評価に有効そうな組み合わせの抽出
• cf) 実現確率探索
– 将棋を対象に評価
4
本研究の貢献
• 局面評価に有効そうな組み合わせ特徴の絞
り込みを行う新しい手法の提案
• 高次の組み合わせ特徴の利用の実現
• 将棋における高次組み合わせ特徴の有用性
の評価
5
本発表の流れ
• 関連研究
• 提案手法
• 評価設定
• 実験
• おわりに
6
本発表の流れ
• 関連研究
• 提案手法
• 評価設定
• 実験
• おわりに
7
組み合わせ特徴と評価関数
• 駒の2項関係による評価関数 [T. Kaneko, et al., 2003]
– 既存の多くの評価要素
駒の2項関係として表現可能
– 2駒間では十分に表現できない特徴も
• Ex) 駒によって遮られている長距離効き
• 詰み評価関数の自動生成 [M. Miwa, et al., 2005]
– 「駒の位置」, 「利き」を組み合わせた特徴の抽出
• 飽和頻出パターン抽出, カイ二乗値による絞り込み
– 最大23要素の組み合わせ特徴
• 人手の評価関数に近い精度を実現
碁石のパターンへのハッシュ利用
[D. Silver, et al., 2007]
• 碁石の配置パターン (最大5x5)を利用した評価関数
– 4x3以上のパターンをハッシュにより圧縮
ハッシュ値が同じ
パターンで重みを共有
“D. Silver, et al., Reinforcement learning of local shape in the game of go, IJCAI’07”
より表を引用
8
実現確率探索
[Y. Tsuruoka, et al., 2002]
9
• 局面の実現確率を用いた可変深さ探索
– 各指し手の遷移確率を用いて実現確率を算出
– 遷移確率は棋譜から導出
• Ex) 激指ではロジスティック回帰を利用
現在の局面の実現確率
(遷移確率)
(実現確率)
Px  Pm  Px
指し手の
遷移確率
直前の局面の
実現確率
“Y. Tsuruoka, et al., Game-tree search algorithm based on realization probability, ICGA Journal 2002”
より図を引用
10
本発表の流れ
• 関連研究
• 提案手法
• 評価設定
• 実験
• おわりに
11
アプローチ
• 盤面を駒や升で構成されたグラフと考える
– 各ノードには「種類, 位置」のラベル
• 組み合わせ特徴 = グラフ上のパス
– パスの総数はとても多く, すべては展開困難
パスに重要度を定義して枝刈り
A
パス
B
A
B
B
C
・・・
D
・・・
E
C
D
展開
C
・・・
12
提案手法の評価関数
減衰定数により長いパス
(=高次組み合わせ特徴)の影響度を調整
f (w, G)   wii (G)
where i (G) 
i
d : パスの大きさの上限

| p|1
pG ,1| p| d , h ( p ) i ,
importance ( p ) threthold
重要度の高いパス
のみを利用
p : グラフ中のパス
h(p) : pのハッシュ値
λ : 減衰定数
ハッシュ関数を用いることで
パスのインデックスを計算
13
パスの展開と枝刈り
• 各要素間 (エッジ) に結合度を定義
– パスの重要度 = パス上のエッジの結合度の積
– 重要度が閾値以下のパスを枝刈り
選択されたパス
「A-B」, 「A-B-C」, 「A-B-D」, ・・・
0.5
0.5
0.4
0.2
C
B
1.0
0.08
B
cut
0.08
0.3
0.15
A
C
0.1
D
cut
E
0.05
・・・
閾値 = 0.1
最大長さ = 3
14
ハッシュ関数によるインデックス
• パスのインデックス
パスのハッシュ値
– Zobrist Hash [Zobrist, 1970] を利用
– 特徴の総数をハッシュサイズに抑え込む
• 2種類のハッシュ
– グラフのノードに乱数 (パスの経路を考慮しない)
– グラフのエッジに乱数 (パスの経路を考慮する)
rand(A)
rand(B)
rand(C)
A
B
C
rand(A-B)
rand(B-C)
hash(A-B-C)
= rand(A) ^ rand(B) ^ rand(C)
OR
= rand(A-B) ^ rand(B-C)
15
本発表の流れ
• 関連研究
• 提案手法
• 評価設定
• 実験
• おわりに
16
評価環境
• 将棋プログラム「激指」を利用
– 第20回世界コンピュータ将棋選手権のバージョン
• 激指の評価関数を変更することで実験
– 探索ルーチンには激指オリジナルを使用
– 評価関数のパラメタを学習させて評価
17
学習方法
• 「激指」の学習で用いられた手法を利用
– Bonanza Method [K. Hoki, 2006]
– Averaged Perceptron [M. Collins, 2002]
• プロ, アマ混合の30,000棋譜を用いて学習
– 探索はルート局面から深さ6相当
– 各局面で棋譜以外の手は16手をランダムに選択
18
評価関数
• ベースとして単純な駒割を利用
– 評価関数 = 駒割 + 各種手法
• 各種手法
– 提案手法：駒グラフ, 利きグラフ
– 比較手法：all_two, kkp_kpp, atkk
19
駒グラフと利きグラフ
６
５
４
駒グラフ
角
歩
三
銀
金
二
四
• 駒を全対全で結んだグラフ
• ハッシュの計算
ノード基準
• エッジの結合度
– 棋譜からロジスティック回帰により推定 (後述)
パスの長さの最大値は4に制限
６
５
４
角
二
歩
三
銀
金
利きグラフ
四
• 駒と升を利き (含む間接利き) で結んだグラフ
– パスの起点は駒に限定
• ハッシュの計算
エッジ基準
• エッジの結合度
– 利きがある：1.0, 利きがない：0.0
20
棋譜を利用した結合度の学習
• 「エッジ = 2駒間の関係」として学習
– LIBLINEAR (ロジスティック回帰, LR) を用いて学習
– 学習用の棋譜から訓練データを作成
データのラベルをチェック
y = +1 (if t0 == 先手),
-1 (if t0 == 後手)
t0
棋譜の手
t1
t2
・・・
tn
訓練データ (x, y)
ランダムに一つ手 (tj) を選択
エッジの差分を計算
x = edges(t1) – edges(tj)
21
学習された結合度の分布
• エッジの重み (w_e) を結合度 (p_e) に変換
pe,i
1

1  exp we,i 
※予稿集とは式が異なるので注意
8
p_e,i
正例 : p_e, i (p_e,i > 0.5)
6
占有率 (%)
4
2
0
2
4
6
負例 : 1,0 - p_e, i (p_e,i < 0.5)
8
0.5
0.6
0.7
0.8
p_e,i
0.9
正例(%)
負例(%)
0.9~1.0
0.016822
0.015848
0.8~0.9
0.058717
0.060234
0.7~0.8
0.236484
0.231238
0.6~0.7
2.387789
2.412282
0.5~0.6
25.243782
25.229019
計
27.942289
27.948621
※ p_e,i = 0.5 (i.e. w_e,i = 0) は含めていない
1.0
22
結合度の利用方法
• LRでは正例の分類確率が得られる
– 得られた結合度をそのまま扱うのは不適切
• 正例・負例で別々に重要度を計算
A
正例
負例
0.8
0.8
B
×
0.4
0.4
C
×
0.7
0.7
(1.0 - 0.8) × (1.0 - 0.4) × (1.0 - 0.7)
D
=
0.224
=
0.036
どちらかが閾値を超えるかチェック
23
比較手法
ハッシュを利用する乱数の設定
特徴
名前
用いない
all_two
2駒の全組み合わせ
kkp_kpp
2玉と1駒の全組み合わせ
1玉と2駒の全組み合わせ
ノードに付与
atkk
2駒の全組み合わせ
2玉と1駒の全組み合わせ
1玉と2駒の全組み合わせ
ノードに付与
※条件をそろえるために, 提案手法で生成する盤面グラフを用いて実装
24
評価方法
• 評価基準は次の3つ
基準
詳細
一致率
学習に用いなかった500棋譜で計測
不一致度
学習に用いなかった500棋譜で計測
勝率
初手30手を固定（100局面, 先手後手で計200試合）
1手あたりの探索ノード数を50万ノードに制限
※不一致度は以下の式を用いて計算
(M:棋譜の手以外の手の集合, t:最善応手手順後の局面)

1 N
不一致度   T wT  (t j )  wT  (t1 )
N i 0 jM i

1
T ( x) 
1  exp 3x / 100
25
本発表の流れ
• 関連研究
• 提案手法
• 評価設定
• 実験
• おわりに
26
実験
1. 駒グラフにおける4要素パターン
2. 駒グラフにおける枝刈りの閾値と精度
3. 既存手法との比較
a. all_two, kkp_kpp, atkkとの比較
b. 激指の既存評価関数を用いた比較
※実装の見直し, 手法の変更に伴い予稿集とは以降の結果が異なるので注意
27
1. 駒グラフにおける4要素パターン
• テスト用の500棋譜中の30～70手目の局面で
のパターンを列挙
– 重要度の高い4要素のパターンのうち上位100パ
ターンを抽出
– 既存手法との比較実験で得られた重みを用いて
パターンの評価値も調べる
• 減衰定数を0.5として計算
• パターンは重複してカウントさせるため, 最終的な評価
値は2倍の値を表記している
28
重要度が最も高いパターン
抽出されたパターン
▲２七歩 , ▲２八飛, ▲３七角, ▲３六歩
重要度
-0.779690
評価値
-45.6940
評価値の詳細
サブパターン
重み
▲２七歩 , ▲２八飛
-37.8101
0.5
▲２八飛, ▲３七角
-9.5258
0.5
▲３七角, ▲３六歩
-2.4587
0.5
▲２七歩 , ▲２八飛, ▲３七角
-0.7845
0.25
▲２八飛, ▲３七角, ▲３六歩
8.0595
0.25
▲２七歩 , ▲２八飛, ▲３七角, ▲３六歩
1.8526
0.125
“CC Resources for Shogi Applications”, http://www.muchonov.com/bona/
より画像の素材を利用
減衰
29
評価値が最も大きいパターン
抽出されたパターン
△１四歩 , △２二玉, △３二金, △２三歩
重要度
+0.621807
評価値
-192.9503
評価値の詳細
サブパターン
重み
△１四歩 , △２二玉
-25.9238
0.5
△２二玉, △３二金
-98.9921
0.5
△３二金, △２三歩
-33.7543
0.5
△１四歩 , △２二玉, △３二金
-21.1438
0.25
△２二玉, △３二金, △２三歩歩
-38.5311
0.25
△１四歩 , △２二玉, △３二金, △２三歩
-17.7706
0.125
“CC Resources for Shogi Applications”, http://www.muchonov.com/bona/
より画像の素材を利用
減衰
30
2. 駒グラフにおける枝刈りの閾値と精度
• 駒グラフに関して, パス生成時の閾値の違い
による精度の変化を調査
– 閾値：0.4, 0.45, 0.5, 0.55, 0.6
– 減衰定数は予備実験によって調整
– ハッシュサイズは2^24に統一
31
枝刈り閾値と精度の関係
閾値
11
10
精度が向上
不一致度
9
8
有効特徴数
一致率
不一致度
赤：0.4
8,452,262
37.8672
4.66838
緑：0.45
4,090,410
37.4666
4.70421
青：0.5
2,352,143
37.0758
4.78376
紫：0.55
605,469
35.7126
5.13301
201,162
水：0.6
精度の向上が鈍い
34.7554
5.59606
高次の特徴選択の正確さが低い可能性
※有効特徴数：非零のパラメタの総数
7
6
大
5
小
4
0
5,000
10,000
閾値0.5前後で
20,000
25,000
棋譜数精度に開き
15,000
30,000
閾値
32
3-a. 既存手法との比較
• 利きグラフ, 駒グラフを用いた提案手法を既
存手法 (all_two, kkp_kpp, atkk) と比較
– 既存手法についても提案手法と同様に予備実験
により減衰定数を調整
– all_two以外はハッシュサイズを2^24で統一
– 速度はXeon X5560(2.8GHz)で測定
33
探索速度の比較
300,000
赤：速度
緑：平均評価特徴数
2,500
2,000
200,000
156,520
150,000
126,201
1,500
112,472
100,000
74,691
50,000
1,000
平均評価特徴数
探索速度 (nodes/sec)
250,000
275,578
3,000
500
0
0
all_two kkp_kpp
atkk
koma
kiki
※平均評価特徴数：局面評価で出現する特徴数の平均
34
精度・対戦比較
kkp_kppも精度で他に劣る
学習期間が足りない可能性
各種手法の有効特徴数と精度
手法
有効特徴数
一致率
不一致度
all_two
1,585,855
37.8710
4.77810
kkp_kpp
15,701,153
36.5022
5.06266
atkk
15,737,354
37.7703
4.67875
koma
8,452,262
37.8672
4.66838
kiki
16,777,214
36.7603
5.01192
駒グラフは不一致度が最も良い
駒グラフは既存手法と同程度の強さ
提案手法の比較手法及び相互対戦での勝率 (%)
利きグラフは精度で他に劣る
all_two
kkp_kpp
atkk
koma
kiki
＼
利きのない組み合わせ特徴が欠落するため
koma
50.0
60.0
48.0
kiki
39.0
50.0
39.5
利きグラフは既存手法に対して負け越す結果
53.0
47.0
35
3-b. 激指の評価関数を用いた比較
• 激指の評価関数を利用した場合を評価
– 評価関数 = 激指の評価関数 + 各種手法
• パラメタの初期値として激指オリジナルを用いる
• 減衰定数は再調整
• 激指の評価関数部分にはハッシュを用いない
36
精度・対戦比較 with 激指
各種手法の有効特徴数と精度
手法
有効特徴数
none
一致率
不一致度
350,730
39.1640
3.77321
all_two
1,872,374
40.8526
3.59242
kkp_kpp
15,488,058
40.8386
3.57085
atkk
15,617,337
41.0516
3.53186
koma
8,180,896
41.0482
3.54278
kiki
17,127,676
41.3484
3.53955
利きグラフの精度が大きく向上
提案手法の比較手法及び相互対戦での勝率
(%)
空升も用いた組み合わせ特徴なのが影響した可能性
既存手法に対して同程度以上の成績
＼
none
all_two
kkp_kpp
atkk
koma
57.5
52.5
44.0
52.5
kiki
58.0
52.0
46.0
50.5
koma
kiki
52.5
47.5
※none
: 激指の評価関数をそのまま学習したもの
kkp_kppに対しては精度と逆の成績に
37
提案手法に関するまとめと考察
• 提案手法における2つのグラフ
– 駒グラフ
• 既存手法を包括する特徴群であり, 単体でも精度大
• 閾値実験及び比較実験において精度向上
高次組み合わせ特徴の有用性
– 利きグラフ
• 疎なグラフとなるため, 単体では精度が出ない
• 激指の評価関数と併用することで効果あり
利きを用いた組み合わせ特徴の有用性
38
本発表の流れ
• 関連研究
• 提案手法
• 評価設定
• 実験
• おわりに
39
おわりに
• 組み合わせ特徴の絞り込むことで, 高次組み
合わせ特徴の活用法を提案
– 4要素までの組み合わせ特徴の利用の実現
– 既存手法と同程度以上の精度を獲得
• 今後の課題
– 空升の情報の活用
– 組み合わせ特徴の選別, 利用方法の改善
ご清聴ありがとうございました

Download Report