棋譜数の上界を下げる


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

棋譜数の上界を下げる




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 
ツールボックス

下から選んでください:

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