棋譜数のカウント
一つ一つ辿って手の数を数えていく。
今のところ個人活動では、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手目を打った後の状態で
パスをする必要がある局面数と終わった局面数です。
これらは全棋譜数には内数として含まれてますが
パス数と終了数とは排他的に数えてます。
最終更新:2006年03月06日 18:09