月、「主人公の好感度問題」と題された、あの一大プロジェクトが、今日完結する......。「主人公の好感度問題」とは生まれて初めて買ったエロゲ―こと、ワガママハイスペック(以下ワガハイ)をプレイしていたときのこと。このゲームは、共通ルートでの選択肢の選び方によって、各キャラの好感度パラメータが変化していき、最終的に好感度の高いキャラと恋人になって、あとは一本道のストーリーを見るだけの、ほぼほぼ完全に紙芝居なのですが、その選択肢の選び方について、多くのパターンが未尋ルートに向かうように感じられました。そこで、選択肢の選び方全パターンを実際に試してみて、本当に未尋ばかりなのか、つまり未尋はちょろいのかについて検証してみようというプロジェクトが始動しました。Systemのプロトコルで操作して、選択肢を全探索させた話。手動で全パターンを網羅するというのは、僕が神のみぞ知るセカイの主人公でもない限りやりたくないので、愚直な自動化を行おうとしました。ワガハイを起動した状態で、自動操作プログラムが勝手にカーソルを操作して、全ルートを探索していく作戦です。個ということがわかっていたので、どんな選択肢画面が存在するのかという情報は先に集めておくことができます。そこで、すべての選択肢画面のスクリーンショットを撮影しておき、そのスクリーンショットと一致する画面になったら、上または下の選択肢をクリックするという戦略を取ることにしました。ワガハイには「次の選択肢までスキップ」ボタンがあり、既読のメッセージを飛ばすことができます。クリア済みのセーブデータを使って、高速に探索を行うことができます。選択肢の選び方を生成するアルゴリズムは、すべての選択肢が二択であることと、選び方によっては発生しないイベントが存在しないことを考慮して、まずどんどん上の選択肢を選んでいき、その間で出会った選択肢について遡って下を選んでいくという戦略を取りました。疑似コードにするとこんな感じ。}}これですべてのルートを探索することができるはずですが、実際に完走していないので、本当に探索できるのかはわかりません。「個別ルートの選択肢画面」というのは、どこに出すかという選択肢です。そんなこんなで、このような方法で探索を行い、個別ルートに入ったと確認できたら、そのキャラのカウンターを回していってみようとしたわけですが、選択肢画面はピクセル単位で完全に一致するわけではなく、単純な画面の比較(MD5ハッシュを使っていました)ではうまくいかないようでした。画像ハッシュスクリーンショットがピクセル単位で完全一致しないという問題を受けて、似たようなスクリーンショットを判別できる必要がありました。いう画像ハッシュの存在を知ったところだったので、これを利用することにしました。アルゴリズムをちゃんと調べていないので、あまり挙動がわからないですが、似たような画像のハッシュ値を比較したとき、ハミング距離が小さくなるように設計されています。バイトのハッシュを出力します。文字以下(今思うとひどい判定方法だな)ならば、同じ画面だと判定するようにしたところ、うまく画面の判定ができるようになりました。アプリができあがりました。実際に動いている様子は、次のリンクに動画で公開しておきます。シーンには突入するまでは撮影していませんが、体験版の範囲は超えているのでご注意ください。FirstWagahighChoices.mp4で、実際に動かして放置してみた結果ですが、途中でワガハイがフリーズしてしまいました。途中でフリーズしたときに、再開する方法を作っていなかったので、最初からやり直しです。いうわけで、この方法ではいつまで経っても成功しないな、と思いました。台を占有されてはたまったものではないということで、最初の作戦は失敗に終わりました。台を占有されないようにするには、何とかしてワガハイを仮想環境で動かさなければいけません。仮想環境で動けば、探索を並列に実行することも簡単になります。相手にするのは難しそうだと感じました。アプリを扱うことはできないようでした。アプリなので、起動するにはディスプレイが必要です。上にはそんなものはないので、仮想的なディスプレイを用意します。パッケージリポジトリにも含まれているので、これを利用することにしました。経由で操作することができるようになりました。wenquanyiで十分なフォントがインストールされます。イメージにできたところで、どのように自動制御を行えばよいのでしょうか?前回の探索コードでは、一定時間待機し、操作を行い、一定時間待機し、を繰り返していましたが、ログファイルを見ると、選択肢スキップ(スキップにかかる時間は一定ではありません!遠いところまでジャンプするほど時間がかかります)が完了したときにはログが吐かれるらしく、これを参考にすることで、最小限の待機時間にすることができます。前回のコードでは、選択肢を選んだあとの待機時間に特別扱いがありましたが、操作不可能な間はカーソルがになるので、カーソルを見ることで、待機すべきかどうかを判断することができるようになり、特別扱いが不要になります。いうわけで、新たな要件として、カーソルが取得できることが追加されました。クライアントとして動いているワガハイに対して操作を行うには、どのような方法を使うのが良いでしょうか?思いついたものとして次のものがありました。サーバーとクライアントライブラリの相性が悪く、よく切断されてしまうので却下されました(記憶があいまい)。実装は完璧ではないので、さまざまな躓きポイントがありました。上で動かそうとしてみました。そのときの話は「それでも僕はWineでMonoを動かしたかった」をご覧ください(明言はしなかったのですが、この記事はワガハイを自動操作するための試行錯誤だったのです)。実装されておらず、回避しなければなりませんでした。最大の問題は、カーソルを取得することができなかったことです。サーバーはカーソルに関してすべてを関知しているわけではなく、各プロセス任せな部分がありました。そのため、他のプロセスのカーソルを取得することができませんでした。経由でしゃべることで、完全な制御を手に入れることにしました。したがって、自動操作に必要な命令はすべて行えるはずです。上で探索プログラムを動かすことも、技術上可能です。プロトコルを実装することにしました。サーバーの実装は、非常に参考になりました。プロトコルを例に挙げているのも、これがあったからです。どのようにワガハイを自動操作するかについて答えが得られたところで、この探索システムのコンポーネントに名前を付けておきましょう(実際にはこれが一番最初に決まっていた気がする)。サーバーとなって、操作を中継することもできます。デバッグすることができます。ワガハイのログファイルを読む機能も実装してあります。行って......と、ほとんど変化しない選択肢のスクリーンショット相手にはオーバースペックのように感じていました。採用することにしました。次のように計算されます(記憶を頼りに書いているので間違っていたらごめんなさい。実装と同じように動作しているので間違っていないはずです)。難しい画像処理(勉強しなきゃな......)は必要なく、中央値さえ求められれば計算できるアルゴリズムになっています。いうわけで、このハッシュ関数を、選択肢画面のハッシュ値を生成するのに使っていきます。使ったデバッグツールになりました。ありません)を使って通信します。送信され、実際にワガハイが操作されます。このツールを使って、各種ボタンの画面上の座標を調べたり、選択肢画面のスクリーンショットを撮ったりしました。インターネットにスクリーンショットを投げたときに一番良い反応が得られるツールでもあります。機能が充実してきたところで、第2章は完結です。今思うと、なかなかボリュームのあることやっていたんだなぁという気持ちです。上のワガハイを操作するかについては、試しては技術的な限界に気づき捨ててを繰り返して夏休みをすべて使ってしまいましたからね。手を付けることになりました。最難関は越えているので、手を動かせばそのうち完成する部分でもありました。最終的に新しい枝が見つからなくなったら終わり、というすごく雑な実装になりました。実際の挙動は次の通りです。空の操作指示を持つジョブを作成し、ワーカー(Ashe)に渡す。指示通りに操作を行う。どちらを選ぶかの指示がなくなったら、その後は上を選び続ける。通った選択肢画面を管理サーバー(Kaoruko)に報告する。通った選択肢画面の個数と、ジョブの操作指示の個数を照らし合わせ、足りなかった部分は上を選択したものとして記録する。足りなかった部分で下を選んだ場合についてジョブキューにエンキューする。指示は、ジョブキューのうち、操作指示の個数が少ない順に渡す。5番の操作指示の個数が少ない順に渡す仕様は、実際に探索を回していて、終盤に差し掛かったときに並列実行性が段々落ちていく(新しいジョブが開拓されない)ことに気づいて追加しました。ちから業という感じがしますが、ジョブ数の上限がわかっているので問題ありませんでした。上で書いたように、操作指示を受けて、実際にワガハイを操作していきます。ワガハイが起動したことを確認したら、次のように操作を行っていきます。タイトル画面になったことを確認し、「はじめから」をクリックする。最初の選択肢まで、「次の選択肢までスキップ」を使ってスキップする。クイックセーブする(1回の探索が終わったときに、ここまで戻ってこれるようにしておきます)。指示通りに選択肢を選んでは、「次の選択肢までスキップ」を繰り返す。