詰め将棋エンジン - 詰め太郎の冒険

我は今週から年明けまで休暇なのでグウタラしながら無明のコード書きです。

誕生当時はちょいと複雑な詰め将棋が苦手な詰め太郎君でしたが色々改良・改造してそれなりに速くなりました。

変更点

①普通は合法手の生成はその度に行いますが、詰め将棋の場合手数が限られるので一度訪れた局面からの合法手は記憶しておき再使用します。(合法手生成が遅くてもこれならカナリ時間短縮になります)

②「詰め」の判断も時間が比較的掛かるので詰まない局面は覚えておき判断の高速化を図ります。

③飛・角・香を打つ手のうち玉との距離があって意味の無い合い駒が起きる手は削る。

(例) 

13手詰め
http://www2.wbs.ne.jp/~vmax/shogi/java2/java13.3.html

この場合、飛は8箇所に打てますが9二、8二、7二...に打つ手は無駄なので削ります。

④(安直ですが)並列化でSPEED UPです。

結果

速度は持ち駒(大駒・香の有無)によってかなり違ってくるようです。

13手詰め
http://www2.wbs.ne.jp/~vmax/shogi/java2/java13.3.html

ラップトップ(2コア)で計測して約50秒で回答を見つけました。初めてチャレンジした時は(①~④無しで)時間が掛かりすぎたのでギブアップしました。

13手詰め
http://www2.wbs.ne.jp/~vmax/shogi/java2/java13.2.html

この様に大駒・香が持ち駒に無い場合は10秒程度ですみます。

発見

素朴な質問
http://www.tokinclub.com/dp/node/562

以前「飛・角・歩の不成りは在り得るか?」と質問しましたが、ここにその回答(?)を見つけました。

15手詰め
http://www2.wbs.ne.jp/~vmax/shogi/java2/java15.2.html

詰める為には不成りが必要でこれ無しでは正解にたどり着けません。

いや~、詰め将棋は奥が深いですね。

追記

13手詰め
http://www2.wbs.ne.jp/~vmax/shogi/java2/java13.3.html

...は改良の結果、ラップトップ(2コア)では30秒程度に短縮ですう。

投稿者: 紫外線 投稿日時: 月, 12/21/2009 - 11:10 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

岡村孝雄氏作 「驚愕の曠野」

詰め将棋について読んでいたらトンデモナイ作品がありました。

史上初、完全玉座裸玉
http://www.ne.jp/asahi/tetsu/toybox/kinen/kinen003.htm

詰め太郎の更なる改良

改良点⑤

これは上記の③と関係しますが、「敵玉の近くに打つ手を優先処理する」

改良点⑥

王手判断を少々高速化

...全部合わせて上記の13手詰めはラップトップ(2コア)で12秒程度に短縮しました。

(追記)更に頑張って9秒台ネ。

改造してみました...

前述の...

①普通は合法手の生成はその度に行いますが、詰め将棋の場合手数が限られるので一度訪れた局面からの合法手は記憶しておき再使用します。(合法手生成が遅くてもこれならカナリ時間短縮になります)

を...「合法手」の代わりに「局面」を記憶して試験しましたが、速度は変わらずでした。従って却下でした。

「局面」を記憶することにより演算時間の得は在った筈なのですが「局面」は「手」を記憶するより遥かにメモリーを食うので差し引きゼロらしい...です。

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。