ぷよぷよのプレイ動画を解析して棋譜を生成する
この記事は KMC アドベントカレンダー の 3 日目の記事です。 昨日は PrimeNumber さんの PEZY-SC/SC2を使った話 でした。
背景と問題
ぷよぷよの上達を阻む問題として「自分の手が良いのか悪いのかわからない」という問題があります。 ツモが毎回ランダムであるため、仮に悪い手を指したとしてもその後のツモに救われて何とかなる場合もありますし、仮に良い手を指したとしてもその後のツモが悪いと形が崩れてしまう場合もあります。 ある手が良いか悪いを知るためには、何度も試行を重ねて統計的に判断しなければなりません。 これは非常に時間がかかります。
幸いなことに、現在多くの上級者が YouTube にプレイ動画をアップロードしています。 プレイ動画を解析して上級者がある局面でどういう手を指したかどうかを知ることができれば、それを使って自分のプレイを評価できるのではないでしょうか？
しかし、プレイ動画はそのまま統計処理できる形式ではありません。 統計処理に適した形式、つまり棋譜(= 手順をテキストとして書いたもの)に変換する必要があります。
そこで今回、ぷよぷよのプレイ動画を解析して棋譜を生成するプログラムを作ったので、その紹介をしていきます。
解析に用いた動画
このプログラムを作るにあたり『ぷよぷよクロニクル 第2回おいうリーグ S級リーグ ようかん vs まはーら 50先』 をサンプルとして利用させていただきました。
使用した言語/ライブラリ
今回の動画解析は Python と OpenCV を使いました。Jupyter notebook で作業すると動画のフレームやメトリクスのグラフなどをインラインで描画できて便利でした。
↓ Jupyter notebook で動画の1フレーム目を描画している図:
フィールド上のぷよの認識
フィールドの枠の位置は時刻にかかわらず一定なので、今回は given ということにしました。 フィールドには横に6個、縦に12個のマスが等間隔で並んでいるため、枠の位置が決まればマスの位置も自動的に決まります。
次に、マスの状態（空、赤、黄、青、緑、紫、おじゃまの7状態）を判定します。 これは単純に状態ごとに予めパターン画像を用意しておいて、マスの画像とパターン画像との差分が最も小さかった状態を選ぶというアルゴリズムにしています。
下図の上の画像が (4, 4) に位置するマスの画像で、下の画像が赤のパターン画像との差分を取った画像です。 全体的に黒くなっていてそれっぽい感じがしますよね？
下図は実際のフィールドに対してフィールド認識した結果です。 左が与えられたフィールドの画像で、右が認識結果を使って作った画像です。 地面に設置しているぷよは正しく認識できていることがわかると思います。 一方で操作中のぷよは正しく認識できていません。 これは認識アルゴリズムがマス目単位で判定しているからです。
ぷよを置いた瞬間かどうかの判定
ぷよぷよの棋譜を生成したいという目的において、操作中のぷよが空中にある状態のフレームは不要です。 ぷよが接地し、場所が確定した瞬間のフレームこそが重要です。 ではどうやってぷよを置いた瞬間のフレームを識別すればよいでしょうか？
ぷよを置いたとき、次に起こりうることは次の3通りです。
- 次のぷよをツモる
- ぷよが消える
- おじゃまぷよが降る
そこで１から順に考えていきます。
1. 次のぷよをツモる瞬間の判定
あるフレームが次のぷよをツモる瞬間かどうかは、ネクスト欄およびダブルネクスト欄を見れば判定できます。
これらの欄はツモの瞬間にぷよがスライドし、次のぷよが表示されます。 これ以外のタイミングでは動きません。 したがって、これらの欄に変化があるかどうかを調べればぷよをツモったかどうかがわかります。
次のグラフはネクストぷよ表示欄について、1フレーム前とのピクセル差分の合計値を表しています。 x軸は時刻です。ツモったタイミングに合わせて値が跳ねているため、これの変化率を見ればツモの瞬間がわかります。
しかし、実際にやってみるとうまくいかない場合があります。 例えば下図のようなケースです。 連鎖光がネクスト欄に重なっており、ナイーブに判定するとツモったとみなされてしまいます。 今回はネクスト欄とダブルネクスト欄両方に連鎖光が重なることは少ないだろうということで、両方の欄で独立にツモ判定を行い、両方が true だった場合にツモったと判定することにしました。 しかし、絶妙な軌道で連鎖光が発射されると誤判定しそうなので、この判定の改善は将来の課題です。
また、ゲームのせいなのか動画のせいなのかわからないのですが、たまに連続する2フレームが全く同じ画像になっていることがあります。このときに1フレーム前とのピクセル差分を取るとゼロになってしまって誤判定します。今回は3フレーム前と比較することで回避しました。
2. ぷよが消える瞬間の判定
ぷよが消える瞬間はスコアを見れば簡単に判定できます。 ぷよが消えるときだけスコアは「数値×数値」という表示になります（普段は一つの数値です）。 なので×マークがあるかどうかをパターンマッチで判定することにしました。
x軸を時刻、y軸をピクセル差分としてグラフにプロットしてみました。 800フレーム目のあたりから13連鎖しているのが見てとれると思います。
3. おじゃまぷよが降る
実はおじゃまぷよが降る場合は特に判別しなくても後処理で何とかできるので、処理していません。
情報を集約して棋譜を作る
これでぷよをツモる瞬間のフィールドの状況、ぷよが消える直前のフィールドの状況が時刻情報付きでわかったことになります。 後は連続する２つのイベントの間のフィールドの差分を取れば、どこにぷよを置いたのかがわかりますし、ぷよの消滅が連続して何回起こったのかを数えれば何連鎖したのかがわかります。
実際にある試合の様子を棋譜として出力してみたら以下のようになりました（1Pのみです）。 結構それっぽい棋譜ができました。
33: ▲1一黄 ▲2一青 59: ▲3一青 ▲3二紫 85: ▲2二紫 ▲2三青 108: ▲2四黄 ▲2五赤 135: ▲4一紫 ▲4二赤 160: ▲3三黄 ▲4三紫 186: ▲1二青 ▲1三黄 209: ▲3四赤 ▲3五青 237: ▲5一赤 ▲6一赤 261: ▲1四黄 ▲1五赤 288: ▲5二黄 ▲5三赤 316: ▲6二黄 ▲6三黄 339: ▲1六赤 ▲2六青 364: ▲6四赤 ▲6五赤 389: ▲5四黄 ▲5五赤 412: ▲5六紫 ▲6六紫 435: ▲6七紫 ▲6八赤 458: ▲4四青 ▲4五黄 479: ▲1七青 ▲1八青 499: ▲3六赤 ▲3七赤 520: ▲5七黄 ▲5八紫 538: ▲3八青 ▲3九青 560: ▲4六赤 ▲4七黄 581: ▲5九紫 ▲6九赤 601: ▲4八黄 ▲4九青 622: ▲5十青 ▲5十一紫 642: ▲6十青 ▲6十一赤 661: ▲6十二黄 681: ▲2七黄 ▲2八赤 700: ▲1九赤 ▲2九赤 718: ▲1十黄 ▲2十紫 759: ▲4十紫 ▲4十一紫 777: ▲4十二青 ▲5十二黄 804: ▲3十赤 ▲2十一黄 832: ▲3十一紫 ▲2十二青 発火 873: 2連鎖 914: 3連鎖 956: 4連鎖 996: 5連鎖 1038: 6連鎖 1082: 7連鎖 1122: 8連鎖 1162: 9連鎖 1203: 10連鎖 1244: 11連鎖 1286: 12連鎖 1327: 13連鎖 1397: ▲3一黄 ▲3二紫 1463: ▲3三黄 ▲3四赤 1529: ▲投了
661 フレーム目でぷよを1個しか置いていないことになっていますが、これは片方のぷよが画面外に置かれたからです。 また、おじゃまぷよの落下はこの棋譜には書かれていませんが、プログラムの中のデータとしては取得できています。
Future work
今のところ PoC レベルなので、実用にはまだまだ全然足りません。
まず、まだ 1P 側しか取れないので 2P 側も取る必要があります。 ゲームオーバー判定が背景に依存しているので背景が変わると動きません。 ぷよクロじゃなくてぷよスポにも対応したいです。 全消しの場合、パターンマッチが誤爆するかもしれません（試してない）。
暇を見つけてぼちぼちやっていきたいです。
まとめ
はじめての動画処理でしたが、意外と泥臭い力技で何とかなりました。 やってみるものですね。
明日は utgwkk さんの「レコード多相についてお話します」です。お楽しみに。
