無限に4列RENを繋げたい！
みなさんこんにちは、Mです。
今回もテトリスのお話です。
はじめに
中開けREN、強いですよね。
わたしは今お盆休みで帰省しているのですが、弟たち3人をまとめて刈り取る生活を送っています。
でも、中開けRENには弱点があります。
つながらない場合があるということです。
ミノのツモ順によっては、どうあがいてもRENが途切れてしまう場合があります。
...本当にそうなのでしょうか？
まだ発見されていないだけで、どんなツモ順でも半永久的にRENを繋げられる消し方が存在するのではないでしょうか？
そうおもった私は、さっそく研究してみることにしました。
RENの基本について
あらかじめ、RENについて軽く触れておきます。
RENは、(おもに対戦形式の)テトリスゲームの戦術の一つです。
特定の形にミノを積み上げ、落ちてくるミノを使って連続でライン消去を狙います。
ミノを積み上げるやり方にはいくつか種類がありますが、2~4列を開けた状態で高く積み上げるのが基本です。
開ける幅が狭くなればなるほどライン消去できるミノが多くなり、広くなればなるほどライン消去できる回数が多くなります。
そのため、正しい消し方が判断できることを前提に、実戦では最も間隔の広い4列RENを用いることが多いと言われています。
今回も、できるだけ多くの回数RENを繋げることが目的ですので、4列RENを対象に考えます。
※より専門的には、種3の4列RENを対象にしています。参考にしたサイトが種3だったから、というのが正直な理由です。
4列RENにおける地形の特徴
4列RENの消し方については、こちらのページを参考にしました。
piyoureharehare.blog92.fc2.com
※参考にしたというより、そのまま利用させていただいています。
このページを眺めていて、気づいたことがあります。
それは、無限にRENを繋げるには、いずれかのミノでライン消去できる地形を常に維持する必要がある、ということです。
これは当然のことのように思われるかもしれませんが、ある地形からあるミノを使ってライン消去するとき、消したあとの地形もさらに何れかのミノでライン消去できる形でなければなりません。
4列RENにおける地形は、基本的に下部2段の8マスに対するミノの有無で区別されます。今回は種3なので8つのうち常に3つのみにミノが存在することになります。
この地形の組み合わせは有限ですが、前述のように、その地形が(無限にループすることを前提とした)RENの途中に発生するとき、その地形は以下の2つの条件を満たす必要があります。これらの条件を満たす地形を「適切な地形」と呼ぶことにすると:
(1)適切な地形から、何れかのミノ1つを使ってライン消去したあとに発生する地形であること。
(2)そのミノを使ってライン消去することで、この地形から何れかの適切な地形を発生させることのできるミノがIミノの横置き以外に1つ以上存在すること。
※Iミノを横置きし続けることで、いかなる地形でも無限ループが可能になりますが、7種一巡の法則を満たさないため、そのようなパターンは考慮しません。
言い換えれば、「適切な地形」→Iミノ横置き以外のライン消去→「適切な地形」...の形で、(かつこの形でのみ、)RENの無限ループは構成されるべきだということです。
上述したページでは、そのような条件を満たす地形が14種類、左右反転を区別すると28種類が挙げられています。
※地形の横幅は必ず4マスであることから、左右対称の地形は存在しません。
状態遷移図を書こう
ここで、当然にあるアイデアが生まれます。
4列RENが有限個の地形間を遷移し続けるなら、その様子は状態遷移図として表現できるのではないでしょうか。
この状態遷移図の中から、あらゆるツモ順に対応した無限ループのルートを発見できれば、目的のルートが得られます。
そこで、さっそく状態遷移図を書いてみることにしました。
draw.io(diagrams.net)で書いてみる
まずは普段慣れ親しんだ描画ツール、draw.ioを使って書いてみます。
※このサイトって、「draw.io」と「diagrams.net」のどちらが正しい名称なんでしょうか？
画面右側の「スクラッチパッド」から、画像をアップロードして利用することができます。
...
あまりにも煩雑になってしまい、手書きで作成するのには無理がありそうです。
なにか他の方法を考えることにしました。
Graphvizを使おう
すべてを手書きするのではなく、状態同士のつながりを記述して、自動的に図を生成してくれるようなソフトはないのでしょうか。
調べたところ、こんなページが見つかりました。
ほしい機能にぴったりです。Graphvizを用いて状態遷移図を作っていくことにします。
※Graphvizが生成するのは有向/無向グラフですが、有向グラフと状態遷移図の違いがよくわかりませんでした。今回はこれを状態遷移図として扱うことにします。
こんな感じで状態どうしのつながりを記述していきます。消去に使うミノは、エッジの色で表現することにしました。
300行弱のソースコードを記述して、CUIを叩くだけで、このような図が生成されます。
行き先が存在しないことを「end」という状態で示したのですが、あまりに多くの矢印がendに集中するのでわかりにくくなってしまいました。
そこで、endへ行く矢印と、Iミノによる自分自身への変化を省略した図がこちらです。
正直、この状態でも人間の手には余りそうです。次回以降、もう少しこの図を処理しやすく加工していきます。
ここまで読んでいただき、ありがとうございました。
M
参考文献
記事内にURLを示したサイトのほかに、以下のページを参考にしました。
