「証明つきの棋譜数の上界」の編集履歴（バックアップ）一覧はこちら
「証明つきの棋譜数の上界」(2006/03/02 (木) 15:44:54) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
* 4.09732*10^79
< (28*35*42*49*56) * 55 !
出元 = 244
[解説]
n 手目において着手可能数は (60-n+1) ! を超えない。
なぜなら n 手目において空マスは n 個しかないからだ。
また、n 手目において着手可能数は (8-1)(4+n-1) を超えない。
なぜなら、現在置いてある 4+n-1 個のいずれかの隣8マスにしか
新しい石は置く事ができず、
かつその8マスのうち少なくともひとつは既に石が置いてあるからだ。
これより、n≦5 のとき (8-1)(4+n-1) ≦ (60-n+1) ! より、
オセロの全棋譜数は
(7*4 * 7*5 * 7*6 * 7*7 * 7*8) * (54 * 53 ... * 1)
=28*35*42*49*56*55*54*...*3*2*1
を超えない。
* 7.4732*10^71
< 24571192 * 50 !
出元 = 271 & 260
271 ：名無しさん＠５周年 ：2006/02/22(水) 00:49:24
一方試合数絞りの方は
260の10手目=24571192を信じるとすると
全試合数 <= 24571192 * 50*49*...*1 < 7.4732e+71 (= 10^71.8736)
これは確実。
[解説]
1手目までの棋譜数（途中経過）を全探索で求め、
のこりの50手を単純に順列で求めている。
全探索のところは証明ではないけど、複数人が確認してるからOK？
* 2.4082 * 10^70 (現在世界最小。。。たぶん)
< 1,939,899,208 * 48 !
出元 = 329
: 最大棋譜[kifu]数とは？ | &br()オセロのように膨大な棋譜数をもつゲームでは、存在する全棋譜数を数え上げで求めるのは困難になると考えられます。そこで「全棋譜数は絶対これ以上にはならないな」という見積もりが立てられれば、また、それが、&br()&br()「オセロの試合数はおよそ10^XXくらいであると考えられている」&br()&br()などと謳い、そのゼロの多さで読者を「へーオセロってすごいんだねー」と言わせて満足したいだけの目的で書かれた本や記事の、適当に（かつちょっと安全に）見積られた「概算」数をちょっとでも下回れたなら、このThreadに書き込んでいる人々ははそんな雑誌を読んでる女の子の後ろから「ま、ちゃんと調べるとあと10個ほど少ないんだけどね、ゼロが」とささやいたり「ははは。まさか！この人は天文学的に楽観だなぁ俺もそんなスケールの人間になりたいよ」などとほざける訳でそんなしょうもない密かな楽しみが生まれるんじゃないかと思うわけなんです。どうでもいいんだけど。
: 絞り方の基本形 | このThreadで書かれている棋譜数の見積もり最大値は、オセロを含むような別の大きなゲームを考えて、かつそれがオセロより単純に解析できることを利用する流れで絞られています。&br()たとえば、60 ! などは色構わずとりあえず石を順番に並べていくゲームを考えたときの全棋譜数であり、そのゲームはオセロを含みますから、オセロの全棋譜数はいくらなんでも60 ! を超えないだろう、という感じです。
: 最大棋譜数 | 全棋譜数より大きい数字のこと。棋譜数はそれを超えないという意味。「最大」というのは御幣があるかもしれない。誰かいい呼び方考えて。
: 着手可能数 | ある局面のときにそのゲームのルールに則って置ける空マスの数。「局面」をノード、「着手」を有向辺と考えたときに、あるノードから出ている有向辺の数。
