目次

記事の概要

これまで収集してきた将棋ウォーズの棋譜データから適当に特徴量を作って,階層型クラスタリングを適用する.ついでに棋譜からプレーヤーを推定する問題も考えてみる.

将棋ウォーズデータについては以下の記事などを参照してほしい.

先行研究

将棋やチェスの棋譜から特徴量を生成して棋譜を分類したりプレーヤーを推定する,といったテーマの論文・ブログ記事などを日本語・英語で探してみたが,見つからなかった.似たような話を強いて挙げるとすれば,以下の2つがあった

  • 機械学習系のコンペで「チェスの棋譜からプレーヤーのELOレーティングを推定する(Description - Finding Elo | Kaggle)」という問題があった
  • 中村 貞吾,梶山 貴司 「棋譜テキストからの特徴素抽出とそれを用いた棋譜の分類」, 情報処理学会研究報告,09196072,情報処理学会.2000-03-17,2000,27,79-86,http://ci.nii.ac.jp/naid/40004563208/

データセットの概要

第3回将棋ウォーズ棋神戦」開催期間中に,ランキングで上位100位に入っていたユーザーの10秒指しの棋譜を収集した.もちろん上位100位に入っていたユーザーで10秒指しで一局も対局していない場合があるし,100位以内に入っていなくてもデータセット中に何回も現れるユーザーも居る.今回収集できた棋譜は14996件であった.一手も指さずに終局した局などを除いて,先手と後手で分割して(後述の)前処理すると最終的に29514件のデータが得られる.

ここで,各ユーザーがデータセット中に出現する回数を片対数プロットすると以下のようになる.(横軸にユーザーが並んでいて,縦軸がそのユーザーの出現回数)

ユーザーの対局数

これを見ると,10局以上対局しているのは500人以下であることがわかる.こういった状況だと後述の棋譜からユーザーを推定する問題が少し難しくなるだろうという予想がつく(実際難しい).そこで今回は,とりあえずデータセットの中で対局数が10局以下のユーザーのデータは削除することにする.

特徴量

残念ながら先行研究が見つからなかったので,自分で特徴量を考える.今回特徴量として採用したのは以下の3つである1

  • 最初の手(先手なら1手目,後手なら2手目)を指すのに使った時間
  • 持ち時間の使い方を見る特徴量
  • 最初の手を見る特徴量

実際の特徴量は以下のようになる.

first_ctime           1.000000
t0                    0.007812
t1                    0.218750
t2                    0.210938
t3                    0.179688
t4                    0.140625
t5                    0.062500
t6                    0.054688
t7                    0.039062
t8                    0.046875
t9                    0.031250
t10                   0.007812
first_move=+1716FU    0.000000
first_move=+1918KY    0.000000
first_move=+2726FU    0.000000
...
first_move=-5354FU    0
first_move=-6152KI    0
first_move=-6172KI    0
first_move=-6364FU    0
first_move=-7162GI    0
first_move=-7172GI    0
first_move=-7374FU    0
first_move=-8232HI    0
first_move=-8242HI    0
first_move=-8252HI    0
first_move=-8262HI    0
first_move=-8272HI    0
first_move=-8384FU    0
first_move=-9192KY    0
first_move=-9394FU    0
Name: 1, Length: 67, dtype: float64

以下では下2つについて詳しく説明する.

持ち時間の使い方を見る特徴量

持ち時間の使い方を見るために,今回は以下のような手順で特徴量を作った.

  1. 先手の考慮時間と後手の考慮時間をそれぞれ取り出す.
  2. 先手と後手それぞれの考慮時間のヒストグラムを作る.
  3. ヒストグラムの値を特徴量として使う.

例えば,以下のような棋譜データがあるとする.

+7776FU\nT2\n-8384FU\nT2\n+5756FU\nT1\n-7162GI\nT1\n...

このとき,先手の考慮時間の列は $(2, 1, \ldots)$ で,後手の考慮時間の列は $(2, 1, \ldots)$ となる.得られた2つの考慮時間の列について,それぞれ(全て足すと1になるような)ヒストグラムを作る.今回は考慮時間の範囲が0~10秒なので11個のビンがあるヒストグラムが描ける.例えば以下のような感じ.(t0は考慮時間0秒で指した手の意.以下同様)

考慮時間のヒストグラム

そして,11個のビンの各値(高さ)を11次元の特徴量として採用する.(全て足すと1になるので実質10次元だが)

最初の手を見る特徴量

最初の手(先手なら1手目,後手なら2手目)を特徴量として使いたいので,最初の手を 1-of-n 符号化法で0-1ベクトルに直す.最初の手をなにも処理せずにそのまま使っているので,例えば盤面をひっくり返したら同じに見えるような手(ex.7六歩3四歩)なども異なる手として認識されるし,暗黙のうちにそのデータが先手番のものか後手番のものかという情報も含まれている.

76歩と34歩

(shogipic.jp で作成した盤面.url)

結果

階層型クラスタリングの結果

何も考えずに階層型クラスタリングを使ったので,オプションとしては scipy.cluster.hierarchy.linkage のデフォルト値を使っている.具体的には,距離はユークリッド距離,クラスタ間の距離は最短距離法を採用している.

データ数が大きいと非常に見づらくなるので,とりあえずデータ数100の場合の結果を載せる.

少ないサンプルでの結果

かなり都合の良い状況ではあるが,パッと見た感じうまく分類できているように見える.

また,データ数3000の場合の実行結果(下記のプログラムの実行結果)はデンドログラムのPDFに置いてある.

ユーザーの同定も試してみる

ちなみに上で使った特徴量を属性値,ユーザー名をラベルとしてk-NearestNeighbor ($k \le 30$)を用いて特徴量からユーザーを推定する問題を考えてみると,正答率が良くて17%くらいになる(下図参照).もっと高級な分類器を使えば正答率の向上が見込めそうな気はするが実際はどうだろうか.

k-NNの結果

(横軸が $k$,縦軸が k-NNの正答率を表す.)

ソースコード

  • 階層型クラスタリングをかけるところでindex = range(3000)とデータの一部しか使っていないのは,手持ちのマシンが非力だったからでそれ以上の意味はない.

まとめ

  • 階層型クラスタリングでそれなりにクラスタリングができた
  • 棋譜を使ったユーザー同定も試したが,k-NNを使って約17%の正答率がでたので適当な分類器を使えばもっと良い正答率がでる気がする
  • 人間が指した対局の棋譜を消費時間込みで記録するというケースがあまり一般的では無いように感じた
  • 「持ち時間の使い方を見る特徴量」は多分新しい?

参考文献

  1. もちろん,コンピュータ将棋のプログラムを使って特徴量を抽出したり,コンピュータ将棋で使われている特徴量?を使うということも考えられるが,面倒なので今回は使わない.



blog comments powered by Disqus

Published

18 December 2014

Tags