【プログラミング】ZDDベースのパーフェクトクリア探索アルゴリズム

テトリス Advent Calendar 2025 11日目の記事になります。

こんにちは。knewjade と申します。 2017年のテトリス Advent Calendarから参加していることに震えていますが、今回はそのテトリス Advent Calendar 2017の17日目の記事と同じ問題に対して最近使っているアルゴリズムを改めて共有できればと思っています。

本文は長いです。（いつもどおり）

想定読者

今回の記事には テトリスのゲームをプレイする上で役に立つことは全く書いてありません。
テトリスをプログラムする側の方に何か参考になればうれしいです。

今回はサンプルコード(Rust)を用意しています。 https://github.com/knewjade/bitris-pc-zdd

この記事やコードを最近流行りの生成AIに入れていただくのも自由に行なってください。なんとなくAIフレンドリーに図もテキストで表現してみました。

問題設定

ブロックが存在しない地形から、任意の10個のミノを使ってできる4ラインパフェの組み合わせをすべて求めよ。

こちらは 2017年の記事のゴールと同じで、4x10のフィールドをピース(ミノ)ですべて埋めるところまでをゴールとしています。回転法則は一旦無視するところも一緒になります。

概要: アルゴリズムの全体の大枠を説明します。
各要素の詳細: 登場する要素のデータ構造や具体例を説明します。
グラフの構築: 各要素を使いながらグラフを構築する際の流れを説明します。
補足＆おわりに: アルゴリズムの使い所や注意点などを記載します。

1. 概要

ZDD

ここで紹介するアルゴリズムはZDDの考え方がベースとなっています。

ZDD（Zero-suppressed Binary Decision Diagram）とは、集合の組み合わせを効率的に表現するデータ構造です。たとえば {A, B}, {A, C}, {B, C, D} のような集合の集まりを、グラフ構造で圧縮して保持できます。同じ部分構造を共有することで、組み合わせ爆発する問題でもコンパクトに表現できる点が特徴です。

今回のパフェ探索では、ZDDの「状態の共有」「遷移をグラフで表現」「解にならない場合は極力省略」あたりで共通した考え方を取っています。厳密にはZDDそのものではありませんが、同じように同一盤面をマージしながら探索空間を圧縮していきます。

探索の基本単位

探索の基本単位は「State - Transition - State - ...」の順番に進みます。 Stateは盤面の状態を、Transitionは操作（ピースの配置）を表します。

[State] --Transition(#0)--> [Next State]
    |
    +-----Transition(#1)--> [Next State]
    |
    +-----Transition(#2)--> [Next State]

1つのStateから、複数のTransitionへ分岐できます。それぞれのTransitionが「どのピースを配置するか（or 何もしない）」という選択を表しています。

探索の順番

パーフェクトクリアはすべてのブロックが埋まっている必要があるため、ブロック単位ごとに必ず埋まるように操作(Transition)を決めていきます。ここでいう操作とはブロックの埋め方を決めているだけで、ゲームのような入力や回転法則は考慮しません。左下から順番に縦方向優先で、「そのブロックを埋められて、他とは重ならないピース」を配置していきます。

探索順序（高さ4の場合）:
x=0,y=0 → x=0,y=1 → x=0,y=2 → x=0,y=3 → x=1,y=0 → ... → x=9,y=3

↓4x10のフィールドで表すと↓

         4........L <- Last 
         37........
         26........
First -> 15........

状態のマージ

操作した結果、同じ盤面状態になった場合はStateを合流させます。

このマージにより、探索空間を大幅に圧縮できます。異なる配置順序でも、同じ盤面になれば同じStateとして扱います。

[State A] --ピースX配置--> [盤面状態 α]
                              ↓
                         [State C] (マージされた単一の状態)
                              ↑
[State B] --ピースY配置--> [盤面状態 α]

終端ノード (State)

ピースを置いた結果すべてのブロックが埋まった場合は、成功を表す「1-State」に進みます。

また、どのピースも配置できず行き詰まった場合は「0-State」に進みます。ただし、ZDDの思想に従い、0-Stateへの遷移は多くの場合省略されます。

[State A] --ピースX配置 (完成)--> [1-State]

[State B] --どのピースも配置できない--> [0-Transition] --> [0-State]

グラフ全体のデータ構造

ここまで説明した一連の流れを、2つの配列を使ってグラフで表現します。 Stateから始まり、TransitionとStateを終端ノードに辿りつくまで行き来します。

State配列:      [0-State] [1-State] [初期盤面] [State #2] [State #3] ...
Transition配列: [0-Stateへの遷移] [1-Stateへの遷移] [操作 #1] [操作 #2] ...

State配列・Transition配列いずれも、0番目と1番目は特殊な終端ノードです。 2番目以降に、実際の探索で使うStateとTransitionが追加されていきます。

2. 各要素の詳細

ここでは登場する各要素の詳細な説明を記載しています。説明はアルゴリズムの核となる要素だけで、サンプルコードのすべては紹介していません。

なお、コードはRustのデータ構造をベースにしています。ただし、Rustを触っていなくてもわかる程度には補足を入れています。

State

Stateのデータ構造は以下のとおりです。

struct State {
    pub transition_index: TransitionIndex, // このStateの操作に対応するTransition配列の開始位置
    pub length: u8, // このStateから続くTransitionの数
}

たとえば State { transition_index: 10, length: 3 } は、Transition配列の10番目から3つの操作ができることを表します。

Transition

Transitionが表す操作は2種類あります。

ピースを配置する：あるピースを盤面に置く操作
何もしない：すでに他のピースで埋まっているのでスキップする

このTransitionのデータ構造は以下のとおりです。

struct Transition {
    pub placement: u16, // 配置するピースの情報（操作を数字にまとめる）
    pub state_index: StateIndex, // 遷移先のState配列の位置
}

ピースを配置しない場合は、placementに最大値（u16::MAX）を設定します。

(placement: u16)で表す配置の数値化

配置するピース情報は16ビットの数字に圧縮しています。このピースは、ライン消去によってピースが縦方向に分離するケース考慮しています。

u16 = [index(上位ビット)] | [using_rows(height分のbit列)]
index = shape * 4 * 10 + orientation * 10 + lx

shape: ピースの種類（I, O, T, S, Z, J, L）
orientation: 向き（North, East, South, West）
lx: ピースの最も左にあるブロックのX座標
using_rows: ブロックを実際に配置する行のビットマスク

例1: T-East (lx=3, 1〜3段目)

     ..........
     ...T......
     ...TT.....
     ...T......
lx = 0  3     9

T-East
lx: 3
using_rows: 0b0111（1〜3段目を使用）

例2: J-North (lx=5, 2&4段目)

     .....J....
     ..........
     .....JJJ..
     ..........
lx = 0    5   9

J-North
lx: 5
using_rows: 0b1010（2段目と4段目を使用）

Buffer

State自身はグラフを構築する上で必要な情報を持っていません。たとえば、フィールドがいまどんな状態であるかも、Stateだけではわかりません。

グラフ構築時には、中間データとして「Buffer」を使います。このBufferはStateと 1:1 になります。要はStateの補足情報のような立ち位置になります。データを具体的にたくさん持つ代わりに、探索中で必要な一部分だけに限定することで、メモリ効率を高めています。

struct Buffer {
    pub board: Board32, // 盤面の状態
    pub remaining: u8,  // 残りの空きマス数
}

Bufferは「今後全く同じとして扱って良いか」を判断するための情報を持ちます。同じBufferを持つ状態は、同じStateとしてマージされます。

たとえば「各種ミノで使える個数を1つずつ」という制約をつける場合を考えます。フィールドのブロックの置き方が同じでも、過去にどのミノを使ったかで今後の選択肢が変わります。その場合はBufferに「どのミノを使ったか」の情報が必要になります。

3. グラフの構築

Buffersが持っている範囲

グラフの構築は幅優先で行います。「そこまでにわかっているすべてのStateに1つ操作を加えて、新しいStateのまとまりを作る」を繰り返します。

[操作前のState群] --すべてのStateに1つずつ操作を加える--> [1手進んだState群]

操作順はブロック単位なので、Buffersはブロックを埋める前の状態と埋めた後の状態

【x=2,y=1のブロックを埋めた後の各データ】

PrevBuffer:  | この範囲のStateの数と同じだけのBuffer     |
NextBuffer:                                             | この範囲のStateの数と同じだけのBuffer      |

             | 操作前のStates,Transitions (x=2,y=0まで)|  | 操作後のStates,Transitions (x=2,y=1まで) |
States:      [State], [State], ... .........., [State], [State], [State], ..............., [State]
Transitions: [Trans], [Trans], .............., [Trans], [Trans], [Trans], .......,........ [Trans]

構築の詳細な手順: サンプルコードの具体例

各ブロック位置で、あるBufferから次のTransitions・States・Buffersを作成する処理の一部を記載します。

1. すでにブロックが埋まっている場合

そのブロックが前のピース配置で埋められている場合は、何もしないTransitionを1つだけ作ります。そして、Bufferはそのまま次にコピーされます。

// すでにブロックが埋まっている場合は操作する必要がない
if current_buffer.board.is_occupied_at(location) {
    // スキップした新しいBufferを作る。実体はコピーされるだけ
    let next_buffer = current_buffer.skip();

    // 次のStateの場所を決める。もし同一状態があれば、同じインデックスにマージされる
    let next_state_index = next_state_registry.get_or_insert(next_buffer);

    // 何もしないTransitionを作って、Transitions配列に追加する
    let transition = Transition::noop(next_state_index);
    transaction.write_transition_unchecked(transition);
}

2. ブロックが空いている場合

そのブロック位置を埋められるピースをすべて配置してみて、配置できる組み合わせは次に進みます。

// そのブロック位置を埋める可能性のあるピースをすべて試す
for placement in current_placements.iter() {
    // Bufferの状態に新しく配置してみる
    let Some(next_buffer) = current_buffer.put(placement) else {
        continue; // 他のピースと重なる場合はスキップ
    };

    // 配置できる場合は進む

    let next_state_index = if next_buffer.is_completed() {
        // 配置した結果、パフェが完成するなら、1-Stateに繋げる
        StateIndex::TRUE
    } else if is_last_block {
        // 最終ブロックで未完成な場合は諦めて、0-Stateに繋げる
        StateIndex::FALSE
    } else {
        // パフェは完成していないが、今後完成する可能性はまだあるので、次に進める
        next_state_registry.get_or_insert(next_buffer)
    };

    // 操作を数字に変換した上で、Transitionを作って、Transitions配列に追加する
    let placement = converter.freeze(placement);
    let transition = Transition::operation(placement, next_state_index);
    transaction.write_transition(transition);
}

グラフ構築後

グラフが完成したら、ルートノードからStates・Transitionsを再帰的に辿ることで、探索結果を復元できます。最終的に1-Stateに到達するすべてのパスが、この探索での解となります。

4. 補足＆おわりに

アルゴリズムの説明は以上になります。最後にこのアルゴリズムの補足を書きつつ、終わりになります。

このアルゴリズムの使い所

テトリスの1手ごとの幅優先探索との相性が良いアルゴリズムです。このアルゴリズムの核は「中間状態をどう定義するか」です。幅優先探索で解ける問題に対しては、問題に沿った中間状態とその遷移をうまく設定すれば、おそらくどのような問題でも効率的に探索が可能です。

このアルゴリズムが向かないケース

たとえば、テトリスAIのように、探索を繰り返しながら深くしていく探索には、データの保持の仕方的に適していません。

パーフェクトクリア探索における注意

このアルゴリズムにより、フィールドを埋めた状態の列挙までを非常に高速に行えます。たとえば4x10のフィールドであれば、サンプルコードでは約1ミリ秒で5億程度のすべての組み合わせを発見できます（※ Mac mini 2023で実行）また5億ほどの解を、たった4168個のState・7837個のTransitionで表現できています。

Execution time: 1.132375ms
graph.states.len() = 4168
graph.transitions.len() = 7837
count = 522230555

しかしながら厳密なパーフェクトクリアを見つけるには、以下の考慮が必要なことに注意してください。 (この考慮が必要な点は2017年時点と同じです)

1. フィールドを埋められるが、実際に配置できない組み合わせが含まれている

各ミノで必要なライン消去が矛盾しており、実際に配置できない組み合わせも含まれています。たとえば、以下の例は 2つのT(TとXで表現) で2x4を埋めていますが、どちらのTも最初に置けないため配置できません。

TX
TT
XX
TX

今回紹介したいアルゴリズム範囲外だったためサンプルコードには含めていません。しかしながら、最終的に解から除外する必要があります。ちなみに次の考慮点を解消すれば、自動的に解決されます（ただし高速化する場合は、経験上、別の方法で高速に除外したほうが良いです）

2. 回転法則によっては配置できない組み合わせが含まれている

「ハードドロップのみ」と「SRS」で可能なパーフェクトクリアが異なるように、最終的には回転法則に従って配置できるかは別途チェックが必要です。そして残念ながら、もっとも時間がかかるのはこのチェック処理になります。

この処理の高速化は、去年の記事のようなテクニックを使っていくことになります。

おわりに

このアルゴリズムは、2017年にまとめた方法より速く、また他の問題にも応用しやすいので、しばらく気に入って使っています。この仕組みを使い始めてしばらく時間が経っており、マイナーチェンジを繰り返しながら、いまはこの形に落ち着きました。今後大きく変わることはなさそうです（根本から異なるアルゴリズムが登場しない限りは）テトリス探索において応用が効きやすいので個人的によく使っているので、使えそうなことがあれば参考になればうれしいです。

knewjade/zdd-based-perfect-clear-enumeration.md

Select an option

No results found