07/05/09 10:34:57
詰みになる状況を見つけたら爆弾の位置を変更すればいいのかね。
3:1
07/05/09 10:40:58
>>2
おぉ！なるほど！それは考えてなかった・・・。
ゲーム開始の時点で詰み（←どうしようもない2択状態とかのことだよね）にならないような爆弾の配置をすることで頭がいっぱいだったよ。
とりあえず、どういう条件で詰みになるのか、紙と鉛筆で試行錯誤中・・・
4:デフォルトの名無しさん
07/05/09 10:41:19
地雷をひとつも入れなければいい。
その程度のこと考えるまでもないだろ。
5:1
07/05/09 10:42:14
>>4
できれば地雷をいれてやりたいですorz
6:デフォルトの名無しさん
07/05/09 11:20:01
昔、おれ作ったよ。クリックも自動でやっくれる奴。たまにクリックミスするけど、上級で数秒くらい。
今やったら上級で最高2秒で解いた。
7:1
07/05/09 11:34:21
>>6
もしかしてYouTubeとかでよく見かける、自動でマインスイーパを解くやつの作者の人？
2秒っていうのは見たことないので、もし動画を作れる環境があったら、うｐお願いします。
あれって、もし完全に２択の状況になった場合は、ランダムに選んでるわけじゃないの？
いちおう動画へのリンク載せときます↓
人間がやってるように見えなくもないけど、たぶん自動の38秒
URLﾘﾝｸ(www.youtube.com)
どう見ても自動だけど24秒！
URLﾘﾝｸ(www.youtube.com)
8:デフォルトの名無しさん
07/05/09 12:02:33
違う。おれのはハッカーらしく、もっとクールだ。
9:1
07/05/09 12:21:25
と言いますと？？？
10:デフォルトの名無しさん
07/05/09 14:13:36
URLﾘﾝｸ(www.geocities.jp)
11:1
07/05/09 14:49:17
>>10
何気におもしろい！アシスト機能とか楽しく遊ばせてもらいました。
自動でクリアさせたらいきなり1秒でクリアしちゃって、オイラの最高記録が強制的に消えちゃったのがちょっと悲しかったけど、まあ自分のは大した記録じゃなかったから、まあいーや。
ちなみに今考えているマインスイーパは、最初から最後まで100％論理のみでクリアできるようなマインスイーパなんだけど、それって不可能なのかなぁ？
12:デフォルトの名無しさん
07/05/09 14:58:03
昔どこかのサイトで、マインスイーパもどきで
ちょっとルールが変わってるヤツを見たことがあるな
金を消費して、爆弾があるかどうか分からないところも解けてしまう。但し乱用すると金欠に。
13:1
07/05/09 15:28:32
>>12
そういうのもあるんだｗ
金の他にも、例えばＨＰ（ヒットポイント）をつけて、地雷をふんだらダメージを受ける、みたいなのもありかもね。
そうすると、少なくとも、２択に陥って失敗して全てが水の泡になって泣きそうになる状況だけはなくなるし。
14:デフォルトの名無しさん
07/05/09 17:24:07
>>10
運でしか解けないパターンは限られてるから、
爆弾をランダムに配置したあと、そのパターンがあったら
いくつか爆弾を移動してやればいいんでないかな
15:デフォルトの名無しさん
07/05/09 17:25:35
ああアンカーずれた
>>11だった
16:デフォルトの名無しさん
07/05/09 17:36:45
>>1
とりあえず、まず物を作るんだｗ
17:1
07/05/09 17:38:09
>>14
レスどうも。確かに一度ランダムで並べてしまうってのも１つの手だね。
それで、運でしか解けないパターンってのをどうやって検出するかって部分が、やっぱり難しい・・・。
どういう地雷の配置だと詰まるのかを考えるのは難しそうだから、まずは逆にどういう地雷（または数字）の配置だと詰まらず先に進めるのかでも考えてみようかな？
18:1
07/05/09 17:42:45
>>16
物っすかｗｗｗ
まず目的物のアルゴリズムがわかってから実装かなぁって思ってたんだけど、どうしよう？
作るとしたら言語は何がいいかな。
WinのプログラムはC言語でSDKしかまともにやったことなくて・・・。
C#をちょっと触った感触では、色々なことが楽にできそうって印象はあったけど、.NET必須？？
もしくはJavaで作ったらWindows以外のプラットフォームでも動くかなぁとか思ったり。
19:デフォルトの名無しさん
07/05/09 17:59:10
>18
そういうのは、自分がやりやすい環境でやるのが一番
SDKの経験がそれなりにあるなら、SDKでやるよろし
C#が楽そうなら、C#でやるよろし
いきなり不慣れな環境で始めると、作るより先に
その環境に慣れることから始まるから時間掛かりすぎる
20:デフォルトの名無しさん
07/05/09 18:46:09
詰みにならない状況とは何か、を洗ってみるのが重要だと思うなあ。
21:1
07/05/09 19:52:19
>>19
たしかに・・・。
とりあえず後でどうするかはわからないけど、HTML+JavaScriptで簡単なテストプログラムを作ってみてます。
右クリックとかできないのがツライけど。
22:1
07/05/09 19:55:52
>>20
詰みにならない状況ですか。
今のところ、確実に左クリックで開くことができるマスか確実に右クリックで旗を立てられるマスが一つもない状況のことかと思っとります。
でも、よく考えたら、ゲーム開始したばかりの状態はある意味で詰みだよなぁ。
確かにきちんと考えてみる必要がありそうかも。
23:デフォルトの名無しさん
07/05/09 19:58:41
>>22
＞でも、よく考えたら、ゲーム開始したばかりの状態はある意味で詰みだよなぁ。
それはどこか自動的に開くようにしたらいいと思う。
あるいは、最初クリックした地点に地雷があったら、
それを詰みにならないところに移動させるとか。
24:デフォルトの名無しさん
07/05/09 19:59:57
待てよ？ 例えば最初クリックした地点が数字だった場合って、これも詰みだよな？
開ける地点によって詰みか詰みじゃないかが変わってくるのか。
25:デフォルトの名無しさん
07/05/09 20:12:48
付属のマインスイーパって絶対に一発目は地雷にはならないよね？
だから、1クリック目で問題が決まってると思ってたんだけど。
26:デフォルトの名無しさん
07/05/09 20:14:29
“必ず解ける”とは全く別の事になるけど、
・確実に安全だけど開いていない場所
・確実に地雷だけど旗を立てていない場所
・地雷があるかどうか分からないのに旗が立っている場所
地雷を踏んだ時にこれらの数に応じて、時間にペナルティを与えるとか。
27:デフォルトの名無しさん
07/05/09 20:29:43
つまり、最初にクリックした地点の周りには地雷がないようにする、ということか。
28:1
07/05/09 21:37:56
>>23-25
Windows標準のやつみたいに、一発目は絶対に地雷にならないようなものにしたいとこだね
>>26
それも実装としては面白いかもしれない。
方針そのものを変えるって点では、>>12とか>>13に近いものがあるかな。
>>27
そういうことになるかも。
たぶん、最初にクリックした場所の隣8マスの中に１つでも爆弾があると、いきなり詰みになるっぽい。
29:デフォルトの名無しさん
07/05/09 22:04:51
地雷で囲まれた部分ができてると勘に頼る必要が出るんだっけ？
30:デフォルトの名無しさん
07/05/09 22:12:03
○○○○○
○●●●○
○●○●○
○●●●○ ●：地雷
○○○○○ ○：床
となってたら、ここが最後まで残れば、
地雷の数から真ん中に地雷があるかどうかが分かる。
でも、これが端っこにあると・・・
┌──
│●●●○
│●○●○
│●●●○ ●：地雷
│○○○○ ○：床
右上の４箇所のどこに床があるのか分からなくなる。
単に囲まれたってだけじゃダメっぽいな。
31:デフォルトの名無しさん
07/05/09 22:12:34
右上じゃないや、左上。
32:デフォルトの名無しさん
07/05/09 22:22:40
つまり、地雷の残り個数が０なら、
数字からだけでは地雷があるかどうか分からない箇所の全てに
地雷がないということが分かる。
残り個数が０でない場合は、未定箇所の個数がその個数と等しければ、
全て地雷だということが分かる。
残り個数が０でなく、未定箇所の個数がその個数と等しくなければ、詰み。
33:1
07/05/09 22:25:17
>>30
何か興味深いけど、ちょっと意味がわからんとです。
実際にその地雷配置でゲームを開始して、あるところまで行ったとして、どれが確定済みで、どれが確定していないのかだけ、もうちょい詳しく書いてもらえるとありがたいかも。
34:デフォルトの名無しさん
07/05/09 22:27:11
>>26 とは違うペナルティ案として、時間がかかるが(数秒程度)
指定したマスに地雷があるかどうか調べる機能をつけるのも
手っ取り早くていいかも。
35:デフォルトの名無しさん
07/05/09 22:31:54
①②③②①
②♪♪♪②
③♪◇♪③ ①②③：周りの地雷の数（１、２、３）
②♪♪♪② ♪：地雷があると確定した箇所
①②③②① ◇：印のついてないブロック
という状況になった場合、
地雷の総数が８個ということであれば、真ん中に地雷がないと分かり、
地雷の総数が９個ということであれば、真ん中に地雷があると分かる。
①②③②①○①②③②①
②♪♪♪②○②♪♪♪②
③♪◇♪③○③♪◇♪③
②♪♪♪②○②♪♪♪②
①②③②①○①②③②①
という状況になった場合、
地雷の総数が１６個ということであれば、両方の真ん中に地雷がないと分かり、
地雷の総数が１８個ということであれば、両方の真ん中に地雷があると分かり、
地雷の総数が１７個ということであれば、どっちの真ん中に地雷があるのかが分からなくて詰み。
36:デフォルトの名無しさん
07/05/09 22:41:14
プログラムで実際にといてみて
解けなければ再出題すればいいじゃん。
今時のマシンならあっという間に解けるんだし。
37:1
07/05/09 22:45:37
>>34
たしかにそのほうが実装しやすそう。
ペナルティ系の実装はペナルティ系で、まとめておくのもいいかも。
>>35
な、なるほど・・・！
地雷の総数（or残数）から割り出せる場合は詰みにならないって、そういうことか。
ちょっとこれはあまりに混乱しそうだから、まずは地雷の総数は考慮しない場合のアルゴリズムを考えて、後から地雷の総数も考慮するように修正するほうがわかりやすいかも。
貴重な考察ｔｈｘ！
38:1
07/05/09 22:49:26
>>36
お、また新しい意見出ましたね。
何だかラスベガス法を彷彿させるアルゴリズムだけど、やってみる価値はあるかも。
今はまだ、どうやったらプログラムで解けるかってのも考え中っすorz
39:1
07/05/09 23:20:07
かなりいい加減ですが、ひとまずマインスイーパっぽくは見えるバージョンです。
URLﾘﾝｸ(2sen.dip.jp:81)
練習も兼ねて、実験用のプロトタイプっぽくなればいいなぁと思ってたけど、ロジックがごちゃごちゃになりすぎてダメかもｗ
ちなみにIEだと大丈夫だけど、Fxだと微妙に選択範囲が出てきてしまう。
たしかgetSelectionとか使ってごにょごにょやるんだった気がするけど失念orz（誰か教えてください）
操作方法
・クリック＝Win版の普通のクリックの役割＋「左右同時クリック」の役割を兼用
・Ctrl＋クリック＝Win版の右クリックの役割＋「左右同時クリック」の役割を兼用
40:デフォルトの名無しさん
07/05/09 23:55:45
おお、ちゃんとマインスイーパしとるｗ
41:デフォルトの名無しさん
07/05/10 00:00:16
>>1 がちゃんとプログラムをアップしてきたのにビックリした age
42:1
07/05/10 11:27:15
>>40-41
どうもです。
まあひとまず最初の一歩って感じだけど、やっぱJavaScriptだと動作がもっさりしてるんで、C言語で高速軽快なのを作りたい気持ちが高まったかも。
えーと、それで今、ある時点で詰まらずに地雷か数字を確定することができる必要十分条件みたいのを模索してます。
>>10の作者の人に教えてもらえば一発なんですが・・・。
「縁の部分に１・２・１があったら２つの１の横に地雷を置ける」とか具体例を挙げていってもキリがないので、もっと一般的、法則的なものが欲しいとこです。
43:1
07/05/10 11:39:55
一人で考えてても埒があかないので、ちょっとしばらく独り言を書き込むんで、つっこみがあったらよろしくお願いします。
まず、ある数字のマス１つだけに着目したとすると、確定できるものといったら、
そのマスの周りでまだ開いてないマスの数 ＝ 表示されてる数字から、そのマスの周りで確定した地雷（＝旗）の数を引いたもの ・・・・・・（１）
であるときに、その「まだ開いていないマス」ってのが、全部地雷であることが確定するわけです。
何か当たり前のこと言ってるだけなのに、言葉にすると妙に長くなるなぁ・・・。
44:1
07/05/10 11:43:52
たぶんマインスイーパをある程度やったことがある人なら、（１）の右辺にある
「表示されてる数字から、そのマスの周りで確定した地雷（＝旗）の数を引いたもの」
というのが、プレイ中つねに念頭におくべき重要な数であるってのはある意味常識かな？と思ったり思わなかったり。
何かこの数字に名前つけてやろうかな？
どっかのマインスイーパ解説サイトには「実質的な値」って言い方してた気がするので、とりあえず「実質値」とでも呼んでおくか。
45:1
07/05/10 11:45:09
そうすると、
まだ開いてないマスの数 ＝ 実質値 ・・・・・・（２）
であるならば、まだ開いてないマスは全部地雷だよ。ってことで、ちょっとすっきりかな。
46:1
07/05/10 11:48:25
さて次はもっと重要な、２つの隣接するマスに表示された数字・・・じゃなかった、２つの「実質値」の関係から、確定できるものを考える。
えーと、どうやって考えたらいいんだろう？
とりあえず２つのマスを X 、Y とおいて、実は今まで自分なりに考えてきた中で、このXとYの「差」が、確定できる地雷の秘密を握っていると、感じてきております。
47:1
07/05/10 11:53:00
うーん・・・例えば
？？？？
確②①確
確確確確
ってなってたら
★？？☆
確②①確
確確確確
★は地雷、☆は数字になるはず。
ちなみに、①とか②は実質値なので、実際に表示されている値とは違い、「確」の中の地雷の数を差し引いたものを表す。念のため確認。
48:1
07/05/10 11:55:28
何か混乱してきた・・・
やっぱ X と Y でいこう
？？？？
確 Ｘ Ｙ.確
確確確確
ってなってたとしたら、どうなるんだろう？
X - Y の数字は、えーと、うーんと・・・
49:1
07/05/10 12:00:01
こういう風に考えてみようかな？
？？？？
？ Ｘ Ｙ.？
？？？？
あれだ、たぶん。
ＸとＹが共有しているマスが４マスあって、共有していないマスがＸ、Ｙのそれぞれの側に３マスずつある。
で、Ｘ－Ｙの値が共有している部分の数と何か関係していたら、確定できるものがでてきそう？
50:1
07/05/10 12:02:50
意味がわからんので、とりあえず数字を入れるかな
？？？？
？②①？
？？？？
うーん・・・これだと何も確定しないから、いくつかすでに確定しているものが必要なのか
51:1
07/05/10 12:08:14
つーか、よく考えたらこうだわな
？？？？
確②①？
確確確？
↓
★？？☆
確②①☆
確確確☆
そういやこのパターン、実践でよく使うわな。
52:1
07/05/10 12:09:56
連続投稿で規制くらったので、この辺にしときます。
すいませんでした。
煮詰まってきたし、もうちょい考えをまとめてから、出直してきますorz
53:1
07/05/10 12:39:06
重大なことに気付いたので、再び失敬します
？？？？ → ★？？☆
確②①？ → 確②①☆
確確確？ → 確確確☆
？？？？ → ★？？☆
？③①？ → ★③①☆
確確確？ → 確確確☆
？？？？ → ★？？☆
？④①？ → ★④①☆
？確確？ → ★確確☆
これってつまり、Ｘの値が増えれば、Ｘの側のＹとは共有していない部分で確定していなければならない数が減っていくということじゃないですか！
54:デフォルトの名無しさん
07/05/10 12:52:22
わかった！！
たぶん、共有部分の数はどっちかって言うとどうでもいいのかも。
Ｘ－Ｙの値 ＝ Ｘの側の非共有部分の未確定マス数
であるとき、Ｘの側の非共有部分の未確定マスはすべて地雷、かつ、Ｙの側の非共有部分の未確定マスは全て数字、ってことっぽい。
このことは、次のような場合でも成り立ちます。
？？？？ → ？☆☆☆
？？①？ → ★？①☆
？④？？ → ★④？☆
？確確？ → ★確確？
④の側の非共有未確定マスは左側に３マス。で、４－１＝３と一致。
あー、もうこれ間違いないな。どういうパターンでやっても確実に成り立つかも。
ちょっとすっきりしたので、今度こそ立ち退きます・・・。
55:デフォルトの名無しさん
07/05/10 16:04:33
残り部分が全部確定解放可能な部分がないという条件の場合のみで、
たとえば最善を尽くした結果残っている1/2の選択の場合、
クリックしたほうをかならず正着にすればいいよな。
ただ、残りが確定解放可能かどうかの判断がめんどそうだ。
数字だけみた一次元解法では正着がわからなくても、
こっちにあると過程した場合の予測（二次元解法）から離れた位置までの整合性で正着が導き出せる場合もあるからで、
この解法で正着が出る残り場所がある場合は上記特例にあてはまらない
56:デフォルトの名無しさん
07/05/10 17:23:20
マップを生成したらコンピュータに解かせて
最後まで詰まなかったものだけを人間に出題すればいんじゃね
57:デフォルトの名無しさん
07/05/10 17:25:14
既出だったｽﾏｿ
58:デフォルトの名無しさん
07/05/10 21:52:29
右から開いた場合と左から開いた場合で違ってきたりしないかね？
59:デフォルトの名無しさん
07/05/10 22:08:16
>>10を試してやろうとダウンロードしてきて気が付いたんだが、XPにマインスイーパーが入ってなかったorz
60:デフォルトの名無しさん
07/05/10 22:47:11
>>59
[ スタート メニュー ] → [ コントロール パネル ] → [ プログラムの追加と削除 ] → ( 左側の ) [ Windows コンポーネントの追加と削除 ] → [ アクセサリとユーティリティ ] を選択して [ 詳細... ] をクリッコ → [ ゲーム ] にチェックを入れる。
61:1
07/05/11 02:13:44
>>55
それもけっこう良い手かも。
あと、難しいのが、「詰み」という状況が、いわゆる「最後の２択」のようなもののほかにも、序盤～中盤でこれ以上は進めねーよ！って時にもあるから、それをどうするかだね。
って言ってて思ったけど、そういう場合にも「勘」であけた所を必ず正解（非地雷）にすればいいのかな。
ちょっと面白そうな方法かも。
62:1
07/05/11 02:16:13
>>56-57
今ちょうど、コンピュータに解かせる方法を考えて、その方法（>>36）を試してみる予定。
もし上級の盤面で、地雷配置の作り直し回数が多くなりすぎないなら、使える方法だと思う。
63:1
07/05/11 02:18:20
>>58
ごめん、それはどういう状況での話？
一番初めのところかな？
>>59
けっこう楽しいのでお勧め！
64:1
07/05/11 02:29:34
実は>>10をやっていて気付いたんだけど、２つの数字から確定部分を推測するのって、別に隣接してなくても大丈夫なんだね。普通にプレイしていた限りでは全然気付かなかったなぁ。
確確？？？ → 確確？☆☆
確①？①？ → 確①？①☆
確確？？？ → 確確？☆☆ ☆は地雷ではないことが確定の意味
とりあえずこの状況は、>>54で割り出せそう。
あと、２つだけの関係に限らず、３つの関係から出せるものもあるな。かなり極端なのだと、
？？？？？？？ → ☆☆？★？☆☆
？①？④？①？ → ☆①？④？①☆
？？？？？？？ → ☆☆？★？☆☆
こんなふうにほとんど確定してない状況でも、かなり沢山確定させることができるみたい。
まあこんな状況は普通にプレイしててもまず出てこないけどｗ
65:1
07/05/11 02:36:56
>>55
ごめん、後半を微妙に読み飛ばしてたｗ
>こっちにあると過程した場合の予測（二次元解法）から離れた位置までの整合性で正着が導き出せる場合もあるからで、
ってのがなかなか想像できないんだけど、できたら具体例みたいなの出してもらえないすか？
いちおう>>54のやり方は、「地雷があると仮定した場合」ってのを包含しているような気がしているんですが、いかがでしょう？
これに、３つ以上の数字を含めた>>64の後半みたいなのも加味した、もうちょい一般的な法則出せばなんとかなりそうな気はする・・・。
今日はこの辺にしときます。
それではまた明日ﾉｼ
66:55
07/05/11 10:02:54
>>65
具体的にいえば、>>54みたいなやつで、
結局完全手詰まりまで解けるルーチンを作れる、
つまり>>10のソフトをつくれないとだめだ
67:デフォルトの名無しさん
07/05/11 11:20:10
今北産業。
取り敢えず、マインスイーパのオプションの紹介。ルールの基本は同一で、各オプションは組み合わせもできる。
アクション性の低いものから順に。
・露出岩
フィールド中に岩が露出しているマスがある。
そのマスには地雷がないことは確定するが、数字も出ないので岩が多数あると、泣ける。
・地雷再配置マス
そのマスを開けると地雷が(開いてないマスの中で)再配置される。
後述の移動地雷と違って、再配置マスがあることが分かったら避ければいいので(タイムアタックでもなければ)
それほど苦にならない。終盤、所謂詰みの状態で開ければ、巧いこと詰みが回避できるおまけも。
・移動地雷
開けてないマスの中を地雷が(一定時間ごとに)自由に移動する。
#飛び地の間は移動しない方がそれっぽいが、横着して自由移動で実装してしまったw
白マス(周囲に地雷がないマス)を開けたときに連鎖開きするわけだが、移動地雷があると
それも頼りにならないのでかなりきつい。おまけに、移動前にカウントダウンで音が鳴ってくれないと
移動した瞬間に開けて泣きを見ることに。
>64の後半の状況はランダム開けをしない限り発生しないね。
#タイムアタックのときは意図的にやったりするけど。
処で、以下は実践でもしばしばあるパターンけど既出だっけ?
？白白白？ 壁壁壁壁壁
？一二一？ ？一二一？
？？？？？ ？？？？？
↓ ↓
○白白白○ 壁壁壁壁壁
○一二一○ ○一二一○
○★○★○ ○★○★○
68:55
07/05/11 11:48:06
>>67
既出かどうかはわからない。
俺はパターン化はしてないが、
実践で出現すればすぐ解ける
69:55
07/05/11 11:55:23
あと、残りマスが少ない状況で爆弾も残り数個って場合は、
その残り爆弾個数による解法もあるよな。
70:1
07/05/11 12:50:15
>>66
うーん、なるほど。
とりあえず今は>>10相当の処理ができるよう、頑張ってみようと思います。
>>67
なんかそのルール楽しそうｗ
それは、実装済みとかってこと？
もしよければ公開ｷﾎﾞﾝﾇです。
１・２・１に関しては>>42で触れたつもりでいたんだけど、実際には「１・２」の部分に>>54を適用して２段階で同様に進めるから、単に「コンピュータに解かせる」って話ならそれでオッケーかなぁと。
>>69
トータルの地雷数から割り出せるっていう話に関しては、>>30-33,35,37あたりでちょこっと触れたんだけど、同時に考えると頭がパンクしそうなので、また後ほど考えるという方針でお願いしますｗ
71:55
07/05/11 13:16:11
初心者用機能として、
何かのキーを押すと、解法が存在するマスを色つき表示するとか楽しいかもな
壁壁壁壁壁
？一二一？
？？？？？
たとえば前述のこれだったら？のマスが黄色くなるとか
72:67
07/05/11 13:19:52
>>70
元は仕事場にあったSolaris1(Sun-OS4)の時代のSunのEWS用だから、
Linuxでも(XLibが使えるから)コンパイルできる筈なんだけど……
流石に転職とメディアの都合で復元は難しいだろうな。
アイデア自体はMac版を参考にしたからMacOS7時代のゲーム集にはありそうだ。
#国産じゃないけど。
そっちの方も、現在手元にMacがないから見ることもできないな。
なんかこう、アシスト機能つけたの思い出して懐かしくなってきているんだけど、
改めて作るほどの気力は今一起きないなぁ。
で、そのアシスト機能は>67で書いた1-2-1みたいな(比較的単純な)パターンに対して
旗を立てたり勝手に開けたりする程度の機能なんで、(論理的には詰みじゃなくても)
自分の知らないパターンは放置する軟弱仕様だったな。
で、更に思い出したのだけど基本ルールがマインスイーパと違う、似たようなパターンの
ゲームも幾つか作ってた。それは更に古くてPC-8001のbasicだったりしたはず。
#そっちに至っては20年前か……
73:デフォルトの名無しさん
07/05/11 13:22:11
これはもう、あれだ
３次元マインスイーパーを作るしかないな。
74:55
07/05/11 13:23:31
>>73
その話は１０年前にきいた覚えがあるｗ
75:デフォルトの名無しさん
07/05/11 17:23:17
見下ろし型３次元テトリスとか？
76:1
07/05/11 19:46:43
>>71
それいいね。
とりあえずコンピュータに解かせる処理がうまくいけば、そういうオプションをつけることもできそう。
>>72
なるほどー。
何気にマインスイーパって歴史深いのかな？
>>67みたいなアイデアは今まで見たことも考えたこともなかったので、斬新でおもしろかったです。
>>73
ググったらけっこう出るねｗ
Linux版だとかっちょいい概観の3D版があるみたいだけど、手元にLinux環境がないorz（３ヶ月前にLinux入れてたマシンのマザボが爆発したｗ）
Flash版でBombSweeper3Dやってみたら、ちょっと面白かったよ。
でもさすがに、3D版の自作はしんどそうだ・・・
77:1
07/05/12 02:39:01
>>64みたいな複数マスの数字から割り出す、地雷か数字かの確定方法の一般法則らしきものができたので、書いておこうと思います。
数学でいう「集合」で出てくる記法を使っていますが、ちょっとだけ辛抱してください。
集合を使った理由は、マスの「共有」とか「除外」とかを、積集合や差集合でストレートに表現できるからです。
あ、その前に、これまでのレスで勝手に命名してしまった言葉がいくつかあるので、あらかじめ確認しておきます。
・確定マス ＝ 左クリック等で開いた数字マス or 地雷であると判明して旗を立てたマス or 壁
・未確定マス ＝ まだ触ってない、初期状態のマス
・実質値 ＝ 表示されている数字から、周囲の確定マス内の地雷数を差し引いた数値
（注：数字マスには>>67でいう「白」のマスも含まれる。「０」という数字であると解釈できるため）
ということで、以下は「ある瞬間において詰みにならないための必要条件」の１つです。
でも最終的には十分条件がほしいんだよなぁ・・・
（下書きしたので、一気に書き込みます）
78:1
07/05/12 02:39:55
αを任意の非地雷マスとし、
・N(α) ＝ マスαの実質値（「Number」の頭文字のつもり）
・Q(α) ＝ マスαの周囲8マス中で未確定なものの集合（何が来るかわからないマスなので、「Questionable」の頭文字）
とする。
オブジェクト指向のプログラミングに慣れてる人は、α.getNumber()とか、α.getQuestionableSquares()みたいに考えるとわかりやすいかも。
それで、そうすると、
N(α) - ΣN(β) = | Q(α) - ∪Q(β) |
という関係が成り立つ場合に、Q(α) - ∪Q(β) に属するマスは全て地雷、∪Q(β) - Q(α) に属するマスは全て非地雷、ということが確定する。
（注：絶対値の記号は、その集合に属する個数を表す。あと、集合の引き算は差集合、すなわち除外を表す）
（続く）
79:1
07/05/12 02:40:26
ただし、ここでβというのは、1つ以上の未確定マスをαと共有するマス（つまりβというのは複数個ある）とし、
・ΣN(β) ＝ 「βの実質値」を全部合計した数値
・∪Q(β) ＝ 「βの周りの未確定マス」全部の和集合
とする。（本当はΣとか∪はもっと巨大に書きたいとこだけど、雰囲気でご理解ください）
もう少し精確に書くと、
・S(α) ＝ ｛β (≠α) | Q(α)∩Q(β)≠φ｝ （ここのφは空集合のこと）
としたとき、上記の「Σ」と「∪」は、それぞれのβ∈S(α)に対して全部の「和」および「和集合」って感じ。
ちなみに S(α) ＝ φ の場合、αの数字だけを考慮することになり、
「N(α) ＝ |Q(α)| ならば、Q(α) は全て地雷」
というシンプルな状況（>>45あたり）になる。
それと>>54前半は、|S(α)| ＝ 1 の場合。
80:1
07/05/12 02:40:57
数式だけだと、「何のこっちゃい？」って感じだと思うので、以下は具体例。まず通常はありえないけど、>>64を題材とすると、
□□□□□□□
□①□④□①□
□□□□□□□
□は、まだ開いていないツルツルの未確定マス（「？」は見づらいのでやめましたｗ）。
④をα、左側の①をβ、右側の①をγすると、S(α) ＝ ｛β, γ｝で、N(α) = 4、N(β) = 1、N(γ) = 1、ってのは問題なさそう。
で、Q(α)は④の周り8マス、Q(β)は左の①の周り8マス、Q(γ)は右の①の周り8マスのこと。
そうすると、N(α) - {N(β) + N(γ)} = 4 - (1 + 1) = 2 になる。
そして、Q(α) - {Q(β) ∪ Q(γ)}ってのは、④の周り8マスから、2つの①の周り8マスと重複しているものを除外したマス、すなわち④の上下2マスだけになる。
つまり、| Q(α) - {Q(β) ∪ Q(γ)} | = 2 となり、上の N(α) - {N(β) + N(γ)} の値と一致する。
ということは、④の上下2マスは両方とも地雷で、なおかつ、①の周辺だけど④の周辺ではないような部分は全て非地雷であることがわかる。
81:1
07/05/12 02:41:32
というわけで、
☆☆□★□☆☆
☆①□④□①☆ ★は確実に地雷
☆☆□★□☆☆ ☆は確実に非地雷
という結果になる。
あと、>>55で思い出したんだけど、地雷の「存在を仮定」して進める方法は戦略として重要なので、もう一言追加。
N(α)からN(β)やN(γ)を引き算するということは、αとβの共有部分やαとγの共有部分に、N(β)個、N(γ)個の地雷が存在すると仮定することに相当する。
で、Q(α) - Q(β) ∪ Q(γ) の個数と比較することで、その仮定を検証していることになる。
両者の数値が一致した場合には、仮定が正しいことになり、非共有部分の地雷or非地雷が完全に決定する、という仕組みになっている。
さて、この辺で一段落ということにします。
週末中には、>>36,56の実装ができあがりそうです。
82:デフォルトの名無しさん
07/05/12 21:14:53
なんか難しくてよくわからないけど、
背理法＋バックトラッキングでも、十分高速だと重。
^１．後から開いた数字とその周囲を優先、
^ (未確定マスー実質値)の絶対値の小さいもの優先で、数字を一個選択
^２．その周囲に★を仮に置いてみる。同時に☆が仮に決定
^３．それを再帰的に繰り返す
＾ ↓
^ ａ．矛盾(＝２で★や☆の数が超過で置けない)したら
^ 一つ前に戻って別の場所に置く
^ ↓
^ 全部の場所、ケースで矛盾すれば、はじめに置いた★が☆に決定
^ それを開いて１へ
^ そうでなければ、１で別の数字を選択
^４．全部の数字で矛盾が発見できなければ、解は不定。失敗
^ 未確定マスがゼロなら、解有り。成功
効率は１のところの選択アルゴリズムの性能次第だけど、
判定に時間かかるなら、その問題は捨ればいいし
83:デフォルトの名無しさん
07/05/12 21:32:21
ごめん。
(未確定マスー実質値)の絶対値の小さい
↓
Ｍｉｎ((未確定マスー実質値),実質値)のなるだけ小さいもの
ですた。
84:1
07/05/13 11:47:13
>>82
なるほど、地雷があるのを仮定して進めるのをストレートにやるってことかな。
基本的に「確定」みたいなことをせず、最後まで仮定だけで試してみて、詰みがあるかどうかだけを見つける感じ？
それと、最初の「優先度の選択」のところがちょっと理解しきれなかったんだけど、俺のやりかたより断然シンプルな形でできそうだね。
いちおう今は>>78に近い方針で実装を試みてるんだけど、破綻しそうな予感もしてるので、参考にさせてもらう可能性大です。
85:1
07/05/13 11:55:25
えーと、まだ「コンピュータに解かせてダメならやり直し」って状態まで完成はしてないんだけど、ちょっと観測用としては面白いのでうｐしてみました。
URLﾘﾝｸ(2sen.dip.jp:81)
「自動で推論」ってやつがあるけど、これは>>78の一般形ではなく、数字2つだけの関係から導きだせるものだけです（つまり>>80の形は検出できない）。
理由は簡単で、「2つのマスを見るだけじゃ解けないけど3つ見れば解ける」状況はほとんど起こらないこと、あとそれでしか解けないものを、「解ける」と言い張るのもちょっと強引かと思ったからです。
（本当は実装が面倒くさかった、というのは内緒ですｗ）
86:1
07/05/13 12:03:46
いくつかわかったのは、
・上級でも、「2つのマスから推論」を使うだけでクリアできる確率は何気に高い（チェックボックスに全部チェックを入れて解いてみてください）。
・初級や中級なら、「推論」を使わなくても大抵解ける。
・一方で、1回解くだけでも結構時間がかかる。
って感じかな。
まあ時間がかかるのは、JavaScriptだからってのもあるし、あと書いたアルゴリズムを大して見直してなくて、「とりこぼし」がないようにするために、かなり余分にチェックしすぎてる面があるかもしれないためだと思われます。
87:1
07/05/13 12:25:06
うわ、>>78で検出できないケースがありましたorz
×××× → ××××
□①×× → □①××
□②①× → □②①×
□□□× → ☆□□×
×・・・数字or旗or壁（確定マス）
□・・・初期状態（未確定マス）
☆・・・地雷ではないことが判明
やっぱこれが、「詰みにならない必要条件」に過ぎない故の欠陥ですね。
「詰みにならない十分条件」（＝「詰みになる必要条件」）を見つけないと、ちゃんとしたものにはならないか・・・
88:デフォルトの名無しさん
07/05/13 12:58:29
あぁ、>>82のおかげで、必要十分条件見つけました。
もっとシンプルに考えればよかったんだorz
俺のバカバカバカ！
ある未確定マスに対して、★や☆を仮定してみて、どこか別の場所に矛盾が起こるかどうかを探せばいいんだ。
まず、ある一つの未確定マスに対して、
・「★だと矛盾」かつ「☆だと矛盾しない」なら、当然そのマスは☆に確定
・「★だと矛盾しない」かつ「☆だと矛盾」なら、当然そのマスは★に確定
・どっちも矛盾しないなら、とりあえずそのマスはどちらもあり得る
・ちなみに両方矛盾することは、絶対にありえない
で、同じことを全ての未確定マスに対して繰り返して、1つでも確定するなら詰みじゃないし、1つも確定しないなら詰み。
うーん、そうすると、パフォーマンスを意識するなら>>82の優先順位みたいなやつをうまくつけていく必要がありそう。
まあでも、JavaScriptでやってるおかげで、色々修正するのはけっこう楽かも。
89:1
07/05/13 13:24:30
おっと失礼、88は俺です。名前欄入れ忘れでした
90:1
07/05/14 02:14:56
やっぱ違うなぁ・・・
>>88も色々と穴があるっぽい。
□□□□ ★□□☆
□⑤②□ → ★⑤②☆
□□□□ ★□□☆
これは>>88じゃ検出できないや。
とりあえず別の方針として、ゲーム理論とかに出てくるCSP（制約充足問題）も検討してみようかと思ってます。
なんか実装が難しそうだなぁ・・・
91:1
07/05/14 02:21:46
すいません、たまにはageます。
Janeで見てると上がってるとか下がってるとか全然気にならないから忘れてたorz
92:デフォルトの名無しさん
07/05/14 03:20:46
最初の一個目は、運にのみ支配されている
よって 必ず解けるとはいかない
よってスレ終了ｗ
93:デフォルトの名無しさん
07/05/14 03:22:25
これは ひどい
94:デフォルトの名無しさん
07/05/14 03:25:34
逆説 開始後 最低でも二個運で踏まなきゃならない
→ 必ず解けるは無理ｗ
95:デフォルトの名無しさん
07/05/14 03:46:58
踏んでから生成するんだっつーの
96:1
07/05/14 05:49:50
というわけで、コンピュータに解かせて、解けなければ地雷を配置しなおすバージョンです。
URLﾘﾝｸ(2sen.dip.jp:81)
・初級は問題なし
・中級はちょっと遅いけど、せいぜい3～4回のやり直しでうまくいく
・上級は何十回やり直しても見つからない時があるｗ
まあとりあえず、今の段階では「もっと頑張れば解ける」ような盤面も、「解けない」と結論してる部分もあるから、改良の余地はあるかも。
あと、解くのが遅いのは、アルゴリズムがテキトーだからですorz
一応、中級はけっこう遊べると思う。
やっぱり「論理だけで確実に解ける」地雷配置は、プレイしてて気持ちがいい！
97:1
07/05/14 05:52:15
>>92
えーと、それに関しては>>22-28あたりを参照してください。
今現在の状況としては、
・一番初めの状態では、地雷を配置しない
・最初にクリックした瞬間に、そのマスおよびその周辺を避けて地雷を配置
・あとオプションで、コンピュータに解かせて行き詰ったら配置し直しってやつを実装できたとこ
ってな感じになってる。
98:デフォルトの名無しさん
07/05/14 06:00:41
>>97
荒しや煽りは無視するようにしとけってｗ
99:1
07/05/14 06:10:08
ｽﾏｿ。眠くてぼーっとしてたｗ
まあ途中経過を整理するのにちょうどよかったので、利用させてもらいました、ってことで。
100:1
07/05/14 10:10:40
せっかくHTMLで作ってるんで、ブラウザで直接アクセスできたほうが便利かなぁと思い、とりあえずジオシティーズに置いてみました。
なんかジオシティーズの使い方がよくわかんねぇぇぇぇ
トップ：URLﾘﾝｸ(www.geocities.jp)
実装：URLﾘﾝｸ(www.geocities.jp)
101:デフォルトの名無しさん
07/05/14 11:56:37
1のせいでマインスイーパ久しぶりにはまって時間無駄にした。
102:デフォルトの名無しさん
07/05/14 12:55:46
>>26
速いひとは旗立てないから
そのポイント方式はまずい
103:55
07/05/14 13:18:48
>>102
旗たてて左右両クリックで一気に開くほうがはやくない？
104:デフォルトの名無しさん
07/05/14 13:20:14
なら ・確実に安全だけど開いていない場所 だけでｗ
105:67
07/05/14 13:24:38
あー、見るの忘れてた。
複数の拠点で2chを見ている関係でたまに取りこぼしがあるですよ。
で、私もタイムアタックのときは旗を立てないので、旗をクリア条件にしている
マインスイーパにはえらくストレス溜めさせられますね。
ってことで、旗でペナルティは勘弁。
#まぁ、旗立ゲームと思えばありなんですが。
処で>100のスクリプト、自動展開も自動旗立ても(勿論自動推論も)チェックしていないのに
どんどん展開していきますけどこれって、こちらの環境の問題でしょうか。
今使っているのはこれですが。
--
Mozilla 1.7.12
Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.7.12) Gecko/20060130 Red Hat/1.7.12-1.1.3.4
106:67
07/05/14 13:28:48
>>103
WinMineだと、初級中級とも旗立てない方が速く解けますよ。
私でも初級で2秒で中級で46秒。
#初級の場合、解くと言うよりも反射で運よく開けたって気もしますがw
107:デフォルトの名無しさん
07/05/14 13:34:03
>105
ウチはWin環境でIE/Firefox/Operaで試したが
どうやらIE用に作られてるみたいで、FirefoxやOperaだと上手く動かんかったりする。
まぁ、まだ試作品だから仕方ねーなと思うしか。
108:デフォルトの名無しさん
07/05/14 20:18:29
多くの場面で左右両クリックのが速いけど、それを超える記録を出すには
旗立てないで、かつ配置の運が必要
109:1
07/05/15 00:35:43
>>101
それは失礼ｗｗｗ
>>105,107
すんません、とりあえずWin+IEじゃないと動かないかも。
いちおうFirefoxで、Ctrl+クリックすると選択範囲がでてきちゃう問題は直したつもりなんだけど、まだ一瞬だけ選択範囲が見えちゃうかも。
でもFirefoxは、それ以外は動くんじゃないかな、とは思ったけど、もう一回見直してみます。
Operaは全然わからないんで、ちょっと対応予定ないっす。すいません。
何かonpropertychangeがIEにしかなかったり、onchangeがどのタイミングで呼ばれるかよく理解してなかったりで、イマイチどうしたらいいかわからないんで、詳しい人plzです！
（Web製作板でヘルプ頼もうかな・・・）
最終的にはwinmine.exeみたいな、Win用の実行ファイル単体で作りたいと思います。
あ、でも>>67はLinuxですか。どうしようｗ
110:1
07/05/15 00:42:23
旗立ての話で盛り上がってるみたいだけど、旗を立てないほうが速いってのは初耳だったかも。
マインスイーパも極めるとそうなっていくのか・・・
ちなみに俺はマインスイーパ自体のレベルは全然高くなくって、とにかく暇つぶしにマインスイーパをやるのが好きなだけ。
たいていストレスがたまったときとかに、何気なくやるのがマインスイーパなんだけど、
上級だと自力でクリアできる確率があまり高くないし、運でしか突破できないところまできて地雷を踏むのは余計にストレスになる。
そんなわけで、もっと気持ちよく遊べるマインスイーパが欲しいと思ったわけです。
111:67
07/05/15 00:44:24
大丈夫、Winもある。勿論、ちゃんと動いた。
#で、MozillaOnRedHatでは残りの個数もちゃんと出てなかったことに今気付いたw
112:デフォルトの名無しさん
07/05/15 00:48:28
>>110
お前さんが用意してくれたページで各種機能をオンにして何度か遊んでみたけど、
確かに上級をクリアする為にはかなり運に依存するみたいだな。
判断ミスがゼロでもクリアできる確立は１０～２０％ぐらいなんじゃねぇの？
113:1
07/05/15 00:58:29
>>111
おぉ、それなら安心。
つーかメジャーなブラウザ全部に対応するのって難しいなぁ。
>>112
そんな感じかもね。
今のとこ、クリアできる地雷配置になるまでコンピュータに解かせるのは、上級だとやや非現実的な解決法なのかなぁとも思いつつある。
114:デフォルトの名無しさん
07/05/15 01:09:02
こういうこと言うと元も子もないんだろうけど
ランダムに地雷置いてから解けるかどうか判断するんじゃなくて
１個ずつ順番に解ける位置に置いていくっていうのはどうなの？
115:デフォルトの名無しさん
07/05/15 01:12:03
>>114
それがこのスレの趣旨じゃなかったのか？
116:1
07/05/15 01:34:19
>>114,115
実は、それができたらベストです。
っていうかそれがやりたいんです。
でもいくら考えてもできないから、とりあえず>>36を参考に、ランダムに置いてみる方法を試してみてるとこ。
117:デフォルトの名無しさん
07/05/15 02:19:31
>>116
全パターン網羅してテーブルを作るんだ
118:デフォルトの名無しさん
07/05/15 02:20:57
やっべ
中級クリアしたら寝ようと思ったのが12時10分ｗ
意外と難しいもんなんだな
119:デフォルトの名無しさん
07/05/15 05:55:06
俺自身はプログラミング齧った程度だから具体的なコードは書けないけど
普段解く時『地雷が判明したら、周囲の数値から１引く』
って考えてるんだけど、何かに使えるかな。例えば
□□②
□※②
□④③
□□□
※の部分が地雷だと判明したら、周囲の数値を
②→①、③→②、④→③
要は、数値を『判明してる分を除いてあといくつ地雷が残っているか』と読む。
で、差し引いた結果、数値が：
ゼロになった → 周囲の地雷以外のマスは全てオープンできる
周囲の地雷以外の残ったマス数と一致 → それらも全て地雷が確定
そーすると、残りのマス・数値のパターンは割と限定される。
①②②①、①②①、②①などの
定石パターンに持ち込めればしめたもの。
120:デフォルトの名無しさん
07/05/15 07:00:05
今北
マインスイーパってやっぱ途中で博打しなきゃいかんのね
少ししかやったことないから見付からないときは自分が悪いと思ってた
>>1には頑張って欲しい
121:1
07/05/15 08:33:51
>>117
パターンすか。パターン・・・。パターンが難しい・・・。
>>118
夜遅くまで乙ですｗ
122:1
07/05/15 08:48:14
>>119
今まで使ってた記法を使わせてもらうと、こんな感じのやつのことかな。
□□□□□ □□□□□ ☆★☆★☆
□②③②□ ＝ □①②①□ → ☆①②①☆
□②※②□ □×××□ ☆×××☆
□・・・未確定マス（初期状態）
※・・・旗
×・・・確定マス（数字or空白or旗or壁のどれか、という意味）
★・・・地雷であると判明
☆・・・地雷ではないと判明
いちおう、表示された数値から、旗の数を差し引いた値を、「実質値」という呼び方して使ってる。
今実装できてるやつは、表示されてる数字ではなく、実質値から割り出して計算させてるよ。
（実際のコードの中では、cell.remainderって名前にしちゃってるけど）
123:1
07/05/15 08:49:25
>>120
応援ありがとう！
なんか今いいアイデア浮かんだので、実装してみます。
124:55
07/05/15 10:50:31
>>119
厳密にいえばおれもそれが基本だが、
いちいち１を引く、とかじゃなくて、視覚的に判断している。
たとえば２の数字のまわりに１個地雷確定箇所があったら残りどっかに１個あるってのを、
いちいち２－１＝１とか考えないよな。
３このリンゴをみて、１，２、３とか数えるわけじゃなく見た瞬間３だし、
５個のリンゴがあって３人の子供が1個づつもっていくとしたら、
計算とかしなくても頭の中に２個残ったリンゴが思い浮かぶ。
１桁の足し算、引き算とか、人間は数値計算だと頭ではとらえずに、
観念的、幾何学的に答えがでる。
ただしプログラムを作るとなると計算しなくちゃだめだろうが。
125:1
07/05/15 11:36:41
「明らかに解けるような地雷配置」っていうのを実装してみた。
URLﾘﾝｸ(www.geocities.jp)
何か想像してたのとだいぶ違うなぁ・・・
126:1
07/05/15 11:43:14
しまった・・・。
上級を自動で解かせてみたら、ちゃんと解けないorz
基本的な考え方としては、「2つのマスから推論」を一切せずに解けるように配置したつもりなんだけど、何かおかしなことになってるっぽい。
ボツだなこりゃ。
127:67
07/05/15 12:08:44
>>126
でーりゃぁ配置がかたよっちょるがね。自動旗立てで上級が数秒で解けてしまう。
128:67
07/05/15 12:15:53
自動展開、自動旗立てで、しばしば1クリックで解けてしまう。
1クリックで解けないときは、「七六四」(周囲は旗と壁)なんかができている。
それと、カウントがおかしいのか旗立てがおかしいのか、「残り5個」で地雷踏んでゲームオーバーになった。
#一応ハードコピーは取った。
で、検証したいから暫くゲームオーバーになっても旗の操作できるようにできない?
129:1
07/05/15 12:27:13
>>128
ｽﾏｿ、もう完全にアルゴリズムが間違ってるっぽい。
ゲームオーバー状態で旗の操作はちょっと難しいな。
でもトライしてみる。
130:1
07/05/15 12:40:00
>>128
ゲームオーバー自体にならないようにしてみた。
131:67
07/05/15 13:13:36
＞ゲームオーバー自体にならない
対応乙。
デバッグ終わるまでは何かと便利かと。
で、これで検証できると思ったら、残り60個でクリアしてしまったw
左上はこんな感じ。
□二♪※□□……
二五♪三□□……
♪♪♪二□□……
二三二一※□……
□□□□※□……
□□□□※※……
：
：
右下はこんな感じ
：
：
……□□□□※♪♪♪
……□□※□※♪♪♪
……□※※※※♪♪♪
……□□※♪♪♪♪♪
……□□※♪♪♪♪♪
……※□※♪♪♪♪♪
132:1
07/05/15 13:25:12
>>131
あー、なるへそ。
おいらのとこでも再現できました。
たしかに、まだ地雷が残ってるのにクリアになっちゃってるね。
たぶん原因はわかったかも。
そして修正困難であることもわかってしまったorz
133:1
07/05/15 13:53:55
>>125は失敗に終わったけど、1つ気付いたことがあった。
詰みにならないように地雷を配置していくのには、根本的に難しい点があるかも。
そもそも勘を使わずにマインスイーパを解くには、一発目にクリックした場所から、徐々に広がっていくように解いていくしかない。
そうすると、そのような解き方で詰みにならないように地雷を配置するには、やっぱり最初にクリックした位置から徐々に広がっていくように巡回しながら置いていくしかない。
その場合、本来置くべき地雷の個数に達しないうちに、全部のマスを巡回してしまった時に、バックトラックするのが非常に難しい。
何か良い解決策ないかなぁ？
134:デフォルトの名無しさん
07/05/15 14:03:34
ミスって爆弾を開いてしまっても、そのまま１手戻して続きができる選択もほしいな。
その場合はクリアとかタイムとか得点はないようにして。
感想戦みたいなもんだと考えて。
残り少なくなって間違った時や、操作ミスや勘違いで開けてしまった時、最後までやりたい場合がある
135:1
07/05/15 14:16:24
>>134
あるあるｗ
自動展開とかその他のオプションとの兼ね合いもあるから、すぐにできるかわからないけど、やるだけやってみる。
136:1
07/05/15 14:18:10
と思ったけど、さっきつけたゲームオーバーにならないオプションじゃ役不足かな？
137:デフォルトの名無しさん
07/05/15 14:26:11
フリーセルのように初期配置状態に番号付けておいて
同じ問題を違うところから解くとかやりたい。
138:1
07/05/15 14:46:34
>>137
うーん、ちょっとそれだと趣旨がズレてきちゃうかも。
あるマスを最初にクリックして解ける配置は、別のマスから始めると解けなかったりするから。
139:デフォルトの名無しさん
07/05/15 17:38:55
既存のマインスイーパにログ機能付けて詰まった場合のやり方から何かみえないかな？
140:デフォルトの名無しさん
07/05/15 21:45:37
>>1
考えれば絶対に解けるってのはなかなかやりがいがあるな。
時間を忘れて熱中してしまうわ。
頭悪いから議論には参加できそうにないけど応援してます。
141:デフォルトの名無しさん
07/05/15 22:47:57
マス目最大で地雷の数は最小
ワンクリック勝利
142:デフォルトの名無しさん
07/05/16 02:02:26
>>133
絶対詰まない配置だったら
最初の一発目クリックで全部開いて0秒でクリア出来るぞ
143:1
07/05/16 03:12:41
>>139
いちおう、JavaScriptでの実装で、上級を自動で解かせるオプションを（３つとも）オンにして、クリアできなかったものの地雷配置を観察してみてます。
URLﾘﾝｸ(www.geocities.jp)
まあ今の状態だと、>>87とか>>80みたいな、「3つ以上のマス」から判断することはできてないんだけど、そこそこ色々なことは見えてきそう。
>>140
このプロジェクトの意義に対する理解者が一人でも多いと、すごく励みになります。
頑張ります！
>>141
そんなマインスイーパも楽しいけど、楽しいのは最初だけですがなｗ
>>142
自動で解かせた場合ってこと？
144:デフォルトの名無しさん
07/05/16 03:14:11
俺も密かに応援してる。
いいアイディアが無いからいつもロムってるけど。
145:1
07/05/16 03:16:51
今思ったけど、「解く順序」によって、詰みになるかならないかが変化する可能性があったらどうしよう・・・。
つまり「詰みになるかならないか」が、地雷を全部配置した状態の静的な性質なのか、動的に解いていくことでしかわからない性質なのか。
経験的には静的な性質だと思ってたけど、それを論証する手立てもないし、もし動的に変化しうる性質だったら、ちょっとモチベーション下がるなぁ。
146:デフォルトの名無しさん
07/05/16 03:17:59
>>143
いや、児童じゃなくてもそうだろ？
よく考えてみろよ
詰んでないんだから全部開かれる
147:1
07/05/16 03:20:51
>>144
THX！
あー早く実装したいけど、考えがまとまらない～
148:デフォルトの名無しさん
07/05/16 03:21:31
>>145
南北を上下に分断する配列で地雷源があるとしよう
北から攻めたときは詰まずに最後まで行けるが
南から攻めたときは詰んでしまって先へ行けないケースは
簡単に作れると思う
149:1
07/05/16 03:25:54
>>146
うーん・・・ちょっとよくわからんです。
おいらの実装で、中級あたりで、「ランダム配置で解けるまでやり直す」ってやつでやってみてください。
実際やっても詰みにはならないはずだし、最初から全部開いてしまうってこともないと思います。
「詰み」という言葉自体の意味は、>>22のような感じで使ってるけど、その辺の行き違いはないかな？
150:1
07/05/16 03:29:25
>>148
いちおう、「最初にクリックした場所」によって解けるか解けないかが変わるのは、認識してる。
それじゃ、「最初にクリックした場所」が同じで、解く順番が違う場合に、詰みになるかならないかに変化はあるか・・・って問題。
ちょっとワイアレスの接続状況が悪いので移動します。
151:デフォルトの名無しさん
07/05/16 03:45:49
>>146 じゃないんだけどやってみました
なんか行き詰ってしまったんですけど
これって詰んでますか？
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
152:デフォルトの名無しさん
07/05/16 03:49:59
あー全部開きました
すみません
153:1
07/05/16 05:11:57
>>151
すげー、旗を立てずにやってる。
俺もたまに旗を立てずにやることあるけど、どうしても同じとこを2回以上頭で考えてしまって遅くなるorz
ちなみに、「あれ、おかしいな、詰みにならないはずなのに詰まった」と感じた時は、「自動推論」などを付けてみると見つかる時があるかもです。
154:1
07/05/16 09:35:27
>>125で実装したかったものができました。
実装：URLﾘﾝｸ(www.geocities.jp)
地雷を「明らかに解けるように配置」というやつです。
どういうことかというと、2つ以上のマスを同時に考えないと先に進めないようなものは一切なく、常に「残りの地雷数」から旗を立てることができるようにしてあります。
簡単な話が「自動展開」と「自動旗立て」だけオンにすれば、必ず解けるような配置です。
何か地雷の配置が妙に偏ってるのは、この条件に合致させるために仕方ないことだと思われます。
バックトラックしてないので、上級でやると、たまに地雷配置に失敗しますｗ
155:1
07/05/16 09:38:47
あ、それと、>>139に触発されて、「降参」ボタンをつけました。
本当に降参したいときに押してもいいけど、どちらかというと実際にプログラムで配置された地雷の位置を視覚的に確認するためのもの。
ランダム配置＋自動オプションを３つともオンにしたときに、解けなかったものはどういう配置なのかを観察するのに役立つはず。
あと、失敗してもゲームオーバーにしないオプションをデフォルトでオンにしたので気をつけてください。
真剣勝負したい場合はオフにしてください。
156:1
07/05/16 09:55:50
あ、物ができた時くらいageようかな
157:1
07/05/16 10:25:06
おっと、忘れてた。
実は今回追加した「明らかに解けるように配置」というオプションは、終盤で残りの地雷数から割り出せるようなものも含んでます。
で、それに対応すべく、「自動完了」というオプションも付け加えました（地雷数が残り0になったら強制的に全マスを開く）。
一発目にクリックした位置から、徐々に地雷配置を広げていく方法が結構うまくいくことに気付いたので、今度は複数マスから推論できるようなものに拡張したいと思います。
それができたら、当初の目標はとりあえず達成という感じです。
（バックトラックが一番の難関かも・・・）
158:デフォルトの名無しさん
07/05/16 11:45:49
詰めマインスイーパとかできればいいな
エディット機能で作った盤面をそのまま保存できる。
データ文字列を読み込んでその状態にできる。
エディットでは、地雷配置と既開放マスを設定。
ベストは一個もクリックせず地雷位置を確定させるみたいな。
159:82
07/05/16 13:04:56
なんか思いついた
カーソルを2個づつ移動作成しながら爆弾置けるっぽい
カーソルに移動可能のフラグ立てるときに周りにカラのセルを配置すればいいっぽい
文字じゃ説明困難なんで夜に画像でも書きます
160:デフォルトの名無しさん
07/05/16 13:06:16
今度は
必ず解けるソリティアだな
161:デフォルトの名無しさん
07/05/16 13:17:43
>>160
死ぬほど難しいな････
162:デフォルトの名無しさん
07/05/16 13:24:21
Winについてくる、ソリティアことKlondikeSolitaire?
VegasRuleなら兎も角、Win版みたいな再利用可能なpileだと激しく面倒ですな。
#自動解きさえ難しい。
163:1
07/05/16 14:01:01
>>158
なるほど、おもしろそう。
盤面をシリアライズするのは、テキトーにフォーマット決めちゃえばそんなに難しくないと思うから、盤面の保存/復元みたいなのも後々やってみようかな。
>>159
おぉ！なんか掴めましたか！
縦横斜めのいずれの方向に行くにも1歩と数えて、2個ずつの距離っていうのは、俺も意味がありそうな気がしてます。
でもどうやって地雷を置いていったらいいのか検討もつかないので、画像お待ちしてます。
>>160-162
ソリティアはルールは何とかわかるけど、解けるとか解けないとかそういう議論は全然わからないorz
ソリティアをコンピュータに解かせるのって難しいの？
164:1
07/05/16 14:07:20
すいません、今までの推論の仕方で検出できないものが、またいくつか見つかったので、覚書です。
イマイチ法則性が見つからないなぁ・・・
□□□□ ☆□□★
□②②× → □②②×
□②×× □②××
□××× ★×××
□□□□ ★□□☆
□③①× → □③①×
□①×× □①××
□××× ☆×××
□□□□ ★□□☆
□③①□ → □③①☆
□①×□ □①×☆
□□□□ ☆☆☆□
□□□□□□ ☆□□□☆☆
□①②□①□ → ☆①②□①☆
×××××× ××××××
165:デフォルトの名無しさん
07/05/16 14:17:06
ソリティアってのはトランプのひとり遊びの総称で
Winのは「クロンダイク」っていう名前のソリティアだな
（最近のWinはスパイダーが入ってたりするが）
クロンダイクはその時その時のとれる行動が少ないから
クリアできる時はだいたいアッサリ解ける
どっちかっつーと頭使わずに作業して
勝敗自体は運に任せる感じだから
感覚としてはギャンブルに近いんじゃ？
運ゲーを必ず解けるように作ると
あんまり面白くないものが出来上がると思うぞ
マインスイーパの場合は微妙に頭脳ゲーだから
解けない時に理不尽さを感じる
慣れると割と運ゲーなんだけどなｗ
166:デフォルトの名無しさん
07/05/16 14:19:11
>>1 マインの場合解くことが目的じゃなくてプログラム書くことが目的になってるよな
167:1
07/05/16 14:29:56
>>165
そうだったんだ。勉強になりました。
マインスイーパをやりこんでる人には運ゲーになってしまうのねorz
まあでも、マインスイーパを完全な頭脳ゲー化するのが、このスレの目的であります。
>>166
そうです。プログラムを書くのが目的です。
一方で、解くことに関してある種の完全性を満たす法則を見つけないと、確実に解けるマインスイーパにすることはできないんじゃないかって気はしてるよ。
168:デフォルトの名無しさん
07/05/16 15:12:05
>>164
せっかくのコンピュータなんだから、
総当たり背理法をつかうといいかも？
たとえば、>>164の最初。
あいうえ
お②②×
か②××
き×××
左上の②に着目して、「あ」に爆弾があると仮定し、
もう一個を、「い」にあると仮定する。すると、右の②から、「う」「え」は無有と判断できる。
そして「お」「か」にはないことになるが、左下の②の残り有効マスは「き」のみとなり矛盾が生じる。
つまり、「あ」には爆弾はないのでクリックおｋ
というような、数字表示近接マスの総当たり解放
169:67
07/05/16 15:14:51
クロンダイクソリティアは、手札の山から取るときは一枚ずつ、捲るときは三枚ずつなのが難点。
>162の言う、VegasRuleは山を一枚ずつ捲って空になったら即ゲームオーバーなのかな。
Winのや一般的なのは再利用できるから、使えるカードを敢えて使わない選択があるので試行錯誤が必要になります。
#それが不要なアルゴリズムがあるなら教えて欲しいw
具体的にはこんな感じ。手札を上から順に、a, b, c, d, e, fとします。
初期状態: 空 | 裏
(1)
捲る: c | 裏
c取る: b | 裏
b取る: a | 裏
a取る: 空 | 裏
捲る: f | 空
(2)
捲る: c | 裏
c取る: b | 裏
捲る: f | 空
捲る: d | 裏
d取る: b | 裏 (dが取れない場合) 捲る: f | 空(次のターンでも見えるのはdとfのみ)
b取る: a | 裏
a取る: 空 | 裏
捲る: f | 空
(1)では、a, b, cの回収はできますがd, eは見ることもできません。
(2)では、dが取れるカードならa, b, c, dの回収ができますが、やはりeは見られません。
逆に、dが取れないカードだとcしか回収できず、aもbもeも見えないことになるわけです。
これがあるので、序盤は空捲りで一巡させて三枚ごとの配置(この例ではcとf)を確認しておくことが重要になります。
#仮に、再利用可能で捲るのも一枚ずつだと……すごく、簡単です。
尤も、仮置き場の積み方も選択肢が発生するのでプログラミングでとなると厄介なことには変わりませんが。
#いずれも、選択肢故の試行錯誤(≒バックトラック)が問題なので計算量はそれほどでもないかも知れませんが。
170:1
07/05/16 15:21:18
>>168
確かに背理法を使う方法は>>82にも出てきたけど、割とシンプルなアルゴリズムでできそう。
難しいのは、「どのマスをいくつ仮定するか」ってあたりかな。
「どのマス」に関しては周辺のマスの状況から何らかの優先順位をつけて、PriorityQueueとかで拾って、そこからある距離（おそらく２歩）以内とかでいいけど、「いくつ仮定するか」ってなるとかなり難しいと思う。
それに仮定する数が増えると、計算量がとんでもないことになる。
最終的には、例えば「仮定するのは３マスまで」みたいな妥協案も考えられるかもしれないね。
171:1
07/05/16 15:53:37
>>169
なるほど。
そうすると、クロンダイクソリティアは明らかに解く順序によって、解けるか解けないかが変わってしまうというわけだね。
それだとアルゴリズムでできるのは、飽くまで見ることのできる札から最善手を選ぶだけで、必ず解ける手を打ち出すことはできないってことなのかな・・・？
172:1
07/05/16 16:15:36
ヤバイ、規則性が見えてきたかも試練
□□□□□□ □□★□□☆
□□□③①□ → ☆☆□③①☆
□①□□□□ ☆①□□□☆
□□□□□□ ☆☆☆□□□
□□□□□□□□□ ☆☆□□□□□□☆
□①□②②□②①□ → ☆①□②②□②①☆
□□□□□□□□□ ☆☆□□□□□□☆
□□□××× □□□×××
□□□□④□ □□□★④★
×□□□□□ ×★□□□★
×③□③□□ → ×③□③☆□
×□□□□□ ×★□□□★
□□□□④□ □□□★④★
□□□××× □□□×××
□□□□□□ □□□☆☆☆
□□□□①□ □□□☆①☆
□□□□□□ ☆☆□□□☆
□①□④□□ → ☆①□④★□
□□□□□□ ☆☆□□□☆
□□□□①□ □□□☆①☆
□□□□□□ □□□☆☆☆
□・・・初期状態
×・・・数字or空白or旗or壁（確定マス）
★・・・どうやら地雷
☆・・・どうやら非地雷
数字は実質値（隣接する確定マス内の旗の数を引いた値）
173:デフォルトの名無しさん
07/05/16 16:16:48
>>170
普通に左上から右方向に周囲に未開マスがある数字表示マスをたどっていき、
>>168の用に検出できたら再度左上から・・・
さっきやった処理をまた行う無駄な検索も多くはなりそうだが、
今のコンピューターの能力を考えると大したことない処理量だと思う
174:デフォルトの名無しさん
07/05/16 16:21:15
自分も作ろうかなと思ってるんだけど。
この画像使っちゃだめかな？？
175:デフォルトの名無しさん
07/05/16 16:32:24
>>173
うん、まあ仮定するターゲットを選ぶってことに関しては、全部を網羅しさえすればいいから、色々な方法があると思うけど、「いくつ仮定するか」っていう部分がちょっと大変かも。
というのも、>>172みたいな感じで色々試してみて、少しずつわかってきたんだけど、グラフ探索アルゴリズムでCSP（制約充足問題）を解くようなやり方で、完全な答を出せるかもしれないと感じているところなので。
とりあえず、まずは完全な答を探して、もしそれが無茶であることがわかったら背理法を使ってみるよ。
>>174
画像っていうのは、Webページ上の実装に使ってるやつのことかな？
それだったら、winmine.exeからリソースハッカーで抜き取った画像だから、好きに使ってくれていいと思います。
というか、俺自身も本当は使っちゃいけないんじゃないだろうか、という不安もあるんですがｗ
最終的なリリース版（実行ファイル単体）では、オリジナルの画像に差し替えようかと考えとります。
176:デフォルトの名無しさん
07/05/16 16:35:15
あ、そうなんだ。
じゃあ自分も後で差し替えるかもしれないけどとりあえず使わせてもらう。
ありがとう。
177:67
07/05/16 17:14:59
私の場合、>164のようなパターンは、評価マス(数字のある場所)から順に手繰ることで確定させました。
□□□□ ☆□□★
□②②× → □②②×
□②×× □②××
□××× ★×××
「左上」マスを評価した場合、
○○○□
○②②× 「左上」から「右」に自分の調査対象範囲(○の範囲)を通知。
○②×× 同様に「左上」から「下」に自分の調査対象範囲を通知。
□×××
○二二□ 「右」は自分の対象範囲から「左上」の対象範囲を除外すると残りが一箇所であることから
二②②× 「右」から「左上」に対象範囲内の置ける個数を返答(1-2個×2箇所)。
二②×× 同様に「下」から「左上」に範囲内の置ける個数を返答(1-2個×2箇所)。
□×××
☆□□□
□②②× 「左上」は双方から少なくとも足すと二個置けると言われたので、残り箇所の☆を確定する。
□②××
□×××
って、この調子で長々と書いたのだけどどうしよう……
178:67
07/05/16 17:30:38
>>171
つーか、ソリティアの場合捲るか取るかの判断が悩ましいわけで、その悩ましさが売りですから。
プログラムがいんちきして、手札を全部知ってたとしても解くのは厄介でしょうねぇ。
>172のパターンも>177の応用で処理できそうですが、なんせ当時は(評価で)確定が出るたびに
再描画してたのでアニメーション的楽しさはありましたが実用性は余り……w
179:デフォルトの名無しさん
07/05/16 19:54:27
>>177
うん、今俺の考えてる方法も、その方法に近いです。
ちょっと自分の方法はまだ言葉で説明するのも絵で描くのも難しいですが・・・。
例えばこんな複雑怪奇なやつも、おそらく解けると思う（実用性ゼロだけどｗ）。
□□□□□□ □★★★□□
□□⑥□□□ □★⑥□☆☆
□□□□②□ → ☆□□□②☆
□②□□□□ ☆②□□□☆
□□□⑥□□ ☆☆□⑥★□
□□□□□□ □□★★★□
まだ隠れている地雷の位置を※とすると、実際の地雷の位置はけっこう色んなパターンになる。
□★★★□□ □★★★□□ □★★★□□ □★★★□□
□★⑥□☆☆ □★⑥※☆☆ □★⑥□☆☆ □★⑥※☆☆
☆※※□②☆ ☆□□※②☆ ☆※□※②☆ ☆※□□②☆
☆②□※※☆ ☆②※□□☆ ☆②※□※☆ ☆②□□※☆
☆☆□⑥★□ ☆☆※⑥★□ ☆☆□⑥★□ ☆☆※⑥★□
□□★★★□ □□★★★□ □□★★★□ □□★★★□
（他６パターンほどある）
180:1
07/05/16 19:55:07
名前欄忘れたorz
>>179=>>1です
181:1
07/05/16 19:56:29
基本的には、調査対象を全部グラフで結んでしまうのだけど、結べる条件がちょっと細かい。
簡単に言うと、ある２つの数字マスを結ぶための条件は、周囲の未確定マスの中で「２つの数字マスの間で共有されているマス」が、少なくとも２マスある必要がある（「なぜ」そういう条件なのかは聞かないように。試行錯誤の賜物ですｗ）。
例えば、それぞれの②や⑥の間には、２マスずつ未確定マスがあるのがわかると思う。
またグラフ内のそれぞれのエッジで、共有マス同士の重複は許されない（重複する場合はグラフを形成できない）。
これで、上図の４点を結ぶ４角形ができあがる（対角線は結べない）。
一度グラフを結んだら、全体を巡回しながら、>>177同様に、共有部分は「地雷数のあり得る範囲」の形で整合性をチェックする。
このとき、ある種の「極端さ」が必要で、例えば上図の両方の②は、その非共有マス（グラフ内の誰とも共有していないマス）に一切地雷がなく、また両方の⑥は、その非共有マスが全て地雷、という風に両極端になっていると仮定する。
実際のアルゴリズムでは、両極端なノードが交互に並んでいれば良い。
その極端な仮定の下で矛盾が一つもない場合には、仮定した非共有マス部分が全て確定する。
逆に矛盾が生じた場合には、このグラフから確定できるものは一つもないということになる。
はい、言葉で説明すると意味不明でした。
またちゃんとまとまってから来ますorz
182:1
07/05/16 20:13:03
あ、あと実践的なパターンで、現在の実装では解けなかったものを紹介しときます。（※は旗です。）
③※③②①
①②□※②□
※②□③③□
②③②□□□
□□□□□□
まあ読みの早い人はすぐわかるかもしれないけど、コンピュータにやらせるとちょっと大変そう。
まず、これを実質値に直す。使わない数字マスと旗のマスは全部×に変える。
××××××
××□×①□
×①□②②□
×××□□□
□□□□□□
左側から順に①・②・②・①をつないでグラフを形成し、それぞれの非共有マスが、非地雷・地雷・非地雷・地雷という風に交互になっていると仮定する。（まあ、「非共有マス」を持つのは、３番目の②だけなんだけどね。）
最初の①と次の②の間にある共有２マスには、１つの地雷があるはずで、二つの②の下側の共有２マスにも１つの地雷があるはず。
後の方の②の右下は非共有マスなので、非地雷であるとすでに仮定してある。
そして、最後の②・①の右側２マスにも、１つの地雷があるはず。
これで矛盾は起こらないので、３番目の②の非共有マスが非地雷になる。
××××××
××□×①□
×①□②②□
×××□□☆
□□□□□□
というわけで、一箇所だけ非地雷確定！この１マスが救世主になったりするんだよね。
183:1
07/05/16 20:14:52
>>178
うぉ、そうだったんだ。
手札が全部わかってたとしても解くのが難しいんだね。
184:デフォルトの名無しさん
07/05/16 22:32:09
ソリティアは散々悩んだ挙句、解なしっていうのがヤなんだよな～～。
マインスイーパーは一か八かで解けるけど。
185:デフォルトの名無しさん
07/05/16 23:10:32
>>1
画像描いたのであげます。説明文適当です。
URLﾘﾝｸ(uproda11.2ch-library.com)
186:デフォルトの名無しさん
07/05/16 23:45:15
上は82です。よく見たら図13,14は間違ってたorz
187:82
07/05/17 00:14:54
そこだけ消してうpし直し。
URLﾘﾝｸ(uproda11.2ch-library.com)
2パターンだけですが、４方向＋反転で8通りあるのと、
近くへの×設置や裏側からの爆弾やアキ設置との組み合わせで
他のパターンに見えるものがいろいろ生じるみたい。
188:デフォルトの名無しさん
07/05/17 00:39:56
爆弾ないとこ掘っていくと絵が出来るとかどうよ？
189:デフォルトの名無しさん
07/05/17 00:53:56
何年か前にJavaアプレットで作られたそんな感じのブロック崩しがあったな。
190:1
07/05/17 03:54:32
>>187
ごめん、ちょっとよくわからないかも。図６までは理解できたと思う。
図７→図８の遷移で、爆弾を置く５マスは、図７の時点でアキでもいいの？
図９→図１０の遷移は、図８に行く代りにこっちに行くこともできるって意味でおｋだよね？
図１１→図１２の遷移は、「爆弾をやっぱりアキに変える」わけだから、爆弾の個数が超過したときにやるんだと思うけど、逆にアキの個数が超過した場合には、「アキをやっぱり爆弾に変える」パターンもいるのでは？
図１５→図１６の遷移では、「緑の？」はせいぜい２つまでなら爆弾でもいいということ？
図１７→図１８の遷移は、図７～図１０と同様なオプションであると理解できました。
図１９→図２０の遷移は、図１７のパターンを実際に適用しているのはわかるけど、「周囲が埋まっている」という意味がわからなかったです。
図２１と図２２は、操作としては意味がわかるんだけど（図２１がどうやって実現したかはわからなかったけど・・・）、「配置を完了する条件」がなぜ図２１のコメントのところに書いてあるようになるのかがわからなかったです。
というわけで、細かいとこをごちゃごちゃ書いてしまったのですが、一番重要なのが、「なぜこのアルゴリズムで詰みにならない配置になるのか」という部分にどうも釈然としきれないとこです。
たぶん色んな試行錯誤で見出したものだと思うので、基本的にどういうコンセプトでこれらのパターンが出てきたのか、というところをもうちょっと詳しくお願いします。
（もし時間が許すならば、１ステップずつ実際にパターンを適用している図とか作ってもらえれば、さらに理解が深まるかもです）
191:1
07/05/17 04:00:01
あ、>>154を作ってるときにわかったんだけど、例えば中級なら幅16×高さ16の盤面に40個の地雷を並べるから、非地雷（アキ）は16×16－40＝216個ってことになる。
そうすると、初めから解けるように配置していった場合には、
（１）それまでに決定した地雷数＝40になったら、残りのまだ決めてないマス（？）は全て非地雷（アキ）にする
（２）それまでに決定した非地雷数＝216になったら、残りのまだ決めてないマス（？）は全て地雷にする
ってことで問題ないと思うよ。
192:1
07/05/17 04:02:43
>>188-189
たぶん、今やってる方向から、絵が出てくるように改良するのは難しすぎるかもですorz
193:デフォルトの名無しさん
07/05/17 05:07:59
レイヤー作ればすぐ出来そうな気がするけど
194:1
07/05/17 05:15:04
>>193
ああ、普通にバックグラウンドに絵を描いておけばいいのか。
それなら簡単にできそうｗ
俺は絵心がないので、絵が得意な人は、画像提供お願いします。
195:67
07/05/17 08:02:51
開くと下に絵があるってことか。
寧ろ、地雷の配置がAAになるとかw
Ex.こんなの♪
□□□□□□□
□□●□●□□
□□□□□□□
□□□□□□□
□●□□□●□
□□●●●□□
□□□□□□□
196:1
07/05/17 08:05:00
>>195
実は最初>>188を見たとき、そういう意味だとおもたｗｗｗ
197:デフォルトの名無しさん
07/05/17 08:18:38
ぴくろ(ry
198:82
07/05/17 08:42:14
>>190
A１．図７の時点でアキでもいい。（0が斜めに二つ並ぶだけ）
A２．図７～１０へ行くのは可です。
ただし爆弾数を減らす操作になるので多用できないです。
A３．アキ→爆弾は不可。というか詳しく調べてない。
たぶんアキの数字をどこかで利用すると破綻するじゃないかと。
基本、○をあまり使わなければ、爆弾数多くなるので減らす方向で。
A４．？じゃアキでなくてもいいところを適当に埋めた例。
A５．図２１は間違い。直すの忘れてた。
A６．○や×を置けば爆弾かアキに確定できるから。
○の下の数字と旗の数があっているところ、
×の下の数字と（周囲の数-旗の数）があっているところから
順番に埋めればいい。
なぜかと言うのは、アキに表示される数字が確定した時点で
実際に数字を埋めればわかるかも。いや、俺が間違ってるかもしれんけど…
たとえば図８なら表示は０５１になっているです。
○や×はその場の最大最小値に相当なのでどこにでも書けるわけだし。
あとは夜にでも書きます。
199:82
07/05/17 08:46:36
いや０５１→０５２ですね
200:1
07/05/17 09:23:29
>>198
なるほど、それぞれの操作はだいたい把握できたかも。
解説ありがとう。
「○や×を図３や図４のように、置けるかぎり目いっぱい置く」って場合には、数字が決定できるのはたしかにその通り。
（もちろん８方向のうちで、すでにアキか爆弾か決定している場合はそこを避けて置くことになる）
ちなみにこの方法のみを使って、地雷を配置したものが>>154の「明らかに～」の実装です。
で、図８まで決定すると、表示値は０と５と２になるとのことだけど、図７の灰色の「？」や空白には、爆弾がある可能性もあるんだよね？
何かそこらへんがごっちゃになって、どういうふうに数字が決定していくのかが、ちとまだ難しい・・・。
201:67
07/05/17 10:23:30
よく考えたら(って考えるまでもないけど)>195みたいなのって要は出題型パズルなんですよね。
それこそピクロ(ry とか同様。もう少し地雷を多めにして「必ず解ける」を満たせれば
パズルとして成立できるかも。パズル作家に提案だけしてみようかなw
#あ、スタート地点候補も提示する必要があるのか。
202:82
07/05/17 12:38:38
>>195 201
それいいですね。一問数十バイトで記録できるんだし
iアプリとかにしたら結構流行りそう。
>>200
説明わかりにくくてすいません
よく考えたら△のあるオプション方だけでよかったです
爆弾少なくなりそうなときだけ○設置を思いとどまればいいだけか。
2つのパターンは90度回転すれば対象だから事実上パターン一個に統合できそう
また夜に画像書き直しおします
203:デフォルトの名無しさん
07/05/17 12:45:40
わからん。 一通り読んでみたけど、文字だけじゃ何をいってるのかさっぱりわからん。
俺の理解能力のなさに乾杯。
204:1
07/05/17 14:49:26
>>154を拡張して、2マスから推論のみで解けるような配置にしてみました。
実装：URLﾘﾝｸ(www.geocities.jp)
実はこのスレ立てた当初は、これくらいのものが実装できればいいなあと思ってました。
でも色々考えていくうちに、>>182みたいなちょっと頑張って考えればできるやつとか、>>164みたいなのもあっていいよなぁと思うようになってきたので、もうちょい性能アップさせたいです。
つーか、何かよく観察すると、>>154のときにも見られた、地雷配置の偏り（妙に地雷同士が寄り添っている）があって、どうにも解消できない。
あと、何度もやってると、④と②の数字がやたら繰り返し現われて格子状に地雷が配置されてたりとか、訳がわからない。
なるべく「癖のある出題」にならないような地雷配置を目指したいところです。
205:1
07/05/17 14:59:35
というわけで、課題はまだまだ山積みなんだけど、JavaScriptでの実装は今回でお終いにしたいなぁと思います。
もうコードがスパゲティになりすぎてリファクタリングする気になれないｗ
最後に作った関数なんか、400行を超えとります。
あと、HashMapとかSetとかPriorityQueueとか基本的なADTが気軽に使えないので、精神的に限界です。
もう１から書き直したいorz
でもJavaScriptを久しぶりに書いて、すごい楽しかったなぁ。
いちおうこれからの予定としてはC++を考えてます。
Cで書こうとも思ったけど、STLの存在が頼もしくなりそうなので、C++でいきます。
ただ、GUIのプログラミングとか慣れてないので、まず取っ掛かりに時間がかかるかもしれないです。
ウィンドウってどうやって作るんだっけ？ビットマップってどうやって描画するんだっけ？とかそんなレベルです。
まあ気長に行きましょう。
206:デフォルトの名無しさん
07/05/17 15:01:55
ﾊﾞﾝｶﾞﾚ
207:1
07/05/17 15:07:12
>>201
自分で配置を考えるって形も、色々できて面白そうだね。
必ず解けるような地雷配置ってのが、一発目のクリック位置に依存するあたりとか、難しい問題ははらんでるけど、ちょっとずつマインスイーパの裏に潜む事実がわかってきてるから、将来的にはフレキシブルに対応できたらいいな。
>>202
アイデアはすごいおもしろいし、規則性がガッチリ見えてきたら使えそうな気がするよ。
画像のほう楽しみにしてます。
>>203
すいません、たぶん一番ダラダラ文章書いてるの俺ですｗ
208:1
07/05/17 15:07:56
>>206
おぉありがとう！ﾊﾞﾝｶﾞﾘます！
209:82
07/05/17 22:49:18
とりあえずうpします。というか、
下段の画像の13,14が抜けてるのに今気づいたけどそのままです。
(未確定領域を爆弾で囲んでないかの判定・回避は別にあると仮定してます。)
URLﾘﾝｸ(smallup.dip.jp)
210:1
07/05/18 02:26:25
>>209
ばっちりわかりました！
実は、「１つの数字のみ参照して決定」と「２つの数字から決定」を使うやり方は、>>204で実装したものと非常によく似てるかも。
デバッグのオプションをつけたので、一番上のコンボボックスからは「初級」か「中級」、「2マス推論で解けるように配置」を選び、デバッグにチェックをつけて、適当なマスをクリックしてみてください。
URLﾘﾝｸ(www.geocities.jp)
あ、くれぐれも「上級」でデバッグにチェックしないほうがいいです。
恐ろしく時間かかりますｗ
「中級」もちょっと時間がかかるかもしれないので、辛抱強く待ってください。
デバッグで表示された盤面で、？は「見て」いるところで、その？から爆弾かアキが決定してるのは「次の盤面」であることに注意してください。
Expandは１つのマスだけ見てる場合を、Inferは２つのマスを見ていることを意味してます。
真っ白なマスは、最初にクリックした場所です（画像が少ないのでｗ）。
211:1
07/05/18 02:32:36
で、すごく参考になったのが、相互に反転できるグループを作るって点です。
今の俺のやり方だと、爆弾やアキの個数が最後におかしくなったときは、ランダムにむりやり変えて強行突破してます（「必ず解ける」かどうかわからなくなるので、警告メッセージが出ます）。
とりあえず、あるマスを「見る」という作業が、そのグループの相互反転をできなくする条件ってことでおｋですか？
212:82
07/05/18 08:59:32
それでおkです。
厳密にいうと2地点参照のパターンでは、
参照位置が隣あっている必要はなく、共有部が2が本来の条件ですが
それを定義にすると同じ位置を何度も参照した場合、矛盾しそうで、
まだその辺の処理があまく、隣あっているものに制限して成立させてます。
213:82
07/05/18 09:07:55
携帯からなんで最新の実装はまだ見てません。
見たら改めてコメいれます
214:1
07/05/18 13:49:26
>>212
それじゃひとまず、地雷を配置していって最後の方で個数がおかしくなったときは、グループで反転の処理を作ってみます。
えーと、それで、２マスから推論するパターンについては、隣同士じゃないものも気にせず含めて実装しちゃってます。
基本的に問題ないっす（理屈上、大丈夫っぽい）。
あとデバッグ表示にちょっとだけ色をつけてみたよ。
赤は地雷を置く場所で、青は地雷を置かない場所になっとります。
ランダム＋コンピュータに解かせてみるバージョンのやつも、デバッグ表示してみると楽しいかも。
215:デフォルトの名無しさん
07/05/18 15:03:32
URLﾘﾝｸ(www.geocities.jp)
のやつやってみた。(最新URLここであってる？）
初級-ランダムに地雷を配置
デバッグ:off
展開、旗立、推論、完了:on
失敗しても～:off
×のとこでボムりました。
たしか一番左上クリックしたハズ
□□□□□□□□□
□□□□□□□□□
□１×２１□１２２
□１♪♪２□１♪♪
１２３♪２□１２２
♪１２２２１１１□
１２３♪２１♪１□
□１♪♪２１１１□
□１２２１□□□□
□＝空いてるマス
♪＝旗
216:デフォルトの名無しさん
07/05/18 15:36:11
>>215と同じ条件で
+------
|○１■
|１２■
|■■■
○＝最初のクリック
■＝閉じてるセル
で、とまった。
こんな報告はいらない？
217:1
07/05/18 16:42:19
>>215
最新版はそこであってます。
確かに、地雷を置き過ぎて放置してしまうケースがあるみたいです。
見直してみるので、お待ちください。
>>216
ランダムに配置した場合には、そうなることもあるかと思う。
あ、でも「解けるような配置」をした場合にも、そういうケース（>>209でいう「囲んでいるかどうかの判定））をちゃんと検出してないので、それも改善しないとです。
報告はどんな些細なものでもありがたいです。
218:1
07/05/18 17:50:46
>>215
すいません、バグでしたorz
直しました。
219:82
07/05/18 19:06:37
>>214
最新版やったけど、解けるような配置より、ランダムのが面白いみたい...
良問かどうかの評価関数いれるとか。爆弾増やすとか大変かな。
それと裏側が見えないからこその２マス推論なので、
２マス隣同士でないと共有部分をはさむことになって、結局両側を開いてしまい
ネタばれするっぽい。なんかいらないんじゃないかって気がする。
220:1
07/05/19 02:02:29
>>219
>最新版やったけど、解けるような配置より、ランダムのが面白いみたい...
そうなんです、そこは是非解決したいっす。
たぶん、ランダムってのは、「良問」という点では一番最適なんだと思う。
「解けるような配置」をすることで、「意図」が入り込んでしまい、出題に「傾向」が生まれてしまう・・・。
たぶん、「いかにランダム出題に近づけるか」っていう目標になっていくと思う。
評価関数を使うのは、たしかに有効な手段かもしれない。
221:1
07/05/19 02:05:22
>>219
>最新版やったけど、解けるような配置より、ランダムのが面白いみたい...
そうなんです、そこは是非解決したいっす。
たぶん、ランダムってのは、「良問」という点では一番最適なんだと思う。
「解けるような配置」をすることで、「意図」が入り込んでしまい、出題に「傾向」が生まれてしまう・・・。
たぶん、「いかにランダム出題に近づけるか」っていう目標になっていくと思う。
評価関数を使うのは、たしかに有効な手段かもしれない。
222:1
07/05/19 02:06:11
>ネタばれするっぽい。
ネタばれというのは、プレイヤーに推論させようと思って地雷配置したけど、実は推論しなくても確定できてしまう状況のことだよね。
実は「ネタばれになる条件」は、推論用に注目している２マスがその時点で共有しているマス（例えば隣同士を推論に使うなら最大４マス共有され得る）が、もっと後の決定で「全部地雷」か「全部アキ」になると、結局ネタばれしてしまう。
つまり、推論しなければ解けないようにするには、共有してるマス内の地雷数は、「中途半端」な数であってくれる必要がある。
（実はこのことが、推論するためには「共有マス」が最低２つ必要な理由になってます。
もし１マスしか共有してなかったら、地雷数は０か１という明らかに決定可能な数値にしかならないため）
一方、>>209でも考察している通り、周囲で共有してないマスに関しては、「全部地雷」とか「全部アキ」みたいに「両極端」になる必要がある。
その点では、注目２マスが「隣か隣じゃないか」よりも、そもそも何も考えず決定範囲を広げていくことが問題なのかもしれない。
解決法の一つとしては、推論のとき（というか推論相当の地雷配置をするとき）に共有マスの地雷orアキに関しては、「微妙に決定」な状態（例えば>>187で出してくれた中で、「△」を使うような雰囲気）にするといいかも。
後々その△マスを決定するときには、「確率」を操作することでネタばれを減らせるんじゃないかと思う。
（評価関数を使うのと、意味的には近くなるかも）
223:67
07/05/19 07:39:33
確かに推論版は簡単ですねぇ。偏るから当てずっぽうに開けやすいし読みやすい。
多分タイムアタックやったらランダム版よりかなり早いと思う。
224:1
07/05/19 08:46:36
>>209の、グループごとに反転できる機能つけました。
最新版：URLﾘﾝｸ(www.geocities.jp)
まあぱっと見はあまり変わってないけど、より確実に配置できるはず。
あ、あとたまたま簡単だったので、「隣マス推論で解けるように配置」も加えておきました。
やっぱり「ネタバレ」はどうしても起こってしまうらしい。
225:1
07/05/19 08:49:30
>>223
たしかにその通りorz
まあ実際、ランダムの場合は「解けない場合」すらあるわけだから、「必ず解ける」ようにすると、ランダムより簡単になってしまうのは避けられないかも・・・
あ、でも、「推論でしか進めない」ような配置を意図的に増やすことができたら、もっと面白くなるかもしれない。
がんばろー
226:デフォルトの名無しさん
07/05/19 09:53:11
いまいじってみたけどなんか格好いいね。応援しています。
ところでこのソースぱくらせてもらってもいい？ライセンスとか決めてあるのかな。
独自アルゴリズム(まだ考えてないけど)試したくなってきた。
227:1
07/05/19 10:14:48
>>226
どもども。応援ありがとう。
ソースはどんどん使ってくれていいよ。
ただ、ちょっと汚くなってきたから、いじりにくいかもｗ
もしいい考えが出てきたら、レスくれるとありがたいです。
228:1
07/05/19 11:21:46
今まで勝手な勘違いでつけてた制限（一度推論に使ったマスは、それ以上推論に使わない）を外してみたら、ずいぶんマシになったかも。
相変わらず地雷同士が近寄ってしまうのはあるけど、妙に作為的なパターンは減ったと思う。
最新版：URLﾘﾝｸ(www.geocities.jp)
229:67
07/05/19 11:40:19
>>228
確かに大分よくなったかも。
処で、地雷の数を多めにしたり少なくしたりして試してみるとまた違うものが見えるかもしれない。
地雷数が今上級で20%くらいだと思うけど、25%越えるとかなり違う世界になるから。
中級くらいの広さの25%だと面白いかも。
#いや、それこそ推論で解けるケースが減るわけですが。
230:1
07/05/19 15:59:15
>>229
そういえば、今まで盤面のカスタマイズ機能をすっかり忘れてたorz
というわけで、実装いたしました。
最新版：URLﾘﾝｸ(www.geocities.jp)
25%くらいでも、けっこう推論で解ける配置が作れるかも。
かなり地雷多いのに、最後まで論理だけで解けたし！
30%あたりになると、配置に失敗するケースが出てくるっぽい。
でも50%くらいまで行くと、逆に配置しやすくなって、攻略も楽になるｗ
231:1
07/05/19 18:01:25
JavaScriptはもうおしまいの予定でしたが、まだまだお世話になりそうです。
こんなにコードが長くなるなら、最初からもっと真面目に書けばよかったorz
とりあえず、>>222に書いた、推論させる上で必要だけど決定しないマスの確率をどうやって割り当てようかをずっと考えてるけど、全然いい考えが浮かばない。
それぞれの推論自体に関係した確率（中途半端な地雷数÷共有マス数）と、盤面全体での地雷数による確率（地雷数の合計÷（幅×高さ））をどうやって結びつけたらいいんだろう？
232:デフォルトの名無しさん
07/05/19 23:39:18
つまり島状に囲まれて飛び地になった場所は絶対出来ないっていう意味ですね
だけど囲まれ方が
□□□□□□□□
□●●●●●●□
□●□□□□●□
□●□□□□●□
□●□□□□●□
□●□□□□●□
□●●●●●●□
□□□□□□□□
だと中に入れないけど
□□□□□□□□
□●●●●●●□
□●□□□□●□
□□●□□□●□
□●□□□●□□
□●□□□□●□
□●●●●●●□
□□□□□□□□
こんな形なら中に入っていける可能性あるよね
概出？
233:デフォルトの名無しさん
07/05/19 23:42:32
あ、
>最新版：URLﾘﾝｸ(www.geocities.jp)
ここって
人間が地雷置いてコンピュータに解かせるっていう機能はないんだっけ？
234:82
07/05/20 01:25:34
>>231 >>222 2マス隣同士なら7割ネタばれ
離れていると、ほぼ99.9％ネタばれして消滅って感じなんだけど
数学的に難しすぎて証明できないぉ。
ランダム配置→2マス隣同士の応用で合否判定する感じの、
Javaでやってみた。
旗立て自動。ほかの機能ないけど。
自分で10回くらいやったけど、解けるのしかでないっぽい。
URLﾘﾝｸ(smallup.dip.jp)
235:1
07/05/20 01:55:30
>>232
えっと、一発目のクリックは一番外側ってことかな？
配置中に上の方の図の状態になったら、「囲まれた」という風に認識して、その場合には地雷の数を減らすことで、問題を解決してるよ。
ただし特例として、内側の16マスに一つも地雷がない場合（つまり地雷の総数を20個に設定した上でそのように配置した場合）には、最終的に「残り～個」という地雷数表示から攻略できるので、「囲まれた」場合の解決はしていない。
下の方の図の状態は、「囲まれた」という風に見なさないようにしてあるよ。
236:1
07/05/20 01:57:28
>>233
あ、なるほど。
そういう機能もあったらいいかもね。
ちょっとつけてみようかな。
>>234
隣同士じゃない場合のネタバレ率は考えたことなかったなぁ。
そんなにネタバレしてたんだｗ
ちょっとJava版のほう試させてもらいます。
237:デフォルトの名無しさん
07/05/20 02:23:57
>>234
やってみました。
ばっちりできてるみたいだね。
これの配置アルゴリズムは、隣同士のみの推論をシミュレートするタイプ？
238:デフォルトの名無しさん
07/05/20 09:14:58
初心に戻って実際に解いて判定。1さんのに違いかも
2値推論で3×4枠を回しながら置けるなら同じ要領で逆に消せる
参照2値が離れているとバレるという仮説があってればその方が楽だし。
判定本体はjavaファイル上で一番下の関数だけどわかりにくいかな
239:1
07/05/20 10:52:07
>>238
おーなるほど。
「3×4枠を回しながら」の意味がやっとわかりました。
dr0～dr7ってのは、順々にたどっていくことで、注目する長方形が回転するようなイメージなのかな。
thinkingメソッドの中身はちょっと変数が多くて把握しきれてないですが、基本方針は俺のとほぼ一緒だと思います。
俺のと違って、地雷がキレイにばらけてますね。
なんで俺のは、あんなに偏るんだろうｗ
あと、いくつか細かい違いとしては、
・注目マスを見に行く順序（おいらのはランダムでやったり優先順位つけてみたり、試行錯誤しすぎてコードがぐじゃぐじゃｗ）
・それと俺のは、「注目する２マスを、使えるか使えないか」というところに、「共有部分でまだ未決定なものが２つなければならない」という条件を付け加えちゃってます。
さすがにこれが俺の偏りを生む原因になっているとは思えないんですが、>>234で書いてくれたコードも参考にしながら色々実験してみたいと思います。
240:1
07/05/20 11:04:17
>>238
あ、それと、「隣同士ではない２マスを使うとネタバレする」から、「そういう２マスは使わないべき」とおっしゃってますが、俺はそうしたくないんです。
ネタバレする確率が高いなら、その確率を減らすアルゴリズムを考えたいわけです。
（もし一切ネタバレせずに何とかなるようなアルゴリズムがあれば、さらに理想的）
なぜかというと、生成した地雷配置を攻略するときに、隣同士ではないものから推論できるような場面にも出会い得るような盤面にしたいからです。
さらに後には、３マス以上からしか推論できないものも積極的に入れていきたいです。
３マス以上による推論とは、例えば>>182とか>>164のように、「２マスだけからでは推論不可能」な配置です。
その意味では、有名な「１・２・１」は３マス推論ではなく、２マス推論と１マス推論の組み合わせです。
（１マスだったら「推論」と呼べるほどのものじゃないですが、一貫性を保つためにそう呼んでみます）
241:1
07/05/20 11:22:42
さて、>>233の「人間が手作業で地雷配置」の実装をしようと思ったんですが、自分のコードの汚さに眩暈がしてきてしまったので、これから大幅にリファクタリングします。
気分的には年末の大掃除みたいな感じです。
で、大掃除を始める前に、以前から薄々やりたいなぁと思っていたものを実装してしまいました。
その名も「敏感マウスモード」！
普通はマウスを押して、離したときにクリックしたことになるわけですが、敏感モードでは押した瞬間に反応します。
これの何が良いかと言うと、なんと連続するマスをドラッグで開けたりすることができるんです！
やってみたらけっこう気持ち良いじゃないですか。
Ctrlキーを押しっぱなしでマウスをグリグリ動かすだけでも攻略できたりします。
あと、ゲームオーバー時にテキトーな場所をダブルクリックで、「スタートボタン」を押したのと同じ扱いになったり、ちょこちょこ隠し機能を加えてみました。
最新版：URLﾘﾝｸ(www.geocities.jp)
（いつの間にかジオシティーズの広告が消えてるしｗ）