テトリス Advent Calendar 2017 17日目の記事になります。
こんにちは。newjade と申します。普段はパフェ用のツールを作りつつ、理論値を調べているパフェ屋さんです。だいたい twitter に出没しています。
今日はタイトルにもある通りプログラミングネタ、アルゴリズムの話です。
まず最初に断っておきたいのは、
今回の記事、テトリスのゲームをプレイする上で役に立つことは全く書いてありません。
枠もあまってましたし、 たまにはこういう記事もいいかなぁと勝手に思ってます。
テト界隈には情報系出身者が多いとの風の噂をききましたし、
テトリスはゲームづくりの入門でつくる方も意外と多そうですし、
そういう方には少しは楽しんでもらえるかも？
そんなところで本題です。
一応、今日のメインとなる問題を確認しておきます。
問題
ブロックが存在しない地形から、任意の10個のミノを使ってできる4ラインパフェの組み合わせをすべて求めよ。
問題は単純です。回転法則によって解は若干変わりますが、SRSに従って今回紹介するアルゴリズムで個数求めたところ、2373万7025通りの組み合わせがあるらしいです。
おそらくピンと来ないと思いますが、7種1巡上でありえそうな組合せに絞って一覧にした画像が以下のリンク先にあります（4日目でもさらっと紹介しましたが）。
http://www.gigapan.com/gigapans/201912
既に色々おかしいですが、これでも876万290通りなので、全体はこれの約2.7倍です。
たとえば、Iミノ10個のパターンは上の画像に載っていませんが、これだけでも結構な組合せが考えられます。
完全に組合せ爆発してます。
テトリスの歴史はそれなりに長いので、このパフェの組合せは既に求めらているかと思っていましたが、意外といないっぽいです。ちなみに学術的には ポリオミノ とか 計算幾何学 などの分野にあたりますが、テトリスではライン消去・回転法則など独自ルールがあるため直接関わりがあるものは少なさそうです（個人的な印象）。
そういう背景もあり、テトリスで探索プログラムをかきたいと思う方がいるかは微妙なところですが、拙作の solution-finder で実装したパフェ探索アルゴリズムの基本的な考え方を残しておきます。
パフェを探索するツールをみてまわった印象では、バックトラック法が主流（？）な気がします。
文字だけで適当に説明をすると、次の感じです。
＊ミノが置けそうなところをみつける
- もし置けるところがある場合
とりあえず適当に置いてみる。
その結果、パフェができたら記録する。まだ隙間があるなら次のミノへ進む（＊に戻る）
- もし置けるところがない場合
もうパフェは狙えないので、1手戻ってミノを置き直す。
置き直すところもないときはさらに1手戻って...を繰り返す
定番の探索アルゴリズムなので、詳細な説明は他に譲ります。プログラミングの練習にはもってこいなアルゴリズムです。
パフェ探索でのバックトラック法の短所をざっと挙げるとこんなところです。
-
設定した問題にある「任意の10ミノ」を出すには、工夫しないとこれを7^10回やる必要がある
- ミノを置く順番に影響を受けるため、組合せではなく順列で考えなければならない
-
L→S と S→L のように手順は違うが、結果的に同じ地形になるケースが大量に発生する
- 同じ地形は、ひとつ以外カットする方法が考えられるが、そのときは↓の扱いが難しい
-
LS と JZ のようにミノの組合せが違うが、結果的に同じ地形になるケースの扱いが難しい
- 3ミノで同じ地形、4ミノで同じ地形… となっていくのが厄介
実際に組んでみた印象だと、パフェ可・不可の判定には有用ですが、今回の問題設定で解くのはムリそうだと思いました。
バックトラック法の方向性では限界そうだったので、ゼロからアプローチを考え直しました。
このアルゴリズムの最も大きな枠組みは次のようになります。
- （実際に置ける置けないに関わらず）4x10のブロックをすべて埋める10ミノの組合せを列挙する
- 1で求めた地形に対して、ライン消去や回転法則に従い実際に置ける手順であるかを判定する
1.では、ミノをx座標固定・ライン消去も含めた形で定義して、あとはブロックをひたすら詰めることに注力します。 テトリスでは、ミノがライン消去によって縦方向に分離することはあっても、横方向には分離することはありません。そのため4ラインパフェに限定すると、ミノの種類は現実的な個数に落ち着きます（764種類）。
その上でフィールドを埋めていくと、絶対に組み立てられない組合せが含まれます。
こういった組合せを弾くのが、2.の領域になります。
このように問題を分離することの最大のメリットは、探索を効率的に行いつつ、条件の判定をギリギリまで遅らせて柔軟に対応できる点です。 たとえば、「ハードドロップだけでできる」「テトリスパフェのみ」といった条件も2.を厳しく判定することで対応できます。回転法則などによって、パフェの組合せ自体が変わるのではなく、あくまで選択肢が変わるだけです。
2.は条件付け次第なので、とりあえず後回しにしても良さそうです。
ちなみに自分の実装で、速度的に最もボトルネックになっているのは「SRSで置けるかどうか」の判定です。これもわりと悩ましい問題ですが、この時点で解候補が既に絞られているので、影響範囲を限定できています。
1.だけを考えるなら、問題が少しだけ簡単になりました。764C10 個の組合せについて判定すれば良さそうです。
残念ながら、まだまだムリそうです。これをなるべくはやく列挙させたいです。
ここでテトリスの特性を少し考えてみます。
パフェの組合せは狭い範囲で考えると、どの列で組むかはそれほど影響がありません。
下の地形後の展開はそれほど大きく変わらないです。
そう考えるとパフェの組合せは、横の移動に強いと言えます。
それならば、フィールドを4x3の領域に分割して埋めて、その結果を横に移動させる方法は有効そうです。
ちなみになぜ幅が3なのかというと、横に最も長いIミノでも必ず2つの領域内に収まり、都合が良いためです。
このことから、一番左の領域（領域1）を埋めかたがわかれば、隣の領域（領域2）の状態が決まります。
従って「領域1の埋めかたが決まる」→「領域1から右にはみ出たブロックの配置が決まる＝領域2の状態が決まる」→「領域2のミノの埋めかたがわかる」となります。 そして同様に、そのまま領域3の状態もわかります。領域3の状態が決まれば、領域4の状態がわかります。
ただし、領域4は右端なので1列しか空いてません。
つまり、この時点で領域4がなり得る状態は次の3つしかありません。
- 領域4が空 = Iミノを立ててパフェ
- 領域4が全て埋まっている = 既にパフェが完成済み
- 領域4の壁と重なる = 解ではない
つまり、「すべての4x3領域の埋めかたと、そのときの隣の領域の状態」がわかっていれば、それを3回再帰させるだけですべてのパフェを列挙できるということです。
問題が簡単になってきました。
次は4x3の領域を埋めるミノの組合せがわかっていれば十分そうです。
ミノの組合せさえわかれば、隣の領域の状態は簡単に計算できそうです。
注意がひとつあります。
それは左の領域からどのようにブロックがはみ出てくるかはわからないため、4x3領域の初期状態は色々あります。
初期状態の数は単純に考えると、2^12=4096地形となります。簡単そう！に思えますがまだ結構つらいです。
4x3は一見狭そうですが、ミノをおくとき領域内に1ブロックでも入っていればOKなので、最大6ミノまで詰め込めます（右側には出るが、左側には出ない）。
それを4096回、独立して計算させるとそれなりの時間（とメモリ）がかかります。
これをはやく（＆軽く）したいです。
最終的に目指す状態は、すべての12ブロックが綺麗に埋まっている状態です。
この状態になれば、ミノをさらに追加する必要はありません。
さて、ミノの埋めかたを考えていきます。
もしも、隙間のある領域に1ミノを置いたとすると、最低でも1ブロックは消費することになります。
つまり、既に11ブロックある領域に1ミノ置いたとき、必ず12ブロックとなります。
そのため、このときのミノのおきかたは簡単に列挙できます。
同じように考えて、既に10ブロックある領域に1ミノをおくと、11ブロック or 12ブロックになります。
これらの結果は計算済みなので、その結果に1ミノ分加えればOKです。
つまり、nブロックある領域に1ミノを加えると、n+1ブロック以上の領域になります。
このことから、12ブロックの地形（全て埋まっている状態）から0ブロックの地形（空の状態）を順に計算することで、大部分の計算を再利用できることになります。
改めて全体を俯瞰すると、
- 4x3領域自体は、12ブロックある地形からの再帰
- 4ラインパフェ自体は、4x3領域の再帰
で求められます。つまり、パフェは再帰的に計算・表現できるということです。
そのため、このアルゴリズムだと、再帰のメリットを最大限が得られることになります。
- 最後の領域までの間に、明らかにパフェできない地形が一切生成されないため、解候補の生成が効率的
- ＝ 枝刈りがない
- 最後の領域の壁とのあたり判定は、それまでの計算結果（隣の領域の状態）から計算できる
- 新たな計算が不要で、かつフィールドをビット列で実装していれば
x & y == 0で一撃
- 新たな計算が不要で、かつフィールドをビット列で実装していれば
- パフェ自体も再帰で表現できるため、結果を保持するためのメモリ量を抑えられる
- 自身の計算結果 と 前の計算結果への参照 を持っていれば低コストで再計算可能
solution-finderでは実装に次のような最適化をいれて、さらなる高速化と省メモリを両立させています。
- フィールドのブロックを “列指向” で持っている
- 横移動が
<<で行える。列指向はたぶん珍しい - 4x3で計算する地形を最小限化＆結果が必要になるまで計算を遅延
- マルチスレッド化
ちなみに高さ5以上の探索では、領域の幅を3ではなく2にしています。
計算は多少複雑になりますが、メモリ的に厳しいためそうしています（領域の初期状態が2^15地形だと厳しい）。
ニッチな記事を読んでいただきありがとうございます。
パフェ探索アルゴリズムの説明を書ききれて満足です。
アルゴリズム自体も綺麗にまとまったかなと自分では思ってるのですが、どうなんでしょう。
現在は回転時のミノの移動先を高速に計算できたらいいな（特にSRS）と思いつつ、それこそ先人がいらっしゃいそうなので、何かご存知の方はぜひ教えてください。
18日目は、りょくちゃさんの「私はいかにして全作GMを勝ち取ったか」です。超大作なのでぜひ読んでみてください。
テトリス Advent Calendar 2017 も引き続きよろしくです。