背景と問題ぷよぷよの上達を阻む問題として「自分の手が良いのか悪いのかわからない」という問題があります。ツモが毎回ランダムであるため、仮に悪い手を指したとしてもその後のツモに救われて何とかなる場合もありますし、仮に良い手を指したとしてもその後のツモが悪いと形が崩れてしまう場合もあります。ある手が良いか悪いを知るためには、何度も試行を重ねて統計的に判断しなければなりません。これは非常に時間がかかります。プレイ動画をアップロードしています。プレイ動画を解析して上級者がある局面でどういう手を指したかどうかを知ることができれば、それを使って自分のプレイを評価できるのではないでしょうか?しかし、プレイ動画はそのまま統計処理できる形式ではありません。手順をテキストとして書いたもの)に変換する必要があります。そこで今回、ぷよぷよのプレイ動画を解析して棋譜を生成するプログラムを作ったので、その紹介をしていきます。サンプルとして利用させていただきました。作業すると動画のフレームやメトリクスのグラフなどをインラインで描画できて便利でした。フィールドには横に6個、縦に12個のマスが等間隔で並んでいるため、枠の位置が決まればマスの位置も自動的に決まります。おじゃまの7状態)を判定します。これは単純に状態ごとに予めパターン画像を用意しておいて、マスの画像とパターン画像との差分が最も小さかった状態を選ぶというアルゴリズムにしています。位置するマスの画像で、下の画像が赤のパターン画像との差分を取った画像です。全体的に黒くなっていてそれっぽい感じがしますよね?下図は実際のフィールドに対してフィールド認識した結果です。左が与えられたフィールドの画像で、右が認識結果を使って作った画像です。地面に設置しているぷよは正しく認識できていることがわかると思います。一方で操作中のぷよは正しく認識できていません。これは認識アルゴリズムがマス目単位で判定しているからです。ぷよを置いた瞬間かどうかの判定ぷよぷよの棋譜を生成したいという目的において、操作中のぷよが空中にある状態のフレームは不要です。ぷよが接地し、場所が確定した瞬間のフレームこそが重要です。やってぷよを置いた瞬間のフレームを識別すればよいでしょうか?ぷよを置いたとき、次に起こりうることは次の3通りです。次のぷよをツモるぷよが消えるおじゃまぷよが降るそこで1から順に考えていきます。次のぷよをツモる瞬間の判定あるフレームが次のぷよをツモる瞬間かどうかは、ネクスト欄およびダブルネクスト欄を見れば判定できます。これらの欄はツモの瞬間にぷよがスライドし、次のぷよが表示されます。これ以外のタイミングでは動きません。したがって、これらの欄に変化があるかどうかを調べればぷよをツモったかどうかがわかります。次のグラフはネクストぷよ表示欄について、1フレーム前とのピクセル差分の合計値を表しています。ツモったタイミングに合わせて値が跳ねているため、これの変化率を見ればツモの瞬間がわかります。実際にやってみるとうまくいかない場合があります。下図のようなケースです。連鎖光がネクスト欄に重なっており、ナイーブに判定するとツモったとみなされてしまいます。場合にツモったと判定することにしました。絶妙な軌道で連鎖光が発射されると誤判定しそうなので、この判定の改善は将来の課題です。ゲームのせいなのか動画のせいなのかわからないのですが、たまに連続する2フレームが全く同じ画像になっていることがあります。このときに1フレーム前とのピクセル差分を取るとゼロになってしまって誤判定します。今回は3フレーム前と比較することで回避しました。ぷよが消える瞬間の判定ぷよが消える瞬間はスコアを見れば簡単に判定できます。ぷよが消えるときだけスコアは「数値×数値」という表示になります(普段は一つの数値です)。×マークがあるかどうかをパターンマッチで判定することにしました。x軸を時刻、y軸をピクセル差分としてグラフにプロットしてみました。800フレーム目のあたりから13連鎖しているのが見てとれると思います。おじゃまぷよが降る実はおじゃまぷよが降る場合は特に判別しなくても後処理で何とかできるので、処理していません。情報を集約して棋譜を作るこれでぷよをツモる瞬間のフィールドの状況、ぷよが消える直前のフィールドの状況が時刻情報付きでわかったことになります。後は連続する2つのイベントの間のフィールドの差分を取れば、どこにぷよを置いたのかがわかりますし、ぷよの消滅が連続して何回起こったのかを数えれば何連鎖したのかがわかります。実際にある試合の様子を棋譜として出力してみたら以下のようになりました(1Pのみです)。それっぽい棋譜ができました。フレーム目でぷよを1個しか置いていないことになっていますが、これは片方のぷよが画面外に置かれたからです。おじゃまぷよの落下はこの棋譜には書かれていませんが、プログラムの中のデータとしては取得できています。レベルなので、実用にはまだまだ全然足りません。側も取る必要があります。ゲームオーバー判定が背景に依存しているので背景が変わると動きません。ぷよクロじゃなくてぷよスポにも対応したいです。全消しの場合、パターンマッチが誤爆するかもしれません(試してない)。暇を見つけてぼちぼちやっていきたいです。まとめはじめての動画処理でしたが、意外と泥臭い力技で何とかなりました。やってみるものですね。さんの「レコード多相についてお話します」です。平衡二分木を書くのは何となく難しいイメージがありました。使わずに実装できるものなのか気になったので、試しに実装してみました。使わなくても平衡二分木は実装できました。ないとコンパイルが通りませんでした。