終局局面数

ゲームが終局した盤面の総通り数。

棋譜と違い、一手一手の局面を記憶していかなければならないので、
「時間」の他に「コンピュータの記憶容量」も問題となってくる。
局面数は棋譜数と比べると２０～３０桁近く少なくなるが、
局面数は、（今のところ）棋譜の木をたどって調べていくしかないので、
時間も棋譜の探索と同じぐらいかかると思われる。

局面数の概算→局面数の概算

子話題
→黒石ゲーム
→ありえない局面
→Transposition
→枝刈り

---

3 名無しさん＠３周年 04/07/23 14:44
6*6=36 
2の36乗=68719476736 
68719476736＊２(黒白)=137438953472 
∴137438953472通り 
かな？ 

4 3 sage 04/07/23 14:47
訂正) 
8*8=64 
2の64乗=18446744073709551616 
18446744073709551616＊２=36893488147419103232 
∴36893488147419103232通り 

5 名無しさん＠３周年 sage 04/07/23 17:45
4 
話はそう簡単じゃない。 
まず、打てる場所は8*8-4=60だし（最初の4個はゲームの前から置かれている）、 
最初から隅に打てるわけではないので、盤を回転させていいなら最初の1手目は 
一通りしかない。 

7 名無しさん＠３周年 04/07/23 21:45
>>5
意外に少なくて済みそうだな。最初の１手目は２通りだろ？盤には 
裏表が存在するんだから。

8 名無しさん＠３周年 sage 04/07/24 00:10
たかだか６０回の再帰呼び出しならなんとかなりそうな気がしてしまう

9 名無しさん＠３周年 sage 04/07/28 17:07
>>5 
試合の経過を考えるとそうだけど、ここで考えているのは試合結果なので 
4の考え方でも良いような気がする。 
ただ、5の言うルールとかから推測されるあり得ない試合結果を排除したり 
とか、ゲーム途中でパーフェクトになるパターンとかも考えなくてはなら 
ないので、実は場合分けは結構難しいと思われ。
そうすると8の言うように60回の再帰呼び出しが一番効率良いアルゴリズム 
というのに漏れも一票。 

17 名無しさん＠３周年 04/09/06 02:27
もし、どこにでも置けるとしたならば、 
(8*8-4)!通りなのだから、これ以下なのは間違いない。 

18 名無しさん＠３周年 sage 04/09/09 23:07
おける場所の検索の式が難しいんだよね。 
必ず、他の色をはさむように置かないといけないし… 
割と少ないとは思うんだけど… 

22 名無しさん＠３周年 04/09/27 12:12:56
試合が終わったとき64マス全部埋まるとは限らないが・・・ 
そのへんはどうよ 

36 名無しさん＠３周年 04/10/16 19:11:08
>>23>>24 
さらに言えば、ありえない形もありうる。 
たとえ白黒すべてが盤面にあっても、その形で終わることは絶対にありえない形があるかもしれない。 
やはり、最終形のみを考えて通り数を出すより、１手目から順に計算すべきだと思う。 

37 名無しさん＠３周年 04/10/19 16:53:59
現実にまだ必勝法が見つかっていないくらいだから、 
可能な盤面の数・最終盤面の形とかを厳密に確定するのは 
まだまだ先のことだろうな。 
60! ≒ 8.32 x 10^81よりも少ないことは、素人考えでも分かるが、 
そこから更に絞るとなると... 
第5手目は一通りだから 1*59! ≒ 1.37 x 10^80以下 
第6手目は三通りだから 3*58! ≒ 7.05 x 10^78以下 
第7手目は縦取りだと5通り　斜め取りだと4通り　並び取りだと5通り 
よって14*57! = 5.67*10^77以下 
もう飽きた... 
珠型ルールと禁じ手のない15x15五目並べの必勝法を確立した 
ヴィクター=アリスという人の博士論文によると 
オセロには可能な盤面の数が10^58通りあるそうな。 
http://www.cs.vu.nl/~victor/thesis.html 

http://www.cs.vu.nl/~victor/thesis.html

396 名無しさん＠５周年 sage 2006/03/14(火) 03:31:28 
気分転換に幅優先の全探索してみました。 
手---棋譜数--盤面数-計算時間[s] 
1--------4------4----0.00 
2-------12-----12----0.00 
3-------56-----56----0.02 
4------244----240----0.02 
5-----1396---1344----0.23 
6-----8200---7572----3.31 
7----55092--47624--261.99 
データベースが１本リストなので遅いです。 

397 名無しさん＠５周年 sage 2006/03/15(水) 03:21:20 
t=手数,m=最大着手数,b=盤面数,ti=処理時間[s] 
t= 1, m= 4, b= 4, ti=0.02 
t= 2, m= 3, b= 12, ti=0.00 
t= 3, m= 5, b= 56, ti=0.00 
t= 4, m= 6, b= 240, ti=0.03 
t= 5, m= 9, b= 1344, ti=0.06 
t= 6, m=11, b= 7572, ti=0.31 
t= 7, m=12, b= 47624, ti=1.53 
t= 8, m=14, b= 302418, ti=15.45 
幅探索ずいぶん速くなった。 
パスのない8手までの完全な盤面。

399 よんけた ◆Tl2oC4lIZ2 sage 2006/03/16(木) 15:25:58 
>>396 
おつどす。 
トランスポジションがなかなかの勢いで増えてますね。

405 284 sage 2006/03/18(土) 18:55:54 
>>396 
幅優先ではないんだけど、盤面数を出してみたら396と少し違いました？？ 
手---棋譜数--盤面数 
1--------4------4-(100%) 
2-------12-----12-(100%) 
3-------56-----56-(100%) 
4------244----236-(96.7%) 
5-----1396---1288-(92.3%) 
6-----8200---7092-(86.5%) 
盤面の反転・回転による対称性は考慮していません。 
つまり、>>274での上２つは同一、一番下は別物としてカウントしてます。 
演算量を減らすには対称性も考慮したほうがいいね。 

408 284 sage 2006/03/19(日) 11:46:23 
>>405に対称性を追加しました。あんまり自信ないので誰か検証お願いします。 
手--A棋譜数-B盤面数-(B/A) 
1--------4------1-(25.0%) 
2-------12------3-(25.0%) 
3-------56-----14-(25.0%) 
4------244-----60-(24.6%) 
5-----1396----322-(23.1%) 
6-----8200---1773-(21.6%)

→枝刈り