運ゲー排除マインスイーパー💣脱Unity計画（Android編）＆SATによるソルバー改良

この記事は KMC Advent Calendar 2018 - Adventar の6日目(12/6)の記事です。

5日目の記事は、id:opesanさんの聖地巡礼記2018 - おぺの日記でした。

神戸異人館は何年か前に行ったのですが、確かFateの遠坂邸とかもありましたよね（Rewriteもアニメは見てました）。

はじめに
- 更に1年経ってみて
脱Unity
ソルバー改良
その他
- スクショ共有
- 遊び方動画
現状＆まとめ
終わりに

はじめに

KMC6年目のdamaです。 Twitter等ではDNEK(でぃーねっく) (@dnek_) | Twitterと名乗っています。道を踏み外して京都大学文学研究科修士2回生となっているはずが、更に踏み外してフリーランスのようなことをしつつ自分のアプリも作っています。

この記事を読むのが面倒な人は、とりあえずアプリだけインストールして行って下さると嬉しいです。

更に1年経ってみて

毎年12/6にKMC Advent Calendarの記事だけを書くのもこれで4年目になりますが、去年はこんな感じでした。

今回のタイトルと矛盾していますね。

脱Unity

今までの記事でマルチプラットフォーム対応ゲームエンジンとしてヨイショしてきたUnityですが、色々あってオサラバすることにしたのでその経緯を綴っていこうと思います。

プライバシーポリシー

若干話題が逸れますが、↑の去年の記事から引用します。

そもそもプライバシーポリシーって何かと言うと、「私はあなたのこういう個人情報をこういう方法で使おうと思ってるんですが、いいですか？」という契約文書です。日本語だと個人情報保護方針というやつですね。法的な話もありますが、とりあえずPlayStoreやAppStoreでは、「アプリが個人情報を扱うならそれについてポリシーを示せ」と決められているのです。
Unityで漢字パズルアプリを作ったよ(Android/iOS) - dnekblog

実はUnambiSweeperの方も既にFirebase Analyticsを使っているので、早い内にポリシーを示すように更新するつもりです。
Unityで漢字パズルアプリを作ったよ(Android/iOS) - dnekblog

いつ削除祭りがあるのか分からないので、自分のためにもユーザーのためにも先んじて対応しておこうと思います。
Unityで漢字パズルアプリを作ったよ(Android/iOS) - dnekblog

そして10月のツイートです。

UnambiSweeperのプライバシーポリシー更新をサボっていたのでAndroid版がストアから削除されてしまいました。
新規インストールされる方は修正して再配信されるまで暫くお待ち下さい。
ニジウメは更新してあるので大丈夫です。

ちゃんと配信されているアプリはこちらから↓https://t.co/Xflqxev5KE
— DNEK(でぃーねっく) (@dnek_) 2018年10月3日

誠に申し訳ございませんでした🙇

Unityつらい

そういうわけで散々更新をサボりまくっていた私も流石にマズいと思い1年ぶりにUnityのプロジェクトを開いたのです。

とりあえずビルドしてアプリを起動しプレイしようとレベル選択ボタンを押すと、・・・アプリが落ちる。

どうやら1年前の私はリリース以降何かをイジってそのまま放置していたみたいなのですが、何をどうイジったのか全く分からない。エラーログを読んでも何故落ちるのか分からない。そもそもバージョン管理をしていなかったのが悪いのだが。

それでももっと根を詰めて時間を掛ければ直るのかもしれませんが、ここでUnityを続けて行くかどうかの天秤が傾き、

バージョン管理が面倒くさい（これは古い情報かもしれません）
単純な2D描画しかしないのにファイルサイズが大きくなり過ぎる
アプリの起動も遅くなる
ビルドも遅い
iOS/Androidを共通化した分、それぞれの痒いところに手が届きにくい（結局ネイティブコードを書かないといけない）
AndroidのManifest, Gradle, ProGuard辺りの設定が面倒
Androidのタッチレスポンスが若干遅い（マインスイーパーのようなアクションゲーにおいては致命的？）
ScrollViewの動きがもっさりしている
uGUIが微妙（リップルエフェクトが無いとか）
PlayerPrefs（データのセーブ/ロードを扱うクラス）にBooleanが無い（Intで代用していた）

などなど後の方はどうでも良いかもしれませんが、こんなものに時間を掛けるよりもネイティブでそれぞれ最適化した方が早く良いものができるだろ、と思いUnityを捨てる決意をした訳です。

ちなみに言うと、最近お仕事でSwiftを触っているため学習コストが下がったというのもあります。

Kotlin

脱UnityということでiOSとAndroidをそれぞれネイティブで作っていくのですが、どちらから作るかといえば当然削除されてしまったAndroidです。

そして今回は色々改めるということでKotlinデビューをすることにしました。

KotlinというのはJavaを簡潔・安全になるように改良したイケイケ言語で、Android Studioでも標準で使えるようになっており既存のJavaコードをKotlinに変換してくれる機能も付いています。

一つ個人的に不満な点として、三項演算子がありません。

Javaだと

hoge = a > b ? a : b;

となるのが、Kotlinだと

hoge = if (a > b) a else b

という感じになります。

それでも型推論付き静的型付けとかnull安全とか文字列テンプレートとか総合的にはKotlinが勝っていると思います。

また、Kotlin 1.3からstableになったCoroutinesというものがあります。

blog.jetbrains.com

これは「特定のスレッドに束縛されない、中断可能な計算処理インスタンス」で、とりあえず非同期処理が簡単に書けて便利です。

私はマインスイーパーソルバーをUIスレッドの外で動かしたり、マインスイーパーソルバー内で並列処理をするのに使っています。

描画処理

さて、脱Unityにおいて一番問題となるのが描画処理です。

UnambiSweeperは元々Android Javaでネイティブアプリとして書いていたのですが、当時描画に使っていたSurfaceViewがゴミであることが分かりUnityに移行した経緯があります。

様々なView達

ここにAndroidでの描画方法が大体まとまっています。

quesera2.hatenablog.jp

内容を補足しつつざっくりまとめると、

(Custom) View
- 元々低速だったがAndroid4.0以降ハードウェアアクセラレーションが適用されてまあまあ速い
SurfaceView
- 別スレッドから描画できるので高速だったが、ハードウェアアクセラレーションが適用されないので今では通常のViewに負けている
TextureView
- SurfaceViewの代替としてAndroid4.0で登場し通常のViewに組み込める上にOpenGLで描画してくれるが、Bitmapを延々と生成するだけでメモリ消費が半端なく電力消費もヤバい
- Android7.0以降ではSurfaceViewもViewと同期できるようになりTextureViewは下位互換と化した

というわけで結論としてはCustomViewを使え、もっと高速に描画したいなら今流行りのVulkanを使えということらしいです。

私としては、VulkanはAndroid7.0以降が必要なので現在のシェアを考えると却下、CustomViewも十分な速度が出るか不安でした。

GLSurfaceView

じゃあどうするのかと言うと、↑の記事で奇特と一蹴されてしまったGLSurfaceViewを使います。

まあ奇特と書かれている通り、私も以前は面倒臭そうと思って見て見ぬふりをしていましたが、 OpenGL ESで描画出来て速いということを否定する意見は見当たらなかったので思い切って学んでみることにしました（ちゃんと設計すればTextureViewみたいにメモリも食わない）。

最初に雰囲気を掴むのにこのサイトが良かったので紹介しておきます。

独学で 1 ヶ月間 OpenGL を学んで得た基礎知識のまとめ ~ 2D 編 ~ · けんごのお屋敷

OpenGL ESにはいくつかバージョンがあり1.0と2.0以降でほとんど別物になってるようですが、2.0はAndroid2.2以降で使えるので今ならまず問題ないでしょう。

OpenGL ES | Android Developers

実際に学んでみたところ、確かにコーディング量自体は多いのですが、やっていること自体は合理的で納得できるものでした。少なくとも2Dの範囲であれば努力に見合う成果が得られると思います。

VBO/IBO

また、↑の入門記事には載っていませんが、大量のマスを効率的に描画するのにVBOとIBOをガンガン使っています。

VBO (Vertex Buffer Object) 及びIBO (Index Buffer Objext) は、何度も繰り返し使う頂点座標及びインデックスを予め登録しておくためのものですが、インターネット上にあまり良い資料が無くて苦労したのでざっくりと使い方を書いておきます（入門記事を読んでいる前提で説明します）。

object BufferUtil {
    fun convert(data: FloatArray): FloatBuffer {
        val bb = ByteBuffer.allocateDirect(data.size * 4)
        bb.order(ByteOrder.nativeOrder())

        val floatBuffer = bb.asFloatBuffer()
        floatBuffer.put(data)
        floatBuffer.position(0)

        return floatBuffer
    }

    fun convert(data: ShortArray): ShortBuffer {
        val bb = ByteBuffer.allocateDirect(data.size * 2)
        bb.order(ByteOrder.nativeOrder())

        val shortBuffer = bb.asShortBuffer()
        shortBuffer.put(data)
        shortBuffer.position(0)

        return shortBuffer
    }
}

BufferUtilはHello World in OpenGL! · けんごのお屋敷のJavaコードをKotlinに変換して使わせていただいています。

fun makeBufferObject(buffer: Buffer, size: Int, target: Int): Int {
    val id = IntArray(1)

    GLES20.glGenBuffers(1, id, 0)
    GLES20.glBindBuffer(target, id[0])
    GLES20.glBufferData(target, buffer.capacity() * size, buffer, GLES20.GL_STATIC_DRAW)
    GLES20.glBindBuffer(target, 0)

    return id[0]
}

bufferにはBufferUtilで配列をconvertしたもの、sizeにはバッファーの1要素のバイト数（Floatなら4、Shortなら2）、targetにはVBOならGLES20.GL_ARRAY_BUFFER、IBOならGLES20.GL_ELEMENT_ARRAY_BUFFERを入れます。

fun getVerticesId(left: Float, right: Float, top: Float, bottom: Float) =
    makeBufferObject(
        BufferUtil.convert(floatArrayOf(left, top, left, bottom, right, top, right, bottom)),
            4, GLES20.GL_ARRAY_BUFFER)

頂点座標はこのようにまとめておくと良いでしょう。

あとはvertexIdとindexIdを保持しておき、レンダラーのonDrawFrame()で

GLES20.glBindBuffer(GLES20.GL_ELEMENT_ARRAY_BUFFER, indexId)
GLES20.glEnableVertexAttribArray(attLocPosition)
GLES20.glBindBuffer(GLES20.GL_ARRAY_BUFFER, verticesId)
GLES20.glVertexAttribPointer(attLocPos, 2, GLES20.GL_FLOAT,false, 0, 0)
// unbind with 0.
GLES20.glBindBuffer(GLES20.GL_ARRAY_BUFFER, 0)
GLES20.glDrawElements(GLES20.GL_TRIANGLE_STRIP, 4, GLES20.GL_UNSIGNED_SHORT, 0)

みたいにすればOKです（最後は雰囲気で）。

ソルバー改良

こうしてネイティブにすることによる懸念は消え去ったわけですが、折角作り直すのだから他の部分も改善しよう、ということで一番大事だと思ったのが、ソルバーの改良です。

運ゲー排除とは

運ゲー排除マインスイーパーは、プレイヤーの皆さんに論理的に解ける盤面を提供するために、各盤面が論理的に解けるかどうかの判定を内部で行っています。

もう少し詳しく言うと、内部にマインスイーパーを解くAI（ソルバー）が居て、このソルバーくんは論理的に解ける所まで解いていって、これ以上は論理的に考えても分からん、となったら運ゲーだと判定してくれます。逆に最後まで解けたら、これは運ゲーではないと判定します。

そして実際にプレイヤーに盤面を提供する流れは、

プレイヤーが最初に開けたいマスをタップする
そのマスと周囲8マス以外にランダムに地雷をバラ撒く
ソルバーくんが解く
運ゲーと判定されたら2に戻る、運ゲーではないと判定されたらプレイヤーに提供してゲーム開始

となっています。

さて、ここで問題となるのは、このソルバーくんに論理的に解けるはずの盤面を解かせてみても運ゲーと判定してしまうことがあるということです。

要するに、今までのソルバーくんは運ゲーを「これは論理的に解ける」と誤解してしまうことは無くても、よく考えたら論理的に解けるはずでも「ちょっと自分の頭では分からんな」となることがある訳です。

これの何が問題かと言うと、本来出題されるべき難しい盤面が出題されず、全体的なレベルが下がってしまっているということです。

ソルバーの仕組み

そもそもマインスイーパーのソルバーってどうやって実装するんでしょう？

申し訳ないのですが、詳しいことは秘密です。私の収入源なので。

ただ、おおまかなポイントを何個か紹介していきたいと思います。

全探索

まず、一番ナイーブな方法として全探索があります。

つまり、ある時点で開いていないマスに地雷を配置する全てのパターンを列挙し、どのパターンでも地雷が配置されないマスがあったらそこは安全と判断して開き、次の時点を考えるというのを繰り返すものです。

これは絶対に運ゲーが排除できる単純かつ素晴らしい方法ですが、計算に物凄い時間が掛かる可能性があります。

例えば↓の盤面では、開いていないマスが421個、その中に地雷が99個隠れています。

実際にはこうなっています。

これが分かっていないとして、一体何パターンの配置を考えれば良いのかと言うと

$_{421}C_{99}=243332982655566090675703797315807061004280051114317154993140882340226279607571333586485745193293500$

ざっと $2\cdot10^{98}$ 通りといったところです。

大体の目安として1000万通り処理するのに1秒掛かるとすると、 $7\cdot10^{83}$ 年以上掛かります。

少なくとも我々が生きている間に計算が終わることはないでしょう。

隣接マス

よく考えてみると、上の方の数字マスに隣接しているマス以外はどこに地雷があったところで運ゲーかどうかの判断には関わり得ないですよね？

すると、今回考慮に入れるべきマスは数字マスに隣接している42マスとなり、この中に0〜42個を入れる組み合わせを考えれば良くなります。

つまり42マスそれぞれについて地雷があるかどうかを考えてみれば良いので、

$2^{42}=4,398,046,511,104$ 通りになります。

これなら約5日間で済むので、生きている内に分かりそうです。

地雷数確定マス

ただ、生きている内と言っても1回プレイするのに何日も待ちたくは無いですよね。

そこでもっと人間的な手法を導入してみましょう。

まずは開いていないマスの数と地雷数が一致する場合です。

特に角が1であるような場合は分かりやすく、そこが地雷だと確定するのでその隣にも1があればそこに隣接する他のマスは全て安全となります。

当たり前の話をしてしまいましたが、まずはこういう所から考えて、少しでも組み合わせを減らしていくことが大事です。

隣接数字マス

次に、ちょっとマインスイーパーをやったことがある人なら皆やっているであろう、数字マス同士の比較です。

例えば、有名なパターンとして1 2 1が並んでいたらそれぞれの1の下に地雷があって2の下は安全、みたいなのがありますね。

これをもう少し一般化することで、かなりのパターンが解けるようになります。

今回の盤面であれば、自明なものもありますがとりあえず数字マスは全部で36個見えています。

共通の隣接未開マスを持つ数字マス同士を2個ずつ比較していくと、大体100通りくらいに収まるでしょう。

3個以上の隣接数字マス

ただ、この方法では解けないパターンが存在します。

例えばこんなパターンがあるとします。

?  ?  ?  ?
?  3  2  💣
?  2  2  1
?  💣 1

これはどの2つの数字マス同士を比較しても情報が出ません。

しかし、左上の3と左下の2、右上の2の3個を同時に比較することで、

💣 ?  ?  ✅
?  3  2  💣
?  2  2  1
✅ 💣 1

これだけ推定できます。ここまで来れば恐らく他のマスも解けるでしょう。

これで解決と思うかもしれませんが、この比較する数字マスを3個以上に増やしてしまうと、結局数字マスの組み合わせが爆発的に増えてしまい何日も掛かってしまうことになるのです。

SATソルバー

そういうわけで結局部分的に全探索する羽目になる場合があるのですが、実は比較的効率良く組み合わせを探索する方法があります。

それがSATです。

充足可能性問題 - Wikipedia

詳しくはWikipediaでも読んで欲しいのですが、とある組み合わせの問題を、イイ感じに真偽値を組み合わせた形に変形させることで高速に解けるようにするというものです。

数独ソルバーなんかは大体このSATを使っているはずです。

軽くて速いことで有名なMiniSatというSATソルバーがあるのですが、これのJavaラッパーがあったので使わせていただきました。

github.com

現時点で私以外⭐を付けていませんが、とても役に立っています。ありがとうございます。

残り地雷数

実はマインスイーパーにおける情報は数字マスだけではありません。

残りの地雷数によって配置が確定することがあるのです。

例えばこういうパターンがよくあります。

壁    1  1  1
壁 1  2  💣 1
壁 ?  ?  2  1
壁 ?  ?  1
壁 壁 壁 壁 壁

これは一見すると運ゲーですが、残り地雷数が1個か3個の場合、1通りに確定します。なお、2個の場合は運ゲーです。

実はこの残り地雷数を考慮した処理が一番面倒で、ここが特に企業秘密になります。

厳密モード

こうしてソルバーくんは運ゲーの盤面と運ゲーでない盤面を完璧に判定することが出来るようになったのでした。

無事出題される盤面の難易度は改善されたのですが、これにより「厳密モード」というものが実現可能になりました。

「厳密モード」というのは簡単に言うと、運ゲープレイを禁止するモードです。

たとえ地雷が無いマスであっても論理的に地雷が無いと分かるマスでなければタップした時点でゲームオーバーになります。

つまりこういう感じです。

運ゲー排除マインスイーパ #UnambiSweeper Android版3.0公開! (iOSはこれから)
一から作り直しサイズ大幅削減、描画性能向上!
また判定アルゴリズムを改良し全ての非運ゲー配置が出題範囲に!
これにより運ゲープレイを禁止する「厳密モード」を実現!
スクショ共有機能も追加!https://t.co/XcFY8B6BBU pic.twitter.com/AXjnQIqaIw
— DNEK(でぃーねっく) (@dnek_) 2018年12月4日