第20回世界コンピュータ将棋選手権
アピール文章

提出：2010年3月（5月11日に加筆）
氏名：中村 政義
プログラム名：Staty

* GPS将棋の選手権使用可能ライブラリのコンパイルと簡単な使い方については、下記URLにメモを載せました。
http://masayosshi.com/shogi/


1. 概要
本プログラムは，コンピュータ将棋選手権使用可能ライブラリのgpsshogi-for-csa 0.6，osl-for-csa 0.6の
静的評価関数のパラメータを下記の方法によって学習させたものである．
探索法などは基本的に改変していない．


2. 実力
2010年3月末現在，本家のパラメータ(コンピュータ将棋選手権使用可能ライブラリ gpsshogi-for-csa0.6)に対して
何回やっても勝てないレベルの実力．


3. オリジナルで作ったところ
3.1. 静的評価関数
局面の評価関数を，機械学習の検索の分野などで用いられる順位学習(Learning to Rank)の問題に
帰着させ求めた．

局面間の評価値の大小関係を次のように仮定する．
- ある対局中のある局面において
-- 勝者の局面 > 敗者の局面
-- 棋譜で指された手 > 合法手　(単純に兄弟節点の比較する．最善応手手順後の比較はしていない)
- （時間があれば実装予定）すべての棋譜の中から同一の局面を探して
-- プロ棋士の手 > アマチュア棋士の手 > 合法手

このような評価値の順位関係から，訓練データを作成し，
文献[1]のRankSVMを用いて，評価値の予測器を構築する．
訓練データ数が大規模であるため，確率的勾配降下法により逐次学習を行う(文献[2])．
また，すべての訓練データを用いずに，ランダムサンプリングでも十分な回数の逐次学習の
更新を繰り返すことで非常に高速に学習が可能と報告されている手法(文献[3])を用いて学習する．

なお，実装にあたっては文献[4]でソースコードが公開されている 「sofia-ml」 を用いた．
特徴ベクトルの生成には，GPS将棋と一緒に配布されているソースコードを使用し
（使用可能ライブラリには含まれてないため，選手権出場予定のプログラムには用いていない）
進行度等のパラメータはライブラリのgpsshogi-for-csa 0.6に含まれているパラメータを用いた．


4. 棋譜の手の予測精度比較
4.1 予測精度指標の定義
本家のパラメータと比較するため，次の２つの予測精度指標を決める．

・正答率
ある局面を対象に，すべての合法手を生成し，それらを指した後の局面の評価値を各々求める．
棋譜で指された手と，すべての合法手を比較し，棋譜の手の評価値が高いなら正解，
そうでないなら不正解としてカウントする．これをテストデータのすべて局面において求め，
(正解数) / (不正解数 + 正解数)　
を正答率とする．

例：
合法手はa1〜a4までの４つで，棋譜で指された手はa1の場合
合法手　評価値（高い方が良い）
a1　　　10     　　　　　　　　
a2　　　20
a3　　　-30
a4　　　-10
上のような評価値が得られたとき，正答率は2/3≒0.666 (66.6%)となる．

・平均順位
ある局面を対象に，すべての合法手を生成し，それらを指した後の局面の評価値を各々求める．
評価値の良いものから順に並べたときに，棋譜で指された手の順位を求める．
これをテストデータのすべて局面において求め，この平均値を平均順位とする．
先の例では，評価値順位は a2, a1, a4, a3となるため，順位は2となる．


4.2 学習データ
棋譜にはプロ棋士同士の対戦のみを用いる．
・訓練データ：31000局使用
・予測精度を求めるためのテストデータ：訓練データで用いなかった局面1000局を使用
なお，学習時間は５時間（core2 quad 2.66GHzの１コア使用) 



4.3 結果
上記の手法で求めたパラメータ
正答率:94.4%　 平均順位:6.10（中央値 2.00）

gpsshogi-for-csa0.6のデフォルトパラメータ
正答率:88.9%　 平均順位:10.2（中央値 3.00）

この実験結果から，本手法は次の一手を探索無しで予測することに関しては
予測精度が高いことは読み取れる．しかしながら，この予測精度が高いことが実力
につながるわけではないことを次の章の対局結果に示す．

5. 対局結果
本家のパラメータを用いたプログラム（つまりデフォルトそのまま）と，
上記で求めたパラメータのプログラムを対戦させたところ
持ち時間は3分で0勝10敗と，全敗の結果となった．
一方，互いに1手読み（合法手すべての中から，指した後の局面の評価値が最も良いものを選ぶ）では，
本家のパラメータを用いたプログラムには10勝0敗と全勝した．


6. まとめ
棋譜データの次の１手の予測に関しては，ライブラリに含まれているパラメータより高精度に予測
できる．（ただし，ライブラリに含まれているパラメータは，棋力が強くなるように調整しているはず
なので，この比較は不公平でもある）


7. ひとこと
開発を始めたのは2009年11月です．
私自身，将棋の経験はありません．
中学時代にオセロのAIを自作し，自分自身がそれに負けた経験から，このような分野に興味をもってきました．
今回，学生として最後のチャンスだったのでに挑戦してみました．


8. 参考文献
[1] T. Joachims. Optimizing search engines using clickthrough data. In KDD ’02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, 2002.
[2] T. Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In ICML ’04: Proceedings of the twenty-?rst international conference on Machine learning, 2004. 
[3] D. Sculley. Large Scale Learning to Rank. NIPS Workshop on Advances in Ranking, 2009. 
[4] sofia-ml  - Project Hosting on Google Code (http://code.google.com/p/sofia-ml/)