HATETRISで289 linesに到達するまでの記録

こんにちは、knewjadeです。今回、HATETIRSで289 linesまで到達することができました。動画はこちら（2022-11-26時点のWorld Recordでした。現在では更新されています。 → David&Felipeの記事）

ここでは、その結果を得るためのアプローチを説明していきたいと思います。

「そもそもHATETRISとは？」という方は、こちらをご参照ください。

はじめに: この文章について

このページでは、コンピュータを使った探索方法が書かれています。人間がプレイする上でのゲームの攻略方法ではないのでご注意ください。

背景

まずHATETRISにおけるこれまでのアプローチやその課題などの背景を説明して、今回目指した目標について説明します。

High Scores

最終更新日時	アプローチ	スコア	更新者
2010-05-04	人間が考えて見つける	〜30	Deasuke 他
2017-06-06	???（たぶん機械探索）	31	chromeyhex
2022-11-25	Heuristic Beam Search +α	32〜232	knewjade(66)~David&Felipe(152)~Tim(232)

〜31lines：人間が考える期

HATETRISが公開された2010-04から、筆者が調べはじめる2021-06まで11年間ほどで、約30ポイントが最高スコアでした。この期間の手順は規則的な置き方をしているものがほとんどです。その点で31linesだけは、規則性が比較的少ないので、著者は機械による探索を使っているのではないかと推測しています（真偽は不明です）。

これはただの感想ですが、特に30linesはかなりキレイな積み方で、ある種人間らしい積みのゴールのひとつだと思っています。

『HATETRIS ・ヘイテトリス』30段消し解説動画 → https://www.youtube.com/watch?v=Hd5dNdrrEvQ

32lines〜: 機械探索期

32ines以降の手順はすべてプログラムによって得たスコアであることが明確にされています。それぞれの解説記事を載せておきます。興味がある方はぜひご覧ください。

66lines by knewjade: https://gist.github.com/knewjade/586c9d82bd53f13afa8bcb7a65f8bd5a
86lines by David&Felipe: https://hallofdreams.org/posts/hatetris/ (英語)

これまでの探索方法をひとことでまとめると「heuristicな特徴量ベースの評価関数によるビームサーチ」が基本で、人間が経験的に良さそうな特徴を考えて、それを特徴量として設定しています。

このheuristicを頼るメリットとして、特徴量をうまく定義してあげると、簡単にそこそこ良い結果を得られやすい点です。事前にデータを用意しなくても良いことが多く、知見も学習データもないような領域でのファーストステップとして選択しやすいです。

まさに著者が探索を始めたタイミングでは、機械探索を試みた人は少し居たものの、誰も成功できていない状況でした。今振り返っても、この状況で、少ない作業で結果を得られやすくてリスクの低い特徴量ベースのアプローチを選んだのは、結果として正解だったかなと思っています。

これまでの探索の課題

探索が成功してスコアが伸びてきたことで、以前では考えられなかった手順が存在していることが明らかになってきました。それと同時に、良い手順（地形）をheuristicに表現するのが難しい状況となってきました。

たとえば、heuristicな特徴量のひとつに "holes" があります。これは「穴がたくさんある地形はラインを揃えるのが難しく良くない」という経験がもとになっています。

以下の画像は289linesの途中の地形です。人間にとっては整っているとあまり感じられませんが、たしかにこの後はキレイに消すことができます。つまり、良い穴/悪い穴があるはずなのですが、それを区別して評価するのは現状ではかなり難しいです。

目標

「heuristicに依存しない探索の実現」を第一目標としました。そのため、これまでとは全く異なるアプローチで取り組み始めました。その動機は以下のとおりです。

スコアを更新するのであれば、現在のアプローチをベースに改善しても良かったが、大きな改善は見込めないと考えていたため
できる限りHATETRISに限らない、他のテトリスでの探索にも応用できるアプローチを探ってみたかったため

1.については、前述の課題の通りです。

2.について少し詳しく書くと、テトリスの中でも比較的活発に開発されている対戦AIにおいても、heuristicがかなり大きい割合を占めています。いわゆるNNなどの機械学習を中心としたものは、筆者の知っているかぎり、アカデミックな範囲で少し存在している程度で、実用的なものはほとんどない印象です。

今回の対象はHATETRISですが、そこでうまくいけば、いろんなところに展開できるかもと考えました。（HATETRISはテトリスの中でもかなり難しいテトリスとされています）

HATETRISのルール

ここでは今回のアプローチに関係のあるルールについて少し説明します。

より厳密なルールは公式サイトや、公式のGitリポジトリを参照してください。

落ちていくるミノの種類

通常のテトリスでは何が落ちてくるかはランダムな要素が含まれていることが多いですが、HATETRISでは決まった状況では、必ず同じミノが落ちてきます。そしてそれは、原則、現在の地形から決まります。（例外はLoopの項目を参照のこと）

選択されるミノは「もし落ちてきたら地形が悪くなるもの」が選ばれます。 HATETRISでは 悪い地形＝フィールドが高い地形 と定義しているので、つまり、どのように置いてもフィールドが高くなってしまうミノが優先的に落ちてきます。反対にいうとラインを消去できるミノは、地形を低くする択があると判断され、選択されなくなります。

もし地形の高さが同じになる候補が複数ある場合は SZOILJT の優先順で選ばれます。

ここからわかる重要な戦略が2つあります。

1. フィールドに大きな谷があると、地形全体の高さを変えずにミノを置けるため、出てくるミノをコントロールしやすい。（4列RENのようなイメージ）

システムは「谷底に置くと地形全体の高さは変わらない」と判断するため、ラインを消去できないミノを安定して選んでくれます。そうすることで、落ちてくるミノの種類を変えずに、ブロックを安定して積み上げやすくなります。

2. ラインを消去できるミノは、原則Sミノのときのみ。

ラインを消去できないミノが存在する場合は、基本そのミノが選ばれます。したがって、実際にラインを消そうとするには、すべてのミノでラインを消去できる状態にしなければなりません。そしてそのときに選ばれるミノは、基本、優先順位が最も高いSミノにルール上なります。（例外は少し存在します。たとえば、Sミノで2ライン消しできる場合はZミノになります。）

Loop, Infinite Loop

このページでは、それぞれ次のような状況をこのように呼ぶこととします。

Loop: ある特定のフィールドから、何らかの操作を経て、再び同じフィールドの状態に戻ること
Infinite Loop: Loopを繰り返すことで、ゲームを永遠に終わらない状態にすること

HATETRISでは、この2つの意味は少し異なります。その理由は、ルールとして「ゲーム中に同じ地形が現れる可能性を検知すると、次の優先順位のミノを選択する」というルールがあるためです。

もしInfinite Loopを実現しようとすると、まずは単純なLoopを実現した上で、さらに変化するミノに対してもLoopしなければなりません（これを出現するあらゆる地形で行う必要があります）。そのため、Infinite Loopはおそらく存在しないだろうと思われます。

では、Loop自体はどうであるかというと存在します（今回の探索の過程で発見しました）。以下の画像で、スコア105の地形ではSミノが落ちてくるはずですが、その場合スコア95の地形に遷移できてしまうため、Zミノに修正されています。（地形が完全に一致する前に変化していることに注意してください） → replay

以前の探索では、このLoopも存在しないと仮定してシミュレーションすることで、データの削減（高速化）を行っていました。しかし、今回Loopを発見してしまったため、シミュレーター上では実際では起きない動きをしてしまう出来事がありました。

もし、これから探索を始める方は、このことに注意していただくことをおすすめします。

アプローチ

ここからは、今回のアプローチの詳細を説明していきます。このドキュメントでは、基本的に最終構成にフォーカスして説明します。この過程で失敗した知見もたくさんありますが、それはまた別の機会にでも...。

全体像

今回のアプローチでは、大きく3つのステップを1サイクルとして、このサイクルを何回も回すことで少しずつ改善していきました。以下の画像はその流れを図示したものです。

ここでは、各ステップを次の順番で説明します。なお、すべてのステップは、前のステップの成果物をもとに何かを実施する流れになっています。

Neural Networkの構成
Search
Refine
Learn
サイクルの初期状態

1. Neural Networkの構成

まずはじめに、探索で利用する評価関数のNeural Networkについて説明します。このネットワークは、「地形のブロックの配置」を受け取り、「その地形がどのくらい良いか」を計算します。

全体像

今回のアプローチでは3-Layer Neural Networkを利用しています。総パラメータ数は 122905(hidden24) -> 245809(hidden48) です。

入力層

評価したい地形は、そのままの形でネットワークに渡すのではなく、その地形で出現しているブロックの組み合わせの頻度を渡します。（この「ブロックの組み合わせ」のことをパターンと呼んでいます）

カウントするパターンは大きく2種類あります。

row patterns:
- 1行ごとのブロック配置を0-1022の数字に対応させて、その数字ごとの頻度を数えて入力します
- したがって、1フィールドにつき 16パターン を含む（同じ数字でも重複分をカウントする）
- すべてブロックで埋まっている状態(1023)は起きない想定をしています。
3x4 conv.2D patterns:
- 幅3高さ4ごとのブロック配置を0-4095の数字に対応させて、その数字ごとの頻度を数えて入力します（kernel size=(3x4), stride=1）
- なお、壁・床それぞれ1つ分のブロックも含めてパターン化します。ただし、天井（赤線より上の空間）は含めません
- したがって、1フィールドにつき 10x14パターン を含む（同じ数字でも重複分をカウントする）

【補足】 実装上のバグにより、筆者が実際に使用したものは次の点で異なります。

* row patternsを0-1023に対応させており、パラメータが余分に含まれていた
* conv.2D patternsで、一番上の行を含めておらず、`10x13パターン`で入力していた

ここではあくまで、本来想定していた構成を説明しています。もしかすると、性能に影響があるかもしれませんが、ご了承ください。

隠れ層

隠れ層の数は24から始めました。途中、探索が停滞したタイミングで48に変更しました。

隠れ層の活性化関数には、tanhExp関数を用いました。

そのほかは一般的なNNと同じです。

出力層

入力された地形の良さを数値として返却します。出力層の活性化関数には、tanh関数を用いました。そのため、 -1(悪) <= y <= 1(良) で数値化されます。

この構成に至った経緯

このネットワークの構成はNNUEから着想を得ていますが、最終的なネットワークだけをみると「一般的なNNとNNUEのハイブリットな構成」と言えると思っています。

この構成に至った流れは以下のとおりです。

学習に使うデータを0から作り出す必要があるため、いずれにしろパラメータ数の多い大きなネットワークは難しかった
通常NNで今後ネットワークを大きくするとGPUの計算資源の問題にあたるため、個人的には高速に計算可能なNNUEを採用したかった
一方で、パラメータの少ないNNUEを使用した場合、「整数による誤差がどの程度影響あるのか」といったリスクがありそうと感じた。しかし、NNUEを全く使用したことがない＆機械学習が専門でない自分には判断できなかった

そのため、一般的なfloatなNNの方がモデルの表現的なリスクは少なさそうで、また、中間層を後から変更することは比較的容易にできそうに思ったため、入力層だけNNUEのような構成になりました。

実際、入力層だけでも、計算の大部分をうまくスキップできている印象があります。

もし今後ネットワークを大きくしていく際は、本来のNNUEの形を目指すのが良いのかなと、今の自分は考えています。

2. Search: 探索＆学習フィールドの生成

Beam Searchで、1ゲームを通して探索します。このステップでの主目的は、以降のステップの学習で使う盤面を生成することです。

そのほか、大きな特徴をピックアップして説明します。

評価値

この探索で最大化するのは、ステップ1のネットワークの評価値です。この評価値にはheuristicな特徴量、スコアさえも含みません。ただし、（ほぼ唯一）heuristicな仕組みとして、S,Zミノで再起的にラインを消去した後の盤面も評価して、その中で最大値を採用しています。（David&Felipeのアイデアから着想を得ました。）

ビーム幅

ビーム幅は100k or 200kです。David & Felipeによると、heuristicな手法では100k=68とのことで、4倍ほどの改善となっています。

設定値

今回は試行錯誤しながら学習した都合上、サイクルを進めながら、スコアの停滞・低下が起きたときにいくつかの設定を変更しています。変更した設定はざっくり以下のとおりです。

変化した設定	v1	v2	v3	v4
ビーム幅	100k	200k	200k	200k
各候補が経由した盤面情報	なし	なし	あり	あり
隠れ層の数	24	24	24	48

特に「各候補が経由した盤面情報」は、Loopを発見したことで探索が完全に停止したため、急遽実装することにしました。ただ、はじめから盤面情報を残しながら学習していたら、実行時間がかなり伸びてしまっていたかもしれません。

3. Refine：教師データの作成

実際にNNで学習させる教師データを作成していきます。教師データの作り方は次の流れで行います。

1: Beam Searchの途中の候補から、各depthで4k個の地形をランダムにサンプリングします。
2: 1.の各盤面から幅200のBeam Searchを行い、ミノをさらに10個置いた先の地形で最も良い評価値を求めます。
- 評価値はNNの出力値を直接利用します（SZによる再起は適用しません）
- 途中までの評価値は教師データには反映しません。あくまで10手先の評価値をそのまま返します
- もし、10手先で候補が残らない（ゲームを続行できない）場合は、評価値を -1 として扱います
3: 「1.の盤面の評価値x」、「2.のより深い評価値y」として、 t = x + 0.5 * (y - x) を教師データの評価値としてファイルに保存します。

なお3.で、評価値を0.5倍しているのは、一度で急激に変化するのを防ぐために導入しています。この値の効果は、強化学習の 学習率a=0.933 と同じような働きをすることを期待しています。

ノーマライズ

この評価値の精緻化を行うと、基本的に全体がマイナス方向に動きます。そこで、最後にそのサイクルごとに、評価値を教師データ全体の最小値・最大値が[-1,1]になるようにノーマライズします。

このステップの意図

まずはじめに「ステップ1の候補となった地形は、比較的良い地形であるはず」と考えています。このステップでは、その地形が本当に良いのかを検証するフェーズとして、自分は捉えています。

もし良い地形であるほど「評価値が下がりにくい選択肢が存在しているため、緩やかに低下する」、反対に悪い地形であるほど「評価値-1の盤面に近いため、急速に低下しやすい」と仮定しており、そのギャップによって次の探索の精度が上がると考えています。

4. Learn：ネットワークの更新

ステップ2で生成した学習データ（地形と精緻化した評価値のペア）を基にネットワークの重みを更新します。なお学習データとして、直近3サイクルで生成したデータを利用します。

例）現在5サイクル目の場合、学習対象となるデータは、3,4,5サイクル目で生成したデータになります

このステップでの学習は、一般的なNeural Networkのミニバッチ学習と同等です。

損失関数：二乗誤差 (Mean Squared Error)
最適化アルゴリズム：Adam
バッチサイズ：8192
Early stopping: 3epoch連続でlossが悪化した場合（もしくは100epochに到達した場合）に終了して、学習中に最もlossが小さいWeightを採用する

ここまでの説明で、1サイクルの説明は終わりとなります。 "Learn"で生成されたネットワークをもとに、新たに"Search"を開始できます。

5. サイクルの初期状態

最後に、このサイクルをどのような状態から開始するかを説明します。

今回のアプローチでは"Search"からサイクルを開始しますが、このとき何らかの評価値ネットワークが必要となります。もしかするとランダムな重みのネットワークから始めることもできるかもしれませんが、今回は学習を早く行うためにあらかじめ別な方法で学習しました。

ここではその初期学習について説明します。

初期学習

今回のNeural Networkで入力するパターンには、フィールドの高さに依存するものがありません。したがって、たとえばもしゲームの高さが半分(8)であっても、同じように入力することができます。

また、ゲームの高さが低い場合、全探索で理論値を求めることができます。（参考: David & Felipe's comment）

そこで、高さ4〜7を全探索して得られた地形をもとに、その地形から得られるスコアを高さ7の理論スコア12でマッピングした値を評価値として計算します（eval = (score/12 - 0.5) * 2）。このとき、それぞれの地形の高さを16として扱わずに、入力するパターンの合計頻度が少ない状態のまま入力しています。

このようにして生成した教師データをもとにネットワークを学習させます。今回は、データ数が多いので全体の50%だけを学習に使用しました。

ゲームの高さが変わると、入力される頻度のスケールが変わります。そのため、この方法で得られたネットワークは、基本的に値が大きくなりやすい（=1を出力しやすい）です。しかし今回のアプローチでは、本当に悪い地形の評価を徐々に下げていく動きをするので、この特徴は非常によかったと思っています。

さいごに: 考察・感想

最後に、筆者が今回の手法で思っていることをつらつらと書いておきます。

よかったこと

今回良かったことはheuristicを極力なくした上でスコアを向上できることを示せた点です。テトリスでNN(NNUE)が中心で、かつ最高スコアを目指すみたいな事例はおそらくまだないと思うので、ポテンシャルを示すことができたのは価値があるかなと思っています。

課題

個人的に考えている課題を記述しておきます。

今回のアプローチではNNを利用しているため、いわゆる機械学習みたいな構図になっています。一方で、自分は「機械学習か？」との問いには、厳密にいうとNoだと考えています。

大きなポイントは「教師データの正解となる評価値が、どこかの値に向かって収束しない」点です。たとえば、チェス・将棋・囲碁などの対戦であれば「勝率」であることが多く、一人用のゲームであれば「スコア」であることが多い印象です。ですが、今回はどれでもありません。そのためか、実際に安定性に不安があります。

自分の考察としては、今回の手法は「直近の探索の結果をNNにサマライズして、そのヒントをもとに次のサイクルの探索を行っているのでは？」と解釈しています。つまり、あくまでヒントでしかないため、うまくいかないサイクルもそこそこ発生していました。

以上、この記事はここで終わりとなります。最後に一言だけ。

もしこの方法を基礎に改善していく方が現れることは全く問題なく、それはうれしいなと思っています。ただ、個人的にはできれば、そこには何らかの自分なりの工夫をプラスしてほしいなとも思っています。

この記事が誰かの参考になれば幸いです。

knewjade/HATETRIS_289lines.md