棋譜数の上界を下げる


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

手数の上界を掛けていくなどをして、棋譜数の上界を主に数式で出す。
数は大きいが、説得力のある値。



数式で表現」に貢献している。



39 名無しさん@3周年 sage 04/10/25 14:12:30
円周率は決して正確に求めることはできないが、 
何桁まで求めたかで一つの成果として認められている。 

オセロならば「最高でも何通り以下になる」というのが 
一つの指標になる予感。 

243 名無しさん@5周年 2006/02/02(木) 01:41:24 
概算はいいからこれは絶対に超えないというラインを攻めていこうよ。 
まずは (64-4)!<=10^81.9202 だな。 
これは絶対に超えない。 

244 名無しさん@5周年 2006/02/02(木) 01:53:34 
(64-4)!っていうのは分かりやすくていいんだけど、 
はじめの方の60*59*58…とかが現実的じゃないんだよね。 
後ろのほうの…3*2*1とかはある程度絞れている感じがする。 
なぜはじめの分岐が60パターンもないかというと 
石が少なくて置ける場所が少ないからなんだよね。 
例えば置ける場所っていうのは多くても 
現在置かれている石についてその周り7つ(1箇所は必ず既に置いてある)だけだから、 
5手目までは 既にある石の数*7 という絞り方ができる。これで 
28*35*42*49*56*55*54*...*3*2*1 < 10^79.6125 
ここまで絞れた。うーん。>>243から1/100しか絞れなかったな…道のりは長い… 

245 名無しさん@5周年 2006/02/08(水) 19:54:55 
>>244 
なぜ5手目までなの?

246 名無しさん@5周年 2006/02/10(金) 02:51:54 
六手目からは 
(64-4)! のルールの方が 少ない値で掛けられるからだとおもう。。 

256 256 2006/02/19(日) 22:09:07 
オセロで打てる箇所の数は最大で28かな? 
例えばこういう↓局面。 
++++++++ 
+○○○○○○+ 
+○●●●●○+ 
+○●●●●○+ 
+○●●●●○+ 
+○●●●●○+ 
+○○○○○○+ 
++++++++ 
「28」なのかは証明したわけじゃないけど、 
この局面より打てる場所が多いのは思い浮かばなかった。 
もし28で正しいなら28より大きいのは28にしてしまえるから 
28*28*28*28*...*28*27*...*3*2*1=6.21e+75ってできると思う。 
これだと>>244より4桁くらいしぼれるかな 
誰か「28」の証明か反例探しお願い。

257 256 2006/02/19(日) 23:10:46 
>>256 
もっと多いの見付けた・・。 
これで打てる場所は32個。 
++++++++ 
+○○+○○○+ 
+○●○○●○+ 
+○○●●○++ 
++○●●○○+ 
+○●○○●○+ 
+○○○+○○+ 
++++++++ 
32*32*32*32*...*32*31*...*3*2*1=3.67e+77 
増えていく・・(泣

258 名無しさん@5周年 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 名無しさん@5周年 2006/02/21(火) 10:08:01 
++++++++ 
+○○○+○○+ 
+○●○+●○+ 
+○○○○○○+ 
+++○○+++ 
+○●○+●○+ 
+○○○+○○+ 
++++++++ 
こーいうの(36箇所)はダメなん?

264 256 2006/02/21(火) 17:56:32 
>>263 
僕は空きの数ではなく返せる場所の数を数えてました。 
その局面だと空きは36箇所で打てるのは20箇所ですね。

265 名無しさん@5周年 sage 2006/02/21(火) 22:04:20 
よく分かっていない >>263 がいるスレはここですかw 

266 名無しさん@5周年 sage 2006/02/21(火) 22:04:58 
>>262 
きみの研究に注目しているよ

267 名無しさん@5周年 2006/02/21(火) 22:39:51 
返せる場所の数?

268 名無しさん@5周年 sage 2006/02/21(火) 23:17:14 
全試合数の話題をしているわけだから着手可能数だろがボケ

269 名無しさん@5周年 sage 2006/02/21(火) 23:27:22 
>>267 
解ってねーm9(^Д^)プギャー

270 名無しさん@5周年 sage 2006/02/21(火) 23:35:05 
>>264 
打てるのが20箇所ってどういう意味ですか?

271 名無しさん@5周年 sage 2006/02/22(水) 00:49:24 
256っちの流れいいね。 
まだ最大分岐数33と決まったわけじゃないけど。 
一方試合数絞りの方は 
>>260の10手目=24571192を信じるとすると 
全試合数 <= 24571192*50*49*...*1 < 7.4732e+71 (= 10^71.8736) 
これは確実。

272 名無しさん@5周年 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 に落ちてさらに1、2桁上界、落ちるんですが。

330 284 sage 2006/03/02(木) 09:29:22 
>>329 
最大着手可能数について考えてみました。 
オセロに着手可能数47の盤面がある、と仮定する。 
仮定条件、黒番とし、黒石は挟む石、白石は挟まれる石とする。 
①盤面にある石は17個以下である(64-47=17) 
②黒石(挟む石)1個に対し着手可能数は8(8方向)なので 
47/8=5.875→盤上に6個以上の黒石がある。 
③白石(挟まれる石)1個に対し着手可能数は4(縦横斜めの4ライン)なので 
47/4=11.75→盤上に12個以上の白石がある。 
①の17個以下と②+③の18個以上は矛盾する。 
故に仮定の「オセロに着手可能数47の盤面がある」は間違いなので 
オセロの最大着手可能数は46以下である(証明終了) 
もう少し条件を加えられればさらに減らせると思うのですが。

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

344 名無しさん@5周年 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の条件②黒石(挟む石)1個に対し着手可能数は8(8方向)から、 
②’着手可能数8の時、黒石は最低1個必要。 
③白石(挟まれる石)1個に対し着手可能数は4(縦横斜めの4ライン)なので 
③’着手可能数4の時、白石は最低1個必要。 
よって着手可能数8の為には最低限、黒石が1個白石が2個の計3個必要。 
なので盤面の石で3個セットがいくつとれるか(int(盤上の石数/3))に 
着手可能数8をかけました。 

391 名無しさん@5周年 sage 2006/03/12(日) 06:05:54 
n手目の着手可能数をe(n)とすると 
e(n+1) <= e(n) + 5 
なぜなら、着手可能数が一番増えるケースは、

□□□ 
□★□ 
□□● 

の★のところに打ったときであり、●の隣を除去した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 
着手可能数の増加が最大5というのは黒石ゲームの場合ですね。 
その値とオセロゲームでの15手目最大23を単純に足すのはマズいのでは? 
オセロには黒番・白番があるので。 
通常のオセロでも黒番の着手可能数が1~2でも、白番は+6(7~8)以上になることは十分ありえますし。

400 256 sage 2006/03/17(金) 06:26:17 
終盤のほうで、「空き数=最大着手可能箇所数」の局面が実際にあるか探してみました。 
1~28個空きでは見つけましたが29個空きからなかなか見つかりませんでした。 
29個空きで28箇所の着手可能箇所がある局面に至る棋譜は見つけましたが・・。 
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 
29個見つかりました。 
N手--空数---棋譜 
31----29----F5D6C4F4F6F3D3F7E6C5D7E3E2F2G7E7C3G6G5C7D2B4G3C2B2B3B5B6B7C6G2

403 名無しさん@5周年 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 
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。