棋譜数のカウント

棋譜数のカウント

一つ一つ辿って手の数を数えていく。
今のところ個人活動では、14手ぐらいが限界とされている。
棋譜数の上界を下げるに貢献。

120 名無しさん＠３周年 sage 2005/05/14(土) 03:17:20 
４×４ 
＋＋＋＋ 
＋●○＋ 
＋○●＋ 
＋＋＋＋ 
初手 1通り 
＋＋＋＋ 
＋●○＋ 
＋●●＋ 
＋●＋＋ 
二手 3通り 
＋＋＋＋　＋＋＋＋　＋＋＋＋ 
○○○＋　＋●○＋　＋●○＋ 
＋●●＋　＋○●＋　＋●○＋ 
＋●＋＋　○●＋＋　＋●○＋ 
三手 11通り 
●＋＋＋　＋●＋＋　＋＋●＋　＋＋＋●　　＋＋＋＋　＋＋●＋　＋＋＋＋ 
○●○＋　○●○＋　○○●＋　○○●＋　　＋●○＋　＋●●＋　＋●●● 
＋●●＋　＋●●＋　＋●●＋　＋●●＋　　●●●＋　＋○●＋　＋○●＋ 
＋●＋＋　＋●＋＋　＋●＋＋　＋●＋＋　　○●＋＋　○●＋＋　○●＋＋ 
＋＋＋●　＋＋＋＋　＋＋＋＋　＋＋＋＋ 
＋●●＋　＋●●●　＋●○＋　＋●○＋ 
＋●○＋　＋●●＋　＋●●●　＋●●＋ 
＋●○＋　＋●○＋　＋●○＋　＋●●● 

121 名無しさん＠３周年 sage 2005/05/14(土) 03:54:47 
四手　31通り 
●＋＋＋　●＋＋＋　　＋●＋＋　＋●＋＋　　＋＋●＋　＋＋●＋　＋＋●＋ 
○●○＋　○●○＋　　○●○＋　○●○＋　　○○●＋　○○○○　○○●＋ 
＋○●＋　＋○○＋　　＋○●＋　＋○○＋　　＋○●＋　＋●●＋　＋●○＋ 
○●＋＋　＋●○＋　　○●＋＋　＋●○＋　　＋●○＋　＋●＋＋　＋●＋○ 
＋＋＋●　＋＋＋●　＋＋＋●　　　＋＋＋＋　　＋○●＋　＋＋●＋　＋＋●○　＋＋●＋ 
○○●＋　○○○○　○○●＋　　　○○○＋　　＋○●＋　＋●●＋　＋●○＋　＋●●＋ 
＋○●＋　＋●●＋　＋●○＋　　　○●●＋　　＋○●＋　＋○●＋　＋○●＋　＋○○○ 
＋●○＋　＋●＋＋　＋●＋○　　　○●＋＋　　○●＋＋　○○○＋　○●＋＋　○●＋＋ 
＋○＋＋　＋＋＋＋　＋＋＋○　＋＋＋＋　　　○＋＋●　＋＋＋●　＋＋＋●　＋＋＋●　＋＋○● 
＋○●●　＋●●●　＋●○●　＋●●●　　　＋○●＋　○●●＋　＋●●＋　＋●●＋　＋●○＋ 
＋○●＋　＋○●＋　＋○●＋　＋○○○　　　＋●○＋　＋○○＋　○○○＋　＋●○＋　＋●○＋ 
○●＋＋　○○○＋　○●＋＋　○●＋＋　　　＋●○＋　＋●○＋　＋●○＋　○○○＋　＋●○＋ 
＋＋＋＋　＋＋＋＋　＋＋○＋　　＋＋＋＋　＋＋＋＋　　＋＋＋＋　＋＋＋＋ 
○●●●　＋●●●　＋●○●　　○○○＋　＋●○＋　　○○○＋　＋●○＋ 
＋○●＋　＋●●＋　＋●○＋　　＋○●●　＋○●●　　＋●●＋　＋○●＋ 
＋●○＋　○○○＋　＋●○＋　　＋●○＋　○○○＋　　＋●●●　○●●● 

260 256 2006/02/20(月) 07:59:34 
プログラムを作って実際の数を調べてみた。 
1・・・4 
2・・・12 
3・・・56 
4・・・244 
5・・・1396 
6・・・8200 
7・・・55092 
8・・・390216 
9・・・3005320 
10・・・24571192 
24571192*33*33*...*33*32*...*3*2*1=1.39e+70 
急ごしらえなのであんまり速くないからとりあえず10手まで。 
あと、まだバグがあるかも知れないから誰か検証お願い。

332 293 sage 2006/03/02(木) 17:58:43 
全探索（11手まで）してみたら>>260と微妙に違ってた。 
[ 0] -> 1( 0) 
[ 1] -> 4( 0) 
[ 2] -> 12( 0) 
[ 3] -> 56( 0) 
[ 4] -> 244( 0) 
[ 5] -> 1396( 0) 
[ 6] -> 8200( 0) 
[ 7] -> 55092( 0) 
[ 8] -> 390216( 0) 
[ 9] -> 3005320(228) 
[10] -> 24571192(356) 
[11] -> 212260296(6384) 
括弧内はゲーム終了数（内数）。9手目でのゲーム終了数分を足すと10手目も同じなんだけど… 
Wikiにある11手目のデータも9手目・10手目での終了分を足せば同じ結果に。 
…私が悪いの？

333 293 sage 2006/03/02(木) 21:51:00 
12手まで出したついでによんけたﾀﾝの分岐平均（どうやって出したの？）と比較してみた 
手数平均分岐←の積実際の数誤差[%] 
11440 
2312120 
34.664555561.785714286 
44.36062392442.049180328 
55.8582140013960.286532951 
65.8361817082000.365853659 
76.723554930550920.294053583 
86.94363814113902162.256442586 
97.5566288217030053204.097733353 
107.900522770584245711927.328126368 
118.376819074462821226029610.13645435 
128.7781674356344193989224013.68817765 
平均分岐数を単純に掛け合わせるのは危険っぽい。

334 293 sage 2006/03/02(木) 21:51:40 
ごめん>>333じゃ読めないね。Wikiに入れておく。

336 284 sage 2006/03/03(金) 08:02:23 
12手の全検索、というか1/4検索です。 
初手は１手固定にして、全棋譜数、パス、終了数は結果を４倍しています。 
|手|最大手数|　　全棋譜数　　|パス　　|終了　| 
|-1|-------0|---------------4|-------0|-----0| 
|-2|-------3|--------------12|-------0|-----0| 
|-3|-------5|--------------56|-------8|-----0| 
|-4|-------6|-------------244|-------0|-----0| 
|-5|-------9|------------1396|-------0|-----0| 
|-6|------11|------------8200|-------0|-----0| 
|-7|------12|-----------55092|-------0|-----0| 
|-8|------14|----------390216|-------0|-----0| 
|-9|------15|---------3005320|------24|-----0| 
|10|------16|--------24571192|-----228|---228| 
|11|------18|-------212260296|-----932|---356| 
|12|------20|------1939892240|----7396|--6384| 
ゲーム終了の考え方は>>332に近いですが 
10手目が打てない場合に10手目の終了としています。 
(332とは１手ずれる） 
実は一晩かけて13手目までやったんですが結果がおかしいです。 
変数は８バイト用意しておいたんですが、出力をミスったかもしれない。 
|13|------21|------1249899332|---35588|-16384|

337 293 sage 2006/03/03(金) 09:10:51 
ちょっと遅れたかな。一応こちらも13手探索終了 
64bit整数を使ったつもりなので出力は大丈夫なはずです。 
|手|　　全棋譜数　　|終了　　| 
|-1|---------------4|-------0| 
|-2|--------------12|-------0| 
|-3|--------------56|-------8| 
|-4|-------------244|-------0| 
|-5|------------1396|-------0| 
|-6|------------8200|-------0| 
|-7|-----------55092|-------0| 
|-8|----------390216|-------0| 
|-9|---------3005320|-----228| 
|10|--------24571192|-----356| 
|11|-------212260296|----6384| 
|12|------1939892240|---16384| 
|13|-----18429768516|--299624| 
ゲーム終了の考え方は10手目を打った後に両者が置けなくなったら10手目の終了としています。 
確かに変ですね。改良します。 

338 284 sage 2006/03/03(金) 10:15:20 
>>337 
乙です。12手目まで一致してますので安心しました。 
ゲーム終了の考え方は336と337(332初出)のどちらが良いでしょう？ 
私の場合(336)はプログラミングの都合だけだったので、他の皆さんの意見も聞きたいです。 
>>333-335手数平均の積と実数の誤差ですが 
これは平均の算出誤差というより手法としての誤差でしょうね。 
全検索で手数平均を算出しても同じくらいの誤差があるでしょう。 
１２手で１４％の誤差で、手が進むにつれて誤差は大きくなるでしょうし 
平均１０手で２０％の誤差があるとして0.8^(60/10)=0.26 
６０手目で９９％（実数との割合が１００倍違う）としても 
10^51～10^56くらいではないでしょうか。（もう少し大きくなるかもしれないが） 
まあ、これくらいざっくりした数値でしかないのは確かですが、無意味な値ではないと思います。

339 284 sage 2006/03/03(金) 11:28:43 
ごめん。>>336の表の３手目のパスの値 8 は 0 が正解です。 
（動作チェックルーチンの消し忘れ） 
>>337も表はコピペみたいだから３手目の終了は0ですね。 
すみませんでした。 

340 293 sage 2006/03/03(金) 14:04:32 
さらに進めて14手探索しました。>>336と同じく1/4探索ですが。 
|手|分|--全棋譜数--|--パス-|--終了-| 
|-1|-0|-----------4|------0|------0| 
|-2|-3|----------12|------0|------0| 
|-3|-5|----------56|------0|------0| 
|-4|-6|---------244|------0|------0| 
|-5|-9|--------1396|------0|------0| 
|-6|11|--------8200|------0|------0| 
|-7|12|-------55092|------0|------0| 
|-8|14|------390216|------0|------0| 
|-9|15|-----3005320|-----24|------0| 
|10|16|----24571192|------0|----228| 
|11|18|---212260296|----576|----356| 
|12|20|--1939892240|---1012|---6384| 
|13|21|-18429768516|--19204|--16384| 
|14|22|184042835408|--67536|-299624| 
私は全探索は一旦この状態で手を引こうと思います。 
時間がかかる（↑で200分弱）割になかなか前へ進めないので。 
n手目のパス数と終了数はn-1手目を打った後の状態で 
パスをする必要がある局面数と終わった局面数です。 
これらは全棋譜数には内数として含まれてますが 
パス数と終了数とは排他的に数えてます。