手数の上界を掛けていくなどをして、棋譜数の上界を主に数式で出す。
数は大きいが、説得力のある値。
39 名無しさん＠３周年 sage 04/10/25 14:12:30
円周率は決して正確に求めることはできないが、
何桁まで求めたかで一つの成果として認められている。
オセロならば「最高でも何通り以下になる」というのが
一つの指標になる予感。
243 名無しさん＠５周年 2006/02/02(木) 01:41:24
概算はいいからこれは絶対に超えないというラインを攻めていこうよ。
まずは (64-4)!<=10^81.9202 だな。
これは絶対に超えない。
244 名無しさん＠５周年 2006/02/02(木) 01:53:34
(64-4)!っていうのは分かりやすくていいんだけど、
はじめの方の60*59*58…とかが現実的じゃないんだよね。
後ろのほうの…3*2*1とかはある程度絞れている感じがする。
なぜはじめの分岐が60パターンもないかというと
石が少なくて置ける場所が少ないからなんだよね。
例えば置ける場所っていうのは多くても
現在置かれている石についてその周り７つ（１箇所は必ず既に置いてある）だけだから、
5手目までは 既にある石の数*7 という絞り方ができる。これで
28*35*42*49*56*55*54*...*3*2*1 < 10^79.6125
ここまで絞れた。うーん。>>243から1/100しか絞れなかったな…道のりは長い…
245 名無しさん＠５周年 2006/02/08(水) 19:54:55
>>244
なぜ5手目までなの？
246 名無しさん＠５周年 2006/02/10(金) 02:51:54
六手目からは
(64-4)! のルールの方が 少ない値で掛けられるからだとおもう。。
256 256 2006/02/19(日) 22:09:07
オセロで打てる箇所の数は最大で２８かな？
例えばこういう↓局面。
＋＋＋＋＋＋＋＋
＋○○○○○○＋
＋○●●●●○＋
＋○●●●●○＋
＋○●●●●○＋
＋○●●●●○＋
＋○○○○○○＋
＋＋＋＋＋＋＋＋
「２８」なのかは証明したわけじゃないけど、
この局面より打てる場所が多いのは思い浮かばなかった。
もし２８で正しいなら２８より大きいのは２８にしてしまえるから
28*28*28*28*...*28*27*...*3*2*1=6.21e+75ってできると思う。
これだと>>244より4桁くらいしぼれるかな
誰か「２８」の証明か反例探しお願い。
257 256 2006/02/19(日) 23:10:46
>>256
もっと多いの見付けた・・。
これで打てる場所は３２個。
＋＋＋＋＋＋＋＋
＋○○＋○○○＋
＋○●○○●○＋
＋○○●●○＋＋
＋＋○●●○○＋
＋○●○○●○＋
＋○○○＋○○＋
＋＋＋＋＋＋＋＋
32*32*32*32*...*32*31*...*3*2*1=3.67e+77
増えていく・・（泣
258 名無しさん＠５周年 sage 2006/02/19(日) 23:53:43
ちょっと試してみたがオレも32ヶ所以上はできなかった
259 256 2006/02/20(月) 07:16:44
33個見つけました。
＋＋＋＋＋＋＋＋
＋○○●○○○＋
＋○●＋○●○＋
＋●＋●●＋○＋
＋○○●○●○＋
＋○●＋○●○＋
＋○○＋○○○＋
＋＋＋＋＋＋＋＋
33*33*33...*33*32*...*3*2*1=8.68e+77
261 よんけた ◆Tl2oC4lIZ2 sage 2006/02/21(火) 00:11:16
>>259お疲れ様です。
よくみつけたなあ
一万本適当に棋譜作ったとき最高25手という棋譜が一本だけあった。
30手～はほとんど無視していいぐらいに少数になると思う。
>>260
それにしても計算早くないですか？
262 256 2006/02/21(火) 03:14:21
>>261
＞一万本適当に棋譜作ったとき最高25手という棋譜が一本だけあった。
＞30手～はほとんど無視していいぐらいに少数になると思う。
僕もそう思います。
ちなみに>>256の局面とは違いますが、28箇所置ける局面まで辿りつく棋譜は作れました。
F5D6C3D3C4F4F6G6E6E7F7G5E3C5F3B3B4B5B6B7C7G2G3G4D7G7C6B2C2D2F2E2
もっと多いのも探してみますが、
>>257とか>>259みたいな局面を実際に並べて作れるかは疑問に感じてます。
＞それにしても計算早くないですか？
プログラムの計算はあんまり速くないと思います。
今のプログラムのノード展開速度は220kn/s(@Pentium4 2.4GHz)くらいでした。
WZebraとかだとこの20倍くらいは速度が出てますし。
でも速くするアイディアはいくつかあるのでそのうち改良してみます。
263 名無しさん＠５周年 2006/02/21(火) 10:08:01
＋＋＋＋＋＋＋＋
＋○○○＋○○＋
＋○●○＋●○＋
＋○○○○○○＋
＋＋＋○○＋＋＋
＋○●○＋●○＋
＋○○○＋○○＋
＋＋＋＋＋＋＋＋
こーいうの(３６箇所)はダメなん？
264 256 2006/02/21(火) 17:56:32
>>263
僕は空きの数ではなく返せる場所の数を数えてました。
その局面だと空きは36箇所で打てるのは20箇所ですね。
265 名無しさん＠５周年 sage 2006/02/21(火) 22:04:20
よく分かっていない >>263 がいるスレはここですかw
266 名無しさん＠５周年 sage 2006/02/21(火) 22:04:58
>>262
きみの研究に注目しているよ
267 名無しさん＠５周年 2006/02/21(火) 22:39:51
返せる場所の数?
268 名無しさん＠５周年 sage 2006/02/21(火) 23:17:14
全試合数の話題をしているわけだから着手可能数だろがボケ
269 名無しさん＠５周年 sage 2006/02/21(火) 23:27:22
>>267
解ってねーm9(^Д^)ﾌﾟｷﾞｬｰ
270 名無しさん＠５周年 sage 2006/02/21(火) 23:35:05
>>264
打てるのが20箇所ってどういう意味ですか？
271 名無しさん＠５周年 sage 2006/02/22(水) 00:49:24
256っちの流れいいね。
まだ最大分岐数33と決まったわけじゃないけど。
一方試合数絞りの方は
>>260の10手目=24571192を信じるとすると
全試合数 <= 24571192*50*49*...*1 < 7.4732e+71 (= 10^71.8736)
これは確実。
272 名無しさん＠５周年 sage 2006/02/22(水) 00:57:36
混乱してるみたいなので一応解説。
＞僕は空き(☆ & ＋)の数ではなく返せる場所(☆)の数を数えてました。
＞その局面だと空き(☆ & ＋)は36箇所で打てる(☆)のは20箇所ですね。
☆＋☆＋☆☆＋☆
＋○○○＋○○＋
☆○●○☆●○☆
＋○○○○○○＋
☆＋☆○○☆＋☆
☆○●○☆●○☆
＋○○○＋○○＋
☆＋☆＋☆☆＋☆
今回の論点は「打てる場所」です。
329 271 sage 2006/03/02(木) 04:06:42
オセロ12手後 の棋譜数 1,939,899,208 譜 、最大着手数 20手 でした。
オセロ棋譜数上界更新。
1,939,899,208 * 48! < 2.4082 * 10^70
10手後から考えて1桁しか落ちてないなぁ…。
>>256の最大着手数の流れはもう終わったの？
これで最大着手数 33手って分かれば 順列計算のなかの
48*47*...*34*33 が全部 33 に落ちてさらに１、２桁上界、落ちるんですが。
330 284 sage 2006/03/02(木) 09:29:22
>>329
最大着手可能数について考えてみました。
オセロに着手可能数47の盤面がある、と仮定する。
仮定条件、黒番とし、黒石は挟む石、白石は挟まれる石とする。
①盤面にある石は17個以下である（64-47=17)
②黒石（挟む石）１個に対し着手可能数は８（８方向）なので
47/8=5.875→盤上に６個以上の黒石がある。
③白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので
47/4=11.75→盤上に１２個以上の白石がある。
①の１７個以下と②＋③の１８個以上は矛盾する。
故に仮定の「オセロに着手可能数47の盤面がある」は間違いなので
オセロの最大着手可能数は46以下である（証明終了）
もう少し条件を加えられればさらに減らせると思うのですが。
331 284 sage 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 名無しさん＠５周年 sage 2006/03/04(土) 00:50:33
>>331
＞>>330は、もっと単純に出来ましたね。
＞330の条件②と③により、着手可能数は
＞int(盤上の石数/3)*8以下になる（intは切捨ての意）
うーん、この最後の int(盤上の石数/3)*8 が分からないや…。
>>330は理解できたんだけど。
346 284 sage 2006/03/04(土) 08:32:12
>>344
＞うーん、この最後の int(盤上の石数/3)*8 が分からないや…。
330の条件②黒石（挟む石）１個に対し着手可能数は８（８方向）から、
②’着手可能数８の時、黒石は最低１個必要。
③白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので
③’着手可能数４の時、白石は最低１個必要。
よって着手可能数８の為には最低限、黒石が１個白石が２個の計３個必要。
なので盤面の石で３個セットがいくつとれるか（int(盤上の石数/3)）に
着手可能数８をかけました。
391 名無しさん＠５周年 sage 2006/03/12(日) 06:05:54
n手目の着手可能数をe(n)とすると
e(n+1) <= e(n) + 5
なぜなら、着手可能数が一番増えるケースは、
□□□
□★□
□□●
の★のところに打ったときであり、●の隣を除去した５つの□マスであるから。
これから、15手の最大分岐数=23より、
e(16) <= 23+5*1 = 28
e(17) <= 23+5*2 = 33
e(18) <= 23+5*2 = 38
e(19) <= 23+5*2 = 42
e(20) <= 23+5*2 = 41
これ以上は単純な空マスの数の方が小さくなるので
1891844432704 * 28 * 33 * 38 * 42 * 41! = 9.3333 * 10^67
Allisによる概算上界 10^58 まであと9桁です。
http://dais.main.jp/reversi/solve-reversi.html
392 293 sage 2006/03/12(日) 12:43:38
>>391
Allisの論文を探して見てみましたが、オセロについて書かれている内容は
大石さんの書かれていることとほぼ同じです。
（あとは世界チャンピオンに勝ったのがいつ頃とか、今ではプログラムに勝てる人間はいないだとか）
というより大石さんはAllisの論文のオセロ部分を翻訳されたのでは？
で、何を言いたかったかといえば、その中で棋譜数（ゲーム木の大きさ）に関しては
あくまでも予測の概数で、根拠のある
上界は示されていないということでした。
状態数に関する研究も、方法としてはこのスレの方が上っぽい
(2マス連続の先にしか置けないという考慮が書かれていない)ですし。
こっちは概数出していませんけどね （ﾉ∀｀）ｱﾊﾊ
394 284 sage 2006/03/12(日) 16:08:18
>>391
着手可能数の増加が最大５というのは黒石ゲームの場合ですね。
その値とオセロゲームでの15手目最大23を単純に足すのはマズいのでは？
オセロには黒番・白番があるので。
通常のオセロでも黒番の着手可能数が１～２でも、白番は＋６（７～８）以上になることは十分ありえますし。
400 256 sage 2006/03/17(金) 06:26:17
終盤のほうで、「空き数＝最大着手可能箇所数」の局面が実際にあるか探してみました。
１～２８個空きでは見つけましたが２９個空きからなかなか見つかりませんでした。
２９個空きで２８箇所の着手可能箇所がある局面に至る棋譜は見つけましたが・・。
N手--空数---棋譜
32----28----F5D6C3D3C4F4F6G6E6E7F7G5E3C5F3B3B4B5B6B7C7G2G3G4D7G7C6B2C2D2F2E2
33----27----F5D6C3D3C4F4F6G6E6E7F7G5E3C5G7F8D7C7B7B4B6B5B3C6G4G3G2C2B2D2F3F2E2
34----26----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8
35----25----F5D6C3D3C4F4F6G6E6E7F7G5E3C5F3B3B4B5B6B7C7G2G3G4D7G7C6B2C2D2F2E2A5A4A3
36----24----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8
37----23----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6A5A8G2B8A7A6
38----22----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8
39----21----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8G8
40----20----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1
41----19----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1G8
42----18----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1
43----17----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1G8
44----16----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1
401 256 sage 2006/03/17(金) 06:27:58
45----15----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1G8
46----14----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3
47----13----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3G8
48----12----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5
49----11----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3G8H8H7
50----10----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7
51-----9----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5G8H8H7
52-----8----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7
53-----7----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7G8H8H7
54-----6----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5
55-----5----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5G1
56-----4----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5H1H2
57-----3----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5G1H1H2
58-----2----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5H1H2H3H4
59-----1----F5F6E6F4E3C5C4D6B5D3C3F2F3E2G4G5C6D2C2B2B3B4D7G6G3E7F7G7C7B7B6G2A8B8C8D8E8F8A1B1C1D1E1F1A2A3A4A5A6A7H8H7H6H5G1H1H2H3H4
402 256 sage 2006/03/17(金) 07:20:04
２９個見つかりました。
N手--空数---棋譜
31----29----F5D6C4F4F6F3D3F7E6C5D7E3E2F2G7E7C3G6G5C7D2B4G3C2B2B3B5B6B7C6G2
403 名無しさん＠５周年 sage 2006/03/18(土) 05:08:24
盤面はどんな感じっすか？
404 256 sage 2006/03/18(土) 06:08:28
>>403
>>402の29個のはこんな感じです。
F5D6C4F4F6F3D3F7E6C5D7E3E2F2G7E7C3G6G5C7D2B4G3C2B2B3B5B6B7C6G2
＋＋＋＋＋＋＋＋
＋●●●●●◆＋
＋●○○○●●＋
＋●○○○●＋＋
＋●○○●●●＋
＋●○○○○●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋
ちなみに僕が棋譜を並べたり盤面を作ったりする時はいつもこれ↓使ってます。
http://www2.next.ne.jp/~runoth/runoth.html
最終更新：2009年08月19日 23:58
