将棋ソフトウェアにおける棋譜データの利用と機械学習

将棋ソフトウェアにおける棋譜

データの利用と機械学習

佐藤 佳州

筑波大学システム情報工学研究科

パナソニック株式会社先端技術研究所

1

目次

コンピュータ将棋の現状とこれまでの歴史

ゲームの基本的なアルゴリズム

将棋における棋譜を利用した知識獲得

今後の研究動向

まとめ

2

目次

コンピュータ将棋の現状とこれまでの歴史

ゲームの基本的なアルゴリズム

将棋における棋譜を利用した知識獲得

今後の研究動向

まとめ

3

コンピュータ将棋とは

•

人間の指示なしに，コンピュータ自身が考え，指し手

を返すプログラム

•

様々な将棋ソフトが存在

•

Bonanza，GPS将棋，激指，YSS（AI将棋），Ponanza，…

•

年に１回，世界一のプログラムを決定するための，

世界コンピュータ将棋選手権

_{が開催されている}

•

今年はBonanzaが優勝

•

ハードウェア制限なし

（GPS将棋：東大の教育用計算機で参加：3000コア以上）

•

学問的には，人工知能の一分野

4

電王戦

•

コンピュータ将棋が一躍注目を集めたイベント

•

第一回（2012年）

•

米長永世棋聖にコンピュータが勝利

⇒

かつての名人を破る

•

第二回（2013年）

•

現役プロとの対局において，コンピュータが

３勝１敗１分

⇒

初めて現役のプロに勝利

たった１０人しかいない

A

級棋士に勝利

5

コンピュータ将棋の歴史

2000年代後半から急速に強くなる ⇒

機械学習の成功

＋

並列探索の導入

実現確率探索

詰将棋

アルゴリズム

アマチュア高段者

ルール通りに指す アマチュア低級者

プロ中級

並列探索

クラスタ探索

評価関数の機械学習

初めての

プログラム

枝狩り手法の充実

2010

2000

1990

1980

強さ

技術

動向

手作業による評価関数

選択探索

合議

（現在）

6

目次

コンピュータ将棋の現状とこれまでの歴史

ゲームの基本的なアルゴリズム

将棋における棋譜を利用した知識獲得

今後の研究動向

まとめ

7

ゲームの基本的なアルゴリズム

•

人間は，

「読み」

と「大局観」

で指し手を決定

•

コンピュータの場合，それぞれ

「探索」

と「評価関数」

で実現

ゲームの基本的なアルゴリズム

•

人間は，

「読み」

と「大局観」

で指し手を決定

•

コンピュータの場合，それぞれ

「探索」

と「評価関数」

で実現

▲７六歩

_▲２六歩

考えられる手を

すべて展開していく

（図では省略）

_{探索深さ ＝ １}

9

ゲームの基本的なアルゴリズム

•

人間は，

「読み」

と「大局観」

で指し手を決定

•

コンピュータの場合，それぞれ

「探索」

と「評価関数」

で実現

▲７六歩

_▲２六歩

考えられる手を

すべて展開していく

（図では省略）

△３四歩

△２六歩

_△３四歩

△５二玉

探索深さ ＝ ２

10

ゲームの基本的なアルゴリズム

•

人間は，

「読み」

と「大局観」

で指し手を決定

•

コンピュータの場合，それぞれ

「探索」

と「評価関数」

で実現

▲７六歩

_▲２六歩

考えられる手を

すべて展開していく

（図では省略）

△３四歩

△２六歩

_△３四歩

△５二玉

▲２六歩

▲１八香

▲７七角

▲９八香

▲７６歩

▲５八玉

探索深さ ＝ ３

11

ゲームの基本的なアルゴリズム

•

人間は，

「読み」

と「大局観」

で指し手を決定

•

コンピュータの場合，それぞれ

「探索」

と「評価関数」

で実現

▲７六歩

_▲２六歩

終局までは探索できないため，ある程度の深さで探索を打ち切る

△３四歩

△２六歩

_△３四歩

△５二玉

▲２六歩

▲１八香

▲７七角

▲９八香

▲７６歩

▲５八玉

探索深さ ＝ ３

12

ゲームの基本的なアルゴリズム

•

人間は，

「読み」

と「大局観」

で指し手を決定

•

コンピュータの場合，それぞれ

「探索」

と「評価関数」

で実現

▲７六歩

_▲２六歩

△３四歩

△２六歩

_△３四歩

△５二玉

▲２六歩

▲１八香

▲７七角

▲９八香

▲７６歩

▲５八玉

探索深さ ＝ ３

末端局面の優劣を

評価関数

で数値化

+10

-2

+3

-8

+15

₊₅

13

ゲームの基本的なアルゴリズム

•

人間は，

「読み」

と「大局観」

で指し手を決定

•

コンピュータの場合，それぞれ

「探索」

と「評価関数」

で実現

【最善手▲７六歩】

▲２六歩

△３四歩

△２六歩

_△３四歩

△５二玉

▲２六歩

▲１八香

▲７七角

▲９八香

▲７６歩

▲５八玉

+10

-2

₊₃

-8

+15

₊₅

+10

₊₃

_-8

₊₁₅

-8

+3

+3

自分の手番 では，評価値が最大になるノードを，

相手の手番 では，評価値が最小となる（相手に取って最大になる）

ノードを，選択する

14

ゲーム木探索の難しさ（研究内容）

•

探索： よさそうな手を深く探索したい

（無駄な手は探索したくない）

•

評価関数： 局面の優劣を正確に

数値化することは困難

15

棋譜を利用した機械学習

（今回は評価関数に焦点）

評価関数とは（１）

•

局面の優劣を数値化する関数

評価関数

-４５ （互角）

評価値

16

評価関数とは（２）

•

評価関数の例

• 従来は数千以上のパラメータ

を手作業で調整

• 人間の知識を正確に数値に

落としこむのは困難

機械学習が成功

[保木 2006]

将棋プログラムの飛躍的な

性能向上に繋がる

17

目次

コンピュータ将棋の現状とこれまでの歴史

ゲームの基本的なアルゴリズム

将棋における棋譜を利用した機械学習

今後の研究動向

まとめ

18

棋譜を用いた評価関数の学習

•

機械学習（教師あり学習）とは ：

教師データ（棋譜）を用いて，パラメータを自動調整する

19

エキスパートの棋譜

各パラメータを

自動で決定

【将棋における評価関数の学習】

棋譜と同じ手を選択できるようにパラメータを学習する

（人間の真似を目指す）

※ 以降，具体的な学習手法の概要を説明

Comparison Training [Tesauro 2001]

•

評価関数学習の最も一般的な学習手法

•

棋譜中の

エキスパートの指し手とその他の合法手を比較

20

教師局面

棋譜中の指し手

その他の

_合法手

αβ探索

末端局面

（評価局面）

エキスパートの指し手の評価が，その

他の合法手の評価を十分に上回るよう

に評価関数を学習

Comparison Training [Tesauro 2001]

2013/12/16-18 NINSコロキウム 分科会

21

Training position

Experts’ move

Other legal

_moves

Alpha-beta

search

Leaf

positions

𝐽

₁

(𝑃, 𝒗) = 𝑇 𝜉 𝑝

_𝑚

, 𝒗 − 𝜉 𝑝

₁

, 𝒗

𝑀

_𝑝

𝑚=2

𝑝∈𝑃

目的関数

𝑃

: 学習局面の集合

𝑀

_𝑝

: 局面 𝑝

における合法手の数

𝑝

_𝑚

: 局面 𝑝 において指し手 𝑚 を選択した時の局面

(𝑚 = 1：棋譜中の指し手）

𝜉 𝑝

_𝑚

, 𝒗 : 𝑝

_𝑚

において，αβ探索を行った時の結果（評価値）

𝒗

: 評価局面の特徴

𝑇(𝑥)

: シグモイド関数

棋譜中の指し手の

評価値

その他の合法手

の評価値

•

チェスでも一部同様の手法が取り入れられる（Deep Blue）

•

将棋への応用[保木 2006]で大きな効果

学習データの規模

•

将棋の評価関数に用いられている学習データの規模

⇒ 見た目以上にずっと大きい

数万局

_{の棋譜から学習}

一般的な認識

_{それってビッグデータなの？}

実際には

…

数百万局面

から学習

1棋譜に百局面

程度含まれる

数億手

_から学習

_{実際には膨大なデータを処理}

1局面に数百手

含まれる

•

手作業では不可能だった，数十万以上のパラメータ調整が可能に

•

計算機の性能向上が，機械学習成功の大きな後押し

22

目次

コンピュータ将棋の現状とこれまでの歴史

ゲームの基本的なアルゴリズム

将棋における棋譜を利用した知識獲得

今後の研究動向

まとめ

23

現在の評価関数の性能

•

評価関数の性能 ＝ 局面の優劣を正しく判断する能力

•

理想的な評価関数があれば，探索は不要（極論）

プログラム

レーティング

※ 本番用

約

3000～

gps_l （

学習／古いマシン）

2523

gps_normal （手調整／古いマシン）

2150

gps500 （ほとんど探索しない）

1583

【参考】Floodgate (東大： http://wdoor.c.u-tokyo.ac.jp/shogi/)

コンピュータ同士を自動対局させ，レーティングを出すサーバー

学習による強さの向上

も大きいものの，

実際には探索による

強さの向上はレーテ

ィング的にはそれ以上

現在の将棋プログラムの強さ

＝ 評価関数（以前より人間に近づく）

＋ 探索（人間を凌駕）

まだ改良の余地は大きい

24

今後の研究動向

（＋自分の研究）

•

将棋の場合，近いうちに人間のプレイヤに勝つことは確実

•

ただし，評価関数については，人間の評価能力（大局観，表現力）を獲

得したというわけではなく，さらなる研究の余地は大きい

【今後の研究課題】

（例）



特徴学習

（Feature Learning，Representation Learning）

•

データから，どのような特徴を評価するかという特徴自体を学習

•

（参考）Deep Learning



強いプログラムを学習するための

目的関数の学習



どのような学習棋譜が強いプログラムを生み出すか？

同じ学習棋譜でも，学習方法が異なれば，得られる知識は全く異なる

25

目的関数の学習 [Sato et al. 2013]

•

単純なComparison Trainingが学習してくれることはそれほど多くない

＝ プロの棋譜（指し手）との全体的な一致率の向上のみ

26

𝐽

(𝑃, 𝒗) = 𝑇 𝜉 𝑝

, 𝒗 − 𝜉 𝑝

, 𝒗

【課題】

•

勝敗に直結する局面で最善手を指したい

•

評価値の差の制御が考慮されていない

【手法】

•

学習局面の性質に応じて，一致の重要度，正解手と不正解手の評価値の

差を制御するパラメータ等を目的関数に導入

•

導入されたパラメータは，学習されたプログラムの強さを適応度とした進化

的計算で学習 ⇒

強くなるように棋譜を真似する目的関数を学習

•

従来手法と比較して，

6割程度の勝率を得る

どのような学習棋譜が有用か？（戦術）

27

順位

戦術

重要度の平均

1

四間飛車穴熊 － 銀冠

1.121

2

居飛穴模様 － 藤井システム

1.100

3

森下システム － △９五歩８四歩型

1.088

4

▲４七銀３七桂 － 金矢倉

1.079

5

相掛かり▲２六飛 － △５四歩型

1.061

・・・

・・・

・・・

96

居飛車穴熊 － 本美濃

0.951

97

矢倉 － 引き角

0.922

98

左美濃 － 高美濃

0.914

99

角交換型 － ゴキゲン中飛車

0.901

100

相腰掛け銀 － △６五歩型

0.899

穴熊，銀冠，矢倉など囲いを

発展させる戦術が上位に

実際の対局における戦術選択の比較

28

• 提案手法と従来手法の対局実験において，それぞれのプログ

ラムが選択した戦術を比較

戦術

各戦術の選択回数

従来手法

提案手法

本美濃

131

77

高美濃

45

54

銀冠

61

175

流れ矢倉

28

15

金矢倉

33

45

居飛車穴熊

210

215

四間飛車穴熊

38

40

三間飛車穴熊

65

39

提案手法では，囲いを

発展させる戦術や固い

囲いが選択されやすく

なっている

重要度を導入すること

により，

コンピュータに

とって勝ちやすい戦術

の選択を実現

提案手法

勝率0.581

目次

ゲーム研究の流れとコンピュータ将棋の現状

ゲームの基本的なアルゴリズム

将棋における棋譜を利用した知識獲得

今後の研究動向

まとめ

29

まとめ（１）

【棋譜を用いた評価関数の機械学習】

•

棋譜を教師とした機械学習の成功により，コンピュー

タ将棋は，人間のトッププレイヤに迫る強さを得る

⇒ ほぼ確実に，数年以内に人間を上回る

•

ただし，評価関数は人間の大局観以上のものが得ら

れているとはいえず，今後も改良の余地は大きい

•

同じ学習データを用いても，その活用方法（学習方

法）によって得られる知識は全く異なる

⇒ さらなる機械学習技術の研究が重要

30

まとめ（２）

【ビッグデータ研究としての意義】

•

将棋，囲碁等のゲームでは数万局（その背後に隠

れている数億手の教師データ）を容易に入手可能

•

個人情報，著作権等が絡まないオープンなデータ

•

ビッグデータに基づく機械学習の基礎研究対象とし

て，ゲームは今後も果たすべき役割は大きい

31