(この記事は具体的なコードの説明はせず、アルゴリズムの考え方に書いて語っただけの記事です。)
概要
テトリスで強いCPUを作る
テトリスは20x10のフィールドに7種のミノを設置し、横一列を揃えることでブロックが消去され、揃え方によって相手へ攻撃ができる。
NEXTやHoldを活用することが重要であり、先を見越してミノを置くことが必要である。
世の中にはつよいCPUが開発されており、スピードだけではない強さをみせている。かっこいい。
運任せでなく、人間と同じ入力速度にしても安定して勝てるような強いCPUを作りたい。
上位勢になればなるほど 火力効率が高いのは当然で、自分の攻撃リソース,相手のリソース,相手の盤面展開,相殺当て外し...などを考慮した戦略構築が重要となる。最終的には相手の攻撃まで読めるようなCPUを開発したい。これはその足掛かりである。
実際のコードは読むのにテトリス本体のコードも必要でとても長いので、ここではアルゴリズムの考え方のみを書き、コードそのものはgithubに公開しておく。(めっちゃ汚いけど まあ雰囲気はわかると思う...。)
環境
実装:Python
テトリス:ワールドルール準拠自作テトリス(火力はぷよテト)
テトリス用語省略表記
ネク:NEXT
テンプレ:テンプレート
TSS TSD TST:Tspin single,double,triple
SRS:SuperRotationSystem ミノの特殊回転のこと。回転する時の状況によってミノの座標が少し移動する。
1手:ミノ1つ置く分
地形:盤面の様子
積み込み:後の攻撃のために攻撃をせず、ミノを積み上げていくこと
制作
いくつかの考え方から複数種類のアルゴリズムを作成した。
・全探索型
全てのミノの置き方を試し、出来上がった盤面を評価してスコアが最も高い置き方を選択する。
・テンプレ型
テンプレの通りに置く。NEXTを読んで使うテンプレを選択し、置いたミノをカウントし、カウントを考慮して指定された場所に置く。
・REN型
全探索型の手法で積み込み(予定)、テンプレ型の要領でRENを撃つ。
制作 CPU入出力動作
CPUのアルゴリズムを制作する前に、CPUが盤面を読み、ミノを操作できるような機能を作る必要がある。
ここでは、使うテトリスは自作なので、その部分については省略する。
制作 全探索型[未完]
全探索型はまだ完成していない。パターンがあまりに多く、処理が重すぎて開発が難航したためである。コードの軽量化やcythonでの実装も挑戦したが、あまり改善されなかった。
評価
盤面の“良さ”を評価する。
何を“良い地形”とするかはテトリスのプレイスタイルによる。
ここではとりあえず、「穴バラが無く、高低差の少ない地形」を良い地形とする。つまり平積みである。
また、Tspinが撃てる地形も高く評価する。Tspinが撃てる地形と穴バラが無いことは両立しないため、しきい値調整でバランスをとる。
関数evaluation
探索
可能なミノの置き方全てを考える。
ざっくり、x座標10 * 方向4 通りとした。(壁に埋まるあり得ないパターンは除外する。)
(これでは回転入れが考えられない。どうやって回転入れ考えたらいいんだろう...)
そして、各盤面を評価し、そのうち最も評価の高い置き方を選択する。
探索は、ネクストも含めて行う。そのため、"考えられる全ての置き方"というのは、指数関数的な量である。考えられる全てについて探索をすると処理が膨大になってしまうため、"明らかに悪そう"な手については探索をやめる必要があるが...。
(そもそも40手読みでも結構重たい なんでやねん)
関数serch
動作
これはHOLDとNEXT1つ pic.twitter.com/sTtx6bOLeX
— 6186milktea (@6186milktea) May 25, 2023
結局、処理が重たいせいで制作が止まり、半端な状態で終わっている。Tスピンやらせた
— 6186milktea (@6186milktea) May 27, 2023
まあまあ pic.twitter.com/1wacIUXqNJ
制作 テンプレ型
動きとしては、ネクを読み、今のミノをどの位置に置くかを決めるだけである。
そのため、盤面の評価が不要で、処理はとても軽い。
巡ごとに置いたミノを記録し、その記録から判断して今のミノの置き方を決定する。
巡ごとにネクストを読んで組み分け選択をする。明確な条件が考えづらいテンプレもあるので、そのようなものについては一度今のネクストでシュミレーションし、詰みが発生しなかった場合は採用するようにした。
盤面評価はおじゃまミノの段数を数えるだけなので、回す処理はちょっとだけ配列参照するだけ。
(本来テンプレは人間が簡単に火力構築をするためのものであるので、優秀なテンプレがあるとはいえ、それがネクごとの最適解であるとは言い難い。CPU作成としては成長がないので別に面白くない...。)
動作
このときはテンプレファイルを完成させてなかったのでこのテンプレの本領発揮ができていない。 動画では完走したのは3Pだけだが、実際は全員できる。とりあえずホットケーキ積み
— 6186milktea (@6186milktea) July 1, 2023
分岐少なかったり、先読みパターン決めできてないけど 仕上がりの雰囲気くらいはあるかな
(ほっとけーき組めないことまあまああるしほかのテンプレのがよかったな) pic.twitter.com/c928ysV9Gw
制作 REN型
テンプレ型の要領でパターンを考え、全探索型と同様に探索し、最も長くRENがつながる置き方を選択する。
処理軽減のため、テンプレ型と同様にタネの形、対応するミノの置き方、次のタネの形をjsonファイルに記述した。
(積み込みについては何も考えていない。全探索型の評価を弄ればなんかできそう。)
探索
あらかじめ書いたタネ-ミノ対応ファイルを参照し、ありうるすべての置き方について考えていく。
全選択型とは異なり、置き方を考えるための処理は無い。
探索数についてもせいぜい30~40回程度。全て配列を読むだけなので全然重くない。
選択
ある時のネク全てでRENがつながったとしても、その次がつながらない可能性がある。
残すタネ、ホールドのミノ、その次のミノ(予測)を見ることで、さらにつながりやすい手を選択することができる。
・ネク6予測
ミノの7巡法則を使えば、まだ表示されないネク6番目以降何が来るかをある程度予測することができる。 最初に全てのネクを記録し、ネク送り毎にネク5番目を記録、7種揃ったらリセットでカウントできる。
RENが延びる条件を考え、評価する。
最後に残る地形とホールドがかみ合えば、6手先までRENが確定するため、評価を高くする。
最後に残る地形と確定予想ネクが噛み合えば、ネク6でRENが確定しホールドを維持できるため、評価をとても高くする。
地形と予想ネクが噛み合う可能性があれば、評価をちょっと高くする...。
このようなずいぶん先の選択をすることでも、RENの継続率は大きく上昇する。
(参考19REN率:無評価->上記評価、3割弱->5割強)
動作
(CPU用にソフドロ時間とライン消去アニメーションをめちゃめちゃ短くしてる)予想ネク選択:5割強の動画(上げ忘れ 資料用) pic.twitter.com/TJxkxesV61
— 6186milktea (@6186milktea) September 21, 2023
おわり
以上で現状のCPU開発の進捗記述はおわり。
以下に参考とした資料や自分のメモツイをぶら下げておく。
全然未完のこんな記事を読んでくれてありがとう！
参考サイト
テンプレ紹介サイト
4列REN全タネ、置き方パターン表
SRS詳細
作業ログ
平積み型制作ログ
https://x.com/6186milktea/status/1660274956591300608?s=46&t=7b1TSHzK6tg1PuszyrB92Q
テンプレ型制作ログ
https://x.com/6186milktea/status/1675177495069626369?s=46&t=7b1TSHzK6tg1PuszyrB92Q
REN型制作ログ
https://x.com/6186milktea/status/1691756651681046887?s=46&t=7b1TSHzK6tg1PuszyrB92Q
修正
2023/09/22 とりあえず記事完成