テトリスの高難度版「HATETRIS」はどのように攻略されていったのか？

複数のブロックを並べて消していく「TETRIS(テトリス)」の派生形に、嫌な形のブロックだけが延々と落ちてくるという「HATETRIS」があります。このHATETRISで世界記録を達成する方法や歴史について、ふたりで共同ブログを運営している材料科学エンジニアのデイヴィッドとソフトウェア開発者のフェリペ氏が解説しています。

Getting the World Record in HATETRIS | Hall of Impossible Dreams
https://hallofdreams.org/posts/hatetris/

一般的なテトリスは次に落ちてくるブロックがランダムに決定されますが、HATETRISは常にアルゴリズムによって次のブロックが決定されます。アルゴリズムはまず盤面を精査し、最も高く積み上がったブロックを見つけ、次にどのブロックを落とすと最もプレイヤーにとって得となるかを計算します。そして、「最も損になる」と考えられたブロックをあえて選んで盤面に落とすのだそうです。

「HATETRIS」のレビュー記事は以下で確認できます。デイヴィッド氏らいわく、ゲーム開始時に登場するブロックと、2個目、3個目のブロックは必ず「S字」になり、他のほとんどのブロックもS字が続くそうです。レビューの際にもその通りS字ブロックが出続けています。

一番イヤなブロックが絶えず無慈悲に落ち続けるテトリス「HATETRIS」 - GIGAZINE

アルゴリズムにより嫌なブロックが投下され続けて難度が高くなったHATETRISですが、裏を返せば次のブロックはある程度予測できるということです。予測ができれば戦略が生まれ、戦略を磨いていけば高得点が狙えるはずです。

HATETRISはリリース直後にリプレイ機能やリーダーボードが追加され、世界中のプレイヤーがハイスコアを狙って競い合うようになりました。当初は11ポイントが最高でしたが、その後1カ月で17、20、22、28と伸び続け、最終的には日本人プレーヤーのDeasuke氏によって30点というスコアが出されました。Deasuke氏の戦略は人間が実行できる限界のものとされ、30点というスコアはその後7年間破られませんでした。

ところが、2017年頃には31点というスコアが出され、2021年6月にはknewjade氏が既存の戦略の最後の数手を最適化して32点を出し、その2日後には34点を出しました。なお、knewjade氏いわく、「32ines以降の手順はすべてプログラムによって得たスコアであることが明確にされている」とのことです。knewjade氏は機械探索プログラムを実行していて、2021年8月下旬には66ポイントという記録を達成しています。

デイヴィッド氏とフェリペ氏も以前から機械探索によるアプローチを行っていましたが、knewjade氏が66ポイントという記録を出し、さらにknewjade氏が自身の手法をGitHubで公開したことを受け、knewjade氏の手法に手を加えたアプローチを取ることにしたそうです。

knewjade氏からパラメータを送ってもらうなどしてアプローチを整えていったデイヴィッド氏らは、機械学習モデルをトレーニングし、HATETRISのエミュレータでテストを実施。最終的に86ポイントいうスコアをたたき出しました。

デイヴィッド氏らによると、HATETRISのアルゴリズムの特性上、ブロックをできるだけ高く積み上げる方が次のブロックを予測しやすいそうですが、デイヴィッド氏らのアプローチはブロックを極力高く積み上げるものではありませんでした。そのため、もう少し最適化の余地はあるとのことです。

なお、2022年11月にはknewjade氏が289ポイントを達成しています。この記録は、記事作成時点で既に破られています。

Reached 289 lines in HATETRIS using Neural Networks · GitHub
https://gist.github.com/knewjade/24fd3a655e5321c8ebac8b93fa497ed9