Yoshiki's notes
   


About
Open source software, shogi and my life outside of workplace.

Yoshiki Hayashi

Subscribe
RSS

Flavours

  • index
  • circa 1993
  • RSS
  • May
    Sun Mon Tue Wed Thu Fri Sat
           


    Categories

           
    Sun, 29 May 2005

    夕食
    最近、平日は外食することが多いので冷蔵庫の中の物を駄目にしがちで勿体ない。 ので、残り物を食べ尽くすべく料理してみる。で、いざ食べる段になってみると 食卓に8品も載っていてこれには我ながら呆れた。品目は、ごはん、わかめと豆腐の味噌汁、 小松菜と油揚げの煮びたし (昨日からの残り物)、大根の煮物 (同じく残り物)、 大根の葉とじゃこの和え物 (これも残り物)、野菜炒め、たたききゅうりのピリ辛醤油、 こんぶの佃煮、水菜の煮びたし、ピーマンとじゃこの炒め物。

    当然、一人でこんなにたくさん食べられるはずもなく、 基本的に生野菜が調理されたものに化けただけで 当初の目的は達することはできなかった。ちゃんと明日早めに帰ってきて自宅で 食事を取れということなのかな。

    [] permanent link

    Thu, 19 May 2005

    将棋盤 OCR
    他の開発チームメンバと渋谷で飲んでいるときに宣伝しろと言われたので宣伝してみる。 GPS 将棋の使っている将棋ライブラリ OSL の Subversion リポジトリに、 数ヶ月前にでっち上げた将棋盤 OCR スクリプトをしばらく前に放り込んだ (ViewCVS によるアクセス)。基本的には Ruby で書かれていて、 CSA 形式のデータを出力する。あまりにやる気のないコーディングなので、 宣伝するのは躊躇われるのだが、どうせ公開しているのに変わりはないので、 まぁ良いことにするか。

    認識率は使われているフォントにも依るが、体感としては80%くらいである。 慣れると、どの駒が間違いやすいかがわかって編集効率が上がるのだが、 そんなのがわかってるくらいなら認識アルゴリズムを直せ、という気もしないでもない。 手で盤を修正するよりも面倒なので放置してしまっているが。 また、持駒は駒の入る箱を認識させるのが面倒で そもそも detect すらしていなかったり、成桂などの小駒の成駒の一部は 滅多に現れないのをいいことにこれまた認識用のコードがなかったりする。 さらに言うと、エラーに弱く、升目の detect に失敗したときは途中で認識を 止めてしまったりする問題もある。 まぁ、一見さんお断りみたいなかなりいい加減な自分の環境に特化したプログラム だったりするが、我こそは、と思う人は使ってみてフィードバックを頂けると 改良されるかもしれない。しかしまぁ、こんな適当な Ruby スクリプトでも 無いよりは随分ましで、10局面くらいなら手で打った方が速いかもしれないが、 200局面くらいスキャンするとそれなりに役には立ったりする。

    [/shogi] permanent link

    Wed, 18 May 2005

    実現確率探索
    GPS 将棋では実現確率探索を採用していて、おおむね上手く行っていると言って よいと思うのだが、といっても問題が無いわけではない。今のところ、以下の様な 問題が発生している。

    • 実現確率の低い良い手を見逃す
    • 実現確率の低い手による水平線
    • 実現確率の高い手による無駄な探索

    まぁ、どれも実現確率探索の設計通りと言えば設計通りではあるんだが、あまりに 派手な見落としをしてくれたりするとやっぱり直したくなるのが心情ってもんである。

    最初のは GPS 将棋の実現確率の取り方が悪いような気がしなくもないが、一見 ただ捨ての手の実現確率が非常に低くなるために、3手必至やただ捨てからの 駒の素抜きなんかが読めないのはかなり問題である。後、この問題は非対称で、 当たりになってる駒は平気で見捨てるということはやったりする。だから、 きのあ将棋戦では竜を見捨ててちゃんと必至をかけられたわけだけど、竜をただ捨てして 追い込むなんてことは今の GPS 将棋には相当簡単な勝ちが見えていないと できない。2次予選の竜の卵戦では時間がなくて明確な勝ちじゃないのに やっちゃったけど。

    二つ目は、ナイーブな実現確率探索ではなく、α値更新探索延長実現確率探索で ある程度は緩和されてはいるが、例えば本当は良いはずなのに 変な受けの手で実現確率を消費してしまい、それを咎める手を生成できなくて 良い手を見送ってしまったりする。探索延長のもともとの動機は実現確率が低いために 深さが浅いところでリーフに達してしまい、そのために 良いと思ってしまっている局面をなくす、ということなので仕方が無いのだが、 実現確率が足りないために悪いと思ってしまっているのは結構ある。下手すると、 本当は良い手なのに、5手くらいで打ち切られてしまっていることもあったり、 以前は末端で相手の飛車当たりで実現確率を消費してしまい、飛車を逃げる手が 生成できずに評価値が悪くなっているのもあったりしたので、これも何とかしたい。 飛車逃げは静的探索をいじることで今は何とかなっているようである。

    三つ目も設計通りと言えなくはないと思うのだが、GPS 将棋の場合、全局通じて 同じ実現確率を用いているために、終盤では結構外れの手を延々と、しかも 終盤なのでそういう手は結構たくさんあって、全然深く読めないという問題がある。 延々と端の桂香を拾いに行く手を読まれるとそれはそれでうんざりしてしまう。 今は評価関数の仕様上、急激に相手玉に迫ることは可能だけれど、それが無理な ときは非常にじっくりと、むしろ全然迫らない、なんてことになってしまって いたりする。終盤は実現確率の値を変更する、というか進行度に応じて それなりに補正するようにした方が良いのかもしれない。

    まぁ、どれもこれも GPS 将棋の実現確率のカテゴリー分類と実現確率そのものの値が 甘いせいという気がしなくもないが、今使っている実現確率は表面的な 一部分の性質を用いた近似であるので、程度の差こそあれ、上の様な問題は常に 存在することになる。上手い解決策があれば論文になるのだろうが、そんなのは 一朝一夕には思い付かないので、とりあえずは地道に分類や値の調整をすることになる。

    少し実現確率探索について考えてみると、ナイーブな実現確率探索というのは 局面を与えると、手生成部分だけで探索木の形が一意に決まってしまうものである。 どんな評価関数を与えようと、同じ探索木を必ず辿るというのは何となく まずそうだというのは想像できると思う。そこで、α値更新による探索延長ということを 行うことにより、評価関数が探索木の形に影響を与えてくるようになる。 が、やはり探索木の形は大体実現確率の値で決まる。ある局面に対して、 変になるような実現確率の値を持っていると、その局面ではどんな評価値を 使っても話にならなくなってしまう。

    従来の仮評価による探索を考えてみると、こちらは探索木の形は手生成と 評価関数に依存している感じであり、指し手の性質というのは評価値の変動以外には あまり考慮されていない (しているのもあるだろうが)。今でも深さにより 前向き枝刈りにより残す手数を調整しているのかどうかは知らないが、残す 指し手の数はおそらく探索の深さとのバランスを考えて人間が決めた値で、 特に根拠があるわけではないように思う。

    指し手の統計的な性質を捨てるのはもったいないし、それだけに頼って 実は良くなる手が読めないのももったいない。何か良い方法がありそうな気がするのだが、 それは一体何だろうか。

    [/shogi] permanent link

    Fri, 13 May 2005

    大駒の持駒
    決勝の TACOS 戦での3六飛のような、歩を守るためだけに大駒を手放さないように 駒台にある時の点数をちょっと上げて実験。

    筋違い角では持ち角対1歩得でバランスが取れているので、まず大駒が持駒のときは 通常の価値+歩得にしてみる。が、対戦させてみると9勝11敗。棋譜を眺めてみると、 相手に1歩取りに行っている間に馬を作らせているのを発見して、ボーナスが 多きすぎたことがわかる。大駒の持駒は進行度や、さらには進行度差分ボーナスにも 関わってくるので評価値の影響はあんまり自明でなかったりする。

    で、ボーナスを半分、歩の評価値に変更してもう一回同じ局面から対戦させる。 今度は11勝8敗1千日手。GPS 将棋はまだまだ終盤が弱く、必勝の将棋を負けて いたりするので、対戦結果は実はあんまり信用できず棋譜を見ないと何とも 言えないのだが、ちょっと見た棋譜では中盤がもうちょっとまともになったような 感じはする。

    と思って、期待して全部みてみたが、変な手も結構多い。これが 元々弱いせいか、この変更のせいか調べていないが、まっとうになっている 部分もあるので、とりあえず有効にすることにする。

    [/shogi] permanent link

    Sun, 08 May 2005

    第15回世界コンピュータ将棋選手権
    激指を開発していた研究室にいたにも関わらず初めての参加だった世界コンピュータ 将棋選手権が終わった。終わったときはひたすら悔しさで一杯だったが、今冷静に なって振り返ると初の決勝進出はやっぱりよくやったな、と思う。

    GPS 将棋は大会直前に急に強くなったせいもあって、いろいろと準備不足だったことは 否めない。すごくうまくいけば決勝に出られるかも、とは思っていたので半分くらい 冗談で決勝に出れば見にいくよ、とは言っていたんだが、初日から 金子さんと共に 胃の痛い経験をするはめになるとは思ってもいなかった。

    胃の痛い理由の一つは、強さが全然安定していないことで、これはまっとうに強く している暇が全然なかったことが理由。大会2週間前に自玉と敵玉の進行度の差分で 評価値にボーナスを与えるコードを入れたのだが、これがいつでも差分に linear に ボーナスを与えるという凶悪な代物で、はまればめちゃくちゃ強いがはずれると まったく問題にならない、という将棋を指す原因になってしまった。しかも、 自己対戦では30手まで進めてから対戦していたので、序盤が極端に弱くなって しまっていることにまったく気付かず、それなりに余裕で通過する予定だった 1次予選でもかなり冷や冷やするはめになった。結果的には KFEnd 戦の 相手の水平線を誘発してみたり、きのあ戦の突撃からの鮮かな寄せに行ったりと、 変更の収支は黒字だったのでほっと一息といったところ。 来年はもっと安定した将棋の指せる胃の痛くならないプログラムにしたい。

    胃の痛い理由の二つ目は、二日目に詰みを詰みと認識しないバグが発見されたり、 原因不明のクラッシュが発生したり (ハードウェアを疑っている)、かなり致命的な バグが出てきたこと。こういうバグはたいてい私ではなく金子さんのバグなので、 胃の痛さとしてはまだましではあったけど。

    三日目はもうあんまり自分の参加したプログラムを見てる精神的余裕がなかったので、 かなりの時間を激指の観戦に費したが、今回の激指の指し回しには正直かなり 感心させられた。GPS 将棋にはいつやっても負ける気はしないが、自分の棋力では あの激指にはもう勝てなくなってる感じがする。非常に自然な指し方で的確に 相手の疑問手、悪手をとがめていく感じで、今後のコンピュータ将棋の展開に かなり希望をもらった。 普段 GPS 将棋の自己対戦などを解析しているときは、どうせ指せないだろうと 思って変な手のオンパレードのときも流して見ていたが、ちゃんと直していこうという 気力が湧いてきた。

    大会参加までは相当無理をしていたせいか、期間中は相当疲れていて、 大会が終わったらしばらく 将棋プログラムからは休もうと思っていたのに、今ではもう開発意欲に 満ち満ちているのが非常に不思議である。ソースコードも含め、ほぼ全ての 情報を公開してしまっているので来年は決勝進出も難しいかもしれないが、 次回はもっと完成度の高いプログラムで参加したい。

    [/shogi] permanent link