初級初手

hidesugar
記事: 6
登録日時: 2016年11月17日(木) 18:44

初級初手

投稿記事by hidesugar » 2016年11月19日(土) 03:45

長い、三行でまとめろ
・aradesh氏の1兆盤面シミュの1/10程度の性能のプログラムをC言語で作ったので公開する
・それを使って初級と中級を1億盤面シミュしたので3BV分布をまとめた
・初級の初手はR3C3がよさそうだと思う
(11/19(土)9:45修正:シュミレータの速度は10倍くらい負けてた)
(11/26(土)24:40修正:リンク[3]にPASSがかかっていて見れなかったのを修正)
========

先日のaradesh氏の上級1兆盤面における3BVの分布調査[1]に触発され、私もC言語で同様のシミュレータを作りました[2]。
[1]http://www.minesweeper.info/forum/viewtopic.php?f=15&t=1225
[2]http://ideone.com/Z6pSXV
プログラムにはバグが混入しないよう細心の注意を払いましたが、もしお気づきの点がありましたらご指摘ください。
「上級1億盤面シミュでaradesh氏による分布とほぼ一致すること」「『8x8爆弾1』の盤面で期待通りの3bv分布になること」の2つから、恐らく正しいであろうという推測を得ています。
なお上級1億盤面をシミュレーションするのに(環境にもよりますが)25分ほどかかります。これは[1]でaradesh氏が用いたものより10倍程度遅い速度であるようです。

上級に関してはデータの数で圧倒的に負けるので、とりあえず初級1億盤面、中級1億盤面を生成し、分布をまとめました[3]。
[3]https://notepad.pw/share/44fre2el(password:mine)
初級については2分半ほど、中級は10分弱ほどの実行時間がかかりました。
初級に関しては、回転一致/鏡像一致等を除いてユニークなものが189億パターン程度しか存在しないので、これ以上ランダム生成数を増やしても、必ずしも良い近似にはならないように思えます。また回転一致や鏡像一致を除かなくとも1500億程度しかパターンが存在しないので、上手くやれば数十時間程度プログラムを走らせることで完璧な3BV分布図の作成が可能であるように思えます。
(初級中級に関しても、3BVの詳細な分布の調査は寡聞にして知りません。先行研究が存在しましたらご教示ください)

閑話休題

さて、このプログラムを使って、初級における初手の最適化を図ります。
「初手で空白マスをひきあて、かつ、3BV2、かつ、ops1」というような盤面を目標とし、これが発生する確率が最も高いマスを探します。
これ以外の盤面については以下では一切考慮していないことにご注意ください。

まず基本的なことを確認しておきます。
マインスイーパにおいて地雷を配置する次の2つの方法は本質的に同じです
・ランダムに地雷を配置し、もし初手の位置に地雷が存在したときは初めから配置をやり直す
・初手以外のマスにランダムに地雷を配置する
(初手を決める毎に、ある爆弾の配置が選ばれる確率は等しいので)
このことから、任意のマスAと任意の事象Xに対して次の2つの割合が等しくなることが直ちに従います
・「ランダム生成した盤面のうちAが爆弾でないもの」に占める「Xが成立しているもの」の割合
・「Aを初手で開けた盤面」に占める「Xが成立しているもの」の割合

上述[2]のプログラムによる1億盤面シミュレートの際、64マスの各マス毎に「3BV2かつops1であるような盤面において、空白マスである回数」をカウントし、得られたものがこれです。
1843 1510 1985 2127 2098 2018 1503 1838
1490 889 1348 1405 1392 1391 892 1518
1980 1324 1718 1589 1593 1729 1369 2038
2090 1338 1631 1342 1354 1620 1390 2112
2139 1365 1616 1346 1407 1636 1374 2082
2055 1409 1762 1607 1639 1759 1368 1976
1545 936 1333 1358 1434 1374 892 1451
1834 1493 1923 2067 2108 1979 1473 1779
さきほど確認した事実から、「マスAを初手で開けたときに、初手0かつ3BV2かつops1」であるような割合は「『ランダム生成した盤面のうちAが爆弾でないもの』に占める『Aが0かつ3BV2かつops1』」と等しくなります。
ここで当然『ランダム生成した盤面のうちAが爆弾でないもの』は、Aによらず全体の54/64であることから、結局は上の表を比率としてそのまま利用できることがわかります。
(もちろん実際の値としては、これを(1億*54/64)で割ったものになる)

上の表を睨めば分かる通り、割合が高いマスは(対称性を除いた10マスのみに注目して)
R1C4>R1C3>R1C1>R3C3>R3C4>R1C2>R2C4>R2C3≒R4C4>>R2C2となります。
(左上を基点とするR1C1形式により呼称しています)
辺中央が最も確率は良いようですが、あまり盤面の隅の方を初手に選ぶと、2手目までのpathが長くなり時間を浪費する可能性があるので、そのような選択はできれば避けたいものです。
そういうわけで、できるだけ確率がよく、かつ盤面中央に近いマスとしてR3C3が良いように思えます。

このときの割合は0.00206% 程度、 約48000回に1回となります
(3BV1の盤面が出ないことを考慮する必要がありますが、1億盤面シミュで500程度だったので、誤差の範囲だとみなして無視しました)

========

補足1:
今回は条件にops1をつけましたが、これを除いた場合の表は次のようになります
2775 2243 2869 2975 2950 2905 2227 2783
2207 1321 1918 1908 1920 1995 1314 2230
2842 1898 2386 2134 2149 2434 1969 2904
2946 1849 2164 1756 1784 2175 1911 2954
3010 1898 2128 1743 1836 2187 1905 2947
2960 2022 2420 2131 2179 2433 1967 2895
2288 1383 1944 1871 1938 1993 1321 2162
2786 2231 2826 2917 2967 2868 2192 2711
R1C4>R1C3>R1C1>R3C3>R1C2>R3C4>R2C3>R2C4>R4C4>>R2C2


補足2:
「3BV2」という条件の下で「ops1」となる条件付き確率はおよそ7割になるようです
(1億盤面シミュで3432/4941という結果を得ました)

========
需要があれば(あるのか?)
・「3BV2かつops1」を「3BV3以下かつops1」に緩めるとどうなるか
・「『初手0』に占める『3BV2(or3以下)かつops1』の割合」が高いマスはどこか
も考えてみます。

hidesugar
記事: 6
登録日時: 2016年11月17日(木) 18:44

Re: 初級初手

投稿記事by hidesugar » 2016年11月27日(日) 02:22

長い、三行でまとめろ
・初級の盤面を全探索して3BVとopsの分布について調べたので公開する
・初級の初手はやっぱりR3C3がよさそうだと思う
・「初手R3C3が空白マスだったとき、3BV=2or3かつops=1である割合」は1/2500くらい
========

初級の盤面64C10≒1500億盤面を全探索し、3BVとopsについて調べました。
その結果から得られたことを以下いくらかまとめます。
生データが必要であれば下記を参照してください。
・プログラム(実行時間はおよそ28時間弱)
http://hidesugar.web.fc2.com/game/mine_beg_brute-force.txt
・出力ファイルに最低限の手を加えたもの
http://hidesugar.web.fc2.com/game/mine_beg_3bv_distribution.txt

以下では3BVが1である盤面を除外していません。
全体に占める割合が1/200000程度と非常に小さく、除外しなくてもほとんど影響がないためです。
数値は有効数字3桁又は小数第3位まで表し、それ未満を四捨五入しています。

●3BVの分布
mean 17.203 sd 5.480 median 17 mode 16
1:0.000509%(約1/196000)
2:0.00493%(約1/20300)
3:0.0250%(約1/4000)
4:0.0875%(約1/1140)

48:0.0000172%(約1/5820000)←最も少ない
49:0.000798%(約1/125000)
51:0.0000457%(約1/2190000)
54:0.000172%(約1/582000)

●opsの分布
mean 2.668 sd 0.923 median 3 mode 3 max 8
0:0.000172%(約1/582000)(ops=0であることと3BV=54であることは同値)
1:10.200%
2:34.149%
3:37.481%
4:15.188%
5:2.753%(約1/36)
6:0.222%(約1/450)
7:0.00715%(約1/14000)
8:0.000110%(約1/911000)

●低3BVでのopsの割合
3BV=2のとき ops=1:69.1% ops=2:30.9%
3BV=3のとき ops=1:49.0% ops=2:43.9% ops=3:7.0%
3BV=4のとき ops=1:36.3% ops=2:47.9% ops=3:14.7% ops=4:1.1%


●各マスを初手とした時の各事象の発生割合
以下で何度も登場する4x4の表は、盤面左上1/4を表します

・初手で空白を引く割合
これは手計算できる
角…60C10/63C10=53*52*51/(63*62*61)≒59.0%
辺…58C10/63C10=53*52*51*50*49/(63*62*61*60*59)≒40.8%
他…55C10/63C10=53*52*51*50*49*48*47*46/(63*62*61*60*59*58*57*56)≒22.9%
シミュレーション結果でも同じ値になっていることを確認済み

・「初手が空白、かつ、3BV=2、かつ、ops=1」となる場合の数
2730139  2248632  2998868  3182529
2248632  1374182  2044058  2081294
2998868  2044058  2618174  2425353
3182529  2081294  2425353  2032391
R1C4>R1C3>R1C1>R3C3>R3C4>R1C2>R2C4>R2C3>R4C4>>R2C2
・初手が空白だった時、それが「3BV=2、かつ、ops=1」であるような割合
36.212  43.094  57.472  60.992
43.094  46.983  69.886  71.159
57.472  69.886  89.514  82.922
60.992  71.159  82.922  69.487 (/100万)
R3C3>R3C4>>R2C4>R2C3>R4C4>>R1C4>R1C3>>R2C2>R1C2>R1C1

・「初手が空白、かつ、3BV=2or3、かつ、ops=1」となる場合の数
12097280  9936830  13237487  14140024
9936830   6100817   9065763   9447618
13237487  9065763  11903812  11455962
14140024  9447618  11455962  10117492
R1C4>R1C3>R1C1>R3C3>R3C4>R4C4>>R1C2>R2C4>R2C3>>R2C2
・初手が空白だった時、それが「3BV=2or3、かつ、ops=1」であるような割合
160.454  190.436  253.691  270.988
190.436  208.585  309.955  323.010
253.691  309.955  406.987  391.675
270.988  323.010  391.675  345.913 (/100万)
R3C3>R3C4>>R4C4>R2C4>R2C3>>R1C4>R1C3>>R2C2>R1C2>>R1C1

同様にopsの条件を外して「初手が空白だった時、それが3BV=2(または2or3)であるような割合」もR3C3が最も高くなる
========

「人間が反応する以上、『初手で空白を引いた条件の下で、それがいい盤面である割合』が高いマスを押すのが理にかなっているだろう」と考えて調査を行いました。
冒頭にも述べた通り、「初手R3C3が空白マスだったとき、3BV=2or3かつops=1である割合」は約1/2460、「3BV=2かつops=1」なら約1/11200となり、個人的には意外と高い割合だと感じました。
「初手が空白以外ならリセ(所要時間1秒)、空白なら3クリ目まで解く(所要時間3秒)」と仮定すると、3bv=2,ops=1の盤面を引くまで20時間程度F2連打をすればよい計算になります。

hidesugar
記事: 6
登録日時: 2016年11月17日(木) 18:44

Re: 初級初手

投稿記事by hidesugar » 2017年11月22日(水) 23:47

長い、三行でまとめろ
・初級9x9の3BV1の盤面について調べた
・基本的な傾向は8x8の場合と同じ
・初手空白保証の場合、はやり初手R3C3が最も3BV1になる確率が高い
========

プログラムはこちら(実行時間は9x9で6分程度)
http://hidesugar.web.fc2.com/game/mines ... 9_3BV1.cpp

以下で何度も登場する5x5の表は、盤面左上1/4を表します

☆9x9の盤面において3BV1が1である盤面の数:29153308(全体0.00155%・1/64400)

○各マスが空白であるような3BV1の盤面の個数
18897794 15772862 19476723 18990474 19186452
15772862 10318663 14260414 12333780 12638346
19476723 14260414 16860906 13731102 13614757
18990474 12333780 13731102 10064691 9933326
19186452 12638346 13614757 9933326 9672404
R1C3>R1C5>R1C4>R1C1>>R1C2>R2C3>R3C4>R3C5>R2C5>R2C4>>他
この各マスの値を、各マスが空白であるような盤面の数(角C(77,10),端C(75,10),それ以外C(72,10))で割ることで、
初手空白保証の下で、各マスを初手とした時に3BV1となる確率が得られる
17.226 19.027 23.496 22.909 23.146
19.027 19.243 26.594 23.001 23.569
23.496 26.594 31.444 25.607 25.390
22.909 23.001 25.607 18.769 18.524
23.146 23.569 25.390 18.524 18.038 (/100万)
R3C3>>R2C3>R3C4>R3C5>>R2C5>R1C3>R1C5>R2C4>R1C4>>他
最も確率の高いR3C3では約1/31800となる。

○各マスが爆弾であるような3BV1の盤面の個数
10255514 4151480 4669346 4398777 5017328
4151480 537570 1182719 1260576 1489079
4669346 1182719 3561969 3341640 4143273
4398777 1260576 3341640 3769049 4660109
5017328 1489079 4143273 4660109 5761212
各マスの値を3BV1である盤面の総数から引いた後、C(80,10)で割ることで、
初手空白保証ではないときの、各マスを初手とした時に3BV1となる確率が得られる
11.478 15.185 14.870 15.035 14.659
15.185 17.380 16.988 16.941 16.802
14.870 16.988 15.543 15.677 15.190
15.035 16.941 15.677 15.417 14.876
14.659 16.802 15.190 14.876 14.207 (/100万)
R2C2>R2C3>R2C4>R2C5>>R3C4>R3C3>R4C4>他

●考察
以上から次のことが分かります
・初手空白保証なら初手R3C3が3BV1になる確率が最も高い
・初手空白保証でないなら初手R2C2が以下同文
これらの理由は次のように推測することができます
"盤面が十分に大きければ"、「壁から1マス離れた位置に地雷があり、それと壁の間がIslsになる」というのが、3BVに寄与するもっとも大きな要因となります。
初手空白保証でR3C3を選択することで、R2及びC2のマスを計5マス分も爆弾配置対象から除外することができ、3BVが高くなる可能性を排除しています。
参考として以下に8x8の表を付しておきます

☆3BV1である盤面の数:771160(全体の0.000509%・1/196000)
○各マスが空白であるような3BV1の盤面の個数
429889 355096 473561 498824
355096 215490 321622 316147
473561 321622 396298 346047
498824 316147 346047 269866
確率
5.702 6.805 9.076 9.560
6.805 7.368 10.996 10.809
9.076 10.996 13.549 11.831
9.560 10.809 11.831 9.227 (/100万)
R3C3>>R3C4>R2C3>R2C4>>R1C4>R4C4>>>R1C2>>R1C1
○各マスが爆弾であるような3BV1の盤面の個数
341271 172715 154309 125957
172715 37476 46305 44475
154309 46305 113286 109975
125957 44475 109975 128395
確率
3.364 4.682 4.826 5.048
4.682 5.741 5.672 5.686
4.826 5.672 5.147 5.173
5.048 5.686 5.173 5.029 (/100万)


“考察” へ戻る

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[0人]