棋譜数のカウント

「棋譜数のカウント」の編集履歴（バックアップ）一覧はこちら

棋譜数のカウント - (2006/03/15 (水) 13:09:07) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

*棋譜数のカウント
プログラムなどを使って
一つ一つ辿って手の数(棋譜数)を数えていく。

棋譜のツリーを一手目からたどっていく探索とよばれる方法が主に使われる。
問題点はなんといっても時間である。
今のところ個人活動では、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手目を打った後の状態で 
 パスをする必要がある局面数と終わった局面数です。 
 これらは全棋譜数には内数として含まれてますが 
 パス数と終了数とは排他的に数えてます。 

 357 名無しさん＠５周年 sage 2006/03/05(日) 22:13:08 
 完全探索の話 
 >>348の話を踏まえて対称形による枝刈りを一般化したらいいかな。 
 対称形の盤面をみつけたときは対称形の中のひとつだけ深化して 
 あとで k 倍すれば探索空間が減らせて探索がより高速になりますね。 
 対称形（とその復元のための倍率 k）は 
 90°回転対称(k=4), 180°回転対称/鏡面対称(k=2)、非対称(k=1) 
 ですね。 
 ちょっと入れてみましょう。分岐が減って速くなるか、 
 あまり対称形が発生せず対称形の判定に時間がかかって逆に遅くなるか見ものです。 
 っていうかもうみんなやってるのかもしれない。。 

 358 293 sage 2006/03/05(日) 23:03:00 
 >>357 
 重複チェックと似てますね。ただk倍ってのは簡単にはいかない気がしますが。 
 １．探索した盤面が初めてなら、探索後に分岐数と一緒にDataBaseに登録する。 
 ２．これから探索しようとするものと(対称形で)同じ盤面がDBにあれば、その分岐数を使う。 
 ってのが実際的かな？正確には盤面の状態と黒番・白番って情報もいるけど。 

 359 名無しさん＠５周年 sage 2006/03/06(月) 08:28:19 
 >>358 
 重複チェックってやってます？ 
 盤面多いんで結局10手以上になるとメモリ的にDBの実装が難しいと思うんですが。 
 ０．深化の際に累計対称倍率Kというものを再帰関数の引数として与えることにする。 
 １．0手目、K=4を引数に与えて深化開始。 
 ２．再帰関数中、対称形チェック。形によってその盤面の倍率 k を求める。 
 ３．K*k を次の再帰関数の引数に与えて深化。 
 ４．試合終了または深度最大になったらKの値を棋譜数カウントに加える。 
 ５．バックトラックの際には既に深化した分岐の対称形には手を出さない 
 （たとえば、x軸鏡面対称なら盤面の半分より以東の探索をカットする） 
 これでどれだけ深い階層の探索にもメモリを使わなくて済みます。 
 （直系の盤面データ(最大60個)と対称倍率とバックトラック位置だけスタック領域として持てばいいので） 

 361 284 sage 2006/03/06(月) 13:18:36  
 >>359 
 なるほど、とある盤面の対称形を使うわけですね。 
 ０手目（初期配置）で言えばｕ軸対称(k=2)、ｖ軸対称(k=2)、180°対称(k=2)ですがk=4ですよね。 
 ｖ　　　| 
 　＼＋＋＋＋／ 
 　＋＋＋＋＋＋ 
 ＿＋＋○●＋＋＿ｘ 
 　＋＋●○＋＋ 
 　＋＋＋＋＋＋ 
 　／＋＋＋＋＼ 
 ｕ　　　|ｙ 
 ｕ軸＆ｖ軸　あるいは　ｘ軸＆ｙ軸　が成立する時は180°対称は無視する必要があります。 
 また、ｕ軸対称の時、ｕ軸上に打てる場合もk=1になります。（ｖ軸も同様）

 366 名無しさん＠５周年 sage 2006/03/07(火) 01:27:34 
 対称性の話 
 手数tに対して対称形がいくつ出てくるかを調べてみました。 
 t=1 x= 0 y= 0 u= 1 v= 1 
 t=2 x= 0 y= 0 u= 0 v= 0 
 t=3 x= 0 y= 0 u= 0 v= 0 
 t=4 x= 0 y= 0 u= 0 v= 4 
 t=5 x= 0 y= 0 u= 4 v= 0 
 t=6 x= 0 y= 0 u= 0 v= 0 
 t=7 x= 0 y= 0 u= 0 v= 0 
 t=8 x= 0 y= 0 u= 0 v= 60 
 t=9 x= 4 y=14 u=88 v=152 
 注:実装上の関係からv軸u軸に関しては>>361と比べて逆になっています。 
 8手目から結構でてきます。 
 またこのチェックを入れたコストは9手全探索で0.2秒でした。 
 入れた方がいいかもしれません

 368 よんけた ◆Tl2oC4lIZ2 sage 2006/03/07(火) 20:06:40 
 >>366 
 おつです。対称性局面は後々手分けして探索するとき、大切になってくるとおもいます。 
 げっへっへ～ 

 375 名無しさん＠５周年 sage 2006/03/09(木) 03:36:52 
 対称性の盤面数、ちょっと計算方法が間違っていたので訂正。 
 t,u, v, n 
 1,1, 1, 4 
 2,0, 0, 12 
 3,0, 0, 56 
 4,0, 1, 244 
 5,1, 0, 1396 
 6,0, 0, 8200 
 7,0, 0, 55092 
 8,0,12,390216 
 t=手数、v(,u)=v(,u)軸対称な盤面数、n=全棋譜数
 
 これなんですが、対称性を用いた枝刈りのコスト削減が 
 どれだけ深い手数まで調べても1/4にしかならなかったんですよね。 
 よく考えてみると、4手目にひとつ対称な盤面がでてきて、 
 これ以降のこのノードの探索範囲は1/2になるんですが、 
 すでに棋譜数が244もあるので、ひと枝だけがコスト1/2になっても 
 全体の計算量は243/244にしかならないんですよね。 
 結局うまくコスト削減できてるのは１手目のuv対称の1/4だけで、 
 それ以降のはほとんど無視できちゃうんです。 
 ってことで「対称性による計算量削減は１手目しか意味がない」 
 というのが今日の私の結論でした。

 376 284 sage 2006/03/09(木) 12:59:58 
 >>375 
 対称性を用いた枝狩りの有効性は低いですか。実は期待していただけに残念。 
 今、黒石ゲーム２で対称性の枝狩りをやってみようかと考えてます。 
 オセロの全(1/4)探索よりノードを減らせれば、各手数での最大着手可能数を探索できるかな、と考えてます。 
 まあ、既に全探索で14手目最大22着手が出てるので、無駄になる可能性大、ですが。 

 388 293 sage 2006/03/11(土) 13:27:28 
 空いてるマシーンを見つけたので、タラタラと15手探索やらせました。 
 余分な計算を色々削除することでそこそこの高速化を図りましたが、34時間50分かかってます。 
 （ちなみに全く同じプログラムで（手違いで計算させた）14手探索が3時間36分でした。） 
 
 15手探索結果だけ。16手探索は予想時間が10日以上かかるので流石に無理です。 
 15手目の最大分岐数：23 
 15手目の盤面数：1891844432704 
 15手目でパスが起こる盤面数：1092168 
 15手目を打てずに終わる盤面数：887364

 389 271 sage 2006/03/11(土) 22:04:53 
 >>388 
 お疲れです。うちのより１０倍速いですねｗ 
 さっき14手の結果が上がってきたのですが40時間かかってました。 
 計算しながら普通にパソコン使ってますが。 
 12手までは同じ速度だったのにねぇ

 390 293 sage 2006/03/11(土) 22:56:58 
 フフフ、あの12手検索から微妙にプログラムを変更してるんですよ。

 395 256 sage New! 2006/03/13(月) 17:30:26 
 全探索プログラムをC言語で書き直しました。 
 今15手やってます。 
 ぼくも13手までは確認しました。

[[idothello_v06.c>http://www9.atwiki.jp/othello/?cmd=upload&act=open&page=%E5%AE%8C%E5%85%A8%E6%8E%A2%E7%B4%A2%E3%83%87%E3%83%BC%E3%82%BF&file=idothello_v06.c]]

*棋譜数のカウント
プログラムなどを使って
一つ一つ辿って手の数(棋譜数)を数えていく。

棋譜のツリーを一手目からたどっていく探索とよばれる方法が主に使われる。
問題点はなんといっても時間である。
今のところ個人活動では、14手ぐらいが限界とされている。
[[棋譜数の上界を下げる]]に貢献。

最新データは→[[完全探索データ]]

----


 118 名無しさん＠３周年 2005/05/13(金) 21:20:12 
 計算始めました。 
 
 死ぬまでに結果が出たらいいのだが。 

 119 名無しさん＠３周年 2005/05/13(金) 23:55:29 
 >>118 
 まさかとは思うが全通り計算してるのか？ 

 122 名無しさん＠３周年 2005/05/14(土) 23:06:42 
 >>118 
 おまいが死ぬ前にパソコムが昇天するに３０００ガバス

 124 名無しさん＠３周年 sage 2005/05/15(日) 06:49:03 
 >>67 
 オセロでも地球上の全ての物質を素粒子メモリーに変換したとしても間に合わんのね。 
 チェス以降だと宇宙の全素粒子を使用しても記録できない、と。 

 141 名無しさん＠３周年 2005/06/29(水) 10:01:44 
 で、結局全局面は何通りあるの？ 
 >>124 
 1局面100バイトとして、89,475,692,478,931,200バイト 
 1000で考えて89ペタ。 
 1テラ=1000円レベルでコスト的にも不可能じゃなくなる 
 
 148 名無しさん＠３周年 2005/06/30(木) 13:05:25 
 ねえ何か思いついたから聞いて。プログラミングの素人ですが。。 
 
 まず、一局目から始まり、最後まで勝負つくまでの全通りはツリー状でイメージできるよね。 
 んで全通りの計算方法なんだけど 
 まず適当に勝負つくまで局を進ませる。一局一局の手は記憶させておく。 
 んで次に最後の一手が他に無いか探す(特殊な場合以外最後は一通りだけど)。 
 最後の一手が他に無かったら、最後の一手の情報を消す。 
 最後の一手の情報を消すごとにカウントを一つ増やす。 
 一手戻り最後から二手目が他に手がないか探す。 
 あったら、局を進ませる。 
 以下つづける。。。
 
 この方法だと今カウントしている属のみの手を記憶してればいいから容量がなくてもいいんじゃない？

 149 名無しさん＠３周年 sage 2005/06/30(木) 14:30:06 
 深さ優先探索だね。まぁ確かに容量は無くてもいけるかも知れんが、やってみ？ 
 先に結論を言っておくと時間が足りない。4×4で実験してみてどれくらい時間がかかるか報告よろしく

 150 名無しさん＠３周年 sage 2005/06/30(木) 18:56:14 
 でもこれで容量の問題は解決するよね？ 
 かなり説明は省いたけど。 
 
 時間短縮は途中十局目ぐらいまで横ローラー探索をして、そのあとその結果をネットに載っける。 
 んで個々のPCがそれぞれの通りから縦探索をすればかなり時間短縮になるのでは？

 151 名無しさん＠３周年 2005/06/30(木) 20:00:09 
 これは面白くなってきたな。 
 呼びかけるか？ 

 152 名無しさん＠３周年 sage 2005/06/30(木) 20:52:45 
 へへーん。もしかして俺凄い？(・∀・) 
 世界的にもまだ算出されていないんでしょ？ 
 数年掛かりでもヤる価値はあると思うよね。。

8ヶ月経過

 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手目を打った後の状態で 
 パスをする必要がある局面数と終わった局面数です。 
 これらは全棋譜数には内数として含まれてますが 
 パス数と終了数とは排他的に数えてます。 

 357 名無しさん＠５周年 sage 2006/03/05(日) 22:13:08 
 完全探索の話 
 >>348の話を踏まえて対称形による枝刈りを一般化したらいいかな。 
 対称形の盤面をみつけたときは対称形の中のひとつだけ深化して 
 あとで k 倍すれば探索空間が減らせて探索がより高速になりますね。 
 対称形（とその復元のための倍率 k）は 
 90°回転対称(k=4), 180°回転対称/鏡面対称(k=2)、非対称(k=1) 
 ですね。 
 ちょっと入れてみましょう。分岐が減って速くなるか、 
 あまり対称形が発生せず対称形の判定に時間がかかって逆に遅くなるか見ものです。 
 っていうかもうみんなやってるのかもしれない。。 

 358 293 sage 2006/03/05(日) 23:03:00 
 >>357 
 重複チェックと似てますね。ただk倍ってのは簡単にはいかない気がしますが。 
 １．探索した盤面が初めてなら、探索後に分岐数と一緒にDataBaseに登録する。 
 ２．これから探索しようとするものと(対称形で)同じ盤面がDBにあれば、その分岐数を使う。 
 ってのが実際的かな？正確には盤面の状態と黒番・白番って情報もいるけど。 

 359 名無しさん＠５周年 sage 2006/03/06(月) 08:28:19 
 >>358 
 重複チェックってやってます？ 
 盤面多いんで結局10手以上になるとメモリ的にDBの実装が難しいと思うんですが。 
 ０．深化の際に累計対称倍率Kというものを再帰関数の引数として与えることにする。 
 １．0手目、K=4を引数に与えて深化開始。 
 ２．再帰関数中、対称形チェック。形によってその盤面の倍率 k を求める。 
 ３．K*k を次の再帰関数の引数に与えて深化。 
 ４．試合終了または深度最大になったらKの値を棋譜数カウントに加える。 
 ５．バックトラックの際には既に深化した分岐の対称形には手を出さない 
 （たとえば、x軸鏡面対称なら盤面の半分より以東の探索をカットする） 
 これでどれだけ深い階層の探索にもメモリを使わなくて済みます。 
 （直系の盤面データ(最大60個)と対称倍率とバックトラック位置だけスタック領域として持てばいいので） 

 361 284 sage 2006/03/06(月) 13:18:36  
 >>359 
 なるほど、とある盤面の対称形を使うわけですね。 
 ０手目（初期配置）で言えばｕ軸対称(k=2)、ｖ軸対称(k=2)、180°対称(k=2)ですがk=4ですよね。 
 ｖ　　　| 
 　＼＋＋＋＋／ 
 　＋＋＋＋＋＋ 
 ＿＋＋○●＋＋＿ｘ 
 　＋＋●○＋＋ 
 　＋＋＋＋＋＋ 
 　／＋＋＋＋＼ 
 ｕ　　　|ｙ 
 ｕ軸＆ｖ軸　あるいは　ｘ軸＆ｙ軸　が成立する時は180°対称は無視する必要があります。 
 また、ｕ軸対称の時、ｕ軸上に打てる場合もk=1になります。（ｖ軸も同様）

 366 名無しさん＠５周年 sage 2006/03/07(火) 01:27:34 
 対称性の話 
 手数tに対して対称形がいくつ出てくるかを調べてみました。 
 t=1 x= 0 y= 0 u= 1 v= 1 
 t=2 x= 0 y= 0 u= 0 v= 0 
 t=3 x= 0 y= 0 u= 0 v= 0 
 t=4 x= 0 y= 0 u= 0 v= 4 
 t=5 x= 0 y= 0 u= 4 v= 0 
 t=6 x= 0 y= 0 u= 0 v= 0 
 t=7 x= 0 y= 0 u= 0 v= 0 
 t=8 x= 0 y= 0 u= 0 v= 60 
 t=9 x= 4 y=14 u=88 v=152 
 注:実装上の関係からv軸u軸に関しては>>361と比べて逆になっています。 
 8手目から結構でてきます。 
 またこのチェックを入れたコストは9手全探索で0.2秒でした。 
 入れた方がいいかもしれません

 368 よんけた ◆Tl2oC4lIZ2 sage 2006/03/07(火) 20:06:40 
 >>366 
 おつです。対称性局面は後々手分けして探索するとき、大切になってくるとおもいます。 
 げっへっへ～ 

 375 名無しさん＠５周年 sage 2006/03/09(木) 03:36:52 
 対称性の盤面数、ちょっと計算方法が間違っていたので訂正。 
 t,u, v, n 
 1,1, 1, 4 
 2,0, 0, 12 
 3,0, 0, 56 
 4,0, 1, 244 
 5,1, 0, 1396 
 6,0, 0, 8200 
 7,0, 0, 55092 
 8,0,12,390216 
 t=手数、v(,u)=v(,u)軸対称な盤面数、n=全棋譜数
 
 これなんですが、対称性を用いた枝刈りのコスト削減が 
 どれだけ深い手数まで調べても1/4にしかならなかったんですよね。 
 よく考えてみると、4手目にひとつ対称な盤面がでてきて、 
 これ以降のこのノードの探索範囲は1/2になるんですが、 
 すでに棋譜数が244もあるので、ひと枝だけがコスト1/2になっても 
 全体の計算量は243/244にしかならないんですよね。 
 結局うまくコスト削減できてるのは１手目のuv対称の1/4だけで、 
 それ以降のはほとんど無視できちゃうんです。 
 ってことで「対称性による計算量削減は１手目しか意味がない」 
 というのが今日の私の結論でした。

 376 284 sage 2006/03/09(木) 12:59:58 
 >>375 
 対称性を用いた枝狩りの有効性は低いですか。実は期待していただけに残念。 
 今、黒石ゲーム２で対称性の枝狩りをやってみようかと考えてます。 
 オセロの全(1/4)探索よりノードを減らせれば、各手数での最大着手可能数を探索できるかな、と考えてます。 
 まあ、既に全探索で14手目最大22着手が出てるので、無駄になる可能性大、ですが。 

 388 293 sage 2006/03/11(土) 13:27:28 
 空いてるマシーンを見つけたので、タラタラと15手探索やらせました。 
 余分な計算を色々削除することでそこそこの高速化を図りましたが、34時間50分かかってます。 
 （ちなみに全く同じプログラムで（手違いで計算させた）14手探索が3時間36分でした。） 
 
 15手探索結果だけ。16手探索は予想時間が10日以上かかるので流石に無理です。 
 15手目の最大分岐数：23 
 15手目の盤面数：1891844432704 
 15手目でパスが起こる盤面数：1092168 
 15手目を打てずに終わる盤面数：887364

 389 271 sage 2006/03/11(土) 22:04:53 
 >>388 
 お疲れです。うちのより１０倍速いですねｗ 
 さっき14手の結果が上がってきたのですが40時間かかってました。 
 計算しながら普通にパソコン使ってますが。 
 12手までは同じ速度だったのにねぇ

 390 293 sage 2006/03/11(土) 22:56:58 
 フフフ、あの12手検索から微妙にプログラムを変更してるんですよ。

 395 256 sage New! 2006/03/13(月) 17:30:26 
 全探索プログラムをC言語で書き直しました。 
 今15手やってます。 
 ぼくも13手までは確認しました。

[[idothello_v06.c>http://www9.atwiki.jp/othello/?cmd=upload&act=open&page=%E5%AE%8C%E5%85%A8%E6%8E%A2%E7%B4%A2%E3%83%87%E3%83%BC%E3%82%BF&file=idothello_v06.c]]