終局局面数

「終局局面数」の編集履歴（バックアップ）一覧はこちら

「終局局面数」(2009/08/19 (水) 23:56:57) の最新版変更点

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

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

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

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

局面数の概算→[[局面数の概算]]

子話題
→[[黒石ゲーム]]
→[[ありえない局面]]
→[[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%)

→[[枝刈り]]

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

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

局面数の概算→[[局面数の概算]]

子話題
→[[黒石ゲーム]]
→[[ありえない局面]]
→[[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%)

→[[枝刈り]]