発表資料

九州大学大学院システム情報科学府修士1年
末廣 大貴
コンピュータ将棋におけるカーネル法を
用いた静的評価関数の学習
目次
自己紹介
 研究背景
 関連研究
 提案手法
 実験
 今後の課題

自己紹介
九州は福岡から来ました
 研究室では主に機械学習について学んでます
 学部時代は将棋部で、機械学習がコンピュータ
将棋界で流行っていると聞き、研究を始める
 研究室は違うが、瀧本先生と共同研究してます
 そしてこの研究会を紹介されました

でもまさか一人で行くことになるとは・・・
将棋は「解ける」か?
ゲームのパターン数
オセロ
 チェス
 将棋
 囲碁

10の60乗
10の120乗
10の220乗
10の360乗
将棋をしらみつぶしに解くことはほぼ不可能
強い将棋コンピュータを作ろう
「強い」コンピュータ将棋を作るために

局面評価(形勢判断)の正確さ
正確な静的評価関数

先読み(探索)の速さ
枝刈り,並列化など
静的評価関数
入力:局面を表現するベクトル



駒の有無(駒割)
駒の位置関係
玉の危険度
出力:実数(評価値)
を重みベクトルとしたとき,
静的評価関数
例:駒の有無だけを考えた静的評価関数
例:駒の重み(手番で符号を入れ替える)
飛 角 金 銀 桂 香 歩 龍 馬 銀
成
成
桂
成
香
と
170 140 100
91
82
78
65
80
60
50
20
185 160
静的評価関数
先手は後手より
馬1枚得(+160)
角1枚得(+140)
で300点優勢
静的評価関数の作りかた
従来・・・人間の手作業による調整
大変な労力
 作成者の棋力,感覚に依存

ボナンザメソッド(保木,2006)
機械学習による、特徴ベクトルの重みの自動調整
問題提起
特徴ベクトルの要素は作成者が用意しなければ
ならない
→やはり作成者の感覚、棋力に依存
 実際、現在の強豪プログラムの多くは、将棋の
高度な知識が必要とされるような特徴ベクトルを
多く用い、学習を行っている

問題提起

局面の単純な情報のみから、必要な特徴を自
動的に作成し、学習できないか
提案手法
サポートベクターマシンとカーネル法に注目

サポートベクターマシン
カーネル法と相性の良い優秀な学習器

カーネル法
特徴ベクトルの要素同士の組み合わせから成る
新しい特徴を構成する(今回の手法の骨子)
SVM(サポートベクトルマシン)
座標上に学習サンプルが与えられる
超平面
マージン(超平面と一番近い例との距離)
が最大となるような超平面を作成
?
未知の例が与えられる
超平面に応じて分類
SVM(サポートベクトルマシン)
これは二次計画問題なので,効率よく
解くことが出来る
線形分離不可能なデータには性能が不十分
カーネル法

データを高次元の特徴空間上へ写像し、
SVMを線形分離不可能な問題にも対応させる
超平面
カーネル法

カーネル関数
先ほどの式の
を
に置き換え
るだけで,特徴空間上でのマージン最大化超平面
を求めることが出来る
多項式カーネル

次元の点を
像
例:
が2次元ベクトル、
次元の特徴空間に写
ガウシアンカーネル

無限次元の特徴空間に写像
カーネルを使えば,元の特徴のn項関係を特徴
とする特徴空間上で超平面を学習できる
提案手法
プロ棋士の棋譜を用意
 棋譜の全ての局面に対し

 プロが指した手の後の局面(棋譜の次局面)を正例
 その他の合法手後の局面を負例
とする

全ての局面を単純な特徴ベクトルで表したもの
を学習サンプルとして、SVMとカーネル法を用い
た学習を行う
提案手法

単純な特徴ベクトル(値は 0 or 1)の例
B[k][m]
 持ち駒kの枚数m H[k][m]
 盤上の位置pに駒kがある P[p][k]
 盤上の位置pに駒kが利いている E[p][k]
 盤上の駒kの数m
など
要素の数は,トータルで6000弱
提案手法

特徴ベクトルファイルの具体例
(SVMlight,LIBSVM形式)
ラベル B[歩][] B[香][] ・・
・
H[歩][
]
H[香][
]
・・
・
P[11][
]
・・
・
-1
8:1
28:1
・・・ 541:1
560:1 ・・・ 815:1 ・・・
-1
9:1
28:1
・・・ 542:1
560:1 ・・・ 815:1 ・・・
+1
8:1
28:1
・・・ 541:1
561:1 ・・・ 815:1 ・・・
対局方法
学習で得たSVMの超平面を用意
 局面の全ての合法手後の局面の単純な特徴ベ
クトルを書き出す
 超平面と局面のベクトル表現との内積をその局
面の評価値とする
 最も評価値の高い局面を選択する
 minimax法は用いない

学習から対局までの概略図
プロの指した
後の局面
その他の合法手
後の局面
SVMとカーネル
棋譜のある局面
学習から対局までの概略図
すべての合法手
後の局面
SVMとカーネル
対局中のある局面
1.05499
- 0.43635
0.53457
・
・
・
実験

以下のプログラム同士を対戦させた
 ランダムに指すプログラム
 10局学習したプログラム(カーネル法有る無し)
 20局学習したプログラム(カーネル法有る無し)
 Passive
Aggressive(オンラインアルゴリズム)の
カーネルなしで2000局学習
SVMlightを使用(http://svmlight.joachims.org/)
 カーネルは多項式カーネル(
)を用いた
 特徴ベクトルは先ほどあげた6000弱のもの
 全てに詰め将棋ルーチン(7手詰)を搭載

実験
相手
lin10 lin20 ker10
手番
先後 先後 先後
linear10
○
×
ker2
0
PA
rand
2000
勝敗
先後 先後 先後
×
×
× ×
×
○
○
○
4-0
×
×
×
×
○
×
○
○
4-0
○
○
○
○
○
○
10 - 0
○
○
○
○
8-0
○
○
4-0
linear20
×
○
kernel10
○
○
○
○
kernel20
○
○
○
○
×
×
PA
2000
○
×
×
○
×
×
×
×
random
×
×
×
×
×
×
×
×
×
×
0 - 10
重要な問題

なぜ最高で20局しか学習していないのか?
→学習サンプルがメモリに乗らない
(100局で約1.5G)
→サンプル数を増やすと,計算時間が急速に増
大
現在棋譜を50000局用意しているが・・・
課題
学習に時間がかかりすぎる(→並列化?)
 メモリに乗らない(→オンライン?)
 基本特徴ベクトルの追加(相対位置、王手など)
 SVMのパラメータの最適化
 やたら駒を切りたがるので,カーネルに期待しつ
つ,静的評価関数の正確さを測るため探索も入
れた方が良いかも
 ランキング問題として考えてみる
