2009-05-07 GPS将棋について

_ GPS将棋全体について

(GPS将棋の特徴などついて徐々に説明をまとめて行く予定です)

名前の由来
公式ページをご覧ください
開発メンバー
選手権後に開発メンバーのページが作られています
過去の戦績
まとめをご覧ください

_ 今年の選手権に出場したGPS将棋について

ソースコード
わかりやすいバージョンを公開準備中です。(選手権の時のソースコードと開発版が公開されています。不十分ながら解読用資料もご覧ください。)
バイナリ
linux版を公開準備中です。(5/8)公開されました
棋譜と読み筋
こちらのページにjavascriptで表示する将棋盤と形勢判断のグラフへのリンクがまとめてあります。
大きく改良したところはどこか
評価関数(=形勢判断)が以前より正確になりました。
どのように正確にしたか
いわゆる「学習」を行った部分を増やしました。昨年までは序盤の駒の損得に関係の無い形の良さのみ自動的に作り、他は手で調整していました。今年は手の調整をなくし、すべて学習に切り替えました。
学習の考え方は何か
人間の棋譜を分析して、人間が指すのを真似するように自動的に調整します。大雑把には、人間が指した局面の評価値が他の手より高くなるようにすることで実現しています。
同じように学習をしているプログラムが多いのになぜ棋風の違いが出るか?
評価特徴(=局面のどこに注目するか)はプログラマが教えているため差がでます。(評価特徴を自動生成する野心的な研究もありますが、現在まではトッププログラムには採用されていません)。例えば、Bonanza4は利きをあまり見ていませんが、GPS将棋は下に示すように利きに敏感になっています。
どの程度強くなったのか
レーティングにして昨年のバージョンと200-300点ほど差があります。資料: floodgate長期レーティング, 二週間レーティング
将棋クラブ24では指しているか?
5/9現在までに指したことはありません。
新しいバージョンはどのようにできるか
  1. 新しい評価項目を思いついてプログラムを書く
  2. 棋譜を分析して新しい評価項目を含んだ評価関数を作る (1日程度)
  3. 前のバージョンと対戦させて新しいバージョンが勝ち越すかどうかをみる (1日程度)
  4. 統計的に有意に勝ち越せば採用。採用されなければ1か2に戻る
Bonanzaのソースコードは使っているか?
使ってはいません。読んではいます。例えば時間制御など

_ GPS将棋の技術的な構成

  • 将棋盤: 利きに関する関数が充実しています
  • 評価関数: 序盤、中盤、終盤の評価関数を作って内分を取っています。今までの多くのプログラムは序盤と終盤の内分だったことと比べて中盤が増えています。(そのうち中盤を二つにさらに分割予定)。分割を増やすこと自体はオセロで既に行われているので学術的な新規性はありません。「学習」の方法はBonanzaと似ています。2008年のゲームプログラミングワークショップに投稿した論文に詳しい説明があります。
  • 進行度も学習させています
  • 実現確率探索: 激指のアルゴリズムを参考にしています。確率の求め方に工夫があるかもしれません。棋譜から指手の優先度を求めた後優先度順に並び替え、順位や優先度の手がどのくらいの確率で指されるかに変換しています。深さ制御用と幅制御(=前向き枝刈)用の二種類を作っています。もはや確率と呼べる数値ではないですが、元のアルゴリズムの確率に相当する数値という意図です。
  • 静止探索: KFEndの脅威を考慮した静止探索を参考にしています。また王手等も読んでいます。このあたりは山下さんの末端付近での指手の絞り方を参考にしています。
  • 詰探索: df-pnを使っています
  • 詰めろを考慮した探索: KFEndの詰めろを考慮した通常探索を参考にしています。
  • 並列探索: チェスのcraftyを参考にしています。

今後加筆します。

_ GPS将棋の評価関数の中身

  • 目次のようなもの
  • 生データ 約7メガバイトのテキストファイルです。各評価項目の重みが1行に一つかかれています。全体で約300万行、0でないものが約80万行あります。

評価項目の簡単な説明は林くん作成の以下をご覧ください。評価項目は、主に林くんの閃きによるものですが、Bonanza、棚瀬将棋、奈良将棋Blunderなど公開されている情報も参考にしています。

序中終盤共通の値
PieceEvalComponent 駒の価値
PiecePair 2駒の関係。駒の座標に関係ないものと、X座標固定とY座標固定
King25EffectAttack 玉の25近傍の攻撃側の利きの数(max 127)とそこに利きを付けてる駒(max 16)の組み合わせ
King25EffectAttackY King25EffectAttackを玉のY座標別に
ProgressBonus2 進行度による先後の進行度(0から15に正規化)の組み合わせ
ProgressBonusAttackDefense 各玉の、攻撃側の進行度と、防御側の進行度の値の組み合わせ
ProgressBonusAttackDefenseAll 両方の玉の、攻撃側の進行度と、防御側の進行度の値の組み合わせ
序中終盤別の値
PieceStand 持駒の種類別の枚数
Pin 動くと王手になってしまう駒を種類と玉からの相対位置別に
King25EffectEach 玉の25近傍の各桝で、どちらの駒があるか空白か、と、利きで勝ってるか負けてるか同じかの組み合わせ
PawnDropDefense 歩を打てる筋の自玉とのX軸の相対位置
PawnDropAttack 歩を打てる筋の相手玉とのX軸の相対位置
NoPawnOnStand 歩切れでかつ歩の枚数で負けているときの点
GoldRetreat 下がれない金を金のY座標別に
SilverRetreat 下がれない銀を銀のY座標別に
KnigtAdvance 跳べない桂を桂のY座標別に
AllMajor 大駒を全部持っているときの点
KingXBlocked 玉が左右どちらかに行けないときの点、玉のX座標別
KingXBlockedY KingXBlockedを玉のY座標別に
AllGold 金を全部持っているときの点
PtypeX 各駒の種類につき、あるX座標にいるときの値
PtypeY PtypeXと同様に、Y座標別に
AnagumaEmpty 隅に居るときのまわりの3桝が空白かどうか
NonPawnPieceStand 歩以外の持駒の合計枚数
King25EffectDefense 玉の25近傍の防御側のの利きの数(max 127)とそこに利きを付けてる駒(max 16)の組み合わせ
King25EffectYDefense King25EffectDefenseをY座標別に
RookMobility 飛車がX軸とY軸で動ける桝の数
BishopMobility 角が動ける桝の数
LanceMobility 香車が動ける桝の数
RookEffect 飛車の利きがある桝を相手玉との相対位置で評価
RookEffectDefense 飛車の利きがある桝を自玉との相対位置で評価
BishopEffect 角の利きがある桝を相手玉との相対位置で評価
BishopEffectDefense 角の利きがある桝を自玉との相対位置で評価
PawnAdvance 前に進めない歩をY座標別に
PawnDropYAttack 歩の打てる筋の相手玉からのX軸の相対位置を玉のY座標別に
PawnDropYAttack 歩の打てる筋の自玉からのX軸の相対位置を玉のY座標別に
KnightCheck 桂馬で王手がかかるかどうか
PieceKingRelativeBoth ある駒の盤上での各玉からの相対位置
NonPawnPieceStandCombination 歩以外の持駒の種類別の枚数の組み合わせ
NonPawnPieceStandTurn 歩以外の持駒の種類別の枚数を手番別に
King25EffectEachX King25EffectEachを玉のX座標別に
King25EffectEachY King25EffectEachを玉のY座標別に
RookPawnY 飛車のY座標とその筋の歩のY座標
RookEffectPiece 飛車の利きが付いてる駒
BishopEffectPiece 角の利きが付いている駒
RookEffectPieceKingRelative 飛車の利きが付いている駒を玉からの相対位置で
BishopEffectPieceKingRelative 角の利きが付いている駒を玉からの相対位置で
RookPawnYX RookPawnYを玉からのX軸の相対位置で
PawnPtypePtype 歩の前の駒とその前の駒の組み合わせ
CanCheckNonPawnPieceStandCombination 王手がかかりそうなときの歩以外の持駒の組み合わせ
PromotedMinorPieces 相手玉と同じ側にある2枚目以降の小駒の成駒の相手玉からのX軸の相対位置
PieceKingRelativeNoSupport 紐がついてない駒の各玉からの相対位置
NonPawnAttacked 相手からの利きがついている歩以外の駒を手番別に
PtypeYY 各玉のY座標別に駒のY座標で評価
PawnPtypePtypeY PawnPtypePtypeを歩のY座標別に
PawnDropX 各玉のX軸別に、歩を打てる筋のX軸の評価
King3Pieces 縦、横、斜めの玉を中心とする連続した三駒の評価
King3PiecesXY King3Piecesの玉のX座標別のものとY座標別のもの
King25EffectEachXY King25EffectEachの玉のX座標別とY座標別のもの
BishopHead 角の頭に味方の利きがないときにそこにある駒
BishopHeadKingRelative BishopHeadを自玉との相対位置で
KnightCheckY 玉のY座標別に桂馬で王手がかかるときの評価
KnightHead 桂の頭に相手が歩を打てそうなときに、桂のY座標別に評価
RookPromoteDefense 飛車成りを受けている駒と、その駒に利きをつけている駒の種類
PawnDropPawnStand 持駒に歩があるときに、各玉からのX軸の相対位置で歩を打てる筋を評価
PawnDropPawnStandX PawnDropPawnStandを玉のX座標別に
PawnDropPawnStandY PawnDropPawnStandを玉のY座標別に
King25Effect2 玉の25近傍の攻撃側の利き(max 63)と、利きを付けている駒の数と、持駒の飛車角金銀の数の合計の組み合わせ
King25EffectY2 King25Effect2を玉のY座標別に
KnightHeadOppPiecePawnOnStand 桂頭に相手の駒があって、相手の持駒に歩がある場合に、桂馬のY座標と、相手の駒の種類別に評価
KingXBothBlocked 玉が両側に動けないときに玉のX座標別に評価
KingXBothBlockedY 玉が両側に動けないときに、玉の絶対座標で評価
KingRookBishop 王と飛車の相対位置と王と角の相対位置の組み合わせ
PromotedMinorPiecesY PromotedMinorPiecesを各玉のY座標別に
King25EffectSupported 玉の25近傍にある攻め駒の枚数と利きの付いてる攻め駒の枚数の組み合わせ
King25EffectSupportedY King25EffectSupportedYを玉のY座標別に
NonPawnAttackedKingRelative 歩以外の相手の利きがある駒を各玉との相対位置で
NonPawnAttackedPtype 歩以外の相手の利きのある駒を、利きを付けている駒の種類別に
PtypeCount 駒の種類別に、盤上にある数と、持駒も含めて持っている数を評価
PtypeCountXY PtypeCountを自玉のX座標別とY座標別に
PtypeCountXYAttack PtypeCountXYと同様、相手玉版
LanceEffectPieceKingRelative 香の利きがついている駒を各玉との相対座標で
KingMobility 玉の絶対座標別に各向きに続いている空白桝の数
KingMobilitySum 玉の絶対座標別に、各向きに続いている空白桝の数の総和
PtypeYPawnY 歩のY座標と、その筋にいる他の駒のY座標
GoldAndSilverNearKing 玉からある距離(1,2,3)以内の金と銀の枚数の総和
PtypeCombination 味方の駒の種類の組み合わせ
PieceStandCombinationBoth 先後の持駒の持っている種類の組み合わせ
King25BothSide 玉の25近傍のY軸の攻撃側の利きの組み合わせ二つを、玉を挟む形で組み合わせ(挟撃ボーナス)
King25BothSideX King25BothSideを玉のX座標別に
King25BothSideY King25BothSideを玉のY座標別に
GoldAndSilverNearKingCombination 玉からある距離(1,2,3)以内の金と銀の枚数の総和の組み合わせ
KingMobilityWithRook KingMobilityの相手の持駒に飛車がある場合
KingMobilityWithBishop KingMibilyの相手の持駒に角がある場合
NumPiecesBetweenBishopAndKingSelf 相手玉が角筋にいる場合の間にいる玉側の駒の総和
NumPiecesBetweenBishopAndKingOpp 相手玉が角筋にいる場合の間にいる攻め側の駒の総和
NumPiecesBetweenBishopAndKingAll 相手玉が角筋にいる場合の間にいる駒の総和
本日のツッコミ(全5件) [ツッコミを入れる]
_ 奈良(奈良将棋) (2009-05-09 11:40)

優勝、おめでとうございます。<br>今、floodgateですごいレーティング点数がついていますね。<br>目のくらむような評価項目ですね、項目数、プロの指し手との一致率、J'ってどのくらいになっていますか?<br>(人間に将棋の考え方としてフィードバックできる項目が見つかったら面白いですね、「GPS流 将棋に勝つ考え方」を出版できたり。。)

_ kaneko (2009-05-09 13:24)

奈良さん、ありがとうございます。項目数は300万くらいで0でない重みが80万くらいでした。一致率等はやる度に(棋譜を変えると)変わりますが、大雑把には40%よりは上、3.0よりは下という印象です。これらの数値よりも自己対戦で勝ち越すかを重視しています。<br>人間の参考になるかどうかは別にして、GPSが何を考えてこの局面にこの点をつけたかをうまく可視化できると面白いかもしれないと思案しています。

_ 奈良(奈良将棋) (2009-05-09 14:21)

40%, 3.0 というのは皆さん目標とする数値になるのでは<br>ないでしょうか(学習時、探索深さにも拠りますが)。<br>ちなみに項目数については私のは0でない重みは今17万くらいでした。<br>Bonanza(保木さん)がシンプルな評価項目に進んだのとは<br>全く対照的なのがまた面白いです。

_ hoki (2009-05-09 21:00)

優勝おめでとうございます。<br><br>評価項目、半分まで読んだところでメマイが。。。。 凄まじいですね。「学習は Bonanza よりも洗練されてます」ぐらい言ってもいいと思います!

_ kaneko (2009-05-10 01:15)

奈良さん<br>そうですね、Bonanzaとは違う方向(利きの活用)に進んでいるとは思います。<br><br>保木さん<br>ありがとうございます。保木さんの学習の成功がなければ今のGPS将棋はなかったと思います。

本日のTrackBacks(全2件) []
_ コンピュータ将棋協会blog:第19回世界コンピュータ将棋選手権者はGPS将棋 (2009-05-08 00:42)

第19回世界コンピュータ将棋選手権は、ライブ中継のページ、コンピュータ将棋選手権ネット中継ブログにて報じられたとおり、GPS将棋が初優勝。3日間の詳細は上記ページをご覧ください...

_ コンピュータ将棋協会blog:世界コンピュータ将棋選手権戦記2009 (2009-05-24 10:54)

早稲田大学で行われた、第19回世界コンピュータ将棋選手権。昨年に引き続き、現時点でリリースされている開発者の自戦記をひととおり列挙してみますので、皆さんもぜひご一読を。



...