アジョブジ星通信

進捗が出た頃に更新されるブログ。

主人公の好感度問題 完結編

つくったもの C# Docker X11

遡ること 2017 年 4 月、「主人公の好感度問題」と題された、あの一大プロジェクトが、今日完結する……。

「主人公の好感度問題」とは

生まれて初めて買ったエロゲ―こと、ワガママハイスペック（以下ワガハイ）をプレイしていたときのこと。このゲームは、共通ルートでの選択肢の選び方によって、各キャラの好感度パラメータが変化していき、最終的に好感度の高いキャラと恋人になって、あとは一本道のストーリーを見るだけの、ほぼほぼ完全に紙芝居なのですが、その選択肢の選び方について、多くのパターンが未尋ルートに向かうように感じられました。そこで、選択肢の選び方全パターンを実際に試してみて、本当に未尋ばかりなのか、つまり未尋はちょろいのかについて検証してみようというプロジェクトが始動しました。

TL;DR

選択肢の積み重ねでエンディングが分岐するタイプのゲームにおいて各エンディングの出現率を調べるために、Docker上にWineで動かしたゲームを C# からX Window Systemのプロトコルで操作して、選択肢を全探索させた話。

https://mstdn.maud.io/@unarist/100976963847747421

第1章: 愚直な作戦

手動で全パターンを網羅するというのは、僕が神のみぞ知るセカイの主人公でもない限りやりたくないので、愚直な自動化を行おうとしました。つまり、ワガハイを起動した状態で、自動操作プログラムが勝手にカーソルを操作して、全ルートを探索していく作戦です。

探索戦略

共通ルート中の選択肢画面が最大で 12 個ということがわかっていたので、どんな選択肢画面が存在するのかという情報は先に集めておくことができます。そこで、すべての選択肢画面のスクリーンショットを撮影しておき、そのスクリーンショットと一致する画面になったら、上または下の選択肢をクリックするという戦略を取ることにしました。また、ワガハイには「次の選択肢までスキップ」ボタンがあり、既読のメッセージを飛ばすことができます。つまりクリア済みのセーブデータを使って、高速に探索を行うことができます。

選択肢の選び方を生成するアルゴリズムは、すべての選択肢が二択であることと、選び方によっては発生しないイベントが存在しないことを考慮して、まずどんどん上の選択肢を選んでいき、その間で出会った選択肢について遡って下を選んでいくという戦略を取りました。疑似コードにするとこんな感じ。

// (選択肢画面, 上下)
stack = {};

// 次の操作指示を作成する
// 引数 selectionInfo: 到達した選択肢画面
// 戻り値: 操作のリスト
// 実際のコード: https://github.com/azyobuzin/hojiroLT6/blob/2be3ef5cbfbc97819882622e384c7d34be6e0f41/WagahighChoices/ChoiceTracer.cs
Next(selectionInfo) {
    if (selectionInfo が個別ルートの選択肢画面) {
        nextItem = null;
        while (stack.Count > 0) {
            item = stack.Pop();
            if (item.上下 == 上) {
                nextItem = item;
                break;
            }
        }

        if (nextItem == null) return 探索終了;

        actions = { 最初の選択肢に戻る（クイックロード） };
        actions.AddRange(stack.Select((選択肢画面, 上下) => 上下));
        actions.Add(下を選択);
        
        stack.Push((nextItem.選択肢画面, 下));
        return actions;
    } else {
        stack.Push((selectionInfo, 上));
        return { 上を選択 };
    }
}

これですべてのルートを探索することができるはずですが、実際に完走していないので、本当に探索できるのかはわかりません。「個別ルートの選択肢画面」というのは、どこに出すかという選択肢です。深くは言いません。

そんなこんなで、このような方法で探索を行い、個別ルートに入ったと確認できたら、そのキャラのカウンターを回していってみようとしたわけですが、選択肢画面はピクセル単位で完全に一致するわけではなく、単純な画面の比較（MD5ハッシュを使っていました）ではうまくいかないようでした。

画像ハッシュ

スクリーンショットがピクセル単位で完全一致しないという問題を受けて、似たようなスクリーンショットを判別できる必要がありました。ちょうど pHash という画像ハッシュの存在を知ったところだったので、これを利用することにしました。 pHash は、アルゴリズムをちゃんと調べていないので、あまり挙動がわからないですが、似たような画像のハッシュ値を比較したとき、ハミング距離が小さくなるように設計されています。使用した pHash ライブラリ（Shipwreck.Phash 0.0.2）では、 40 バイトのハッシュを出力します。このハッシュ値をすべての選択肢画面について計算しておき、探索中に撮影したスクリーンショットのハッシュ値と比較して、ハッシュ値の 16 進数表現の差が 5 文字以下（今思うとひどい判定方法だな）ならば、同じ画面だと判定するようにしたところ、うまく画面の判定ができるようになりました。

そして、できあがったもの

選択肢のスクリーンショットの撮影と、探索を合わせた GUI アプリができあがりました。

実際に動いている様子は、次のリンクに動画で公開しておきます。 R-18 なシーンには突入するまでは撮影していませんが、体験版の範囲は超えているのでご注意ください。

で、実際に動かして放置してみた結果ですが、途中でワガハイがフリーズしてしまいました。

途中でフリーズしたときに、再開する方法を作っていなかったので、最初からやり直しです。というわけで、この方法ではいつまで経っても成功しないな、と思いました。

この後、実際にどのくらいの選び方があるのか試算してみましたが、選択肢画面が 12 個あるので、最大 212 パターン（正確な値は後で紹介します）ある可能性があり、これをすべて探索するまで Windows マシン 1 台を占有されてはたまったものではないということで、最初の作戦は失敗に終わりました。

第2章: そうか！仮想化だ！（激寒）

さて、 Windows マシン 1 台を占有されないようにするには、何とかしてワガハイを仮想環境で動かさなければいけません。さらに、仮想環境で動けば、探索を並列に実行することも簡単になります。というわけで、仮想化が問題なわけですが、 Windows の仮想マシンを作るにはライセンスが必要（Enterprise の評価版という手もありましたね）なので、普通の Windows を相手にするのは難しそうだと感じました。

そこで、 Docker の Windows Container を使えないかと、 Windows Container 上の Windows Server Core でメモ帳を起動してみましたが、ウィンドウハンドルが生成されておらず、どうやら Windows Container では GUI アプリを扱うことはできないようでした。

Windows 系が全滅したとなれば、最後の頼みの綱は Linux です。つまり Wine 上でワガハイが動くかが問題ということですが、最近のバージョンではムービー再生を除いて動きます！というわけで、 Linux で動かせることがわかったので、 Docker イメージ化して、仮想環境で動いてもらいましょう！

ワガハイの Docker イメージ化

ワガハイは GUI アプリなので、起動するにはディスプレイが必要です。 Docker 上にはそんなものはないので、仮想的なディスプレイを用意します。 X 向けのシンプルな仮想ディスプレイの実装として Xvfb が X.Org より提供されており、 Ubuntu パッケージリポジトリにも含まれているので、これを利用することにしました。

Xvfb 上で実行しているワガハイに対しては x11vnc を使って VNC 経由で操作することができるようになりました。

ここまでの内容について Dockerfile 化しました。

ここでちょっとした tips ですが、 Wine の日本語フォントについては

winetricks wenquanyi

で十分なフォントがインストールされます。 allfonts は時間がかかるわりに、日本語については wenquanyi と変わらなかったです。

どうやって自動操作する？

無事ワガハイを Docker イメージにできたところで、どのように自動制御を行えばよいのでしょうか？

前回の探索コードでは、一定時間待機し、操作を行い、一定時間待機し、を繰り返していましたが、ログファイルを見ると、選択肢スキップ（スキップにかかる時間は一定ではありません！遠いところまでジャンプするほど時間がかかります）が完了したときにはログが吐かれるらしく、これを参考にすることで、最小限の待機時間にすることができます。また、前回のコードでは、選択肢を選んだあとの待機時間に特別扱いがありましたが、操作不可能な間はカーソルが🚫になるので、カーソルを見ることで、待機すべきかどうかを判断することができるようになり、特別扱いが不要になります。というわけで、新たな要件として、カーソルが取得できることが追加されました。

さて、 Linux の GUI アプリ、つまり X クライアントとして動いているワガハイに対して操作を行うには、どのような方法を使うのが良いでしょうか？思いついたものとして次のものがありました。

  1. VNC を経由して操作を行う
  2. 探索プログラムも Wine 上で動かし、 Windows API を用いて自動操作を行う
  3. X Windows System Protocol を使って操作を行う

1 については、カーソルを取得するには、 VNC ライブラリを改造する必要があり、面倒になったのと、 VNC サーバーとクライアントライブラリの相性が悪く、よく切断されてしまうので却下されました（記憶があいまい）。

2 については、やはり Wine の実装は完璧ではないので、さまざまな躓きポイントがありました。最初に Windows 版の Mono を Wine 上で動かそうとしてみました。そのときの話は「それでも僕はWineでMonoを動かしたかった」をご覧ください（明言はしなかったのですが、この記事はワガハイを自動操作するための試行錯誤だったのです）。結局 Mono をやめ、 Rust で書き始めましたが、今度は GetQueuedCompletionStatusEx 関数が Wine に実装されておらず、回避しなければなりませんでした。そして、最大の問題は、カーソルを取得することができなかったことです。 Windows では、 Windows が各ウィンドウのカーソルを管理していますが、 Wine では、 Wine サーバーはカーソルに関してすべてを関知しているわけではなく、各プロセス任せな部分がありました。そのため、他のプロセスのカーソルを取得することができませんでした。

そして、最終的に、探索プログラムが X クライアントとなり、 X のプロトコルを TCP 経由でしゃべることで、完全な制御を手に入れることにしました。 X クライアントが他のアプリに対して行える操作は数多く、ウィンドウマネージャーや VNC サーバーも X クライアントの 1 つです。したがって、自動操作に必要な命令はすべて行えるはずです。

X サーバーへは TCP でも接続することができるので、 Windows 上で探索プログラムを動かすことも、技術上可能です。ですが、 X 関連ライブラリは基本的に Unix 用なので、プラットフォームに依存せずに X プロトコルを話すため、 C# でプロトコルを実装することにしました。実装するうえで、 xcb のプロトコル定義ファイルや、 VNC サーバーの実装は、非常に参考になりました。あと「さぁ fixed を捨てて Unsafe だ」で X プロトコルを例に挙げているのも、これがあったからです。

プロジェクト構想

とりあえず、最難関ポイントだった、 Linux でどのようにワガハイを自動操作するかについて答えが得られたところで、この探索システムのコンポーネントに名前を付けておきましょう（実際にはこれが一番最初に決まっていた気がする）。

ちょうど今までお話ししてきた部分が、 Toa にあたります。 Toa は、 X クライアントとして振舞うライブラリとしても使えますし、 gRPC サーバーとなって、操作を中継することもできます。 gRPC サーバーとなることで、他の層が X プロトコルに直接依存せずに、 Windows からデバッグすることができます。あと Toa にはワガハイのログファイルを読む機能も実装してあります。

画像ハッシュ、再来

さて、前回は画像ハッシュとして pHash を採用しましたが、内部ではフィルターをかけて DCT を行って……と、ほとんど変化しない選択肢のスクリーンショット相手にはオーバースペックのように感じていました。そこで、もっと軽量なアルゴリズムとして、 Blockhash を採用することにしました。

Blockhash は次のように計算されます（記憶を頼りに書いているので間違っていたらごめんなさい。実際のコードはおおむね既存の C 実装と同じように動作しているので間違っていないはずです）。

  1. 画像を 16x16 （パラメータで変えられます）のブロック（小ブロック）に区切り、各ブロックに含まれるピクセルの R + G + B をすべて足し合わせる
  2. 画像を水平方向に 4 個のブロック（大ブロック）に区切り、そこに含まれる各小ブロックの値が、大ブロック内の小ブロックの値の中央値より大きいならば 1、中央値以下ならば 0 とする
  3. 各小ブロックの 0 or 1 を並べた値がハッシュ値

難しい画像処理（勉強しなきゃな……）は必要なく、中央値さえ求められれば計算できるアルゴリズムになっています。というわけで、このハッシュ関数を、選択肢画面のハッシュ値を生成するのに使っていきます。

Mihiro

先ほどのコンポーネントの中に、このプロジェクトを始めるきっかけとなった未尋の名前がありませんでしたが、どこにいったかというと、 Toa を使ったデバッグツールになりました。

Mihiro は、 Toa と gRPC（といっても MagicOnion を使用しているので Protocol Buffers ではありません）を使って通信します。 Toa から一定時間ごとにスクリーンショットとログを受け取り、 Mihiro の画面上で操作を行うと、操作が Toa に送信され、実際にワガハイが操作されます。

このツールを使って、各種ボタンの画面上の座標を調べたり、選択肢画面のスクリーンショットを撮ったりしました。そして、インターネットにスクリーンショットを投げたときに一番良い反応が得られるツールでもあります。

Mihiro の機能が充実してきたところで、第2章は完結です。今思うと、なかなかボリュームのあることやっていたんだなぁという気持ちです。特に、どうやって Linux 上のワガハイを操作するかについては、試しては技術的な限界に気づき捨ててを繰り返して夏休みをすべて使ってしまいましたからね。。

第3章: 完成の向こう側へ

あれから 1 年、簡単にいうと大学の忙しさで一旦放置したらやる気を失ってしまったわけですが、 10/13 のこと、やり残したプロジェクトを終わらせたいという炎が突如燃え上がり、残りの Ashe と Kaoruko に手を付けることになりました。

正直、最難関は越えているので、手を動かせばそのうち完成する部分でもありました。

新しい探索アルゴリズム

今回は、並列に実行できることと、探索するパターン数の上限がわかっているということで、新しい枝を見つけ出しては、それをキュー（といってもその順番で取り出すとは限りませんが）に記録していき、 最終的に新しい枝が見つからなくなったら終わり、というすごく雑な実装になりました。実際の挙動は次の通りです。

  1. 空の操作指示を持つジョブを作成し、ワーカー（Ashe）に渡す。
  2. Ashe は指示通りに操作を行う。もしどちらを選ぶかの指示がなくなったら、その後は上を選び続ける。
  3. 個別ルートに到達したら、ジョブ ID と通った選択肢画面を管理サーバー（Kaoruko）に報告する。
  4. レポートを受信した Kaoruko は、通った選択肢画面の個数と、ジョブの操作指示の個数を照らし合わせ、足りなかった部分は上を選択したものとして記録する。また、足りなかった部分で下を選んだ場合についてジョブキューにエンキューする。
  5. 新しい指示を渡す。指示は、ジョブキューのうち、操作指示の個数が少ない順に渡す。

5番の操作指示の個数が少ない順に渡す仕様は、実際に探索を回していて、終盤に差し掛かったときに並列実行性が段々落ちていく（新しいジョブが開拓されない）ことに気づいて追加しました。

結構ちから業という感じがしますが、ジョブ数の上限がわかっているので問題ありませんでした。

探索ワーカー Ashe の実装

Ashe は上で書いたように、操作指示を受けて、実際にワガハイを操作していきます。 Toa からスクリーンショットやカーソルの状態を受け取って、時にはワガハイがフリーズしていないかを確認しながら、操作を行い、個別ルートに到達したら、 Kaoruko に報告を行います。

ワガハイが起動したことを確認したら、次のように操作を行っていきます。

  1. タイトル画面になったことを確認し、「はじめから」をクリックする。
  2. 最初の選択肢まで、「次の選択肢までスキップ」を使ってスキップする。
  3. クイックセーブする（1回の探索が終わったときに、ここまで戻ってこれるようにしておきます）。
  4. Kaoruko からの指示を待つ。
  5. 指示通りに選択肢を選んでは、「次の選択肢までスキップ」を繰り返す。
  6. 個別ルートに到達したら、報告を行い、クイックロードして 4 に戻る。

Ashe には、デバッガビリティの向上のため、探索指示方法が 2 種類、 Toa の使い方が 2 種類あります。

探索指示については、 Kaoruko なしでも手動で実行できるよう、コンソールから指示を送る機能を付け、初期のデバッグに役立てました。

Toa については、ライブラリ（Wine のプロセス起動を行うので Linux 上でしか動かない）としても使えるし、 gRPC 経由でも使えると説明したように、初期デバッグ時は、 Docker 上で動いている Toa を使ってデバッグを行い、実際の探索ではライブラリの Toa を直接使うことで、管理の手間とオーバーヘッドを減らすことができました。この抽象化はうまくいったなと感じています。

最終的に Ashe はワガハイ本体と合わせてひとつの Docker イメージとして、いろんなマシンに分散させて実行できるようにします。

中央管理サーバー Kaoruko の実装

Kaoruko は gRPC サーバーとなり、 Ashe と通信するほか、 Web UI を備え、探索状況を監視できるようにしました。

当初は Ashe から 1 秒ごとに送られてくるスクリーンショットを愚直に保存していたのですが、ワーカーが増えると SQLite が追い付かなくなる（HDD を使ってるのが悪い）ので、結局スクリーンショット保存機能はオプションになりました。

さぁ、これで WagahighChoices という探索システムの紹介は以上です。ソースコードは azyobuzin/whc にて公開しています。

探索結果のご報告

※実質ネタバレということです。ご注意ください。

プロジェクト始動から 1 年半、このプロジェクトが本当に完結してしまうとは思っていませんでした。奇跡のような感覚さえあり、探索が完走したときは本当に、うれしさと感動がこみ上げてきました。こうやってここまで長々と文章を書いている間にだいぶ落ち着きを取り戻してきてはいますが。

10/27 の 19 時頃より、安定稼働し始め、 3 時前に完走しました。ワーカーは Docker for Windows 上から 2 個、 Ubuntu を入れているノート PC から 3 個を動かし、最後の 1 時間半くらいは、 Surface Book 上の Docker for Windows からさらに 2 個のワーカーを動かしました。

というわけで結果発表です。どうぞ！

かおるこ アーシェ 兎亜 未尋
512 256 224 1568

というわけで、未尋が圧倒的ちょろインということが実証されました！

選択肢の選び方の合計は 2560 でした。これは 210 + 3×29 で、 1 番目の選択肢と 3 番目の選択肢で上を選ばないと、文化祭前夜のかおるこイベントが発生しないため、このような結果になりました。

各選択肢ごとにどっちを選ぶと誰のルートに何%到達するかのデータも取りましたので、ご覧ください。

選択肢番号は、常に上を選び続けたときに出会う選択肢の順番になっているはずですので、ワガハイを持っている方なら説明不要だと思いますので、省略させていただきます。

あああ！終わってしまった！本当に終わってしまった！さぁ、明日……もう日が変わってるから今日は月曜日です。この喜びとちょっとした寂しさをしまって、平日を迎えましょう。こちらからは以上です。