(元)駒得少年の冒険

_ ゲーム情報学研究会

後日に書いていますが、3月9日はゲーム情報学研究会でした。今回は過去最大の発表件数であり、また、よく準備された発表が多かったと思います。

ゲーム情報学会員の方は情報処理学会のweb parkで、それ以外の方は有料で購入するか、無料公開になるまで(2年?)待つか、著者が著者のページで公開していれば読むことができると思います。

_ ゲーム情報学研究会 個人的感想

いわゆる「学習」に関係するもので、コン ピュータ将棋の方も興味を持たれるかもしれない発表について、個人的な感想 を簡単にメモします。コメントするようで恐縮ですが、論評する意図ではありま せんのでお見逃しください。

• 5. 囲碁における勾配法を用いた局面評価関数の機械学習に関する研究
  モンテカルロ囲碁のための着手の実現確率を棋譜から(いわゆるbonanza methodの応用で、棋譜の指手が他の合法手より優るという枠組みの学習で)作 る話。 議論を整理すれば競争率の高い学会でも見劣りしない内容に感じました。
  感想としては、学習後に合法手を確率順に並べた時に、「n番目に推薦された着手が棋譜で指さ れる確率」に注目して補正するアイデアが面白かったです。 ここから先は独り言のようなものですが、実はGPS将棋でも実現確率を求める際に似たような操作をしています。 モンテカルロ囲碁でも探索でも、着手に確率がどのようについていると強 いのかは、まだまともな指標がないようで研究の余地が大きいですね。各局面で 最大の確率がついた手と棋譜の着手を比較する指標は一次近似としては良いの ですが、ある程度のレベルからは、強さとの関係には否定的な報告の方が多かったような。
• 8.αβ探索における探索順序の自動学習
  探索順序の制御の自動化の研究。反復深化やhistory heuristicで十分ではな いかという立場もありますが、この研究のように棋譜の情報を使う方が優ると 個人的には思っています。応用としては、探索順序によるαβの効率化だけでなく深さや幅の制御に広 げて、late move reductionや実現確率をうまく働かせるという方向につなが りそうですね。
• 9. Keepawayタスクにおけるマルチエージェントの協調行動の学習
  ロボカップの親戚でkeepawayというボールを取られないようにパスを回すゲームに おける強化学習。普段馴染んでいない分野ですが、パス回しのアニメーション を見ていると自分でも作ってみたくなる楽しさを感じます。誰もいないスペースにボールを蹴ってはというコメントに対 して、パスを受ける人の 行動も含めると状態空間が増えるので簡単ではないというお答え。
• 10. GAとTD(λ)学習の組み合わせによるゲーム局面評価パラメータの調整
  双方一手読みとはいえ、強化学習でzebraと五分近くまで強くなれるという結 果に驚きました。
• 11. 先読みを教師とした兄弟局面の比較に基づく評価関数の学習
  教師として信頼できる棋譜がない状況で、いわゆるbonanza methodを使う。 終盤読みきった場合は、兄弟の比較だけでなく、読みきった値を教師に加えては とのコメントがありました。たしかに、終局時に勝ち負け以上の情報を取り出 すことは将棋では難しいですが、対象がブロックスデュオやオセロのような場 合は利用しないともったいないかもしれません。
• 12. 評価関数の強化学習における学習高速化手法
  TD(λ)は色々研究の余地がありそうです。個人的には強いプログラムを作る方 に軸足をおいているので当面使うことはなさそうですが、featureさえまとも なら将来的には選手権レベルの実用にもなるのかもしれません。

誤解等ありましたらコメントお願いします

_ Bonanza一万勝 (floodgate)

おめでとうございます!

Bonanza	5121	1389	78.66%	5024	1370	78.57%

_ floodgate月間最多勝

Bonanzaの名誉を讃えるために、というと大げさですが個人的にプログラミングのリハビリも兼ねて、floodgate月間最多勝のページを作ってみました。

トップを逃している2008年5,11月や2009年2月も勝率は一位より高いことを考えると(gpsのプログラムの方が停電やshogi-server再起動後に早く復帰するため試合数が多い影響と思われます)、登場以来、長期間トップを独走していることが表から読み取れます。

将来的には、レーティングや相性(二つのプログラムの間の勝率)などの変化と合わせて時系列的に楽しめるようになると良いなと思います。

_ 個人的近況

大きな仕事があったせいでいろいろな仕事が積み上がってしまっています。あと、今年は花粉症の症状が重いです。一応薬は飲んでいますが、発作的に症状が出るとしばらく室内から出られないことも。

週末のCSA例会の準備を進めなくてはいけないのですが、何とか頑張りたいと思います。

_ OSL資料

先日CSAの例会でOSLの読み方などについてお話してきました。当日配布した資料に質問等を追記して公開しましたので、興味のある方はどうぞ。

当日はたくさんのコメントありがとうございました。質疑はいくつか失念してしまったものがあったかもしれません。何かありましたらここにコメントくださると幸いです。

_ 評価値に幅を持たせた探索

同じくCSAの例会で伊藤研の方が発表された多数決で将棋を指す実験の流れで、B*探索の話題が出ていました。評価値に幅を持たせた評価関数でB*のような探索した場合と、その幅のどこかの評価値をピンポイント使う従来通りの探索プログラムを多数用意して多数決を取った場合で、結果として同じ効果になっているかもしれない、ということですかね。UCT方面や、アンサンブル学習方面等色々比較対象があって面白そうです。
Bonanzaでもcraftyでもzebraでも簡単に実験できそうで、今は良い時代だと思います。論文をお書きになったらぜひGPWにご投稿を:-)
参考文献はこの辺だと思いますが、最近読み返していないので勘違いがあったらご指摘お願いします。

@Article{berliner79:_b_tree_searc_algor,
  author = 	 {Berliner, H.},
  title = 	 {The {B*} tree search algorithm: A best-first proof procedure},
  journal = 	 {Artificial Intelligence},
  year = 	 1979,
  volume = 	 12,
  pages = 	 {23--40}
}
@Article{palay82:_b_tree_searc_algor,
  author = 	 {Palay, A. J.},
  title = 	 {The {B*} tree search algorithm -- new results},
  journal = 	 {Artificial Intelligence},
  year = 	 1982,
  volume = 	 19,
  pages = 	 {145--163}
}
@Article{berliner96:_b_probab_based_searc,
  author = 	 {Berliner, H. and McConnell, C.},
  title = 	 {{B*} probability based search},
  journal = 	 {Artificial Intelligence},
  year = 	 1996,
  volume = 	 86,
  pages = 	 {97--156}
}
@Article{baum97:_bayes_approac_to_relev_in_game_playin,
  author = 	 {Eric B. Baum and Warren D. Smith},
  title = 	 {A Bayesian approach to relevence in game playing},
  journal = 	 {Artificial Intelligence},
  year = 	 1997,
  volume = 	 97,
  pages = 	 {195--242}
}

_ profile feedback optimization

gcc-4.3 とGPS将棋でprofile feedback optimizationを試してみました。 ほぼ局面によらず約9%程度速くなるようです。手順は、以下のようにしました。

• 必要な.ccファイルすべてを#includeするファイルを作る
• -fprofile-generate つきでそのファイルをコンパイル
• 適当に探索させる
• -fprofile-use つきでコンパイルしなおす

適当に探索させる部分の詳細は、適当に選んだ16個の局面(進行度を16段階でつけた時に異なる進行度を持つ局面とした)を45秒探索としています。これを1局面だけの探索にしてテストも同じ局面で行った場合は、上記の数値より速くなりました。しかし、他の局面ではそれほど速度が向上しないので、予想通りですがoverfitと思われます。一方で、16局面で十分かどうかはよく分かりません:(

バイナリの大きさは2/3程度に小さくなりました。cachegrindによる観測ではキャッシュミスが減って分岐が増えていることと合わせると、通常のGPS将棋のコンパイルでは過剰にinline展開してしまっていると想像されます。

先日CSAの例会でGPS将棋でprofile feedbackは(過去に試した時点では)あまり効果はなかったと申しましたが、最近のコードとコンパイラでは割と効果があるようです。