推理将棋（隣の将棋）コミュの954番後手玉棒立ち耐久戦（手数探索問題）

935番からの派生トピックです。

・先手は3手目から居玉への連続王手
・不成なし
・同一局面なし

でどこまで長い手数をかけて詰ませられるでしょうか？

なお、935番や939番のネタばれを意図せず含む可能性がありますので、
両題のネタばれをされたくない方は、これらを解いてからの閲覧をお勧めします。

コメント(45)

最初
全て
最新の40件

前

[6] mixiユーザー 01月26日 11:15

71銀の可能性は昨晩気づきましたが、それでも高々倍にしかならないんですよね。
後半は31銀も取らせてしまうのかしらん？
それもちょっと伸びる程度で終わりそうだなぁ・・・。

[7] mixiユーザー 01月26日 16:18

病院から帰宅したので途中経過報告。
現在の最長は1661手です。
31銀は先手に取らせて、打たせて取り返し、同一盤面で持ち駒が違う局面を作るのに利用しているみたいです。

[8] mixiユーザー 01月26日 17:43

おたがい病院帰りとは奇遇ですね(笑)
やっぱり銀は取らせるんですね。ということは私の考え方は大部分変えないと・・・。

[9] mixiユーザー 01月26日 18:12

千日手チェックにバグが有れば無限ループに陥ってプログラムが不正終了するので、今まで約1日プログラムが動いているのは、千日手チェックが正当に機能している証拠だと思いたいです。

現在の最長は1673手です。
今まで見た詰め上がり局面はすべて
先手 31龍42馬
後手 41銀61角62銀
ですね。
長手数の収束はこれしかないのかもしれません。

[10] mixiユーザー 01月26日 19:05

61角！？
21飛、31合、同飛成、41角合、42龍としたのを52同角と61同角で移動していくんですかね。
それ以外に61に後手角が発生する展開ってないですよね。

ということは、終盤は角1枚でのループを構成しないといけないわけですか。
思ったより最長は難問の様相を呈してまいりました。

[11] mixiユーザー 01月26日 21:25

なんかすごいことになってますね。手数が4桁で61角！とは。
ちなみに、23歩が消えるのは何手目なんでしょうね。

23歩の有無以外は全く同じ局面が可能なので手数の半分より少し少なめのところかなと思いましたが・・・600手目ぐらいかな？

[12] mixiユーザー 01月26日 21:47

1673手解を並べてみました。

＞21飛、31合、同飛成、41角合、42龍としたのを52同角と61同角で移動していくんですかね。
＞それ以外に61に後手角が発生する展開ってないですよね。

仰るとおりの手順です。
一度発生した61角は取られて、再生しています。

＞ちなみに、23歩が消えるのは何手目なんでしょうね。

231手目で消えています。
仰るとおり23歩の有無に関わらず同じ手順が可能なのでこれをもっと後に行えば2400手も可能になるかな

[13] mixiユーザー 01月26日 22:32

一度61角が発生してまた消えるとか、人力じゃ絶対思いつかないでしょうね。
ちなみに21桂はやっぱり早いうちに消えるんでしょうかね。
そうでないと角1枚でのループを構成できませんし。

[14] mixiユーザー 01月26日 23:03

>> ＞ちなみに、23歩が消えるのは何手目なんでしょうね。
>>
>> 231手目で消えています。
>> 仰るとおり23歩の有無に関わらず同じ手順が可能なのでこれをもっと後に行えば2400手も可能になるかな

ということは、23歩が消えてから1400手以上も手が続くんですね。
逆に、その231手目以降の同じ手順を踏めば、23歩を残したまま頑張って、1500手ぐらいまで可能、その後23歩を消して・・・すごい手順だ。

[15] mixiユーザー 01月27日 19:16

24歩を1050手までは指さない様にプログラムを改造したら、2441手解を出力しました。
1050と言う値はプログラム実行時に指定できるようにして、幾つかの値で試してみましたが、今のところ1050が最も長い解を出力しています。
23歩以降1400手続くことから、予想はしていましたが2400手超えが起こるとは

問題が提起されたときには想像もつかなかったです。

[16] mixiユーザー 01月27日 19:41

私も2400は想像だにしてなかったです。
これは人間側は降参するしかないでしょうか(笑)

[17] mixiユーザー 01月27日 22:11

24歩をずっと最後まで指さないと何手まで伸びますか?

コメント#11で23歩が消えるのは、半分より少なめと書きましたけど、23歩がいるまま手順をやりつくした後、23歩を消すのであれば、半分よりやや多めという気がしてきました。少なくとも、22角と21桂は復活できないはずなので、23歩の有無で復元できない局面を考えていくと、前半戦の方が手数が長いはず。

へっぽこさんの検討から勝手に予測すると、23歩がいる前半戦が約1500手、24歩以降の後半戦が1300～1400手になりませんかね。

[18] mixiユーザー 01月27日 22:30

>24歩をずっと最後まで指さないと何手まで伸びますか?

なるほど、これを試してみれば全体の手数が見積もれますね。
24歩を10000手目以降にしか指さない様に指定して、事実上指さない条件の下で探索をしてみます。

[19] mixiユーザー 01月27日 23:06

　1つ仮説を提案します。思い付きですので反論は大歓迎です。
（前提）22角と21桂は復活できない。
（仮説）後手24歩はほぼ手数の真ん中で指される。
（仮説に至る補題）
　先手が15角と指さないといけないのは後手がその次の手で24に駒を打つときだけである。
［補題の証明］
　先手15角の次に後手が24に駒を打たないのであれば（24歩と指すときを除き）、
15角の代わりに24角と打っても以下の進行に支障をきたさない。その角が次の手
で動くのであれば、同一局面禁止の条件から15角と24角はどちらか一方しか着手
できない。（ここまでは問題ないと思う）
　24角（もしくは15角）と打った後、他の手順を挟んだとしても、打った角が移動した時点で、
24角と15角と打った局面が両方存在するなら同一局面に戻っていると推定される
（この部分は推定）。もしくは角を打つ前の局面が同一の場合もあり得る。
　上記推定部分が正しいのであれば、補題は証明されていると考える。

（結論）
　上記補題が正しいのであれば、24歩が指されるのは半分より若干前
（最初の2手と、24歩が指される直前の15角の3手分だけ前が長いが、収束部分が
あるため後ろが長くなるであろう）と思います。

[20] mixiユーザー 01月27日 23:32

＞＞（前提）22角と21桂は復活できない。
ここのところ、単純な２手ではありません。

前半は22角や21桂が居るうちの悪あがきというか、先手が31銀を奪って62に捨てるなど駒の繰り替えがあるので、数10手は手数を稼げるのでは・・・。

後半が長くなる可能性としては、収束に近いところで復元できない局面がある場合（前半で使えない手順がある場合）と考えます。

[21] mixiユーザー 01月28日 09:04

24歩をずっと指さないで探索させてみたところ、1477手解を出力しました。
と言うことは2800手は行けるのかな。
24歩を1400手までは指さないようにして、探索させて見ます。

[22] mixiユーザー 01月28日 13:35

24歩を1350手目まで指さないように指定したところ2639手解を出力しました。

[23] mixiユーザー 01月28日 18:55

2655手解を出力しました。
もっと長い解が有るでしょうが、全探索は時間的に不可能なのでこれにてプログラムを終了します。

棋譜を上げておきますので、ネタバレを承知して読みたい方はダウンロードして下さい。
http://homepage3.nifty.com/SilverHammer/mixi954_2655_00000.csa

[24] mixiユーザー 01月28日 23:17

>>2655手解を出力しました。

棋譜をちらっと見ました。

2手目銀とは驚きです。2手目歩の方が長いのではないでしょうか。

というのは次の理由からです。
１）22角と21桂が消えるのが45手目とは早すぎます。2手目歩ですと、22角と21桂が消えるまでもっと手数を延ばせます。
２）後の手順を考えても、21桂が消えた後はスペースが広い分、2手目歩の方が有利。

[25] mixiユーザー 01月29日 00:43

>2手目銀とは驚きです。2手目歩の方が長いのではないでしょうか。

御助言ありがとうございます。

プログラムの手生成の順番で銀が先になったのでこうなりました。
試しに2手目54歩を強制したところ24歩を突かなくてもあっという間に3800手を超えました。31飛型と53飛型でパターンが増えるのが利いているようです。
24歩を突けば7000手を超えるでしょう。

[26] mixiユーザー 01月29日 00:57

7000手越え

53に後手駒があるパターンが丸々増えるとはいえ、すごい。小宇宙だ

[27] mixiユーザー 01月29日 07:08

現在の最長は8569手です。

http://homepage3.nifty.com/SilverHammer/mixi954_8569_00000.csa

[28] mixiユーザー 01月29日 09:06

>> 現在の最長は8569手です。

いやー、延びますねえ。

チラ見しましたが、
・28手目33桂：あまりにも早すぎます。
・4152手目24歩：その後に4400手以上！

ということは、33桂以前を工夫して序盤を延ばし、24歩以前に4500手越えが可能と推察いたします。9000手も越えそうな勢いですね。

[29] mixiユーザー 01月29日 20:30

　ここまでの結果となおさんのコメントを素に、事が想像以上に重大であることが
判明してきた本問に対して、探索アプローチ案を提案します。

最長手順探索アプローチ（案）
(1)ここまでの結果から、2手目は歩に決め打ち
(2)24歩を禁じた上で
　(2-a)33桂を禁じて最長手順を探索する。
　(2-b)33角と31角を禁じて最長手順を探索する。
(3)(2-a)と(2-b)のうち長手数となった方（おそらく2-bであろう）を素に
　　もう一方を解禁して最長手順を探索する。
(4)(3)で見つかった手順を基本に24歩を解禁して手順を探索する。

　提案だけして、実行環境はおろか実行の力もなく、へっぽこさんにおんぶに
抱っこ状態ですが、ご興味を持っていただけるのであれば、今後のプログラム
作成時の参考にしていただければ幸いです。

[30] mixiユーザー 01月29日 23:53

魚熊さんの方針に近いですが
・24歩を指定した手数まで指さない
・33桂を指定した手数まで指さない
プログラムを走らせています。
33桂を200手、24歩を5000手まで指さないように指定して、朝からプログラムを走らせています。
現在は9731手解を出力しています。
http://homepage3.nifty.com/SilverHammer/mixi954_9731_00000.csa
大台が見えてきました。

[31] mixiユーザー 01月30日 09:19

おお、5桁

も視野に入ってきましたか。

チラ見すると、
・12手目33角(22):超序盤！ですので、
魚熊さんの方針(2)の最初に
(2-0)24歩, 33桂, 33角(31角)を全部禁じて、最長(王手連続)探索
を入れた方が最長手数に早く見つけることができるかもしれませんね。

[32] mixiユーザー 01月31日 04:03

24歩は5500手まで指さない
33桂は250手まで指さない
22角は1000手まで動かさないで探索したら
21328秒で10233手解を出力しました。
大台突破です。

http://homepage3.nifty.com/SilverHammer/mixi954_10233_00000.csa

[33] mixiユーザー 01月31日 11:58

10239手まで伸びました。
http://homepage3.nifty.com/SilverHammer/mixi954_10239_03708.csa

全探索は時間的に無理ですので、これでプログラムを終了します。
まさか5桁になるとは誰も予想できなかったでしょう。

[34] mixiユーザー 01月31日 14:01

へっぽこさんお疲れ様でした。
昨日詰工房で『DD++さん』、『なおさん』とそろそろ大台に乗ったかなと話しました。人力での200手から大幅な飛躍でした。素晴らしい！

[35] mixiユーザー 01月31日 18:27

まさか5桁まで伸びるとは・・・。
機械の力、そしてそれをあつかうへっぽこさんのすごさをまざまざと見せつけられる結果でした。

[36] mixiユーザー 01月31日 21:32

>>10239手まで伸びました。
探索ありがとうございます。早速、並べてみました(笑)
KIFUで１手0.05秒の速度で再生しても8分かかりました。
ものすごい勢いで51玉の周囲が点滅するように動きますね。途中、金や銀が１枚の局面があったり、61角や61銀が出現しては消えたり、狭い中で違う局面が続く様子は感動モノです。詰め上がりは珍しい61金62金形。

[37] mixiユーザー 02月01日 01:15

　1万手超えおめでとうございます。
　ただ、250手目まで禁じた33桂が252手目、5500手目まで禁じた後手22角の移動
が5502手目であることに疑問を感じ、252手目までを詳細検討した結果、以下の
疑問点を確認しました。

・17-18手目52銀同金上について
　当該部分は
　62銀　同金　31飛　41角　同飛成　同金　24角　33銀　同角成　42飛
　52銀　同金寄　42馬　同金直
に変更することにより、明らかに12手延ばせます。21桂が33に移動するまでに
元々61にいた金は42－52-62－61と移動しますが、その金が42にいる間に71の
銀が53まで移動しますので、金の移動に伴って同一局面に戻っていないことは
確認しています。
　この手順がその後再生されるかどうかは確認していませんが、もし手数に
比例して再生されるのであれば、当該手順は40回程度出現可能であり、500手
近い手数の増加に寄与する可能性があります。

　以上既確認部分

以下私案＋なおさんのコメントに基づく推定部分

　今までの議論から、最長手順は
(1)後手23歩、22角、21桂不動のまま極力手数を伸ばす
(2-a)後手22角型のまま後手33桂と指し、(1)の手順を含め、21飛後31、41
　　　連続合の手順による手数の最長化を図る。
(2-b)後手21桂型のまま33角と指し、(1)の手順を含め、先手の62，42，33
　　　等からの角打ちに伴う手数の最長化を図る。
(3)(2)で指さなかった後手の手（桂もしくは角）の手を指し、それに伴う
　　　最長手数の探索を行う。

という手順で求めるのが良い（ただし、2-aと2-bは長いほうを採択する）
と考えています。

　なお、以上の推論は魚熊の個人的見解であり、なおさんのコメントは
参考にさせていただいたものの、なおさんには全く関係のないものである
ことを付記しておきます。

　さらに、以上の手順を実行確認されるのはへっぽこさんの個人的かつ
PCの余裕のあるときに確認いただけるのであれば、それだけで有難いこと
であり、全く強要するつもりのないことであります。　　

[39] mixiユーザー 02月01日 06:58

一点だけコメント。
33桂以前に「53金」形が現れていないので、序盤は延びる余地はあるかなと感じました。

ただ、そのうえで、魚熊さんの(2a～3)と(2b～3)の比較もあり、計算するのも大変だと思いますので・・・

[41] mixiユーザー 02月01日 15:18

40番コメント削除（内容の間違いに気付いたため）

　33桂以前には（22角もそのままのため）先手が飛角を同時に持ち駒にできません。
そのため、53金型は
　後手62金　持ち駒先手角　後手飛銀　で
　15角　24飛　同角　33銀　53飛　同金　33角成　42飛　52銀　同金　42馬
・・・という手順でしか実現できないと思います。
上記手順は61の金が52を通る手順を含んでいますので、37でコメントした手順
とどちらが長くなるかの検討が必要です（同手数？）。

　なお上記手順が33桂以前に実現可能なのは後手の（41金、71銀）が
（41金、71銀）、（41金、先）、（41金、後）、（先、71銀）、
（後、71銀）、（先、先）、（先、後）、（後、後）、（後、先）
（「先」「後」はそれぞれ「先手の持ち駒」「後手の持ち駒」の意味）
（以上実現可能確認済）と当該金銀が61にあるとき（実現可否不明）
ですので、最少9通り、最大16通り可能性があり、33桂以前の手数寄与は
90－160手と想定されます。

　本稿記述中に思いつきましたが、71銀の移動は（71銀自体が再生不可である
ため）33桂（33角、31角）以前に行うのが良いかどうかは検討が必要です。

　いずれにしても真の最長手数を見つけるのは（ここまで来ても）まだまだ
先のことと思えます。

[43] mixiユーザー 02月02日 00:03

33桂以降は、22角が残っている状態でも71銀が再生可能なようです。
（828手目71銀）41→52→61→62→71の繰り替え！

よって、33桂以前に積極的に71銀移動～消去すべきと思います。
21飛を打てる分、31飛成～42龍の余地があって、33桂を先にした方がよさそうですね。

[44] mixiユーザー 02月05日 23:48

しばらく、コメントできなくて済みませんでした。
プログラムの実装上の問題がクリアできず、魚熊さん、なおさん御指摘の手順を読めるようにはまだ出来ていません。
さすがにこの手数を人力で同一局面無しを確認するのは不可能ですので、プログラムに頼るしかないでしょうから、改良を諦めるつもりは有りません。
進捗が有ったらまた報告します。

[45] mixiユーザー 05月27日 22:39

古いトピにコメントします。
プログラム技法の知識が増えたので、進展の可能性が出てきました。
有り得る局面は限られているので、数え上げるのはそれほど難しくありません。
実際先手番の局面数は527089個、後手番の局面数は1295255個でした（2手目以降）
これを計算するのに所要した時間はわずか6秒です。
人間が扱うには大きな数ですが現在のコンピュータの能力からすれば十分手の届く範囲です。
各局面から次の局面への遷移可能な数は平均10くらいでしょうから、遷移表を作るのも難しく有りません。
遷移表が決まっている問題の最長経路を求める手法が、いろいろ知られているので
それらを使えば理論上の最長経路を求めることが出来るかもしれません。

これから勉強して、進展があったら報告します。

ログインすると、残り8件のコメントが見れるよ