 |
(GPS将棋開発参加記録)
|
|
|
(GPS将棋開発参加記録)
|
論文紹介を聞く。ボナンザの作者の方が紹介されていて気になっていたもの。
アイデアは、探索の残り深さが0になって静止探索に移る一手前で静的評価値が探索ウィンドウを十分外れていたらカットしても良いね(Futility Pruning at Frontier Nodes)、もう一手前でも大きく外れていたらカットすると効果あるね(Futility Pruning at Pre-Frontier Nodes)、そのさらに一手前でもとても大きく外れていたら探索深さを減らしても良いかな(Limited Razoring at Pre-Pre-Frontier Nodes)という3本立てと理解。但し王手は除外している。簡単なコードで書けて、かつ効果が高いのが魅力的。駒の価値の評価値の変動に依存しているので、将棋に使う場合は終盤よりも中盤に効果が高そうである。
逆に不満なところは、マージンをどの程度とるか(チェスではそれぞれ、2-4ポーン、ルーク、クイーンが良いらしい)の調整が面倒そうな点。 カットすることにリスクが無いのはマージンを十分に取ったfutility pruningだけなので、どのみちリスクを避けられないならばProbCutの方が扱いやすい可能性もある。 また、静止探索で、パスをしたら評価値をそのまま使う(``stand pat'')を前提としているようで、GPS将棋にはそのままでは適用できない。 (GPS将棋ではKFEnd流の「脅威を考慮した」静止探索をしているので、パスをしたら取られそうな駒について考慮した評価値を使っている)。 とは言え実装は簡単そうなので、効果を期待して時間があったら試してみたいと感じた。
「GPS将棋」というプレートが写った写真を無理矢理16x16に縮小してshortcut iconを指定してみた。しかし、…これは大変格好悪い。CPSのように見えるし。他のサイトと区別するという目的は達成されているのだけれど、美観は大事だと改めて認識してしまった。
ところでtdiaryでshortcut iconの指定の方法は用意されているのだろうか。head内が触れないので試しにbody内に埋めて見たところ、一応firefoxでは表示されてはいるらしい。
ついでに、RSSの中にもイメージを埋めてみる。index.rdfには画像のURLが入っているけど、はてなRSSで見えないな。あれれ?
<アナウンス>
情報処理学会ゲーム情報学研究会のURLが変更になっています。
http://sig-gi.c.u-tokyo.ac.jp/
しばらくは旧URLからもリダイレクトされるはずです。
</アナウンス>
どこに宣伝するべきなのかよく分からないのでとりあえず日記に。Wikiとかあると情報交換に便利だろうか?
もうすぐ発表申込締切。今年はどんな研究が発表されるだろうか。
情報処理学会誌7月号で鶴岡さんがさらっと紹介されている。「相手がこう指したら自分はこう指す」ということを覚えておく手法。
ちなみにGPS将棋にも今年の3月頃から同様のアイデアを入れていて非常に効果があった。キラー手の効果は、良い手を先に試すことで探索量を減らすという観点もあるが、GPS将棋の場合には指手生成の不具合を補うという効果が高いように思う。
将棋プログラムでは、探索の深いところでは試す指手が絞られているため、絞り方がまずいと色々弊害がある。例えば、GPS将棋は駒を取る手を良く読んで逃げる手をあまり読まない傾向がある。そうすると、居飛車の飛車先の歩交換の▲2四歩△同歩▲同飛(駒を取る)△2三歩(飛車とり)▲2八飛(逃げる)という手順をルート付近では指せても、別の手を指した後の深いところで歩交換を始めると△2三歩の後に飛車が(逃げる手を試さないため)取られそうで先手不利というありえない判断をしてしまう。この問題は「△2三歩には▲2八飛」と覚えておけばあっさり解決する。
よく練り込まれた指手の絞り方をしているプログラムにはこのような問題は少ないはずなので、指手をキーにしたキラー手は、作りたての、あるいは歴史の浅い将棋プログラムに対して効果(コストパフォーマンス)が高いのではないだろうか。この手法を導入した時には、「相手がうっかり変な手を指すと詰めろ飛車取りがかかる」というような発見が難しい手を深いところでも指せることを期待していて、そちらの効果は強いプログラムでも有効なはずであるが、今のところそのような感動する探索木は見たことがない。そのうち見てみたいものである。
http://gps.tanaka.ecc.u-tokyo.ac.jp/osl/cgi/viewcvs.cgi/trunk/osl/include/osl/search/bigramKillerMove.h?rev=1638&view=log
最近のtdiaryの変更により、プロキシがrefererを隠していると日記を書けないようなのでprivoxyの設定を変更。
一次予選は個人的には3回目の参加。慣れてきたこともあり和やかな雰囲気で開会を迎える。シードチームから2チーム辞退があったとのことで、2日目にいける枠が増えていた。油断するわけではないけれども、ちょっとほっとする。
期待と心地よい緊張の中で始まった第一試合は、初手合のChips戦。普通の振り飛車対居飛車になったと思いきや24手目△4四角、28手目△3三桂(図)と独創的に進む。今から思えば初戦からGPSの特徴が良くでた棋譜で幕を開けたと言えよう。まるで処女作に作家のテーマが入っているかのようである。(後日につづく)
tdiaryに棋譜をどう載せようか迷っていたのだが、yoshiki君による棋譜再生用 Javascript 将棋盤が登場したので早速使ってみる。素晴らしい。
さくさく動くので、wdoorの棋譜表示も乗り換えようかな。コメントや消費時間も見られると幸せかも。あと面倒そうだけど一手戻すボタン。
(追記) RSSやアンテナにはhiddenにしてあるCSA形式の棋譜が見えてしまっていますね。sageは隠してくれるみたいだけれども。(追記2) 一手戻すボタン、手数表示、消費時間表示が実装されたので更新しました。(追記3) ブラウザによっては見えなかったらしいので更新しました。
_ kaneko [コメントスパムが殺到したので7/5から7/6に移動しました。リンクされてた方がいらしたらごめんなさい。]