ぷよぷよのプレイ動画を解析して棋譜を生成する

この記事は KMC アドベントカレンダー の 3 日目の記事です。 昨日は PrimeNumber さんの PEZY-SC/SC2を使った話 でした。

背景と問題

ぷよぷよの上達を阻む問題として「自分の手が良いのか悪いのかわからない」という問題があります。 ツモが毎回ランダムであるため、仮に悪い手を指したとしてもその後のツモに救われて何とかなる場合もありますし、仮に良い手を指したとしてもその後のツモが悪いと形が崩れてしまう場合もあります。 ある手が良いか悪いを知るためには、何度も試行を重ねて統計的に判断しなければなりません。 これは非常に時間がかかります。

幸いなことに、現在多くの上級者が YouTube にプレイ動画をアップロードしています。 プレイ動画を解析して上級者がある局面でどういう手を指したかどうかを知ることができれば、それを使って自分のプレイを評価できるのではないでしょうか?

しかし、プレイ動画はそのまま統計処理できる形式ではありません。 統計処理に適した形式、つまり棋譜(= 手順をテキストとして書いたもの)に変換する必要があります。

そこで今回、ぷよぷよのプレイ動画を解析して棋譜を生成するプログラムを作ったので、その紹介をしていきます。

解析に用いた動画

このプログラムを作るにあたり『ぷよぷよクロニクル 第2回おいうリーグ S級リーグ ようかん vs まはーら 50先』 をサンプルとして利用させていただきました。

使用した言語/ライブラリ

今回の動画解析は PythonOpenCV を使いました。Jupyter notebook で作業すると動画のフレームやメトリクスのグラフなどをインラインで描画できて便利でした。

↓ Jupyter notebook で動画の1フレーム目を描画している図:

f:id:nojima718:20181203204416p:plain

フィールド上のぷよの認識

フィールドの枠の位置は時刻にかかわらず一定なので、今回は given ということにしました。 フィールドには横に6個、縦に12個のマスが等間隔で並んでいるため、枠の位置が決まればマスの位置も自動的に決まります。

次に、マスの状態(空、赤、黄、青、緑、紫、おじゃまの7状態)を判定します。 これは単純に状態ごとに予めパターン画像を用意しておいて、マスの画像とパターン画像との差分が最も小さかった状態を選ぶというアルゴリズムにしています。

下図の上の画像が (4, 4) に位置するマスの画像で、下の画像が赤のパターン画像との差分を取った画像です。 全体的に黒くなっていてそれっぽい感じがしますよね?

f:id:nojima718:20181203205637p:plain

下図は実際のフィールドに対してフィールド認識した結果です。 左が与えられたフィールドの画像で、右が認識結果を使って作った画像です。 地面に設置しているぷよは正しく認識できていることがわかると思います。 一方で操作中のぷよは正しく認識できていません。 これは認識アルゴリズムがマス目単位で判定しているからです。

f:id:nojima718:20181203205933p:plain

ぷよを置いた瞬間かどうかの判定

ぷよぷよ棋譜を生成したいという目的において、操作中のぷよが空中にある状態のフレームは不要です。 ぷよが接地し、場所が確定した瞬間のフレームこそが重要です。 ではどうやってぷよを置いた瞬間のフレームを識別すればよいでしょうか?

ぷよを置いたとき、次に起こりうることは次の3通りです。

  1. 次のぷよをツモる
  2. ぷよが消える
  3. おじゃまぷよが降る

そこで1から順に考えていきます。

1. 次のぷよをツモる瞬間の判定

あるフレームが次のぷよをツモる瞬間かどうかは、ネクスト欄およびダブルネクスト欄を見れば判定できます。

これらの欄はツモの瞬間にぷよがスライドし、次のぷよが表示されます。 これ以外のタイミングでは動きません。 したがって、これらの欄に変化があるかどうかを調べればぷよをツモったかどうかがわかります。

次のグラフはネクストぷよ表示欄について、1フレーム前とのピクセル差分の合計値を表しています。 x軸は時刻です。ツモったタイミングに合わせて値が跳ねているため、これの変化率を見ればツモの瞬間がわかります。

f:id:nojima718:20181203220412p:plain

しかし、実際にやってみるとうまくいかない場合があります。 例えば下図のようなケースです。 連鎖光がネクスト欄に重なっており、ナイーブに判定するとツモったとみなされてしまいます。 今回はネクスト欄とダブルネクスト欄両方に連鎖光が重なることは少ないだろうということで、両方の欄で独立にツモ判定を行い、両方が true だった場合にツモったと判定することにしました。 しかし、絶妙な軌道で連鎖光が発射されると誤判定しそうなので、この判定の改善は将来の課題です。

f:id:nojima718:20181203220800p:plain

また、ゲームのせいなのか動画のせいなのかわからないのですが、たまに連続する2フレームが全く同じ画像になっていることがあります。このときに1フレーム前とのピクセル差分を取るとゼロになってしまって誤判定します。今回は3フレーム前と比較することで回避しました。

2. ぷよが消える瞬間の判定

ぷよが消える瞬間はスコアを見れば簡単に判定できます。 ぷよが消えるときだけスコアは「数値×数値」という表示になります(普段は一つの数値です)。 なので×マークがあるかどうかをパターンマッチで判定することにしました。

f:id:nojima718:20181203221454p:plain

x軸を時刻、y軸をピクセル差分としてグラフにプロットしてみました。 800フレーム目のあたりから13連鎖しているのが見てとれると思います。

f:id:nojima718:20181203223806p:plain

3. おじゃまぷよが降る

実はおじゃまぷよが降る場合は特に判別しなくても後処理で何とかできるので、処理していません。

情報を集約して棋譜を作る

これでぷよをツモる瞬間のフィールドの状況、ぷよが消える直前のフィールドの状況が時刻情報付きでわかったことになります。 後は連続する2つのイベントの間のフィールドの差分を取れば、どこにぷよを置いたのかがわかりますし、ぷよの消滅が連続して何回起こったのかを数えれば何連鎖したのかがわかります。

実際にある試合の様子を棋譜として出力してみたら以下のようになりました(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 さんの「レコード多相についてお話します」です。お楽しみに。