DEIM Forum 2016 E8-2

特徴語との自動対応によるゲーム局面の検索
牛久敦†

森信介††

亀甲博貴†††

鶴岡 慶雅†††† 京都大学大学院 情報学研究科 〒 606-8501 京都市左京区吉田本町†† 京都大学 学術情報メディアセンター 〒 606-8501 京都市左京区吉田本町††† 東京大学大学院 工学系研究科 〒 113-8654 文京区本郷 7-3-1
E-mail: †ushiku@ar.media.kyoto-u.ac.jp††forest@i.kyoto-u.ac.jp† † †{kameko, tsuruoka}@logos.t.u-tokyo.ac.jp
あらまし 将棋の局面を入力とし、それに対応する解説文の特徴語を出力するモデルの学習を行う。新規局面に対し、特徴語ごとのスコアを出力することで、言語表現を利用した局面検索を可能にした。また、検索結果に対する主観評
価及び具体的な局面を示す。
キーワード

自然言語処理, シンボルグラウンディング, 情報検索

1. は じ め に
画像検索を代表とする、非言語データの検索の需要は、データ量の増加とともに高まっていると言える。自然言語による検説もタグ付けもされていない局面の検索が可能となる。また、将棋を具体的な例として取り上げたが、将来的には医療用データや株価チャートといった非言語データにも応用可能であると考えられる。

索は、検索者が特別にデータを用意する必要がないことに加え、2 章にて関連研究、3 章で提案手法、4 章で実験の説明を行

ある程度抽象的な事象を検索できるといった利点をもつため、う。次の 5 章にて、結果および、具体的な検索結果に触れる。

その中でも特に有用と言える。しかし、画像や動画以外のデー6 章にてまとめを述べる。

タに関しては、自然言語での検索環境は整っていないのが現状である。

2. 関 連 研 究

このようなデータの具体的な例として、株価のチャートや、将棋の局面の検索としては、局面そのものを検索クエリとすチェスなどのゲームの記録などがある。株のトレーダーは、株る、局面検索が存在する。横山ら [1] は、駒の種類、駒の位置、価の変動を予想するために現在の株価と同じようなチャートを駒の所有者をキーとして、その状態の駒が存在する局面の集合探すことが考えられ、また、チェスプレーヤーも学習のためにである転置索引を作成している。入力を複数の検索キーとし棋譜を参照すると考えられる。非言語データについての解説文て、それらの転置索引の積集合を求めることで、局面検索を実やタグを参照することで、検索を行うことができるが、必ずし現している。検索キーを全ての駒に関して行うことで完全一致も全てのデータに解説文やタグが付いているわけではないこと検索、一部の駒に対して行うことで、部分一致検索を行う。利に加え、全ての解説文がデータと対応しているわけではない。

点として、検索クエリとして入力する情報が、局面そのものでそのため、人間による解説文がついていないようなデータの検あるため自分の検索したい棋譜が正確に定まっている時には、索を可能にすることは重要である。

間違いなく検索できるということが存在する。一方で検索クエ以上の問題に対して、自然言語を用いた非言語データの検索を提案する。解説文が付いている一部のデータを利用し、非言リが局面であるため、最大 40 個の駒の位置の入力は煩雑であるという問題も存在する。

語データと解説文の特徴的な単語である特徴語の間のシンボル

非言語データの内容理解に関して、画像から文生成 [2] を行グラウンディングのモデルを作成することで、特徴語による非う研究が行われている。また、将棋においては、亀甲ら [3] の言語データの検索を可能にする。

ものがある。これは、将棋の解説文と局面の素性を利用して、具体的な非言語データの例として、将棋に着目を行う。将

3 層パーセプトロンによって特徴的な単語を予測することで、棋はプロ棋士による棋譜の一部が、解説付きで存在するため、将棋の局面から自動で解説文を生成している。金子 [4] はコン我々の手法が適応可能である。また、将棋の局面検索そのもの

ピュータ将棋を利用することで、プロ同士の対局における現在も有用であると考えられる。具体的には、学習者が特定の戦型の局面の形勢判断と読み筋を解説として出力している。の棋譜を探すことや、プロ棋士が本を書くために棋譜を収集するといった状況が考えられる。本論文では、特定の戦型や囲い

3. 提 案 手 法を示す特徴語を検索クエリとして、検索を可能にする手法を提提案手法について説明する。本手法では、局面と特徴語の対案する。本手法は全文検索と異なり、局面の言語情報を利用し応を学習し、それを用いて新規局面に対して特徴語ごとのスコないため、近年増加するコンピュータ同士の対局といった、解アを出力することで検索を行う。提案手法の学習部分を図 1、2駒間の関係などを素性

単語分割
固有表現抽出

解説文

ゴキゲン中飛車対丸山ワクチンに似た形。

局面素性

NeuralNet

特徴語スコア 

ゴキゲン中飛車 

丸山ワクチン 

棒銀

 

美濃囲い



図1

局面ごとの特徴語スコア学習

3. 2 前 処 理
学習前に前処理として、局面を局面素性に変更し、解説文の単語分割及び固有表現抽出を行う。
局面素性はコンピュータ将棋ソフトである「激指」[5] が局面新規局面
特徴語

スコア

を評価する際の素性を利用している。主として駒の種類や、2駒間の位置の関係を記述している。	

解説文に関しては、単語分割と将棋特有の固有表現抽出 [6] [7]を行った。将棋特有の固有表現の種類としては、戦型を示したものや、駒の囲いなどがある [8]。固有表現タグの一覧を表 1 に示す。これらを学習したものを利用して、解説文に対し、固有

図2

新規局面の特徴語のスコア出力表現抽出を行った （注 1）。今回は結果の確認の簡単さなどから、出力する固有表現を St/戦型と Ca/囲いのタグのものに絞った。

特徴語のスコア出力を図 2 に示す。

3. 1 デ ー タ

得られた将棋特有の固有表現、特徴語を教師データとする。
具体的には、図 1 においては「ゴキゲン中飛車」と「丸山ワ学習に用いるデータとして、ある局面とその局面についてのクチン」が教師データとなる。これらは 2 つとも戦型を示した解説文を用いる。これは、プロ同士の対局の局面ごとに、プロ特徴語である。教師データは語彙数次元のベクトルであり、あによって解説されたものである。具体的な例として、図 1 をる特徴語が出現しているかどうかのスコアを {0,1} のバイナリ示す。
これらの局面は対局の中から抜粋したものであり、ある程度の連続性を持つが、1 手ごと、全ての局面に解説が付けられてで示す。すなわち「ゴキゲン中飛車」「丸山ワクチン」のスコアは 1、解説文に出現していない「棒銀」「美濃囲い」のスコアは0 として学習を行う。

いるわけではない。また、解説文は必ずしも、局面について言3. 3 学及しているわけではなく、「夕食の注文は島がタラコとイカの学習機にはニューラルネットワークを用いた。入力は局面素スパゲティ、森がきつねうどん。」といった局面とは関係して性であり、出力は、1 つの局面に対し複数の特徴語が存在するいないことについて述べられていることがある。

ため、マルチラベルとなっている。誤差関数として、出力の間

習（注 1）：固有表現抽出の精度はおよそ 90%前後であった。

タグ

意味Hu

人 (対局者や解説者を含む人)

Tu

手番 (例: 先手, 後手, ▲, △)Po

位置 (81 通りと「駒台」「同」など小数の例外のみ)Pi

駒 (成り駒を含め有限)Ps

駒の指定 (例: 右, 直)Mc

動きの明確化 (例: 成, 不成)Pa

駒の属性 (道, 利き, 頭)Pq

駒の数 (１ 枚, 切れ)Re

盤面の領域 (中央, 駒台, ４ 筋, ３ 段 目)

Ph

対局の進行 (序盤, 中盤, 終盤)

St

戦型 (「棋士名＋流」も含む)

Ca

囲い (矢倉, 美濃 囲い)

Me

指し手評価

Mn

指し手別名

Ee

評価要素 (部分の評価のみ)Ev

形勢評価 (局面全体の判断のみ)Ti

時間 (概数表現を含む)

Ac

対局者が主語の述語

Ap

駒が主語の述語

Ao

その他の表現が主語の述語

Ot

その他

局面

NeuralNet

特徴語

スコア0.8

A	

0.8

検索クエリ

ゴキゲン中飛車
スコア順に出力

0.2

B	

0.4

C

A, C, B	

図30.8

0.40.2

特徴語のスコア出力による検索

いて主観評価を行った。学習データとして、4,075 局面とその解説文のセットを利用した。特徴語のタグを戦型と囲いに限定した結果、334 次元になった。局面素性は 52,600 次元、中間層は 1,000 次元で 6 層のニューラルネットワークを用いた。また、

表 1 将棋の固有表現名とその意味

バッチサイズは 100 で、エポック数は 150 である。実装に関しては、ディープラーニングフレームワークである Chainer（注 2）違え方によって重みをつけた 2 乗誤差を用いている。

を利用した。また、2 乗誤差の重みに関して、出力されるはずのスコアが出力しない時と、出力されないはずのスコアが出力RSS =n!
i=1α|fi (x) − yi |2 ここで α =⎧⎨α1 (yi − fi (x) > 0)⎩α (otherwise)2fi (x) は入力である局面素性 x に対するニューラルネットのある特徴語の出力されたスコアであり、yi は教師データである。

α は重みであり、α1 > α2 である。ある局面に対する特徴語が、局面の内容を説明していない可能性は存在するが、逆に解説文に書かれている特徴語は、局面の内容とあてはまらない可能性は低いことが予想される。そのため、局面に対して、出力されるはずの特徴語タグが出力しないときよりも、出力されないはずの特徴語タグが出力される時のペナルティを小さくしている。

3. 4 スコア出力
学習したニューラルネットワークを用いて、新規局面に対して特徴語ごとのスコアの出力を行う。出力は特徴語の語彙数次元のベクトルでありスコアは連続量である。スコアが 1 に近いほどその特徴語が、局面と結びついていると言える。

3. 5 検索

新規局面の集合を検索対象として、自然言語による検索を行う。図 3 のように、検索のクエリは特徴語であり、局面ごとの特徴語のスコアを参照することで検索を行う。本研究において、検索クエリである特徴語の入力は 1 つのみであり、スコアが 1に近い局面から順に出力していく。同一の局面が複数存在するときは、出力するのは 1 つのみである。

4. 実

験

複数の特徴語に対して検索を実際に行い、その検索結果につされる時のペナルティの比を 3:1 とした。検索対象として、965
局、109,700 局面を用意し、学習したニューラルネットワークを用いて、特徴語スコアを出力した。
学習時の解説文中の出現頻度が下位の特徴語は、固有表現抽出で間違っている可能性が高く、また十分な学習ができていないと判断して、検索クエリとして、戦型と囲いごとに特徴語タグの出現頻度が高い上位 10 種類を選んだ。検索クエリそれぞれで、実際に検索を行い、検索対象の中からスコアの値が大きい順に 20 局面を選んだ。それらの局面が検索クエリの特徴語と正しく合致しているかどうかを主観評価で判定した。基準として、以下の 4 つの評価を用意した。

•F: プロの対局ならそうなる展開•N: そうなっていない／プロの対局ならそうならない•

Y: そうなっている•

M: まだわからない

検索結果の評価としては、Y あるいは F が望ましいと考えられる。なお、評価は将棋の戦型についての知識を必要とすることから、ある程度将棋に精通した人物が行った。

5. 結

果

主観評価の結果を表 2 に示す。

5. 1 考察全体で 74.8%の局面が F、Y と判定された。「美濃囲い」「四間飛車」といった特徴語は F と評価された割合が非常に高い一方で、「急戦矢倉」では、大部分が N に分類されており検索が（注 2）：http://chainer.org/

タグ

囲い検索クエリ

YFN

M

局面の検索例を図 4 の右側に示す。「ゴキゲン中飛車」は、後穴熊

14240

手番が飛車を 5 筋に振る中飛車戦型の一つである。「ゴキゲン矢倉

12431中飛車」の典型的な局面は、図 4 の左側の局面である。枠で囲銀冠

13142われた部分が、「ゴキゲン中飛車」の特徴的な部分であり検索

美濃囲い

20000

例でもうまく特徴をとらえていることがわかる。

相矢倉

51311左美濃

9416早囲い

7427急戦矢倉

00182

本研究では、将棋の局面とその解説文によって特徴語のスコ相穴熊101000アを出力するモデルにより、自然言語による将棋局面の検索を右玉

13007可能にした。主観評価ではあるが、検索された将棋局面は特徴

103

383326

語の内容を正しく示していた。

Subtotal

52.6% 19.0% 16.5% 13.0%
71.6%

戦略

6. お わ り に

29.5%

本研究では、本来は検索結果として出力されるべきであるが、検索できていない局面について取り扱っていない。それを振り飛車

17021居飛車18002中飛車

20000

棒銀

9137四間飛車

20000発展として、検索クエリとして特徴語を複数にすることや、横歩取り

17003

特徴語を戦型や囲いに絞らないことでより有用な検索が可能に

ゴキゲン中飛車12026なると考えられる。また、固有表現認識の学習を行うことで、相掛かり

14006

相振り飛車

株価のチャートといった他の非言語データへの拡張も行えると13115石田流

124131526933

76.0%

3.0%

Subtotal

79.0%
255
Total

4.5% 16.5%
21.0%444259

63.8% 11.0% 10.5% 14.8%
74.8%

25.3%

表 2 検索クエリと局面の主観評価結果	

図4	

ゴキゲン中飛車の典型例と検索結果の例

うまくいっていない。
また、この実験結果は検索された局面が正しいかどうかを示しているものであり、検索されなかった局面の中に、本来検索されるべき局面があるかどうかについて言及していない。

5. 2 検索結果例
具体的な例として、戦型の一つである「ゴキゲン中飛車」の含め今後の課題として、より客観的な評価を行う必要がある。
また、特徴語ごとに検索結果に大きな差が出ることの分析が必要である。

考えられる。
文献[1] 横山博, 平賀譲. 転置索引を用いた将棋棋譜局面検索システムの構築. 情報処理学会研究報告. GI,[ゲーム情報学], Vol. 2005,
No. 17, pp. 19–26, 2005.
[2] Yezhou Yang, Ching Lik Teo, Hal Daumé III, and Yiannis
Aloimonos. Corpus-guided sentence generation of naturalimages. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, 2011.
[3] Hirotaka Kameko, Shinsuke Mori, and Yoshimasa Tsuruoka.
Learning a game commentary generator withgrounded move expressions. In Computational Intelligenceand Games (CIG), 2015 IEEE Conference on, pp. 177–184.
IEEE, 2015.
[4] 金子知適. コンピュータ将棋を用いた棋譜の自動解説と評価. 情報処理学会論文誌, Vol. 53, No. 11, pp. 2525–2532, 2012.
[5] Yoshimasa Tsuruoka, Daisaku Yokoyama, and Takashi
Chikayama. Game-tree search algorithm based on realization probability. ICGA Journal, Vol. 25, No. 3, pp. 145–152,
2002.
[6] Burr Settles. Biomedical named entity recognition using
conditional random fields and rich feature sets. In Proceedings of the International Joint Workshop on Natural
Language Processing in Biomedicine and its Applications,pp. 33–38, 2004.
[7] Erik F. Tjong Kim Sang and Fien De Meulder. Introduction to the conll-2003 shared task: Language-independent
named entity recognition. In Proceedings of the Seventh
Conference on Computational Natural Language Learning,pp. 142–147, 2003.
[8] Shinsuke Mori, John Richardson, Atsushi Ushiku, Tetsuro Sasada, Hirotaka Kameko, and Yoshimasa Tsuruoka.
A Japanese chess commentary corpus. In Proceedings ofthe Tenth International Conference on Language Resourcesand Evaluation, 2016. (To appear)