将棋のあり得る手順の上限（棋譜の総数の上限）を求めよ

1 ：１３２人目の素数さん：2020/01/19(日) 12:11:14.77 ID:gcpa8LtV.net

できるだけ小さい数を出したやつが優勝ね
まず僕の答えは

(29^81)^(3 * 29^81 + 1)

です
計算方法は次のようになります
まず将棋の特定のマスの状態は
王・飛車・竜王・角行・竜馬・金・銀・成銀・桂馬・成桂・香車・成香・歩・と
で14通り，向きで2通り，何も置かれていない状態を入れて
14 * 2 + 1 = 29
通りあります
つまり将棋盤の状態はたかだか
29^9^2 = 29^81
通り以下なわけです
ここで，4回同じ状態が発生したら千日手となるので，鳩の巣原理より
3 * 29^81 + 1
の手順が進めば必ずある状態が4回発生しているので，それ以上は続かないので上限は上の値になります
これはもちろん相当な過大評価なわけですから，もっと小さい上限を考えるというのがこのスレの目的です

2 ：イナ ◆/7jUdUKiSM ：2020/01/19(日) 17:38:33 ID:6fYcVEZg.net

王と玉が前後左右斜めいかなる方向も絶対にとなりあう盤面はない。
そうとう減らせる。

3 ：イナ ◆/7jUdUKiSM ：2020/01/19(日) 17:43:01 ID:6fYcVEZg.net

前>>2王と玉が同じ方向を向くことは絶対にない。
まず2で割って半分にしていい。

4 ：イナ ◆/7jUdUKiSM ：2020/01/19(日) 17:45:38 ID:6fYcVEZg.net

前>>3
駒をとって盤面にはないことがある。そうとう増える。

5 ：イナ ◆/7jUdUKiSM ：2020/01/19(日) 17:53:31 ID:6fYcVEZg.net

前>>4
二歩はあっても三歩は指せない。

6 ：イナ ◆/7jUdUKiSM ：2020/01/19(日) 17:58:35 ID:6fYcVEZg.net

前>>5一段目や九段目に、行きどころのない歩や香や桂は指せない。

7 ：１３２人目の素数さん：2020/01/19(日) 18:52:42.72 ID:5EDEK9Kw.net

>>6
一回にまとめて書け

8 ：１３２人目の素数さん：2020/01/20(月) 10:53:12 ID:m8kwTHLF.net

1手だ
オレは1手でケリをつける

9 ：１３２人目の素数さん：2020/01/20(月) 21:10:57.54 ID:ISzy00B/.net

とても興味深い問題ですね

10 ：１３２人目の素数さん：2020/01/29(水) 00:30:27 ID:MIlxYHgE.net

同じ盤面で持ち駒が違う場合もある

11 ：１３２人目の素数さん：2020/01/29(水) 17:32:56 ID:bCUCIz0G.net

盤上には自玉と敵玉のいる升を除いた81-2=79の升がある
任意の駒は、盤上にある場合、79升のどこかに、裏返っているかいないか、先手の駒か後手の駒か、
79*2*2=316通りの状態を取りうる
また、盤上にない場合、先手の駒台にあるか後手の駒台にあるか2通りがある
併せて、任意の駒は316+2=318通りの状態を取りうる
駒は全部で40枚あるので、将棋の局面の数は318^40を超えることはない
これは、318^40<324^40=(18^2)^40=18^80<29^81なので>>1より小さく評価できた

ここで>>1のアイデアをパクると、3*318^40+1手進めれば途中に同一局面が3つはある
なので手数は長くともこれを超えることがない
また、n手目を指した直後に終局する棋譜の数は(318^40)^nを超えない
これをnについて、nが取り得る値であるn=0からn=3*318^40+1まで和を取ると、
?[n=0,3*318^40+1](318^40)^n=((318^40)^(3*318^40+2)-1)/(318^40-1)
なので、棋譜の総数はこれを超えない

12 ：１３２人目の素数さん：2020/04/01(水) 08:02:50.73 ID:wzO1l06Y.net

1無量大数って結論出たよ

13 ：１３２人目の素数さん：2020/04/04(土) 11:38:21 ID:lw11YNc1.net

678那由多まで減らせた。

14 ：１３２人目の素数さん：2020/05/27(水) 00:06:29.23 ID:2I72JytV.net

場合の数で実現可能局面数を見積もる
http://www.youtube.com/watch?v=7QcpShRfqGA 21:22,

「将棋における実現可能局面数について」篠田正人
http://www.nara-wu.ac.jp/math/personal/shinoda/legal.pdf
　L ≦ 9.14×10^69

　１無量大数 = 10^68　　　　>>12
に近い？

15 ：１３２人目の素数さん：2020/07/10(金) 20:23:13 ID:Jwwe0dND.net

>>14
動画見たけど論文の「実現可能局面数（手順の数）」じゃなくて
盤面の状態の数のこと言ってるよね
頭悪そう

16 ：１３２人目の素数さん：2020/07/12(日) 22:01:36.03 ID:PHDLpv+i.net

二歩で負けだから、歩は一列に同じ向きでは一つまで、

盤面の状態の総数を計算するのはそれほど実用的な価値ない気がするけど・・
（AIのプログラムを強化とかの目的）

17 ：１３２人目の素数さん：2020/07/13(月) 02:30:14 ID:B4/XaPdS.net

投了なしで詰むまでやる前提？

18 ：１３２人目の素数さん：2020/07/20(月) 02:06:20.24 ID:zoYJRvyp.net

>>1
>つまり将棋盤の状態はたかだか
>29^9^2 = 29^81
>通り以下なわけです
持ち駒の状態が考慮に入ってない

19 ：１３２人目の素数さん：2020/07/20(月) 08:32:46.44 ID:6s/UusVu.net

>>1 は持ち駒の状態を考慮しなくていいでしょ

20 ：１３２人目の素数さん：2020/09/09(水) 22:30:16.54 ID:IR7822fG.net

歩や桂は行き場のないところに置けませんから
それで削げます

21 ：１３２人目の素数さん：2020/10/12(月) 01:32:54.24 ID:lKOdOSZk.net

要はゲーム木の大きさってことか
個人的には正確な合法局面数(ゲームとしての本質は全ての合法局面について考えれば十分という意味で重要に思える)とか棋譜の最長手順の見積もりとかの方が気になる