黒石ゲーム
ルールは
用語集参照。
作りだされる局面の形がオセロゲームの局面の形を満足するので、
オセロゲームの局面数の上界を求める手がかりになるとされる。
276 よんけた ◆Tl2oC4lIZ2 sage 2006/02/22(水) 14:30:18
>>262
>>>259みたいな局面を実際に並べて作れるかは疑問に感じてます。
このことに関してちょっと考えてみました。
ランダムに作った盤面の総通りaは、
a = 3^64 = 4.23912E+28
これはオセロの総棋譜数の予測値より格段に少ない値です。
だから、ランダムに作った盤面は棋譜で表現できるんじゃないかと。
しかしランダムで作った盤面の中には囲碁みたいに離れた石が存在するような盤面もありますし、
試合開始前からある真ん中の四つの石がない盤面もあります(3^60で済みますが)。
つまり置石の形からしてオセロでは表現できない盤面があります。
またさらに、存在してそうな形をしていてもオセロ棋譜で表現できないものもあります。
++++++++
++++++++
++++++++
+++○●+++
+++●○●++
++++++++
++++++++
++++++++とか。
すみません当たり前ですね。
278 名無しさん@5周年 sage 2006/02/22(水) 23:17:26
>>276
60展開後の局面数がもうめちゃくちゃ多く見積もって < 2^64 = 10^19 だから
かなり縮退してそうだね。
あと奇遇性とか連結性(離れ小島は発生しない)とかで絞ったらどうかな。
連結性でいえば、
2x2 の黒石で始まって隣8箇所のどこかに黒石がありさえすれば
黒石が置けるようなゲームを考えると、
必ずそのゲームの棋譜数(局面数)はオセロのそれらを下回るし
解析もやりやすいと思う。
まあオセロより解析が簡単と言えど
その局面数を数え上げるのも結構むつかしいんだが…。
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 名無しさん@5周年 2006/02/23(木) 13:01:49
>>282
ランダムに作った盤面 a=3^64=3.43368E+30 通り
そのうち中央4マスは空にならないとすると b=(3^60)*(2^4)=6.78259E+29
確率はb/a=(2^4)/(3^4)=1/5.06≒19.75%
>石有り/空きの2値のみの局面をランダムに発生させて
出来るなら石有りの発生確率を空きの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のプログラムを改造して石の数毎に分布を調べてみました。
(待つのがめんどくさかったので1億回の試行。ちょっと精度は落ちますが。)
局面発生数のピークは石数が31・32個の付近にありました。(約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倍の確率にしたらどうだろう?
2倍の確率ってのは黒/白/空きの3値の盤面から石有/空きの2値の盤面に変換すると
石の存在確率が空きの2倍であるといったような事からですか?
上の表で石の存在割合が空きの2倍である42石や43石(64*2/3≒42.667)の辺りを見ると、
0.183119~(19.75)~0.203243となってますが、、。
2値の盤面は32ビットの乱数を2個発生させてつなげて作ってました。
各マス毎に乱数を発生させると発生確率を変えられそうですがちょと遅くなりそうな気が。
何かうまい方法はありませんか?
288 名無しさん@5周年 2006/02/23(木) 21:49:53
>局面発生数のピークは石数が31・32個の付近にありました
中心極限定理ってことかな。
0~60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で
黒石n個であるときの一様な試行が得られるよ。
289 284 sage 2006/02/23(木) 22:23:37
>>286
はい、それは了解しています。
>>284は黒石ゲームからオセロゲームへのアプローチのつもりでした。
>>287
お疲れ様です。
石数が45の時任意のマスが埋まってる確率は45/64=0.703
中央4マスが埋まってる確率は0.703^4=0.244≒0.240473なので正解に近いでしょう。
石の発生確率2倍というのは仰るとおり黒/白/空き3値の盤面を想定してのことでした。
前出 b=(3^60)*(2^4)=6.78259E+29 に3値での発生確率を掛ければ
概算の有効盤面数が割り出せるかと考えました。
乱数発生ですが、1マス3ビットで5/8=0.625の乱数は作れますが
乱数発生を3倍にしたにしては精度が低いですね。
8ビット乱数(2^8=256)で5マス(3^5=243)を作るのが効率良いのかな?
それより前出 b の式自体を変えたほうが良さそうですね。
290 256 2006/02/24(金) 01:21:55
>>288
>0~60!/n!-1の乱数を発生させて組み合わせのハッシュの逆関数にかける方法で
>黒石n個であるときの一様な試行が得られるよ。
よくわからなかったのですが、気になるのでもうちょっと詳しく教えてもらえますか?
n個の1をばらまくほうが簡単そうですが、、、これではだめでしょうか?
石数が14個くらいまでならオセロ盤で実際に10手以下の全探索をした盤面と比較できると思ったのですが、
今の方法だと石数が20個くらいまでの局面発生数はほとんどゼロにしかならなかったので、
一様な試行もできればいいなと思ってました。
>>289
石の発生確率を2倍にしてみました。(1億回試行)
乱数は、16個発生させて1マスあたり8ビット使い、
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 名無しさん@5周年 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ビットで、1億回試行中ですが、
さっき1000万回で比較したら処理時間が2倍ちょっとになっちゃいました。
293 名無しさん@5周年 sage 2006/02/24(金) 02:07:57
お疲れ様です。
こっちは後発なので2)の方針でいこうと思います。(対称解は1つ扱い)
>>120が正確ではない(4×4だから)けど参考になる、と自分用リンク。
294 256 2006/02/24(金) 02:26:11
8ビットだと確かに精度が悪くなっているようです。
>>290と同じ範囲でもだいたい1‰以上の誤差が出てきてます。
50~58石あたりでは数%も誤差がありました。
石数--局面発生数--埋まてる数--繋がてる数--埋まてる割合--繋がてる割合
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
そろそろ難しくてついていけなくなりましたが、一生懸命レスさせていただきますw
僕はプログラムのプもかけません。もしかしたら勘違いしているのかもしれません。
空きの発生確率を 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に振り分ける。
例えばEで石数が40の局面発生率は、
64P40 * 0.3333^24 * 0.6667^40
= 0.080229095
296 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:51:00
続き
次にEを基準として次の表を作成する。
石数--A/E---B/E----C/E---D/E----E/E----F/E---G/E----H/E----I/E
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は A割るE という意。少数5桁目を四捨五入しました。
297 よんけた ◆Tl2oC4lIZ2 sage 2006/02/24(金) 13:52:53
続き
つまりなにが言いたいかといいますと、石数42個らへんが一番コンピューター乱数の仕様誤差(?)
の影響を受けにくく、石数42個らへんから、上にも下にも影響を受けやすくなる。ということです。
と思います。
299 293 sage 2006/02/24(金) 22:20:33
前言撤回。複数がやるにしても同じ結果に到達しなきゃ確証得られませんし
自分も3)方向で行きます。取りあえずは>>260と同じ物が出るかを確認し、
もう少し先の手まで進めて上から押さえるつもりです。
300 284 sage 2006/02/24(金) 22:23:54
石の発生確立を2倍にするのは難しいようですね。
発生確率をRとし 0<R<1 とすると
64マスで石の個数 n となる確率は R^n*(1-R)^(64-n) となります。
(実際はこれに組み合わせ数を掛けないといけないが補正係数の算出には不要なので省略)
発生確率2/3と1/2の差を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
>局面発生数のピークは石数が31・32個の付近にありました。(約9.77%)
見直してて気づいたのですが、このようになるのはおかしいですね。
0以上のの乱数を発生させてたようで常に0のビットが1箇所あります。
初歩的なミスですみません。石の発生確率が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
局面発生数のピークが32に来ましたけど、
0~64のちょうど真ん中だからこれでいいですよね?
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
黒石ゲームで石数が4~64の範囲の一様な試行もやってみました。
データとかグラフを載せるとこが欲しいですね・・。
321 256 sage 2006/02/28(火) 16:38:04
318のは今試行の数を増やしているところです。
終わってまとめたらアップします。
326 284 sage 2006/03/01(水) 13:18:49
>>314->>315[[ありえない局面]]あたりを読んでて気が付いたが、
オセロの場合石を置くには最低挟める石と挟む為の石が必要なので、可能盤面は
「初期配置の中央4石を除き、全ての石は3個以上の列に含まれる」と言える。
なので>>314の下の図は、オセロでは有り得ないことが証明出来る。
(>>315の反例を一般化してみた)
黒石ゲームのルール、「隣8箇所のどこかに黒石がありさえすれば黒石が置ける」
というのを「2連続(以上)の黒石の延長上に置ける」とすればどうだろう?
そうすれば、黒石ゲームでも同様のことが言えるようになる。
327 284 sage 2006/03/01(水) 22:34:19
10万回ランダムに棋譜を発生させてみた。パスは1手としない(必ず60手以内で終わる)
平均手数の積は1.4E+53
標準偏差も出して確からしさも出そうかと思ったが1手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
>黒石ゲームのルール、「隣8箇所のどこかに黒石がありさえすれば黒石が置ける」
>というのを「2連続(以上)の黒石の延長上に置ける」とすればどうだろう?
それいいね。ずいぶん絞れました。
7手後の全棋譜数
オセロ / 黒石ゲーム / 黒石ゲーム2(>>326)
55,092 / 679,519,480 / 126,786,952
うーん。完全探索(反復深化)派としては、
黒石ゲームのようにゲームの一般化をしても
ノード数が増えて計算時間が増えるだけで、
(>>271式)の全棋譜数の上界設定に使うにしても
結局オセロの探索結果が12手まで求められるっていうことが
一番上界設定に寄与している気がする。。あたりまえか。
純粋な理論による上界設定には使えそうだけどね。
最終更新:2006年03月02日 15:41