はじめに
この記事は Siv3D Advent Calendar 2024 13日目の記事です。
Tetris®を知っていますか？簡単に説明すると、降ってくるブロック(ミノ)をいい感じに配置してブロックを消していこう！という具合のゲームです。今回はこのゲームを自動でプレイさせてみました。
ソースコードはGitHub Gistで公開しているのでぜひ動かしてみてください。
※自動でプレイさせた、のであって高得点を目指すAIを作ったわけではありません
テトリスを作る
ガイドラインを見よう
テトリスを自動でプレイさせたいので、当然テトリスをOpenSiv3Dで実装してやる必要があります。単にブロックを落とすだけのテトリスであれば簡単ですね。あまり考えずに実装ができそうです。しかしテトリスはそう簡単なゲームではないのはご存じの通り。いわゆる「七種一巡の法則」や「T-spin」なども実装しなければテトリスと言い張ることはできません。
でもご安心を。今の時代、なんとテトリスのガイドラインがあって、そこにテトリスのほぼ全てが記載されているのです！そこに書かれている通りに実装をしていけば、本物さながらのテトリスを作ることができます。
本来のテトリスであれば時間経過でミノが強制的に設置されたり、ミノが地面に接している状態で可能な回転数の制限があったり等々がありますが、今回ではその部分は実装しないことにします。自動プレイなら迷うことがまずないですからね。代わりに、ソフトドロップの操作の仕様を少し変更します。通常のテトリスにおけるソフトドロップの効果は「落下速度を上昇させる」です。しかし今回はブロックの自然落下はしないので、ソフトドロップでは「ブロックを一段下げる」ことにします。
余談
この記事でのテトリスとは別に、人間がプレイするためのテトリスの実装をGitHub上で公開しています。よければどうぞ。もちろんOpenSiv3Dです。バージョンは0.6.2ですが、少なくともv0.6.xの内は動くはずです。今回の実装はv0.6.15を使用していて、このプログラムの切り貼りでテトリスを実装しています。
エージェントを作る
ではテトリスを自動で遊ばせる仕組みを作っていきます。強化学習の分野でこういうものをエージェントと呼ぶので、この呼び方をしていきます。
エージェントがやるべきことは大まかに次の三つの繰り返しです。
- ブロックの置き場所を列挙する
- 一番いい置き場所を見つける
- 決めた置き場所に向かって操作をする
競技プログラミングの文脈で書くと、これの1と3はBFSと経路復元で実装できます。
以下で詳しく説明していきます。
ブロックの置き場所を列挙する
ブロックの置き場所は様々で、同じ場所に置いても向きの異なる置き方があります。このようなものをすべて列挙するために、幅優先探索というアルゴリズムを使います。
全てのミノは、盤面の真ん中一番上で上を向いた状態で登場します。この状態から左右移動や回転、ソフトドロップを行った後の状態は簡単に列挙できます。操作すればいいのです。そしてこれによって分かった状態からまた操作をすれば、二回操作した後の状態が列挙できます。これを繰り返すと、0回以上の操作で到達しうるミノの状態がすべて列挙できるわけです。
これだけではまだ足りません。これだと空中で止まっている状態まで列挙されますが、そのような状態ではまだミノは設置されていないからです。そこで、列挙されたすべての(空中かどうかを問わず)状態からハードドロップをして、その後の状態をブロックが設置された状態として列挙します。
こんな感じのプログラムになります。
std::pair<Array<TetriMino>, HashTable<TetriMino, std::pair<TetriMino, int32>>> genTerminals(const TetriState& state, TetriMino mino)
{
Array<TetriMino>que; // 幅有線探索用のキュー
que << mino;
HashTable<TetriMino, std::pair<TetriMino, int32>> history; // 後述
Array<TetriMino> terminals; // 置いた状態
history[mino] = { mino, 0 };
while (not que.empty())
{
const auto now = que.front();
for (int32 action : step(6))
{
auto nextMino = updateMino(state, now, action + 1); // 操作してみる
if (!nextMino) continue; // 操作できなかった場合
if (action == 5) // ハードドロップで確定
{
terminals << *nextMino;
}
else
{
if (history.contains(*nextMino)) continue;
history[*nextMino] = { now, action + 1 };
que << *nextMino;
}
}
que.pop_front();
}
return { terminals, history };
}
一番いい置き場所を見つける
置き場所を列挙できたので、次はどの置き場所を目的に動くかを決めていきます。今回はそのために、書く置き場所がどれくらい「良い」置き場所かを計算し、最も「良い」置き場所を採用することにします。この評価基準は
- 穴をふさぐような置き方はしない(1か所あたり100000の罰)
- なるべくミノを下に配置する(ミノのy座標×10の報酬)
- 高低差をあまり作らない(左右の高低差×10の罰)
の3つで決めました。もう一度注意すると、今回は「テトリスを自動でプレイする」ことが目的で、「テトリスを上手にプレイする」ことが目的ではありません。したがってスコアはどうでもよく、長く続けばいいのでこうした評価基準にしています。(上手いプレイをさせたいなら最低限遺伝的アルゴリズム使って学習する羽目になりそう)
決めた置き場所に向かって操作をする
最後は決めた置き場所への操作を求めます。この操作は、実は最初にブロックの置き場所を列挙した段階で間接的に求まっています。状態が列挙されたときにその状態が「どの状態から」「どの操作によって」遷移したのかをメモしておけば、それを最後からたどればいいのです。具体的には、決めた置き場所から、その置き場所が遷移した元とその操作を取得して、操作を何かしらの配列に追加し、同じことを遷移元の状態で繰り返すことをします。そうすれば、操作を追加してきた配列は実際に行うべき操作を逆順で並べたものになります。
プログラムではこんな感じの実装です。(コメントアウトしているのはホールドや操作短縮の実装です)
Array<int32> genAction(const TetriState& state)
{
HashTable<TetriMino, std::pair<TetriMino, int32>> history;
Array<TetriMino> terminals;
auto [terminals1, history1] = genTerminals(state, state.curMino);
// TetriMino holdMino = state.hold == 0 ? TetriMino{ state.nexts.front() } : TetriMino{ state.hold };
auto [terminals2, history2] = genTerminals(state, holdMino);
terminals.append(terminals1);
// terminals.append(terminals2);
history.merge(history1);
// history.merge(history2);
int32 terminalIdx = selectTerminal(state, terminals); // いい状態を選ぶ
Array<int32> actions;
auto node = terminals[terminalIdx];
while (history[node].second != 0) // 探索を逆向きにたどっている
{
actions << history[node].second;
node = history[node].first;
}
// if (terminals[terminalIdx].type != state.curMino.type)
// {
// actions << 7;
// }
actions.reverse(); // 逆向きなので元に戻す
if (actions.size() > 0 and actions.back() == 6) actions.pop_back();
// while (actions.size() > 0 and actions.back() == 5) actions.pop_back();
actions << 6;
return actions;
}
細かいところ
ホールド
テトリスの操作には左右と回転、ドロップ以外でホールドがあります。テトリスを長くプレイさせるにはこのホールドを活用することが不可欠です。実際、ホールドなしでプレイさせると多くても200ライン程度しか消すことができませんでした。
ホールドをすると、ホールドのスロットにあるミノ(或いはネクストミノ)とミノを入れ替えます。つまり使えるミノの選択肢が二つあるわけです。これを活用するために、使うミノが現在のものか、ホールドしたときのものかの二通りで置き場所をそれぞれ列挙、評価します。そしてそれらすべてで評価がよかったミノと置き場所を使って操作を行います。一見すると置き場所に困ってしまいがちなミノ(Oミノなど)にホールドが偏ってしまいそうに思えます。しかし実際にやってみるとあら不思議、しっかりとホールドを使い倒してくれます。ホールドを使うと1500ラインくらいまで消せていたので、たぶん永遠にプレイできると思います。多分。(パフェもとっていました)
操作の短縮
これはいわゆるミノの最適化とは異なります。探索の操作復元で得られた操作順をそのまま使うと、ひたすらソフトドロップをしてハードドロップを使ってくれなかったりします。なので、最後のソフトドロップの連発を消し去ってしまって向きと場所さえ合えば即ハードドロップをさせます。(完全に好みの域)
できたもの
最終的にこんなものができました
かなり地形が低いですね。これなら安定して続きそうです。
でもテトリスをあまり打ってくれないのがさみしいです。あわよくばT-spinも打ってほしいけど...いまの評価じゃT-spinはまず無理ですね