証明つきの棋譜数の上界

4.09732*10^79

< (28*35*42*49*56) * 55 !
出元 = 244

[解説]
n 手目において着手可能数は (60-n+1) ! を超えない。
なぜなら n 手目において空マスは 60-n+1 個しかないからだ。
また、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) 
これは確実。

[解説]
10手目までの棋譜数（途中経過）を全探索で求め、
のこりの50手を単純に順列で求めている。
全探索のところは証明ではないけど、複数人が確認してるからOK？

8.540*10^69(現在世界最小。。。たぶん)

330 ：284 ：2006/03/02(木) 09:29:22 
>>329 
最大着手可能数について考えてみました。 
オセロに着手可能数47の盤面がある、と仮定する。 
仮定条件、黒番とし、黒石は挟む石、白石は挟まれる石とする。 
①盤面にある石は17個以下である（64-47=17) 
②黒石（挟む石）１個に対し着手可能数は８（８方向）なので 
47/8=5.875→盤上に６個以上の黒石がある。 
③白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので 
47/4=11.75→盤上に１２個以上の白石がある。 

①の１７個以下と②＋③の１８個以上は矛盾する。 
故に仮定の「オセロに着手可能数47の盤面がある」は間違いなので 
オセロの最大着手可能数は46以下である（証明終了） 

331 ：284 ：2006/03/02(木) 09:58:00 
>>330は、もっと単純に出来ましたね。 
330の条件②と③により、着手可能数は 
int(盤上の石数/3)*8以下になる（intは切捨ての意） 
１２手目、１３手目は石数が16,17なのでint(17/3)*8=40 
>>329の１２手目までを使わせてもらって 
1,939,899,208 * 40 * 40 * 46! = 1.708E+70 
１２手目の最大着手数20も入れて 
1,939,899,208 * 20 * 40 * 46! = 8.540E+69

344 ：名無しさん＠５周年 ：2006/03/04(土) 00:50:33 
>>331 
うーん、この最後の int(盤上の石数/3)*8 が分からないや…。 
>>330は理解できたんだけど。

346 ：284 ：2006/03/04(土) 08:32:12 
>>344 
330の条件②黒石（挟む石）１個に対し着手可能数は８（８方向）から、 
②’着手可能数８の時、黒石は最低１個必要。 
③白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので 
③’着手可能数４の時、白石は最低１個必要。 
よって着手可能数８の為には最低限、黒石が１個白石が２個の計３個必要。 
なので盤面の石で３個セットがいくつとれるか（int(盤上の石数/3)）に 
着手可能数８をかけました。

[解説]
最大着手可能数と完全探索結果による上界。

最大棋譜[transcript]数とは？

オセロのように膨大な棋譜数をもつゲームでは、存在する全棋譜数を数え上げで求めるのは困難になると考えられます。そこで「全棋譜数は絶対これ以上にはならないな」という見積もりが立てられれば、また、それが、

「オセロの試合数はおよそ10^XXくらいであると考えられている」

などと謳い、そのゼロの多さで読者を「へーオセロってすごいんだねー」と言わせて満足したいだけの目的で書かれた本や記事の、適当に（かつちょっと安全に）見積られた「概算」数をちょっとでも下回れたなら、このThreadに書き込んでいる人々ははそんな雑誌を読んでる女の子の後ろから「ま、ちゃんと調べるとあと10個ほど少ないんだけどね、ゼロが」とささやいたり「ははは。まさか！この人は天文学的に楽観だなぁ俺もそんなスケールの人間になりたいよ」などとほざける訳でそんなしょうもない密かな楽しみが生まれるんじゃないかと思うわけなんです。どうでもいいんだけど。

絞り方の基本形

このThreadで書かれている棋譜数の見積もり最大値は、オセロを含むような別の大きなゲームを考えて、かつそれがオセロより単純に解析できることを利用する流れで絞られています。
たとえば、60 ! などは色構わずとりあえず石を順番に並べていくゲームを考えたときの全棋譜数であり、そのゲームはオセロを含みますから、オセロの全棋譜数はいくらなんでも60 ! を超えないだろう、という感じです。

棋譜数の上界 (upper limit of game tree complexity)

全棋譜数より大きい数字のこと。「棋譜数はこの数字を超えない」という意味。この上界をさげていけばなにかいいことがあるかも(なげやりな)

着手可能数 (mobility)

ある局面のときにそのゲームのルールに則って置ける空マスの数。「局面」をノード、「着手」を有向辺と考えたときに、あるノードから出ている有向辺の数。英語の mobility はおそらくチェスから生まれた語句。