棋譜数の上界を下げる

棋譜数の上界を下げる

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