(元)駒得少年の冒険

_ 開発時間の確保

プロシン(www.ipsj.or.jp/prosym/)に参加。雑談中に静岡大の飯田先生から「毎日8時間くらい使わないと強くならないよ」というアドバイスを受ける。強くするにはその程度の投資は必要なのだろうなあ。研究で成果を出すにも資源の集中投入は重要だしね。しかし現状では、GPSチームは、全員合わせても1日8時間に到達しないのではないだろうか;-) 個人的には忘年会新年会の影響で最近触れてなかったけど、とりあえず週8時間は確保したいところ。

将棋関係の他の話題:

• 同じく飯田先生に見栄を切ってみる: 「評価関数の自動生成は面白いけど，将棋はもう充分良い評価関数があるから囲碁の方が向いているんじゃないの?」「いやいや，オセロも最初 は人間が書いた評価関数の方が強かったじゃないですか．将棋でもそのうち越えてみせますから」「ほー，本当にできるかな(笑)」みたいな会話(多少脚色あり)．さて，どうなるかな．
• 三輪さん(激指チーム)に即詰予測関数の進展をちょっと聞く．楽しそう．
• 長嶋さん(静岡大)と自動対戦について色々。プログラムが対局している画面を研究室の壁にプロジェクタで映しているとか。ついつい見入って仕事にならないとか(ありそう!)。GUIが完成したらうちもやるかな
• 横山さんと楽しく飲む(将棋の話はしたようなしなかったような

_ 脱力系バグ

(一応名をふせて)とある先生から gps@wdoor のバグレポートをいただく。開発グループの外の方からいただいた初のバグレポートかも。バグの中身は、相手が無意味な歩の成り捨てをすると投了してしまうというもの。このまま選手権に出場していたら悲劇だったので、とても助かった。(選手権で対戦する可能性もある敵に塩を送られた豪放な精神に感謝。コンピュータ将棋の世界はそういう雰囲気があるかも)

原因は数日前の水平線効果対策の不具合で、その様な局面は局面表に勝ちと登録してあるためそれ以上探索しないが、表にはその時に指すべき手を書いていなかったので、結局どう指せば良いか分からなくて投了してしまうというもの。このトホホな気分を表現するのは難しいが、例えるとコーヒーに塩を入れてしまった感じ?

ところで、その研究室では、卒研の将棋プログラムの対戦相手にgpsを使っていただいているそうで、嬉しいこと。

_ bug free な開発

今回の反省点はテストケースのcoverage不足。とはいえcoverageにあんまりこだわってテストファーストするのもやる気が出ないし、逆にテストを後回しにすると(一見)動いた満足感でその後テストを書く気持になりにくいし、適度なバランスが難しいところ。

開発者が全ての事態を想定してテストケースを書くことは無理なので、テストユーザを増やす努力を払うことも重要なのだろう。そろそろGPS将棋もその段階に来ているのかもしれない。つまりユーザインターフェースの作成や各種distribution向けpackage化などの作業が、強さの向上につながる可能性がある。とりあえず、知合い以外の人からも報告をもらえるように公式メイルアドレスを作るのはどうだろう。

_ 終盤における駒の価値

将棋プログラムでは序盤中盤終盤に応じて適切な評価関数を使いわけることが必要とされている。一方、現在のGPS将棋は、棋譜を見れば分かるようにほとんど駒得の点数しかない評価関数一つだけを用いている。その結果、端に無意味なと金を作るのが大好きで、終盤は寄せに行ってくれないという問題点がある。

終盤の評価関数の作り方については、玉に近いほど駒の得点を高く、離れるほど低くするという方法を山下さんが説明されている(http://www32.ocn.ne.jp/~yss/book.html#SEC3)。但し、その後に問題点が指摘されているので、そのまま使わない方が良いらしい。具体的には、速い攻めが難しい時に持駒を自玉の周辺に無意味に打ちつけてしまい攻め味がなくなる指手を選びがちとのこと(棚瀬さんから聞いたのだが、文献になっているわけではないかもしれない)。その対策としては、役に立たない駒の価値を減らすだけにして、駒の価値を増やすことはやめる、という方法をすぐに思いつくがどうだろう。きのあ将棋も減点方式のようだ(http://www12.ocn.ne.jp/~kinoa/kinoa_kaisetu/hyouka.htm)。持駒の手数を高くしすぎると、逆に持駒を使ってくれないという問題が発生するかもしれないので調整が難しそうである。

なお、終盤の評価関数では、玉の安全度も評価すべき項目である。山下さんの文献には具体的な計算方法が書かれているが、その方法に関する議論や他のプログラムでの計算方法については文献がないように思われる。この辺りはそれぞれの工夫があると思われる一方、手法の良さの評価が難しいので議論しにくいのかもしれない。

_ googlization

最近この日誌がgoogleに登録されたらしく、検索エンジン経由で来訪される方が増えたようだ。アクセスが増えるのは嬉しいことではあるのだけれど、この日誌は読み手の事を考えて書かれているとは言い難いので、本来はあまり上位に来るべきではないような気もする。現状ではコンピュータ将棋のプログラミングに関する文書がweb上に少ないということかもしれない。

_ 詰将棋で必要になる工夫いろいろ

後輩がはまっていたのでついでにまとめ。And-or木の探索の研究において長井さんのdf-pn(+)アルゴリズムは画期的な進歩であり、現在のところ最も良いアルゴリズムと考えられているが、そのまま詰将棋に適用するといくつか落とし穴があることが指摘されている:

• ループによる証明数無限増殖の問題 (囲碁，将棋で発生，オセロでは起こらない)
• rootからの距離を数える方法(岸本さんの対策): Df-pn in Go: An Application to the One-Eye Problem, ACG10 (http://www.cs.ualberta.ca/~kishi/pdf_file/acg_kishimoto_mueller.pdf)
• 将棋独自のヒューリスティクスを使えば防げるかもしれない?
• GHI問題 (graph history interaction, 詰将棋では詰を不詰と判定してしまう問題)
• 長井さんの対策: rootの閾値を工夫する (この方法は不詰の発見に弱いことが岸本さんにより指摘されている)
• 岸本さんの対策: A General Solution to the Graph History Interaction Problem, AAAI'04 (http://www.cs.ualberta.ca/~kishi/pdf_file/AAAI04KishimotoA.pdf)
• 合流による証明(反証)数の二重カウント問題
• 長井さんの対策: 親のポインタをたどって分岐を発見し条件によっては\sumの代わりに\maxを使う
• 柿木さんの対策: 受ける手が少ない時に特別扱い「詰将棋プログラムにおける証明数の２重カウント対策の一手法」CSA例会2005年１月(http://www02.so-net.ne.jp/~kakinoki/book.htm)

長井さんの研究はいずれも「コンピュータ将棋の進歩4」または情報処理学会論文誌に掲載された文献を参照。

_ その他の有用なenhancement

• 証明駒，反証駒: 脊尾さんのGPW99の論文(詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について)が出典，df-pnでも有効
• 岸本さんの研究で閾値の動的な制御 (to appear かな)
• 三輪さんの研究でh の初期化や，詰将棋をいつ呼ぶか (http://www.logos.ic.i.u-tokyo.ac.jp/~miwa/papers.html)
• 局面表のGCについて: 大変そうなのでおいかけてなかったり
• その他、金子も詰将棋関連の研究にちょっと関わっていたり

(他に関連研究がありましたらコメントお願いします)