黒石ゲーム

「黒石ゲーム」の編集履歴（バックアップ）一覧はこちら

「黒石ゲーム」(2009/08/20 (木) 00:00:17) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*黒石ゲーム
ルールは[[完全探索データ]]参照。
作りだされる局面の形がオセロゲームの局面の形を満足するので、
オセロゲームの局面数に関する手がかりになるとされる。


親話題→[[終局局面数]]
----
[[棋譜数の上界を下げる]]からの流れで最高何手打てるかを256が探ってる最中から始まった。


 259 256 2006/02/20(月) 07:16:44 
 33個見つけました。 
 ＋＋＋＋＋＋＋＋ 
 ＋○○●○○○＋ 
 ＋○●＋○●○＋ 
 ＋●＋●●＋○＋ 
 ＋○○●○●○＋ 
 ＋○●＋○●○＋ 
 ＋○○＋○○○＋ 
 ＋＋＋＋＋＋＋＋ 
 33*33*33...*33*32*...*3*2*1=8.68e+77 

 262 256 2006/02/21(火) 03:14:21 
 もっと多いのも探してみますが、 
 >>259みたいな局面を実際に並べて作れるかは疑問に感じてます。 

 276 よんけた ◆Tl2oC4lIZ2 sage 2006/02/22(水) 14:30:18 
 >>262 
 ＞>>259みたいな局面を実際に並べて作れるかは疑問に感じてます。 
 このことに関してちょっと考えてみました。 
 ランダムに作った盤面の総通りaは、 
 a = 3^64 = 4.23912E+28 
 これはオセロの総棋譜数の予測値より格段に少ない値です。 
 だから、ランダムに作った盤面は棋譜で表現できるんじゃないかと。 
 しかしランダムで作った盤面の中には囲碁みたいに離れた石が存在するような盤面もありますし、 
 試合開始前からある真ん中の四つの石がない盤面もあります（3^60で済みますが)。 
 つまり置石の形からしてオセロでは表現できない盤面があります。 
 またさらに、存在してそうな形をしていてもオセロ棋譜で表現できないものもあります。 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋○●＋＋＋ 
 ＋＋＋●○●＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋とか。 
 すみません当たり前ですね。 

 278 名無しさん＠５周年 sage 2006/02/22(水) 23:17:26 
 >>276 
 60展開後の局面数がもうめちゃくちゃ多く見積もって < 2^64 = 10^19 だから 
 かなり縮退してそうだね。 
 あと奇遇性とか連結性（離れ小島は発生しない）とかで絞ったらどうかな。 
 連結性でいえば、 
 2x2 の黒石で始まって隣８箇所のどこかに黒石がありさえすれば 
 黒石が置けるようなゲームを考えると、 
 必ずそのゲームの棋譜数（局面数）はオセロのそれらを下回るし 
 解析もやりやすいと思う。 
 まあオセロより解析が簡単と言えど 
 その局面数を数え上げるのも結構むつかしいんだが…。 

 282 256 2006/02/23(木) 07:56:46  
 >>278 
 石有り/空きの2値のみの局面をランダムに発生させて、 
 中央の2x2マスが埋まっている割合とそのうち全ての石が繋がっている割合を 
 モンテカルロ法で調べてみました。 
 その結果、10億回の試行で、 
 ①　中央の2x2マスが埋まっているもの：62503304(6.2503%)(1/15.999232≒1/16) 
 ②　①のうち全ての石が繋がっているもの：18267113(1.8267%)(1/54.743188) 
 ①は予想通りでした。 
 ②は見当もつきませんでしたが、、、こんなもんなのかぁ。 

 284 名無しさん＠５周年 2006/02/23(木) 13:01:49 
 >>282 
 ランダムに作った盤面 a=3^64=3.43368E+30 通り 
 そのうち中央４マスは空にならないとすると　b=(3^60)*(2^4)=6.78259E+29 
 確率はb/a=(2^4)/(3^4)=1/5.06≒19.75％ 
 ＞石有り/空きの2値のみの局面をランダムに発生させて 
 出来るなら石有りの発生確率を空きの２倍の確率にしたらどうだろう？ 
 そうすれば①の確率は19.75％に近づくだろうし②の確率も変わるはず。 

 286 よんけた ◆Tl2oC4lIZ2 sage 2006/02/23(木) 18:28:19 
 >>284 
 それはオセロゲームの確率。 
 黒石ゲーム(>>278)は 
 a = 2^64 
 b = 2^60 
 で b/a = 1/16 
 ですよ

 287 256 2006/02/23(木) 21:08:46 
 >>282のプログラムを改造して石の数毎に分布を調べてみました。 
 （待つのがめんどくさかったので１億回の試行。ちょっと精度は落ちますが。） 
 局面発生数のピークは石数が３１・３２個の付近にありました。（約9.77%） 
 中央の2x2が埋まったり石が繋がっている割合は石数が増えるほど多くなってました。 
 一部抜き出します。 
 石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合 
 40----1079403----161591----103285----0.149704----0.095687 
 41----616058----102065----70461----0.165674----0.1143740 
 42----328628----60178----44581----0.183119----0.135658 
 43----163666----33264----25916----0.203243----0.158347 
 44----76032----16754----13726----0.220355----0.180530 
 45----32723----7869----6692----0.240473----0.204504 
 46----13226----3490----3093----0.263874----0.233858 
 >>284 
 ＞出来るなら石有りの発生確率を空きの２倍の確率にしたらどうだろう？ 
 2倍の確率ってのは黒/白/空きの3値の盤面から石有/空きの2値の盤面に変換すると 
 石の存在確率が空きの2倍であるといったような事からですか？ 
 上の表で石の存在割合が空きの2倍である42石や43石（64*2/3≒42.667）の辺りを見ると、 
 0.183119～(19.75)～0.203243となってますが、、。 
 2値の盤面は32ビットの乱数を2個発生させてつなげて作ってました。 
 各マス毎に乱数を発生させると発生確率を変えられそうですがちょと遅くなりそうな気が。 
 何かうまい方法はありませんか？ 

 288 名無しさん＠５周年 2006/02/23(木) 21:49:53 
 ＞局面発生数のピークは石数が３１・３２個の付近にありました 
 中心極限定理ってことかな。 
 0～60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で 
 黒石ｎ個であるときの一様な試行が得られるよ。 

 289 284 sage 2006/02/23(木) 22:23:37 
 >>286 
 はい、それは了解しています。 
 >>284は黒石ゲームからオセロゲームへのアプローチのつもりでした。 
 >>287 
 お疲れ様です。 
 石数が４５の時任意のマスが埋まってる確率は45/64=0.703 
 中央４マスが埋まってる確率は0.703^4=0.244≒0.240473なので正解に近いでしょう。 
 石の発生確率２倍というのは仰るとおり黒/白/空き３値の盤面を想定してのことでした。 
 前出 b=(3^60)*(2^4)=6.78259E+29 に３値での発生確率を掛ければ
 概算の有効盤面数が割り出せるかと考えました。 
 乱数発生ですが、１マス３ビットで5/8=0.625の乱数は作れますが 
 乱数発生を３倍にしたにしては精度が低いですね。 
 ８ビット乱数(2^8=256)で５マス(3^5=243)を作るのが効率良いのかな？ 
 それより前出 b の式自体を変えたほうが良さそうですね。

 290 256 2006/02/24(金) 01:21:55 
 >>288 
 ＞0～60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で 
 ＞黒石ｎ個であるときの一様な試行が得られるよ。 
 よくわからなかったのですが、気になるのでもうちょっと詳しく教えてもらえますか？ 
 n個の１をばらまくほうが簡単そうですが、、、これではだめでしょうか？ 
 石数が14個くらいまでならオセロ盤で実際に10手以下の全探索をした盤面と比較できると思ったのですが、 
 今の方法だと石数が20個くらいまでの局面発生数はほとんどゼロにしかならなかったので、 
 一様な試行もできればいいなと思ってました。 
 >>289 
 石の発生確率を2倍にしてみました。（1億回試行） 
 乱数は、16個発生させて１マスあたり８ビット使い、 
 3で割った余りによって石有/空きを決めました。（遅い） 
 石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合 
 34----810312----59684----14553----0.07366----0.01796 
 35----1391979----114885----33877----0.08253----0.02434 
 36----2237616----207915----73092----0.09292----0.03267 
 37----3388840----353598----144910----0.10434----0.04276 
 38----4814954----558985----260877----0.11609----0.05418 
 39----6420635----830327----436917----0.12932----0.06805 
 40----8024164----1153300----673413----0.14373----0.08392 
 41----9401529----1500247----959482----0.15957----0.10206 
 42----10292005----1814899----1251133----0.17634----0.12156 
 43----10535592----2045606----1508248----0.19416----0.14316 
 44----10053709----2147383----1673889----0.21359----0.16649 
 45----8931797----2095020----1712559----0.23456----0.19174 
 46----7381673----1897347----1613363----0.25703----0.21856 
 47----5646603----1586556----1394172----0.28098----0.24690 
 48----4002903----1227091----1109087----0.30655----0.27707 
 49----2617925----874116----807797----0.33390----0.30856 
 50----1568075----568807----535577----0.36274----0.34155 
 51----861444----339229----324220----0.39379----0.37637 

 291 名無しさん＠５周年 sage 2006/02/24(金) 01:33:17 
 ん～、8ビット使って3の剰余で分ける…0が1と2より1/85だけ多い割合で出るから
 この数のシミュには向かないのでは？ 
 剰余にかかる時間 >> 乱数1個発生時間 だろうし、32ビットのまま行ってみては？

 292 256 2006/02/24(金) 01:49:06 
 今32ビットで、１億回試行中ですが、 
 さっき１０００万回で比較したら処理時間が2倍ちょっとになっちゃいました。

 293 名無しさん＠５周年 sage 2006/02/24(金) 02:07:57 
 お疲れ様です。 
 こっちは後発なので2）の方針でいこうと思います。（対称解は1つ扱い） 
 >>120が正確ではない（4×4だから）けど参考になる、と自分用リンク。

 294 256 2006/02/24(金) 02:26:11 
 ８ビットだと確かに精度が悪くなっているようです。 
 >>290と同じ範囲でもだいたい１‰以上の誤差が出てきてます。 
 ５０～５８石あたりでは数％も誤差がありました。 
 石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合 
 34----819799----59304----14654----0.07234----0.01788 
 35----1394987----113825----33552----0.08160----0.02405 
 36----2239644----206965----72737----0.09241----0.03248 
 37----3370795----349045----142996----0.10355----0.04242 
 38----4786955----553633----258442----0.11565----0.05399 
 39----6383626----825334----434910----0.12929----0.06813 
 40----7979411----1147014----670576----0.14375----0.08404 
 41----9371145----1492668----953573----0.15928----0.10176 
 42----10279583----1811139----1249041----0.17619----0.12151 
 43----10544519----2046793----1506964----0.19411----0.14291 
 44----10086594----2156237----1680278----0.21377----0.16659 
 45----8979083----2107749----1723086----0.23474----0.19190 
 46----7424025----1909494----1623887----0.25720----0.21873 
 47----5688036----1597364----1403921----0.28083----0.24682 
 48----4014876----1231054----1111899----0.30662----0.27694 
 49----2609923----870280----803689----0.33345----0.30794 
 50----1558130----564842----531864----0.36251----0.34135 
 51----847121----332688----317532----0.39273----0.37484 

 295 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:50:21 
 そろそろ難しくてついていけなくなりましたが、一生懸命レスさせていただきますｗ 
 僕はプログラムのプもかけません。もしかしたら勘違いしているのかもしれません。 
 空きの発生確率を　Og　。石の発生確率を　Ob　。（つまり　Og　+　Ob　＝　1　） 
 とする。 
 石数が　n　の時の局面発生率は、 
 64Pn * Og^(64-n) * Ob^n 
 です。 
 ---Og-----Ob 
 A--0.3329--0.6671 
 B--0.3330--0.6670 
 C--0.3331--0.6669 
 D--0.3332--0.6668 
 E--0.3333--0.6667 
 F--0.3334--0.6666 
 G--0.3335--0.6665 
 H--0.3336--0.6664 
 I--0.3337--0.6663 
 と石空き発生率A～Jに振り分ける。 
 例えばＥで石数が40の局面発生率は、 
 64P40 * 0.3333＾24 * 0.6667^40 
 = 0.080229095 

 296 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:51:00 
 続き 
 次にEを基準として次の表を作成する。 
 石数--A/Ｅ---B/Ｅ----C/Ｅ---D/Ｅ----E/Ｅ----F/Ｅ---G/Ｅ----H/Ｅ----I/Ｅ 
 3-----0.9310--0.9478--0.9649--0.9823--1.0000--1.0180--1.0363--1.0550--1.0740- 
 6-----0.9361--0.9517--0.9675--0.9836--1.0000--1.0166--1.0335--1.0507--1.0682- 
 9-----0.9412--0.9555--0.9701--0.9850--1.0000--1.0153--1.0308--1.0465--1.0624- 
 12----0.9463--0.9594--0.9728--0.9863--1.0000--1.0139--1.0280--1.0423--1.0567- 
 15----0.9514--0.9633--0.9754--0.9876--1.0000--1.0125--1.0252--1.0380--1.0510- 
 18----0.9565--0.9672--0.9780--0.9890--1.0000--1.0112--1.0224--1.0338--1.0454- 
 21----0.9617--0.9712--0.9807--0.9903--1.0000--1.0098--1.0197--1.0297--1.0397- 
 24----0.9669--0.9751--0.9833--0.9916--1.0000--1.0084--1.0169--1.0255--1.0341- 
 25----0.9722--0.9791--0.9860--0.9930--1.0000--1.0071--1.0142--1.0214--1.0286- 
 30----0.9774--0.9830--0.9887--0.9943--1.0000--1.0057--1.0115--1.0172--1.0230- 
 33----0.9827--0.9870--0.9913--0.9957--1.0000--1.0044--1.0087--1.0131--1.0175- 
 36----0.9880--0.9910--0.9940--0.9970--1.0000--1.0030--1.0060--1.0090--1.0120- 
 39----0.9934--0.9950--0.9967--0.9983--1.0000--1.0017--1.0033--1.0050--1.0066- 
 42----0.9988--0.9991--0.9994--0.9997--1.0000--1.0003--1.0006--1.0009--1.0012- 
 45----1.0042--1.0031--1.0021--1.0010--1.0000--0.9990--0.9979--0.9968--0.9958- 
 48----1.0096--1.0072--1.0048--1.0024--1.0000--0.9976--0.9952--0.9928--0.9904- 
 51----1.0151--1.0113--1.0075--1.0038--1.0000--0.9963--0.9925--0.9888--0.9851- 
 54----1.0206--1.0154--1.0102--1.0051--1.0000--0.9949--0.9898--0.9848--0.9798- 
 57----1.0261--1.0195--1.0130--1.0065--1.0000--0.9936--0.9872--0.9808--0.9745- 
 60----1.0317--1.0237--1.0157--1.0078--1.0000--0.9922--0.9845--0.9769--0.9693- 
 63----1.0373--1.0278--1.0185--1.0092--1.0000--0.9909--0.9819--0.9729--0.9641- 
 ※A/Eは　Ａ割るＥ　という意。少数5桁目を四捨五入しました。

 297 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:52:53 
 続き 
 つまりなにが言いたいかといいますと、石数42個らへんが一番コンピューター乱数の仕様誤差（？）
 の影響を受けにくく、石数４２個らへんから、上にも下にも影響を受けやすくなる。ということです。 
 と思います。

 299 293 sage 2006/02/24(金) 22:20:33 
 前言撤回。複数がやるにしても同じ結果に到達しなきゃ確証得られませんし 
 自分も3）方向で行きます。取りあえずは>>260と同じ物が出るかを確認し、 
 もう少し先の手まで進めて上から押さえるつもりです。

 300 284 sage 2006/02/24(金) 22:23:54 
 石の発生確立を２倍にするのは難しいようですね。 
 発生確率をRとし　0<R<1　とすると 
 64マスで石の個数 n となる確率は R^n*(1-R)^(64-n) となります。 
 （実際はこれに組み合わせ数を掛けないといけないが補正係数の算出には不要なので省略） 
 発生確率2/3と1/2の差を２値での個数ごとの結果に掛け合わせたらどうでしょうか。 
 石の個数nの時の補正係数は{(2/3)^n*(1-2/3)^(64-n)}/{(1/2)^n*(1-1/2)^(64-n)} 
 >>287のデータに補正係数を掛けると 
 石数--補正係数------局面発生数----埋まてる数----繋がてる数 
 40----5.906894946---6375920.125---954501.0612---610093.6445 
 41----11.81378989---7277979.773---1205774.465---832411.4496 
 42----23.62757978---7764684.289---1421860.496---1053341.134 
 43----47.25515957---7734062.946---1571895.628---1224664.715 
 44----94.51031913---7185808.584---1583425.887---1297248.64 
 45----189.0206383---6185322.346---1487403.403---1264926.111 
 46----378.0412765---4999973.923---1319364.055---1169281.668 
 石数0～64のすべてに補正係数を掛けて埋まってる数、繋がってる数のトータルを 
 出せれば石の発生確率2/3のときのデータになるはずです。 
 補正係数を掛けると局面発生数のピークも42～43になるようです。


 301 256 2006/02/25(土) 00:47:27 
 >>287 
 ＞局面発生数のピークは石数が３１・３２個の付近にありました。（約9.77%） 
 見直してて気づいたのですが、このようになるのはおかしいですね。 
 ０以上のの乱数を発生させてたようで常に０のビットが１箇所あります。 
 初歩的なミスですみません。石の発生確率が1/2のはやり直します。

 302 293 sage 2006/02/25(土) 01:03:02 
 >>301 
 あ、よかった。試しに真ん中4つが埋まってるプログラムを作ったら 
 10億回のテストで約2倍（発生回数も、埋まってる回数もなので割合はほぼ一緒） 
 だったのでちょいと不安だったのですよ。 
 ついでにちょいと訪ねてみます。繋がりチェックはどううやってます？

 303 293 sage 2006/02/25(土) 01:19:47 
 作った、ていうだけだと無意味なので一応結果。 
 1/2の割合で石を置いた場合、真ん中4つが埋まってるかどうかのチェック 
 石数-埋まる盤数/発生盤数-埋まる割合 
 26---1218966/-45486584---2.680% 
 27---1907062/-60649877---3.144% 
 28---2785026/-75805416---3.674% 
 29---3779166/-88870059---4.252% 
 30---4802368/-97776964---4.912% 
 31---5689156/100905325---5.638% 
 32---6306276/-97783629---6.449% 
 33---6517819/-88887714---7.333% 
 34---6304380/-75812328---8.316% 
 35---5693658/-60654246---9.387% 
 36---4801615/-45477307--10.558% 
 37---3783263/-31960276--11.837% 
 38---2779478/-21035323--13.213% 
 39---1907262/-12943552--14.735% 
 40---1217947/--7439856--16.371% 
 41----725024/--3994642--18.150% 
 42----400816/--1995761--20.083% 
 43----205262/---929754--22.077% 
 44-----97770/---401131--24.374% 
 45-----42627/---160050--26.634%  

 304 256 2006/02/25(土) 01:26:04 
 >>302 
 繋がりチェックは画像の領域塗りつぶしをするときのような再帰関数でやってます。 
 http://www.sm.rim.or.jp/~shishido/fill.html  

 310 256 sage 2006/02/25(土) 10:30:54 
 石の発生確率が1/2のをやり直しました。（1億回試行） 
 乱数はメルセンヌ・ツイスタを実装して使いました。 
 石数--局面発生数---埋数-----繋数----埋割合(%)--繋割合(%) 
 26-----3259193-----76287-----2155-----2.341-----0.066 
 27-----4590786----127177-----4935-----2.770-----0.107 
 28-----6062081----193814----10284-----3.197-----0.170 
 29-----7532330----280764----19920-----3.727-----0.264 
 30-----8780535----378290----35483-----4.308-----0.404 
 31-----9634737----476656----58036-----4.947-----0.602 
 32-----9935619----560162----88116-----5.638-----0.887 
 33-----9634648----620294---121801-----6.438-----1.264 
 34-----8783902----641192---156250-----7.300-----1.779 
 35-----7533047----620987---182592-----8.244-----2.424 
 36-----6066048----562048---196924-----9.265-----3.246 
 37-----4592260----477504---195003----10.398-----4.246 
 38-----3262028----379078---177332----11.621-----5.436 
 39-----2172546----281015---148555----12.935-----6.838 
 40-----1355366----195240---114113----14.405-----8.419 
 41------794734----127204----81540----16.006-----10.260 
 42------435867-----76380----52814----17.524-----12.117 
 43------222876-----43355----32009----19.453-----14.362 
 44------106482-----22713----17578----21.330-----16.508 
 45-------47634-----11304-----9285----23.731-----19.492 
 局面発生数のピークが３２に来ましたけど、 
 ０～６４のちょうど真ん中だからこれでいいですよね？

 317 305 sage 2006/02/25(土) 18:54:36 
 反復深化で黒石ゲーム全探索してみました。 
 黒石ゲーム 7手目 679,519,480パターン, 最大36分岐 
 オセロ 7手目 55,092パターン, 最大12分岐 
 オセロ 11手目 212,260,880パターン, 最大18分岐 
 はい。

 318 256 sage 2006/02/28(火) 10:31:21 
 黒石ゲームで石数が４～６４の範囲の一様な試行もやってみました。 
 データとかグラフを載せるとこが欲しいですね・・。

 321 256 sage 2006/02/28(火) 16:38:04 
 318のは今試行の数を増やしているところです。 
 終わってまとめたらアップします。

 326 284 sage 2006/03/01(水) 13:18:49 
 >>314->>315[[ありえない局面]]あたりを読んでて気が付いたが、 
 オセロの場合石を置くには最低挟める石と挟む為の石が必要なので、可能盤面は 
 「初期配置の中央４石を除き、全ての石は３個以上の列に含まれる」と言える。 
 なので>>314の下の図は、オセロでは有り得ないことが証明出来る。 
 （>>315の反例を一般化してみた） 
 黒石ゲームのルール、「隣８箇所のどこかに黒石がありさえすれば黒石が置ける」 
 というのを「２連続（以上）の黒石の延長上に置ける」とすればどうだろう？ 
 そうすれば、黒石ゲームでも同様のことが言えるようになる。

 327 284 sage 2006/03/01(水) 22:34:19 
 10万回ランダムに棋譜を発生させてみた。パスは１手としない（必ず60手以内で終わる） 
 平均手数の積は1.4E+53 
 標準偏差も出して確からしさも出そうかと思ったが１手99%として0.99^60=54%なのでやめた。 
 パス、連パスによるゲーム終了は10～16手目あたりと終盤に多く中盤は少ない。 
 手番---回数----最大--最小---総手数---Σ(総手数^2)--平均---標準偏差---パス--ゲーム終了 
 --1---100000-----4-----4-----400000----1600000----4.0000----0.0000------0-----0 
 --2---100000-----3-----3-----300000-----900000----3.0000----0.0000------0-----0 
 --3---100000-----5-----4-----466503----2198527----4.6650----0.8732------0-----0 
 --9---100000----15-----1-----755769----6092271----7.5577----1.6974-----72-----0 
 -10----99981----16-----1-----789548----6684874----7.8970----1.9073-----19----19 
 -11----99977----17-----1-----834035----7433175----8.3423----2.0992-----29-----4 
 -30----99952----24-----1----1202014---15378396---12.0259----2.8944------1-----0 
 -31----99951----25-----1----1185681---14989101---11.8626----2.8772------9-----1 
 -32----99951----23-----1----1192029---15133605---11.9261----2.9610------2-----0 
 -57----99950-----4-----1-----295764-----967274----2.9591----0.4936---2248-----1 
 -58----99948-----3-----1-----232387-----594419----2.3251----0.6372---4422-----2 
 -59----99916-----2-----1-----167192-----301744----1.6733----0.4472---9845----32 
 -60----98996-----1-----1------98996------98996----1.0000----0.0000--25951---920 

 328 271 sage 2006/03/02(木) 03:52:59 
 >>326 
 ＞黒石ゲームのルール、「隣８箇所のどこかに黒石がありさえすれば黒石が置ける」 
 ＞というのを「２連続（以上）の黒石の延長上に置ける」とすればどうだろう？ 
 それいいね。ずいぶん絞れました。 
 7手後の全棋譜数 
 オセロ / 黒石ゲーム / 黒石ゲーム２(>>326) 
 55,092 / 679,519,480 / 126,786,952 
 うーん。完全探索(反復深化)派としては、 
 黒石ゲームのようにゲームの一般化をしても 
 ノード数が増えて計算時間が増えるだけで、 
 (>>271式)の全棋譜数の上界設定に使うにしても 
 結局オセロの探索結果が12手まで求められるっていうことが 
 一番上界設定に寄与している気がする。。あたりまえか。 
 純粋な理論による上界設定には使えそうだけどね。

ルールは[[完全探索データ]]参照。
作りだされる局面の形がオセロゲームの局面の形を満足するので、
オセロゲームの局面数に関する手がかりになるとされる。


親話題→[[終局局面数]]
----
[[棋譜数の上界を下げる]]からの流れで最高何手打てるかを256が探ってる最中から始まった。


 259 256 2006/02/20(月) 07:16:44 
 33個見つけました。 
 ＋＋＋＋＋＋＋＋ 
 ＋○○●○○○＋ 
 ＋○●＋○●○＋ 
 ＋●＋●●＋○＋ 
 ＋○○●○●○＋ 
 ＋○●＋○●○＋ 
 ＋○○＋○○○＋ 
 ＋＋＋＋＋＋＋＋ 
 33*33*33...*33*32*...*3*2*1=8.68e+77 

 262 256 2006/02/21(火) 03:14:21 
 もっと多いのも探してみますが、 
 >>259みたいな局面を実際に並べて作れるかは疑問に感じてます。 

 276 よんけた ◆Tl2oC4lIZ2 sage 2006/02/22(水) 14:30:18 
 >>262 
 ＞>>259みたいな局面を実際に並べて作れるかは疑問に感じてます。 
 このことに関してちょっと考えてみました。 
 ランダムに作った盤面の総通りaは、 
 a = 3^64 = 4.23912E+28 
 これはオセロの総棋譜数の予測値より格段に少ない値です。 
 だから、ランダムに作った盤面は棋譜で表現できるんじゃないかと。 
 しかしランダムで作った盤面の中には囲碁みたいに離れた石が存在するような盤面もありますし、 
 試合開始前からある真ん中の四つの石がない盤面もあります（3^60で済みますが)。 
 つまり置石の形からしてオセロでは表現できない盤面があります。 
 またさらに、存在してそうな形をしていてもオセロ棋譜で表現できないものもあります。 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋○●＋＋＋ 
 ＋＋＋●○●＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋ 
 ＋＋＋＋＋＋＋＋とか。 
 すみません当たり前ですね。 

 278 名無しさん＠５周年 sage 2006/02/22(水) 23:17:26 
 >>276 
 60展開後の局面数がもうめちゃくちゃ多く見積もって < 2^64 = 10^19 だから 
 かなり縮退してそうだね。 
 あと奇遇性とか連結性（離れ小島は発生しない）とかで絞ったらどうかな。 
 連結性でいえば、 
 2x2 の黒石で始まって隣８箇所のどこかに黒石がありさえすれば 
 黒石が置けるようなゲームを考えると、 
 必ずそのゲームの棋譜数（局面数）はオセロのそれらを下回るし 
 解析もやりやすいと思う。 
 まあオセロより解析が簡単と言えど 
 その局面数を数え上げるのも結構むつかしいんだが…。 

 282 256 2006/02/23(木) 07:56:46  
 >>278 
 石有り/空きの2値のみの局面をランダムに発生させて、 
 中央の2x2マスが埋まっている割合とそのうち全ての石が繋がっている割合を 
 モンテカルロ法で調べてみました。 
 その結果、10億回の試行で、 
 ①　中央の2x2マスが埋まっているもの：62503304(6.2503%)(1/15.999232≒1/16) 
 ②　①のうち全ての石が繋がっているもの：18267113(1.8267%)(1/54.743188) 
 ①は予想通りでした。 
 ②は見当もつきませんでしたが、、、こんなもんなのかぁ。 

 284 名無しさん＠５周年 2006/02/23(木) 13:01:49 
 >>282 
 ランダムに作った盤面 a=3^64=3.43368E+30 通り 
 そのうち中央４マスは空にならないとすると　b=(3^60)*(2^4)=6.78259E+29 
 確率はb/a=(2^4)/(3^4)=1/5.06≒19.75％ 
 ＞石有り/空きの2値のみの局面をランダムに発生させて 
 出来るなら石有りの発生確率を空きの２倍の確率にしたらどうだろう？ 
 そうすれば①の確率は19.75％に近づくだろうし②の確率も変わるはず。 

 286 よんけた ◆Tl2oC4lIZ2 sage 2006/02/23(木) 18:28:19 
 >>284 
 それはオセロゲームの確率。 
 黒石ゲーム(>>278)は 
 a = 2^64 
 b = 2^60 
 で b/a = 1/16 
 ですよ

 287 256 2006/02/23(木) 21:08:46 
 >>282のプログラムを改造して石の数毎に分布を調べてみました。 
 （待つのがめんどくさかったので１億回の試行。ちょっと精度は落ちますが。） 
 局面発生数のピークは石数が３１・３２個の付近にありました。（約9.77%） 
 中央の2x2が埋まったり石が繋がっている割合は石数が増えるほど多くなってました。 
 一部抜き出します。 
 石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合 
 40----1079403----161591----103285----0.149704----0.095687 
 41----616058----102065----70461----0.165674----0.1143740 
 42----328628----60178----44581----0.183119----0.135658 
 43----163666----33264----25916----0.203243----0.158347 
 44----76032----16754----13726----0.220355----0.180530 
 45----32723----7869----6692----0.240473----0.204504 
 46----13226----3490----3093----0.263874----0.233858 
 >>284 
 ＞出来るなら石有りの発生確率を空きの２倍の確率にしたらどうだろう？ 
 2倍の確率ってのは黒/白/空きの3値の盤面から石有/空きの2値の盤面に変換すると 
 石の存在確率が空きの2倍であるといったような事からですか？ 
 上の表で石の存在割合が空きの2倍である42石や43石（64*2/3≒42.667）の辺りを見ると、 
 0.183119～(19.75)～0.203243となってますが、、。 
 2値の盤面は32ビットの乱数を2個発生させてつなげて作ってました。 
 各マス毎に乱数を発生させると発生確率を変えられそうですがちょと遅くなりそうな気が。 
 何かうまい方法はありませんか？ 

 288 名無しさん＠５周年 2006/02/23(木) 21:49:53 
 ＞局面発生数のピークは石数が３１・３２個の付近にありました 
 中心極限定理ってことかな。 
 0～60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で 
 黒石ｎ個であるときの一様な試行が得られるよ。 

 289 284 sage 2006/02/23(木) 22:23:37 
 >>286 
 はい、それは了解しています。 
 >>284は黒石ゲームからオセロゲームへのアプローチのつもりでした。 
 >>287 
 お疲れ様です。 
 石数が４５の時任意のマスが埋まってる確率は45/64=0.703 
 中央４マスが埋まってる確率は0.703^4=0.244≒0.240473なので正解に近いでしょう。 
 石の発生確率２倍というのは仰るとおり黒/白/空き３値の盤面を想定してのことでした。 
 前出 b=(3^60)*(2^4)=6.78259E+29 に３値での発生確率を掛ければ
 概算の有効盤面数が割り出せるかと考えました。 
 乱数発生ですが、１マス３ビットで5/8=0.625の乱数は作れますが 
 乱数発生を３倍にしたにしては精度が低いですね。 
 ８ビット乱数(2^8=256)で５マス(3^5=243)を作るのが効率良いのかな？ 
 それより前出 b の式自体を変えたほうが良さそうですね。

 290 256 2006/02/24(金) 01:21:55 
 >>288 
 ＞0～60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で 
 ＞黒石ｎ個であるときの一様な試行が得られるよ。 
 よくわからなかったのですが、気になるのでもうちょっと詳しく教えてもらえますか？ 
 n個の１をばらまくほうが簡単そうですが、、、これではだめでしょうか？ 
 石数が14個くらいまでならオセロ盤で実際に10手以下の全探索をした盤面と比較できると思ったのですが、 
 今の方法だと石数が20個くらいまでの局面発生数はほとんどゼロにしかならなかったので、 
 一様な試行もできればいいなと思ってました。 
 >>289 
 石の発生確率を2倍にしてみました。（1億回試行） 
 乱数は、16個発生させて１マスあたり８ビット使い、 
 3で割った余りによって石有/空きを決めました。（遅い） 
 石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合 
 34----810312----59684----14553----0.07366----0.01796 
 35----1391979----114885----33877----0.08253----0.02434 
 36----2237616----207915----73092----0.09292----0.03267 
 37----3388840----353598----144910----0.10434----0.04276 
 38----4814954----558985----260877----0.11609----0.05418 
 39----6420635----830327----436917----0.12932----0.06805 
 40----8024164----1153300----673413----0.14373----0.08392 
 41----9401529----1500247----959482----0.15957----0.10206 
 42----10292005----1814899----1251133----0.17634----0.12156 
 43----10535592----2045606----1508248----0.19416----0.14316 
 44----10053709----2147383----1673889----0.21359----0.16649 
 45----8931797----2095020----1712559----0.23456----0.19174 
 46----7381673----1897347----1613363----0.25703----0.21856 
 47----5646603----1586556----1394172----0.28098----0.24690 
 48----4002903----1227091----1109087----0.30655----0.27707 
 49----2617925----874116----807797----0.33390----0.30856 
 50----1568075----568807----535577----0.36274----0.34155 
 51----861444----339229----324220----0.39379----0.37637 

 291 名無しさん＠５周年 sage 2006/02/24(金) 01:33:17 
 ん～、8ビット使って3の剰余で分ける…0が1と2より1/85だけ多い割合で出るから
 この数のシミュには向かないのでは？ 
 剰余にかかる時間 >> 乱数1個発生時間 だろうし、32ビットのまま行ってみては？

 292 256 2006/02/24(金) 01:49:06 
 今32ビットで、１億回試行中ですが、 
 さっき１０００万回で比較したら処理時間が2倍ちょっとになっちゃいました。

 293 名無しさん＠５周年 sage 2006/02/24(金) 02:07:57 
 お疲れ様です。 
 こっちは後発なので2）の方針でいこうと思います。（対称解は1つ扱い） 
 >>120が正確ではない（4×4だから）けど参考になる、と自分用リンク。

 294 256 2006/02/24(金) 02:26:11 
 ８ビットだと確かに精度が悪くなっているようです。 
 >>290と同じ範囲でもだいたい１‰以上の誤差が出てきてます。 
 ５０～５８石あたりでは数％も誤差がありました。 
 石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合 
 34----819799----59304----14654----0.07234----0.01788 
 35----1394987----113825----33552----0.08160----0.02405 
 36----2239644----206965----72737----0.09241----0.03248 
 37----3370795----349045----142996----0.10355----0.04242 
 38----4786955----553633----258442----0.11565----0.05399 
 39----6383626----825334----434910----0.12929----0.06813 
 40----7979411----1147014----670576----0.14375----0.08404 
 41----9371145----1492668----953573----0.15928----0.10176 
 42----10279583----1811139----1249041----0.17619----0.12151 
 43----10544519----2046793----1506964----0.19411----0.14291 
 44----10086594----2156237----1680278----0.21377----0.16659 
 45----8979083----2107749----1723086----0.23474----0.19190 
 46----7424025----1909494----1623887----0.25720----0.21873 
 47----5688036----1597364----1403921----0.28083----0.24682 
 48----4014876----1231054----1111899----0.30662----0.27694 
 49----2609923----870280----803689----0.33345----0.30794 
 50----1558130----564842----531864----0.36251----0.34135 
 51----847121----332688----317532----0.39273----0.37484 

 295 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:50:21 
 そろそろ難しくてついていけなくなりましたが、一生懸命レスさせていただきますｗ 
 僕はプログラムのプもかけません。もしかしたら勘違いしているのかもしれません。 
 空きの発生確率を　Og　。石の発生確率を　Ob　。（つまり　Og　+　Ob　＝　1　） 
 とする。 
 石数が　n　の時の局面発生率は、 
 64Pn * Og^(64-n) * Ob^n 
 です。 
 ---Og-----Ob 
 A--0.3329--0.6671 
 B--0.3330--0.6670 
 C--0.3331--0.6669 
 D--0.3332--0.6668 
 E--0.3333--0.6667 
 F--0.3334--0.6666 
 G--0.3335--0.6665 
 H--0.3336--0.6664 
 I--0.3337--0.6663 
 と石空き発生率A～Jに振り分ける。 
 例えばＥで石数が40の局面発生率は、 
 64P40 * 0.3333＾24 * 0.6667^40 
 = 0.080229095 

 296 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:51:00 
 続き 
 次にEを基準として次の表を作成する。 
 石数--A/Ｅ---B/Ｅ----C/Ｅ---D/Ｅ----E/Ｅ----F/Ｅ---G/Ｅ----H/Ｅ----I/Ｅ 
 3-----0.9310--0.9478--0.9649--0.9823--1.0000--1.0180--1.0363--1.0550--1.0740- 
 6-----0.9361--0.9517--0.9675--0.9836--1.0000--1.0166--1.0335--1.0507--1.0682- 
 9-----0.9412--0.9555--0.9701--0.9850--1.0000--1.0153--1.0308--1.0465--1.0624- 
 12----0.9463--0.9594--0.9728--0.9863--1.0000--1.0139--1.0280--1.0423--1.0567- 
 15----0.9514--0.9633--0.9754--0.9876--1.0000--1.0125--1.0252--1.0380--1.0510- 
 18----0.9565--0.9672--0.9780--0.9890--1.0000--1.0112--1.0224--1.0338--1.0454- 
 21----0.9617--0.9712--0.9807--0.9903--1.0000--1.0098--1.0197--1.0297--1.0397- 
 24----0.9669--0.9751--0.9833--0.9916--1.0000--1.0084--1.0169--1.0255--1.0341- 
 25----0.9722--0.9791--0.9860--0.9930--1.0000--1.0071--1.0142--1.0214--1.0286- 
 30----0.9774--0.9830--0.9887--0.9943--1.0000--1.0057--1.0115--1.0172--1.0230- 
 33----0.9827--0.9870--0.9913--0.9957--1.0000--1.0044--1.0087--1.0131--1.0175- 
 36----0.9880--0.9910--0.9940--0.9970--1.0000--1.0030--1.0060--1.0090--1.0120- 
 39----0.9934--0.9950--0.9967--0.9983--1.0000--1.0017--1.0033--1.0050--1.0066- 
 42----0.9988--0.9991--0.9994--0.9997--1.0000--1.0003--1.0006--1.0009--1.0012- 
 45----1.0042--1.0031--1.0021--1.0010--1.0000--0.9990--0.9979--0.9968--0.9958- 
 48----1.0096--1.0072--1.0048--1.0024--1.0000--0.9976--0.9952--0.9928--0.9904- 
 51----1.0151--1.0113--1.0075--1.0038--1.0000--0.9963--0.9925--0.9888--0.9851- 
 54----1.0206--1.0154--1.0102--1.0051--1.0000--0.9949--0.9898--0.9848--0.9798- 
 57----1.0261--1.0195--1.0130--1.0065--1.0000--0.9936--0.9872--0.9808--0.9745- 
 60----1.0317--1.0237--1.0157--1.0078--1.0000--0.9922--0.9845--0.9769--0.9693- 
 63----1.0373--1.0278--1.0185--1.0092--1.0000--0.9909--0.9819--0.9729--0.9641- 
 ※A/Eは　Ａ割るＥ　という意。少数5桁目を四捨五入しました。

 297 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:52:53 
 続き 
 つまりなにが言いたいかといいますと、石数42個らへんが一番コンピューター乱数の仕様誤差（？）
 の影響を受けにくく、石数４２個らへんから、上にも下にも影響を受けやすくなる。ということです。 
 と思います。

 299 293 sage 2006/02/24(金) 22:20:33 
 前言撤回。複数がやるにしても同じ結果に到達しなきゃ確証得られませんし 
 自分も3）方向で行きます。取りあえずは>>260と同じ物が出るかを確認し、 
 もう少し先の手まで進めて上から押さえるつもりです。

 300 284 sage 2006/02/24(金) 22:23:54 
 石の発生確立を２倍にするのは難しいようですね。 
 発生確率をRとし　0<R<1　とすると 
 64マスで石の個数 n となる確率は R^n*(1-R)^(64-n) となります。 
 （実際はこれに組み合わせ数を掛けないといけないが補正係数の算出には不要なので省略） 
 発生確率2/3と1/2の差を２値での個数ごとの結果に掛け合わせたらどうでしょうか。 
 石の個数nの時の補正係数は{(2/3)^n*(1-2/3)^(64-n)}/{(1/2)^n*(1-1/2)^(64-n)} 
 >>287のデータに補正係数を掛けると 
 石数--補正係数------局面発生数----埋まてる数----繋がてる数 
 40----5.906894946---6375920.125---954501.0612---610093.6445 
 41----11.81378989---7277979.773---1205774.465---832411.4496 
 42----23.62757978---7764684.289---1421860.496---1053341.134 
 43----47.25515957---7734062.946---1571895.628---1224664.715 
 44----94.51031913---7185808.584---1583425.887---1297248.64 
 45----189.0206383---6185322.346---1487403.403---1264926.111 
 46----378.0412765---4999973.923---1319364.055---1169281.668 
 石数0～64のすべてに補正係数を掛けて埋まってる数、繋がってる数のトータルを 
 出せれば石の発生確率2/3のときのデータになるはずです。 
 補正係数を掛けると局面発生数のピークも42～43になるようです。


 301 256 2006/02/25(土) 00:47:27 
 >>287 
 ＞局面発生数のピークは石数が３１・３２個の付近にありました。（約9.77%） 
 見直してて気づいたのですが、このようになるのはおかしいですね。 
 ０以上のの乱数を発生させてたようで常に０のビットが１箇所あります。 
 初歩的なミスですみません。石の発生確率が1/2のはやり直します。

 302 293 sage 2006/02/25(土) 01:03:02 
 >>301 
 あ、よかった。試しに真ん中4つが埋まってるプログラムを作ったら 
 10億回のテストで約2倍（発生回数も、埋まってる回数もなので割合はほぼ一緒） 
 だったのでちょいと不安だったのですよ。 
 ついでにちょいと訪ねてみます。繋がりチェックはどううやってます？

 303 293 sage 2006/02/25(土) 01:19:47 
 作った、ていうだけだと無意味なので一応結果。 
 1/2の割合で石を置いた場合、真ん中4つが埋まってるかどうかのチェック 
 石数-埋まる盤数/発生盤数-埋まる割合 
 26---1218966/-45486584---2.680% 
 27---1907062/-60649877---3.144% 
 28---2785026/-75805416---3.674% 
 29---3779166/-88870059---4.252% 
 30---4802368/-97776964---4.912% 
 31---5689156/100905325---5.638% 
 32---6306276/-97783629---6.449% 
 33---6517819/-88887714---7.333% 
 34---6304380/-75812328---8.316% 
 35---5693658/-60654246---9.387% 
 36---4801615/-45477307--10.558% 
 37---3783263/-31960276--11.837% 
 38---2779478/-21035323--13.213% 
 39---1907262/-12943552--14.735% 
 40---1217947/--7439856--16.371% 
 41----725024/--3994642--18.150% 
 42----400816/--1995761--20.083% 
 43----205262/---929754--22.077% 
 44-----97770/---401131--24.374% 
 45-----42627/---160050--26.634%  

 304 256 2006/02/25(土) 01:26:04 
 >>302 
 繋がりチェックは画像の領域塗りつぶしをするときのような再帰関数でやってます。 
 http://www.sm.rim.or.jp/~shishido/fill.html  

 310 256 sage 2006/02/25(土) 10:30:54 
 石の発生確率が1/2のをやり直しました。（1億回試行） 
 乱数はメルセンヌ・ツイスタを実装して使いました。 
 石数--局面発生数---埋数-----繋数----埋割合(%)--繋割合(%) 
 26-----3259193-----76287-----2155-----2.341-----0.066 
 27-----4590786----127177-----4935-----2.770-----0.107 
 28-----6062081----193814----10284-----3.197-----0.170 
 29-----7532330----280764----19920-----3.727-----0.264 
 30-----8780535----378290----35483-----4.308-----0.404 
 31-----9634737----476656----58036-----4.947-----0.602 
 32-----9935619----560162----88116-----5.638-----0.887 
 33-----9634648----620294---121801-----6.438-----1.264 
 34-----8783902----641192---156250-----7.300-----1.779 
 35-----7533047----620987---182592-----8.244-----2.424 
 36-----6066048----562048---196924-----9.265-----3.246 
 37-----4592260----477504---195003----10.398-----4.246 
 38-----3262028----379078---177332----11.621-----5.436 
 39-----2172546----281015---148555----12.935-----6.838 
 40-----1355366----195240---114113----14.405-----8.419 
 41------794734----127204----81540----16.006-----10.260 
 42------435867-----76380----52814----17.524-----12.117 
 43------222876-----43355----32009----19.453-----14.362 
 44------106482-----22713----17578----21.330-----16.508 
 45-------47634-----11304-----9285----23.731-----19.492 
 局面発生数のピークが３２に来ましたけど、 
 ０～６４のちょうど真ん中だからこれでいいですよね？

 317 305 sage 2006/02/25(土) 18:54:36 
 反復深化で黒石ゲーム全探索してみました。 
 黒石ゲーム 7手目 679,519,480パターン, 最大36分岐 
 オセロ 7手目 55,092パターン, 最大12分岐 
 オセロ 11手目 212,260,880パターン, 最大18分岐 
 はい。

 318 256 sage 2006/02/28(火) 10:31:21 
 黒石ゲームで石数が４～６４の範囲の一様な試行もやってみました。 
 データとかグラフを載せるとこが欲しいですね・・。

 321 256 sage 2006/02/28(火) 16:38:04 
 318のは今試行の数を増やしているところです。 
 終わってまとめたらアップします。

 326 284 sage 2006/03/01(水) 13:18:49 
 >>314->>315[[ありえない局面]]あたりを読んでて気が付いたが、 
 オセロの場合石を置くには最低挟める石と挟む為の石が必要なので、可能盤面は 
 「初期配置の中央４石を除き、全ての石は３個以上の列に含まれる」と言える。 
 なので>>314の下の図は、オセロでは有り得ないことが証明出来る。 
 （>>315の反例を一般化してみた） 
 黒石ゲームのルール、「隣８箇所のどこかに黒石がありさえすれば黒石が置ける」 
 というのを「２連続（以上）の黒石の延長上に置ける」とすればどうだろう？ 
 そうすれば、黒石ゲームでも同様のことが言えるようになる。

 327 284 sage 2006/03/01(水) 22:34:19 
 10万回ランダムに棋譜を発生させてみた。パスは１手としない（必ず60手以内で終わる） 
 平均手数の積は1.4E+53 
 標準偏差も出して確からしさも出そうかと思ったが１手99%として0.99^60=54%なのでやめた。 
 パス、連パスによるゲーム終了は10～16手目あたりと終盤に多く中盤は少ない。 
 手番---回数----最大--最小---総手数---Σ(総手数^2)--平均---標準偏差---パス--ゲーム終了 
 --1---100000-----4-----4-----400000----1600000----4.0000----0.0000------0-----0 
 --2---100000-----3-----3-----300000-----900000----3.0000----0.0000------0-----0 
 --3---100000-----5-----4-----466503----2198527----4.6650----0.8732------0-----0 
 --9---100000----15-----1-----755769----6092271----7.5577----1.6974-----72-----0 
 -10----99981----16-----1-----789548----6684874----7.8970----1.9073-----19----19 
 -11----99977----17-----1-----834035----7433175----8.3423----2.0992-----29-----4 
 -30----99952----24-----1----1202014---15378396---12.0259----2.8944------1-----0 
 -31----99951----25-----1----1185681---14989101---11.8626----2.8772------9-----1 
 -32----99951----23-----1----1192029---15133605---11.9261----2.9610------2-----0 
 -57----99950-----4-----1-----295764-----967274----2.9591----0.4936---2248-----1 
 -58----99948-----3-----1-----232387-----594419----2.3251----0.6372---4422-----2 
 -59----99916-----2-----1-----167192-----301744----1.6733----0.4472---9845----32 
 -60----98996-----1-----1------98996------98996----1.0000----0.0000--25951---920 

 328 271 sage 2006/03/02(木) 03:52:59 
 >>326 
 ＞黒石ゲームのルール、「隣８箇所のどこかに黒石がありさえすれば黒石が置ける」 
 ＞というのを「２連続（以上）の黒石の延長上に置ける」とすればどうだろう？ 
 それいいね。ずいぶん絞れました。 
 7手後の全棋譜数 
 オセロ / 黒石ゲーム / 黒石ゲーム２(>>326) 
 55,092 / 679,519,480 / 126,786,952 
 うーん。完全探索(反復深化)派としては、 
 黒石ゲームのようにゲームの一般化をしても 
 ノード数が増えて計算時間が増えるだけで、 
 (>>271式)の全棋譜数の上界設定に使うにしても 
 結局オセロの探索結果が12手まで求められるっていうことが 
 一番上界設定に寄与している気がする。。あたりまえか。 
 純粋な理論による上界設定には使えそうだけどね。