趣旨

技術チャレンジ部の企画『テトリスでPythonを学ぼうv4』にて、2023年1月～3月に実施されたテトリス大会で4冠を達成しました。
この記事では各レギュレーションでの攻略方針や優勝プログラムの解説をします。
これを超えるプログラムを作る土台になればと思います。
※ルールベースでの取り組みです

本企画の概要はこちら：https://github.com/seigot/tetris/blob/master/README.md

共通方針

◆新しい穴を作らない
新しい穴を作ることでその行を含むFullLinesで消せる行が1つ減ります。ハイスコアを目指すうえで致命的です。
なので新しい穴は作りません。

◆端以外に溝を作らない
3ブロック以上の溝を埋めるためにはIミノを使う必要があります。
Iミノは4行消しに使いたいので、溝が出来てしまうのを防ぎます。そのために3ブロック以上の段差を避けます。

◆深い溝を埋める勇気を持つ
新しい穴を作らないことを優先すると、Iミノが来ない場合に3ブロック以上の溝を埋めることができずGame Overになるリスクがあります。
適当なところで 穴を作るコスト < 深い溝があるコスト にします。

◆IミノをHoldする
基本的にIミノが得点源なのでHoldします。
ただし、新しい穴を作らない、溝を作らない等のためにIミノを使わざるを得ない場合は放出します。

◆デコボコさせない
凹凸は少ない方が良いです。ただ、前述の要素の方が優先度が高いです。

◆一番上のブロックだけ考える
計算量を減らすため各列の一番上のブロックのみに着目します。
穴を作らずに積んでいた場合、デメリットはありません。
既存の穴がある場合、次の一手のみを比較する評価には影響しません。FullLinesの行数に影響するとしてもFullLinesを発生させられる列は1つしかなく、かつ消せる行数を最大にすることが結局のところ最善です。なので穴の有無を考慮する必要はありません。
既存の穴がある場合、二手以上先を比較する評価には影響する可能性があります。穴だったマスが露出するとその後の検討が変わります。

盤面シミュレート方法

シミュレート範囲：
Hold = N（しない）：必ず全探索（x座標, 回転）
Hold = Y（する）：今のshapeindexとHoldしているshapeindexが異なる場合のみ全探索

算出方法：
実際のコード： https://github.com/mattshamrock/tetris/blob/level_4/game_manager/block_controller.py

現在の盤面 GameStatus["field_info"]["backboard"]から各列の一番上のブロックの高さcur_boardを算出します。要素数10のリストで表せます。
またcur_boardの高さの差cur_dyを算出します。"右の高さ-左の高さ"としています。要素数9のリストで表せます。
これ以降高さの差"dy"に着目してシミュレートします。

ある盤面に対してミノを1つ置く動作を「各列の一番高いブロックに決められた数上積みする動作」と捉えてみます。重力に負けるテトリスをイメージしてもらえば分かりやすいと思います。するとcur_dyはミノの縦方向のブロック数の差だけ増減します。
例えばShapeTのdirection = 3（凸の形）だと[1,2,1]個のブロックが追加されるため
cur_dyは[1,1,-1,-1]だけ増加します。
このとき増加するに要素のindexを考える際は、基準点のx座標だけでなく、基準点から左に何ブロック目が開始位置かを考慮する必要があります。これは基準点が取れるx座標の下限値と等しいです。
こうしてcur_dyから増加させた盤面をtest_dyとおきます。

test_dyは重力に負けた姿なので、重力に負けないテトリスでのdy dy_idealと比較し、test_dyを補正すると同時に新しい穴の数を算出します。
dy_idealはブロックの左端とその更に左側に掛かるdy、またブロックの右端とその更に右側に掛かるdyに対しては予め規定出来ないことに注意します。
test_dyとdy_idealの各要素の差をdy_difとします。
dy_difの各要素までの和を左から順に取ります。これはブロックの左端の補正を0マス分としたときに各列を何マス分上方向に補正する必要があるかを表します。和が取る値の最大値（最大値がマイナスの場合は0）が、ブロックの左端に掛かるdyを補正するべき値になります。また、それはブロックの左端の下に出来る穴の数でもあります。
ブロックの左端のdyが補正できると、あとはdy_difの通りにtest_dyを補正します。その時に各列に出来る穴の数は、各列で上方向に補正するマス数です。つまりdy_difのその列部分までの和と、和が取る値の最大値との差です。
ブロックの右端とその更に右側に掛かるdyを補正します。ブロックの右端の下に出来た穴の数だけ補正します。

これでミノを置いた後の盤面を"dy"で表すことができます。
同時に新しい穴の数も算出できます。

FullLinesの算出方法

行が消えるのは、ブロックを置く前と置いた直後を比較して「最も低い列の高さ」が増加したときです。
そのときに消える行数は、「最も低い列の高さ」が増加した値と同じです。ただし最も低かった列に新しい穴が出来たとき、その穴の数だけFullLinesになりません。

Level 4 攻略

提出コード： https://github.com/mattshamrock/tetris/blob/level_4/game_manager/block_controller.py

◆前提にしたこと：

最低 1ms/手で180sec実行するので限界値は180,000手です。
ただ、ランダムに次の手を決めても手元PCの処理速度では70,000手でした。
1ms未満での処理が現実的ではないため、評価精度を上げる場合は
計算量の増加割合 < 180手あたりのスコア増加割合　
にしないとトータルスコアが下がると考えました。

◆何手先まで読むか：

先読みしない方式で level 3換算で約13,000点の精度が確保できました。
最終候補2つのみで次の候補手を探索したとしても計算量が3倍になり、かつlevel 3換算のスコア最大値が約23,000点なので、先読みしない方式に決めました。

◆戦略：

低い位置で安定してDrop Down Scoreを稼ぎつつ、コスパの悪い1行消しを避ける

「共通」に記載した要素をベースに、
【基本】
・2行消し以上を狙う
・高さを低く抑える
・溝が5ブロック以上になると新しい穴を作って埋めてよい
・Iミノは、3行消し以上/溝を埋める/穴を避ける　に使う

【ピンチ(積んだ後の高さ10以上）】
・1行消し以上を狙う
・Iミノを使うのは、2行消し以上/溝を埋める/穴を避ける

◆補足：

低くしたい側と反対側の端が隣より3ブロック以上低くなることを避けた方が良いです。ただし計算量を優先して評価値に入れませんでした。
ピンチの判定には積んだ後の高さではなく積む前の高さを使った方が良いです。
低い状態の2行消しより高くした1行消しの方が評価値が高くなる、等の可能性があるためです。

Level 1 攻略

提出コード： https://github.com/mattshamrock/tetris/blob/level_1/game_manager/block_controller.py

◆何手先まで読むか：

最大まで先読みしたいので5手先（つまりN=6）まで検討しました。
評価の高い候補手180個に絞って次以降の手を深く検討しました。
最大で68通りに分岐するので [1*68, 68*68, 180*68, 180*68, 180*68, 180*68] を検討する形です。

5手先まで読んだ結果最も評価の高い手を採用します。
ただしblock_number >= 175になると、180手目までを読んだ結果最も評価の高い手を採用します。

各シミュレーションの評価時に、少なくとも以下の情報をメモしておきます。
・初手… [hold(Y/N), 回転, x座標, 評価値, 新しい穴の数, FullLinesの数, dy]
・次以降の手… [評価値, 新しい穴の数, FullLinesの数, dy]
検証用に他の情報もいろいろメモしておいた方が便利です。

◆戦略：

「共通」に記載した要素をベースに、ハイスコアを追求します

4行消し狙い
Iミノが定期的に来るので4行消しのみを狙う。ただし最終盤のみ3行消しを許容する
4行消しをするためにはどこか1列を溝にし、それ以外の列で4段以上積む必要があります
しかし両端以外を溝にするとツインタワーのような盤面になり、置き方の柔軟性が減ります。なので端を開けます
　　　　・一番低い列lowestに両端以外が該当する：減点
　　　　・デコボコに対する減点：低い側の端のみ減点を控除
　　　　・溝に対する減点：低い側の端のみ減点を控除
　　　　・1～3行消し：減点
これにより端1列だけ空けつつ他を平坦に積みあげていきます

◆先読みによる評価値計算で気を付けること:

FullLinesの評価値加算を累積させる
そうしないと5手先でのFullLinesのみを評価するため

FullLinesの評価値加算は、早い手ほど高める
Drop Down Scoreを稼ぐために早く消した方が有利なため

新しい穴の評価値減算を累積させる
そうしないと5手先にできる穴のみを評価するため

FullLinesから差し引く穴の数を累積させる
そうしないと大穴を作った後に横にミノを置いてFullLinesと判定してしまうため。
厳密には穴の数だけ差し引かなくても良い可能性があるものの、厳しめに罰している

◆補足：

コードとして反省点が多いです。
・1手先ごとにほぼ同じコードを繰り返し書いている
・if と elifのゴリ押しでフラグを立てている
・引数の使い方がたぶん適切でない
など。
もっとすっきりと書けるはずです。

5手先まで検討しているものの、3手先くらいで初手の候補がほぼ絞られている気がします。
初手候補に幅を持たせつつ評価値の高い手の先読みを進めたいです。

Level 2 攻略

提出コード： https://github.com/mattshamrock/tetris/blob/level_2/game_manager/block_controller.py

◆戦略：

Level 1 の考え方をベースに、ミノの偏りで高く積まれてしまうケースへの対応を追加しています。
ある程度高くなると3行消しを許容しています。
非常に高くなると1行消しを許容しています。
また最終盤は1行消しを許容しています。

一番高いブロックの高さmaxYを導入する
右と左どちらが高いかは重要なので左右を区別する。

3行消しを狙える手を評価する
低い側の端から2番目の列が、3番目の列より1マス低い場合に評価値加算する
Iミノが来ない場合にL or Jを使って3行消しを狙えるため。
なおLとJのどちらが使えるかは左右によって異なります

山なりの盤面を避ける
3列消しをするためには低い側の端から2番目が他の列より低い盤面を維持する必要があるため
また山なりの盤面は溝に発展しやすく不利なため。
低い側と反対側の端を、周囲より1-2マス高くすることで実現しています

一見成立しそうでもGame Overになる手を考慮する
先読みする中で条件を満たすとその時点でGame Overになるため避けます
　・最も低い側の端があるサイドのいずれかの列の高さが19を超える場合
　　　　↑ IミノでFullLinesを狙うときに引っ掛かってGame Over
　・左側の列の最大の高さが20を超えているときに、中央より左側にミノを置く場合
　　　　↑ 大抵Game Over
　・右側の列の最大の高さが20を超えているときに、中央より右側にミノを置く場合
　　　　↑ 大抵Game Over

その手に至るまでにGame Overになっているかを評価値計算に含む
Game Overになりそうな手を減点しますが、足切りを設定していない場合は次手の検討に回る可能性があります。
評価値は基本的にその盤面から都度計算するため、Game Overの条件を満たしたのち盤面を改善する手順が最善手になり得ます。

穴の上にブロックが置かれた場合を考慮する
端を空けていた列がブロックで塞がれる場合、早期に穴の上のブロックを消して再び端を空けたいです。
このときに反対側の端の方が低くなっている可能性があります。塞いでいるブロックが最も低いとすると、そのブロックは基本的に消えているためです。
この場合、反対側の端を低く維持し、塞がれている側を積んでしまいます。
これを防ぐために、両端とも高く積まれている場合は低い方の端に優先して積みます

◆補足：

Game Over寸前まで積みあがることは稀ですが起きた時はその対処法が勝敗を分けます。
付け焼刃でいろいろ評価値を調整しているものの
・Game Overになる条件を整理する、
・メモにGame Overの有無の枠を追加する
など改善の余地があります

Level 3 攻略

提出コード： https://github.com/mattshamrock/tetris/blob/level_3/game_manager/block_controller.py

◆戦略：

Level 2 の考え方をベースに、初期ブロックへの対応を追加しています。

初期ブロックを優先的に消す場合は2行消し以下が想定されます。
一方でDrop Down Scoreは最大で10点/手増加します。
2行消し2回（600点）と4行消し1回（1300点）には700点の差があります。
この点差を4行分のDrop Down Scoreで補うには175手が必要です。
4行消しするまでDrop Down Scoreが低くなることを考慮しても、細かく掘り下げることでスコアが不利になると考えました。
しかし初期ブロックの盤面から4行消しを安定的に狙うことは難しいと分かり、整地を導入しました

下から7-9行目に穴の少ない土台を確保し、その上でLevel 2と同様の4行消しを狙う
探す範囲の下限は7行目です。上限は9行目とその列で最も高いブロックのうち低い方です。
この範囲に穴が少なければ土台ができている、または十分低くなっていると判定します。
Game Overになると初期ブロックが復活します。そのためこの判定は毎回行います。
この範囲に穴が5個以上あれば1行消しを許容します。ただし2行以上まとめて消すことを優先します。また、最大の高さが増える時に減点します。

ピンチの判定を緩くする
Level 2 より土台が高い位置にあります。なので"高くなりすぎている"の判定を比較的緩くしています。

◆補足：

早期に初期ブロックの穴を減らして4行消しに移行する方が有利です。
しかし一番上のブロックだけ考えている都合、初期ブロックを整えることが最大効率で出来ていないと思います。
効果的な対策を思いついていません。

新しいパラメーターを見つける＆調整する

思考のみで必要なパラメーターを見つけるのは難しいです。
基本的なプログラムを作った後に何度も180秒分を回し、特にスコアが低い回に着目して対策を考えることにしました。

ログとして GameStatus["debug_info"]["random_seed"]やstatus_strをテキスト等に出力するよう設定したうえで適当な回数連続実行します。

command = ["python", "start.py","-l","2"]
for i in range(300):
    subprocess.run(command)

ログからスコアが低い回が見つかります。そのrandom seedとスコアのメモを取ります。
-rにGameStatus["debug_info"]["random_seed"]を設定するとその回が再現できます。
検討ログ等を適宜出力しながら課題と対策を考え、その結果新しいパラメーターが必要なら追加していきます。
これを繰り返すことで強くなっていきます。

なおパラメーターを変更した結果もともと対応できていた盤面に対応できなくなる場合がありました。
対策として、スコアが低くなるseed（難しいseed）のメモを残し、定期的に実行してスコア維持を確認しました。

seed_2 =[ 16780796800965872,16780797995533510,16780799394337290]
for eachseed in seed_2:
    command = ["python", "start.py","-l","2","-r", str(eachseed)]
    subprocess.run(command)

まとめ

とても強いプログラムですが戦略、コード共に改善の余地があります。