サイト内検索
Translation here

2016/02/06(土)マインスイーパーアルゴリズム(応用編)

この記事は概要からの続きです。
基本編ページ

計算の仕方:
1と2のそれぞれのセルでANDを取り、以下のルールで評価を行う。
・一致数
 →入力が?の場合は結果を問わず0とする
・不一致があった場合は評価値を-1にする
 →入力が?の場合は処理をスキップする

(全てのケースは別ページにまとめます)
今回は他のパターンは不一致で評価値0になるケースですが、以下のようにすると実践的になります。

例図
□|□|□|□|□|
□|□|1|2|□|
これも同じように考えてみましょう。
  • 1だけ
?|●|●|●|?|
?|●|1|2|?|
  • 2だけ
?|?|■|■|■|
?|?|1|2|■|
【凡例】
●:1だけの候補
■:2だけの候補
★:1と2の候補
?:いずれの候補でもない
?|●|★|★|■|
?|●|1|2|■|
同様のルールで評価の高い組み合わせは以下です。
以下はすべて1点です。
?|□|★|□|■|
?|□|1|2|□|
?|□|★|□|□|
?|□|1|2|■|
?|□|□|★|■|
?|□|1|2|□|
?|□|□|★|□|
?|□|1|2|■|
以下はすべて0点です。
?|●|□|□|■|
?|□|1|2|■|
?|□|□|□|■|
?|●|1|2|■|

?+?+?+?+?+?|□+□+□+□+●+□|★+□+□+□+□+□|□+★+□+□+□+□|■+□+■+□+□+□|
?+?+?+?+?+?|□+□+□+□+□+●|1+1+1+1+1+1|2+2+2+2+2+2|□+■+□+□+□+□|
(細かい内容は別ページにまとめます)

さて、最後に今まで出てきたすべてのパターンでORを取り、0になった場所は安全です。
この時の?は1とします。
(今回は例が良くないので安全地帯はありません)


別例で説明しましょう。
□|1|□|□|2|
□|□|□|3|□|
凡例
■:2→3
★:2→3
確:確定
●|1|★|確|2|
●|●|★|3|確|

分離します。

5点
□|1|★|確|2|
□|□|□|3|確|
□|1|□|確|2|
□|□|★|3|確|

 |1|★|確|2|
 |1|★|3|確|
この形まではできます。

配置は運ゲーですが、その際の最適な理論値は求められます。
これにアルゴリズムの話で最適解を求めるところまで突き詰めると
「最短クリック数でマインスイーパーを完了させる時、最短で何クリックで実現できるか」を測るのも面白そうです。
(空白である場所を探してクリックする等)

しかしこれを実装するとなると非常に難しい事に気づくと思います。
試しに6×6ぐらいでやってみるといいかも?

2016/02/05(金)マインスイーパーアルゴリズム(基本編)

この記事は概要からの続きです。
概要ページ

まずゲームを始めた時に適当にポチポチ押す瞬間が発生しますが、この瞬間からゲームは始まるわけです。
私はいつも四隅を押さえるようにしています。その方が特定が楽なのと、後半戦で「どっちか」押さざるを得ない状況が生まれやすいからです。

具体的には以下のような図です。
□|□|□|□|□|
1|1|1|1|1|
ケースバイケースですが、この図は以下の可能性があります。
■|●|1|■|●|
1|1|1|1|1|
中央は安全ですが確実に1と出るので何の参考にもなりません。
つまり■と●の二通りが出た時にはじめてユーザーの判断を待つようにします。

ではこれを発展させましょう。
□|2|□|□|1|
□|2|1|2|□|
これは比較的簡単にできますね。
では解いてみます。
□|2|□|□|1|
□|2|1|2|□|
この時、未確認ブロックで確定している情報は以下の通りです。
・右2を挟むように爆弾がある。
・右2の上、右上1の左隣は2である。
□|2|■|2|1|
□|2|1|2|■|
さて、この時は未確認ブロックで確定している情報はどちらかに爆弾があり、どちらかは1である事です。
が、どちらなのかは分からないのです。
(こういう事が起こるから四隅はさっさと抑えてしまいたいですね)
  • やりたいこと
1の場合は自動化したい
2の場合はそこで止めてほしい

2は比較的楽です。
問題は1の実装。

今、このように簡単に述べましたがどういうケースなのか、真面目に考えてみたいと思います。
まず最初に1を順番に見ていきます。
  • A案
?|×|●|□|1|
?|×|1|×|●|
  • B案
?|×|□|●|1|
?|×|1|×|□|
(紛らわしいので2は×に置き換えています)
1の候補だけでも黒塗りの数だけあります。
実際に置くと上記2パターンが候補になります。
?は使われないものなので、明示的にするために分けました。
理由は後述します。


続いて2の候補についてフォーカスしましょう。
と、言いたいところですが実は全てが候補です。
ちょっと分かりにくいので一つずつフォーカスしましょう。
  • A案
●|2|●|●|×|
□|2|×|2|□|
  • B案
●|2|●|□|×|
□|2|×|2|●|
  • C案
□|2|●|●|×|
●|2|×|2|□|
  • D案
□|2|●|□|×|
●|2|×|2|●|
  • E案
●|2|□|●|×|
●|2|×|2|●|
(紛らわしいので1を×に置き換えています)
上記が2だけで考えられる全パターンです。

3はないので1・2で考えた時にANDを取ると最も評価値が高いパターンは以下の2通りができます。
ただし、?は任意の値が入るものとします。
  • 8点
1のA案
?|2|●|□|1|
?|2|1|2|●|
2のB案
●|2|●|□|1|
□|2|×|2|●|
  • 8点
1のA案
?|2|●|□|1|
?|2|1|2|●|
2のD案
□|2|●|□|1|
●|2|1|2|●|
【考え方】
ここから一気に難しくなります。ついてきてくださいね?

マインスイーパーアルゴリズム(応用編)

2016/02/04(木)マインスイーパーアルゴリズム(概要)

のむらです。
技術的な記事を扱う事に主軸を置いたコンテンツですが、最近はコラムばっかり書いてる気がしますね…

さて、今日は更に息抜きでゲームの話をば。
と言ってもゲームで遊びましょう、というのでは芸がないのでちょっと技術よりです。
普通にマインスイーパーを遊ぶ話は日常系の方をご覧ください。
window10でマインスイーパーやソリティアを遊びたい!|きょうのごろーさん


爆弾数が1のマスを見るとバシバシ押しまくりたくなるんですが、もう何十回もやってると分かり切ってるところはプレイアシスト的にガシッと埋めてくれないかなぁ、と思ってくるんですよね。
というのも、最初のうちは純粋に楽しいんですが興が乗ってくるとスコアプレイを目指してしまう。

プレイ環境がスマート端末という事もあり、なまじ画面が広くて正直スクロールしてまでサーチするのが面倒くさい。
その上、クリック(タップ)ミスがひどい事になる(原因は連打とグラフィカル部分の処理落ち)

ということで思考放棄をしたに近い覚醒状態でもポチポチやりたいワケです。
アプリケーションの何らかのアクションにフックするとかそういうレベルまで来ると全然別の話になるのでここではそこまで言いません。
が、ざっくりアルゴリズムっぽい話を。
同期の最適化とかその辺まで行くと血管がいくつ切れるか分からないので投げます。
あと、そもそもゲームの放棄とも取れるので、ゲーム性については言及しないように。


では実例を交えてみていきましょう。
ちょっと長いので休憩を入れましょう。


マインスイーパーアルゴリズム(基本編)
OK キャンセル 確認 その他