忍者ブログ
コンピュータ将棋など…。
[352] [351] [350] [349] [348] [347] [346] [345] [344] [343] [342]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

なのはの詰ルーチンはdf-pnベースで、基本的に岸本さんの「IS 将棋の詰将棋解答プログラムについて」http://www.is.titech.ac.jp/~kishi/pdf_file/csa.pdf の最小距離法を使っています。
この中の「4. 最小距離法の限界」に書かれている「将棋依存の条件を書き下すことで解決している」というのがなんなのか未だわかりません…。

ただ、問題を解かせている中で異様に時間がかかるものがあり、よくよく確認してみるとこの事例に当てはまっていました。

それは大内延介「実戦詰将棋100題」第95番(17手詰)という問題で、現状だと69.3秒かかっていました。


大内95

正解手順は▲11角打▽12玉(22)▲22金打▽13玉(12)▲12金(22)<略>と進むのですが、まず▲11角打▽13玉(22)▲12金打と読んでしまうと、その局面はルートからの最小距離md=3でハッシュに登録します。
その後、正解手順の▲11角打▽12玉(22)▲22金打▽13玉(12)まで来ると次の手の▲12金打とした局面がmd=3で登録されているため異常な子節点の判断となり、その局面のほかの手が反証されない限り展開されなくなってしまい、そこで長時間費やしていました。

適当な対策を入れたところこの問題自体は 9ms で解けるようになり、「これで解決!」と思いきや、他の問題集で解けなくなっている問題が出てきたり、逆にノード数がやたらと増加してしまう問題があったりで、平均的にもパフォーマンスが落ちていました。orz

あちらを立てればこちらが立たず、という感じでなかなかうまくいきません。


しかも、これって2008年11月20日のエントリーでもわからないって言ってるし、進歩ないなー。orz
PR

コメント
無題
>あちらを立てればこちらが立たず

複数のバリエーションで並列探索して早い者勝ち!...はどうでしょう?
【2011/11/23 04:09】 NAME[紫外線] WEBLINK[URL] EDIT[]
Re:無題
それ、いいかも。
でも、思考ルーチンから呼び出すときにちょっと困りますね。
【2011/11/24 19:33】
将棋依存の条件を書き下すこと
前回の記事にコメントした時も「将棋依存の条件を書き下す」って何?状態でしたが、今回かずさんが入れた「適当な対策」で何を書いたのか分からないので問題が何なのかも分からない(爆)。

今回の記事を見て、やっぱり「いい加減に実装」しちゃダメなんだろうなーとは思うものの。

ソースが得られるところからヒントを探すしかないのかな…。
GPS将棋とかBonanzaとか。

あるいは、岸本さんに直接聞いてみるのか(爆)。
【2011/11/23 16:50】 NAME[うさぴょんの育ての親] WEBLINK[] EDIT[]
Re:将棋依存の条件を書き下すこと
手順を遡って、同一局面がなかったら異常な子節点でない、としてみたら、見かけ上の分岐に引っかかりました。
【2011/11/24 19:35】
何か分かりそうな気がするんだけど…
うーーん、時間をかけて考えれば分かりそうなところまで辿り着いている感じがすごーくするんですけれども…。
「手順を遡る」っていうところで既にある意味まずい気がします。
df-pnじゃなくて、もっと前のアルゴリズムだったのか、記憶が怪しいんですが…。

そもそも「局面は手順と分けられない」ので、「ハッシュ値として手順も入れておく」って誰がいつどこでやってたんでしたっけか。
【2011/12/17 21:23】 NAME[うさぴょんの育ての親] WEBLINK[] EDIT[]
Re:何か分かりそうな気がするんだけど…
手順も入れておくのは岸本さんの不詰めを正しく証明するアルゴリズムでしょうか。
もうちょっとがんばってみます。
【2012/01/02 04:45】
無題
あぁ、私は古い「コンピュータ将棋協会誌」とか「コンピュータ将棋の進歩」シリーズとか、その辺りで見たのかも知れないです…。あるいは何かの折りの研究発表だったかも知れず。
「ネット上にある情報」と「ない情報」と、色々あるわけで。
誰がいつどこで発表したのか&いつ私がそれを知ったのか、までは、覚え切れていないですねぇ…。頭の中ぐちゃぐちゃで申し訳ない。

新しいテクニックが発表されたら、それまでのテクニックは不要になったりもしているのですが、どの時点で何が不要になったのかまでは流石に覚え切れない…。GHI問題って、それだけで何か大量に論文が出ていたし(--;

自分で書いたdf-pnのコードも『何かバグってる』んですが…_no
【2012/01/02 11:45】 NAME[うさぴょんの育ての親] WEBLINK[] EDIT[]
Re:無題
まぁ、試行錯誤していきます。
【2012/01/03 01:24】


コメントフォーム
お名前
タイトル
文字色
メールアドレス
URL
コメント
パスワード
  Vodafone絵文字 i-mode絵文字 Ezweb絵文字


トラックバック
この記事にトラックバックする:


忍者ブログ [PR]
カレンダー
09 2017/10 11
S M T W T F S
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
フリーエリア
なのはの応援をしていただき、かつ協力いただける方は、アマゾンでの買い物は下のリンクからお願いします
プロフィール
HN:
かず
性別:
非公開
バーコード
ブログ内検索
最古記事
カウンター
アクセス解析