駒得少年の冒険

_ 人工知能学会会誌 解説記事

2012年1月号に「コンピュータ将棋の評価関数と棋譜を教師とした機械学習」という解説記事を書きました。解説なので内容は基本的に既存の手法の説明です。実験を通じて性能を紹介する部分で、将棋クラブ24(出版された24万局集)やコンピュータ将棋(floodgate)の棋譜の学習結果と対戦勝率を調べてみていて、ここは関係者の人にも新しいかもしれません。意外とfloodgateの棋譜が健闘し、一方、24の棋譜をランダムに使うのはやめたほうが良さそうという結論でした。なお、1年後に無料でPDFが公開されるようですが、それまでに読むには人工知能学会の会員になるか、印刷された会誌を探すかする必要があるかもしれません。

_ CSAライブラリ

次回の選手権向けにosl-for-csa (バージョン 0.8)と gpsshogi-for-csa (バージョン 0.8)が登録されました。forkしたタイミングはそれぞれr4395とr2633です。ユーザから見たライブラリの使い方に関しては、第20回の世界コンピュータ将棋選手権に参加されたStatyの作者の方が、とてもわかりやすい説明(http://masayosshi.com/shogi/)を書いてくださっています。

_ USIと状態管理案

右図は、あから2010の通信の一部でも使っていた、USIをベースにしたプロトコルの簡略化した状態遷移図です。(ちなみに秋頃書いていたGPS将棋の紹介記事がコンピュータソフトウェア1月号に掲載予定です。USIにも触れていてこの図はここから取りました。) 図中で、>が上流から思考部への通信、<が思考部から上流への通信です。

基本的な状態遷移は図の実線の矢印部分です: プログラムは左のidle状態でスタートし、positionを受け取ったり、図では省略されていますがoptionなどの処理をします。go infiniteを受け取ると、思考に入りsearch状態に遷移します。search状態では、infoという文法で定期的に状態を上流に伝えます。stopを受け取ると searrh finished状態に遷移し、bestmove で最善手を報告してidleに戻ります。

さて、思考部を作っていると、stopが来る前に指し手が一手に定まったらbestmoveを返したくなります(特に既存のプログラムを微調整してUSIに対応する場合)。上流側も、もう指手が変化しないという状態を知ると良い場合があります(たとえば、いわゆる合議のように思考部の最善手を集約して指手を決める時に持ち時間を節約したい)。そこで、あから2010では、search状態から下の点線部分にあるように思考部がstopを待たずにsearch finished 状態に遷移することを許しました。すると、上流のstopと思考部のbestmoveが同時に起こったらどうなるか? という競合の問題を解決する必要があります。あから2010の場合は、図のsearch finishedやidle状態の点線のように、search以外の状態で到着したstopを無視するという解をとりました。(が、少し実装は面倒なので、この文章の末尾で別の案を提案します)

USIの元提案 (http://www.geocities.jp/shogidokoro/usi.html) や、将棋所バージョン (http://www.geocities.jp/shogidokoro/usi.html) では、go infinite に限ってstopが来るまではbestmoveの出力を禁止することで、競合が起こらないようにしています。しかし、go byoyomi 10000 等時間指定がある時は、依然競合があります。時間制限がある時はstopを使わないなら別ですが、それは不便ですし、仮に時間前のbestmove出力を禁止したとしても、stopが思考部に届くまでに10秒を越える等の例で分かるように、通信に遅延がある環境で頑健なクライアントを作りたい場合は競合に対処しておく必要が依然としてあるわけです。

ところで、囲碁のgtpというプロトコルでは、コマンドと応答に名前をつけることが可能です。具体例を示すと、usiのgoとbestmoveに対応する応答はgtpでは
genmove b
= E7
となりますが、ここでgenmoveの行頭に数値のidをつけると、
0 genmove b
0 = E7
というように、応答の先頭にもそのidを提示する規約になっています。http://www.lysator.liu.se/~gunnar/gtp/gtp2-spec-draft2/gtp2-spec.htmlの2.5節のあたり。

そこで、USIでもposition, go, info, stopにid=xで対応する局面を明示可能にして、
position id=0 startpos
go id=0 infinite
info id=0 pv 7g7f
stop id=0
bestmove id=0 7g7f

等でいかがでしょう。細かくは、goやstopで提示されるidは思考部が最後に受け取ったpositionと同じでなければならない、と決めておいたほうが良いかもしれません。またid=xをどこに挟むかは、理由があれば変更しても良いかもしれません。(コメント歓迎)

_ その他の変更案

細かいところでいくつか

• go ignoremoves: go searchmoves 7g7f 2g2f とすると、7g7fと2g2fだけ探索するという文法があります。この反転で、go ignoremoves 7g7f 2g2fとすると7g7fと2g2fは候補手に含めない、という文法が必要です。応用先は、予測読みとか、探索の分担があります。上流が合法手を全て生成できれば、searchmovesでも理論上は同等のことができますが、合法手が100を越えることを考えると冗長さが耐えられないので。
• go book: 定跡が有る時だけ返す。無い時はpassを返す。思考部が定跡を使うかどうかを制御したいケースがあります。原案では、USI_OwnBookというオプションで設定することが提案されています。しかしオプション関係は面倒なので、通常のgoでは定跡は使わない。定跡の手がほしい時は専用のgo bookコマンドを使うと使い分けては? (定跡がなければ探索させるとかは上流で制御)
• go declarewin: 勝ち宣言できる時だけ返す。できない時はpassを返す。
• ponder 変更: あまり検討していませんが、idがあるとシンプルにできることの紹介です。 (1) ponderを許可するかどうかは上流から通知される (2) 思考部はponderが許可されている場合、いつでもinfo を上流に送って良いことにする。GUIの場合に、これを表示するかしないかは上流が決める。思考部が現在どの局面を探索しているかはidとpvから読み取る。最後の探索結果がbestmove id=0 7g7fで、その後
  info id=0 7g7f 3c3d 2g2fであれば、34歩の局面を予想している、と解釈可能(ですよね)。
• legalmoves 局面の合法手を全て生成(コマンド名は要検討)

gtpやgogui から輸入すると良さそうな機能としては、

• list_commands 思考部がサポートしているコマンドを表示
• オプションはgui側が保存する (ユーザが保存メニューを選ぶと、今までに思考部に与えたset option関係をファイルに保存する)
• gogui-analyze_commands goguiから輸入

などがあります。gogui (http://gogui.sourceforge.net/)で囲碁プログラムを開発する場合、開発者はデバッグ用に独自のgtpコマンドを作って、応答を文字列だけでなく、各マスに対応するする数値を白や黒の四角の大きさで可視化することもできます。

_ 追記

コメントいただいたこともあり少し補足します

• idなくても動くのでは?
  動くけど、idの方がbetterという立場の提案です。開発過程では、bestmoveをうっかり二回返すバグとか、(ponder絡みの混乱で)古い局面のinfo を送ってしまうなどは十分想定されて、id方式の方が怪しい挙動を手早く検知できて便利/普及しやすいかと。
• ponderも動くのでは?
  ponderに関しては動かないという問題はなくて、相手考慮中に一手だけ予想して探索するという方式に固定されていることが、他の方式のプログラムとは合わないということですね。提案方式なら複数の手を順番に/並行して探索していても、一応情報の表示が可能です。
• この文章の位置づけについて
  改定案が出されるならこのような点も議論してほしいという希望がありますが、この案で多数派工作をしようという意図はありません。メリットデメリットを共有したり、見落としがないかとか、トレードオフがある場合はどちらが良いかの議論をするための材料になればという趣旨です。コメントありがとうございます。

_ shogi-server (+floodgate)@wdoor 停止

12月10日(土)に学内の停電があるため、wdoorで動かしているshogi-serverはfloodgate機能も含めて停止します。再開は、同日夜または月曜日の可能性が高いです。

_ 16th Copmuter Olympiad

昨年の金沢に続き、今年はTirburgでコンピュータオリンピアード将棋部門が開かれ、Bonanzaをプレーオフで破ったGPS将棋が優勝という結果でした。持ち時間は40分切れ負けでした。勝敗としてはGPW杯で負けた借りを返せて良かったのですが、棋譜を見ても、玉側から仕掛けたりとか、あまり強く見えないのは…

_ GPW2011

ゲームプログラミングワークショップ2011が開催され今年も素晴らしい研究が多数集まりました。予稿集をぜひご覧ください。

_ GPS将棋r2614

今年のGPS将棋のWindows版が公開されています。Bonanzaや激指とは異なる読みを試したい方か、柿木将棋以外の詰み探索を試したい方には有用かもしれません。LinuxのDebianやUbuntuをお使いのかたは公式パッケージに採録されています。