Implementation of legal move generation in Tetris

move_generation.md

テトリスにおける合法手生成

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

こんにちは。knewjade と申します。 前回のテトリス Advent Calendar 2017では newjade で参加していて、当時はパフェを研究してました。 そのあとはプログラムで色々つくったり調べたりしていました。最近は低空飛行気味ですが、いまだにテトリスを考えるのは楽しいものの、作業時間が他の興味にとられ続けてる民です。

今回はSRS周辺のプログラム実装の知見について書いていきたいと思います。

対象読者 テトリスのプログラムを書いている方。ゲームプレイの話は一切でてこないです

本日の問題

ここで解きたい問題は以下の通りです。 簡単にまとめると次に置けるミノの位置を求めたいということです。

あるフィールドと操作するミノの種類が与えられたとき、最終的に接着可能な[座標,ミノの向き]をすべて列挙する。

実装の前に

本題に入る前に、前提となるいくつかの技術と用語を整理します。

SRS

テトリスの回転操作では、ミノの回転ごとに移動先候補がいくつかが決まっており、その中で一番最初に移動できる位置に移動する形で行われます。 SRSもこの仕組みに沿っています。 SRSを具体的にわかりやすく説明しているサイトはたくさんあるのでそちらを参照してください！

• Harddrop: https://harddrop.com/wiki/SRS
• Tetris Channel (日本語): https://tetrisch.github.io/main/srs.html

Bitboard

ボードゲームの探索でよく使われるテクニックの一つで、盤面をビット列(0/1)で表現するものです。

近年のテトリスのゲーム内では各ミノに色が決まっているため、画面上のフィールドがカラフルに見えることが多いです。 その一方で、ゲームの基本ルール上で色情報が使われることはありません。 たとえば「1列がそろっている」というルールは、ブロックの存在のみで判定できます。 そのためブロックの存在を0/1で表現することで高速に処理できます。

テトリスのフィールドを表現するには、配置可能なエリアに絞っても幅10x高さ20のマスと200ビット以上が必要となります（※実際にはさらに上部にもブロックがあり、移動もできるためもっと必要です）。 そのため、複数個の変数（配列）で表現されることも多いです。

このときのデータ構造は、ブロックを辿っていく方向で大きく2つに分けられます。

行指向 (row)

横方向に1行を1つのまとまりとしてデータを持つ形式です。 得意な処理は横方向に参照する処理で、たとえば「1列がそろっているか」の判定は簡単にできます。

＜使用例＞

• MisaMino: https://github.com/misakamm/MisaMino
• cold-clear (v1): https://github.com/MinusKelvin/cold-clear
• solution-finder::percent (1変数6行): https://github.com/knewjade/solution-finder/tree/main/src/main/java/core/field
• fast-reachability (※筆者が見た中で最も速そうな合法手生成の実装): https://github.com/ImpleLee/fast-reachability/tree/main

列指向 (column)

縦方向に1列を1つのまとまりとしてデータを持つ形式です。 持ちたいフィールドの高さに合わせて、その高さ分の型の配列で表現します。 実際のゲームを想定すると、64ビットの型(e.g. uint64_t, u64)の配列で表現することになると思います。

得意な処理は縦方向に参照する処理で、たとえば「ハードドロップしたときに地面はどこになるか」の判定は簡単にできます。

＜使用例＞

• solution-finder::path,setup (1変数の中で列指向): https://github.com/knewjade/solution-finder/blob/main/src/main/java/core/column_field/ColumnSmallField.java
• cold-clear-2: https://github.com/MinusKelvin/cold-clear-2
• bitris: https://github.com/knewjade/bitris
• テトリス Advent Calendar 2024 12日目のCSDotNETさんの記事: https://zenn.dev/csdotnet/articles/f6d0eb58f9d3f3

結局どちらが良い？

筆者は全然わかりません。無難なことをいうとユースケース次第な気がします。
たとえば、4ラインパフェのようにある特定の行しか利用しない場合は行指向が有利で、
パフェ全列挙のように探索順が列ごとなら列指向が有利です。
今回紹介する合法手生成はどちらでも実装できるので、良い結論がみつかったらぜひ教えてください。

この記事で「位置」と呼ぶものは？

「ミノの座標」と「向き」をセットで扱ったデータをここでは「位置」と表記します。 例）上向きSミノと下向きSミノは同じ座標でも位置は区別される

なぜ向きもセットで扱う必要があるかというと、見た目のブロックの配置が同じだとしても、ミノの向きが異なるとその次の回転で到達できる座標も変わるためです。

本題

よくある実装と課題

テトリスの合法手生成でよくみる実装は以下の通りかなと筆者は思っています。

1. Queueにスポーン位置を記録
2. Queueから現在位置を取り出す
3. 移動（左右下）・回転後の移動位置を求める
4. 3のうち、まだ訪れたことがない位置であればQueueに追加する
5. Queueが空でなければ2.に戻る。空なら終了

このアルゴリズムはとてもシンプルな一方で、すべての到達可能な位置の数だけSRSの判定が行われます。 テトリスの探索処理で「SRSがボトルネック」になる場合は、SRS1回の処理が重いというよりも、SRSの処理回数が増えることが原因になりやすいかなと考えています。

今回紹介する方法

各位置で独立してSRSすることが課題であると考えると、 「複数の位置のSRSをまとめて行うと、トータルの回数が減って高速化できるのでは」というのが今回のアイデアです。

SRSの判定処理そのものはかなりシンプルな仕組みなため、1回あたりを改善するにも限界があると思っています。 （SRSの回転テスト(移動できるかの判定)はBitboardだと高速に判定できてしまう故）

だからこそ、回数をどれだけ減らすことができるかが重要なポイントだと筆者は考えています。

アルゴリズム

全体像

アルゴリズムの基本的な流れは以下の通りです。

1. 事前計算：ミノがブロックと重ならない位置をすべて列挙
2. スポーン位置を到達可能な位置として記録
3. 移動操作によって新しく到達できる位置を求める
4. 回転操作によって新しく到達できる位置を求める
5. 手順3,4で到達可能な位置に変化があれば3.に戻る。なければ終了

全体の流れ自体は「よくある実装」とほぼ同じ構造です。 2つで異なる点は、「よくある実装」では1ループで1つの位置の移動・回転を行うのに対し、このアルゴリズムではその瞬間にわかっている到達位置からのすべての移動・回転を同時に行うという点です。

各手順の詳細を以下で説明していきます。

手順1: 事前計算

配置可能な位置をまとめて計算して、回転方向ごとに保持しておきます。 これにより今後、1bitの判定で回転・移動できるかを判定できるようになります。

ちなみに手順2以降の計算はこの事前計算結果だけで完結することができます。 結局のところ、移動できる／できないさえわかれば十分で、毎回4ブロックを動かす必要はありません。

【例：下向きTミノで配置可能な位置を計算する】

この手順ではフィールドを、ブロックの形に合わせてどこか1箇所に集まるようにスライドします。 スライドした結果、4つすべてが空白であればそこは配置可能な位置となります。

ちなみに画像では回転軸に集約していますが、どこに集めるかは好きなように決めても問題ありません。 筆者は左下に集約しています。

手順3: 移動

すでにわかっている到達位置から右／左／下移動で移動できる位置を求めます。

【例：右に移動する】

右移動の場合はわかっている到達位置を右に1つずらして、事前計算した配置可能な位置とのANDを取ることで次に移動できる位置を求めることができます。 そして元の到達可能な位置とのORを取って、新しくみつけた位置を含んだ到達可能な位置として記録します。

左移動・下移動も同じように求めることができます。 この処理をすべてのミノの向きで行います。

手順4: 回転

移動（手順3）と同様に、すでにわかっている到達位置から右／左回転で移動できる位置を求めます。

【例：左回転する】

ぱっと見は複雑ですが、処理自体は「右移動」とほとんど変わりません。 到達位置を回転先にあわせてずらして、事前計算した配置可能な位置とのANDを取ることで実際に配置できるかを判定できます。

移動との違いは、SRSではいくつかのテストパターンがあるため、それらをすべて試す必要がある点です。 テストして回転後に配置できるとわかった位置は次のテストパターンには進まないため、都度NANDを取って回転できなかった位置だけを次のテストに進めます。 最後にすべてのテスト結果を、元の到達可能な位置とのORを取って、新しくみつけた位置を含んだ到達可能な位置として記録します。

左回転も同じように求めることができます。 この処理をすべてのミノの向きで行います

手順5: 終了判定

移動／回転処理を行っても到達可能な位置に変化がなくなれば、さらに到達できる位置はないと判断できます。 したがってその瞬間の到達可能な位置の中で、地面と接着している位置（1つ下にブロックがある位置）が合法手となります。 （接着も事前計算結果から1bitで判断できます）

さいごに

さらなる改善

基本的なアルゴリズムの紹介は以上ですが、細かく改善できるところはあります。

たとえば、処理の重さは "移動処理＜回転処理" なため、最初に移動範囲をなるべく増やしておくと回転回数を減らすことができます。 空のフィールドのような移動だけですべての位置に到達できるフィールドに対しては、回転1回だけで処理を完了できる可能性もあります。

もし他に良い改善案とかあればぜひ教えてください！

実装の紹介

ここで紹介したアルゴリズムの実際の実装を2つほど紹介します。

bitris (著者の実装)

https://github.com/knewjade/bitris/blob/main/src/internal_moves.rs#L414-L519

Rustで書かれています。 基本的な流れは紹介したものをそのまま実装しています。 ただ12日目のCSDotNETさんが紹介したようなSIMD的な高速化は取り組んでいないなど、そこまでの最適化はまだされていません。 （筆者がMacユーザーなこともあり、どちらかというと環境互換やメンテナンス性を重視しているため）

fast-reachability by ImpleLee

https://github.com/ImpleLee/fast-reachability/tree/main

C++で書かれています。 今回紹介したアルゴリズムと同じアプローチで、かつSIMDでの最適化も実践されています。 そのため、筆者がこれまで見た中で一番速い実装な気がしています。 本当に速度を求めている方は参考になると思います。

ひとこと

テトリスはプログラミングのチュートリアル的に作られることも多いものの、SRSはそのときだいたい省略されがちですが意外と奥が深いので、みなさんどんどん実装していきましょう！！！

Hi! Thank you for writing this post. It was a nice read!
Just a quick note, the original algorithm was created by wirelyre 3 years ago.
Here is their implementation in their PC finder:
https://github.com/wirelyre/tetra-tools