棋譜数のカウント


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

棋譜数のカウント

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


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

121 名無しさん@3周年 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手固定にして、全棋譜数、パス、終了数は結果を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とは1手ずれる) 
実は一晩かけて13手目までやったんですが結果がおかしいです。 
変数は8バイト用意しておいたんですが、出力をミスったかもしれない。 
|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手数平均の積と実数の誤差ですが 
これは平均の算出誤差というより手法としての誤差でしょうね。 
全検索で手数平均を算出しても同じくらいの誤差があるでしょう。 
12手で14%の誤差で、手が進むにつれて誤差は大きくなるでしょうし 
平均10手で20%の誤差があるとして0.8^(60/10)=0.26 
60手目で99%(実数との割合が100倍違う)としても 
10^51~10^56くらいではないでしょうか。(もう少し大きくなるかもしれないが) 
まあ、これくらいざっくりした数値でしかないのは確かですが、無意味な値ではないと思います。

339 284 sage 2006/03/03(金) 11:28:43 
ごめん。>>336の表の3手目のパスの値 8 は 0 が正解です。 
(動作チェックルーチンの消し忘れ) 
>>337も表はコピペみたいだから3手目の終了は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手目を打った後の状態で 
パスをする必要がある局面数と終わった局面数です。 
これらは全棋譜数には内数として含まれてますが 
パス数と終了数とは排他的に数えてます。 
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。