こんにちは、knewjadeです。 今回、HATETIRSで289 linesまで到達することができました。動画はこちら（2022-11-26時点のWorld Recordでした。現在では更新されています。 → David&Felipeの記事）
ここでは、その結果を得るためのアプローチを説明していきたいと思います。
「そもそもHATETRISとは？」という方は、こちらをご参照ください。
このページでは、コンピュータを使った探索方法が書かれています。 人間がプレイする上でのゲームの攻略方法ではないのでご注意ください。
まずHATETRISにおけるこれまでのアプローチやその課題などの背景を説明して、今回目指した目標について説明します。
| 最終更新日時 | アプローチ | スコア | 更新者 |
|---|---|---|---|
| 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) |
HATETRISが公開された2010-04から、筆者が調べはじめる2021-06まで11年間ほどで、約30ポイントが最高スコアでした。 この期間の手順は規則的な置き方をしているものがほとんどです。 その点で31linesだけは、規則性が比較的少ないので、著者は機械による探索を使っているのではないかと推測しています（真偽は不明です）。
これはただの感想ですが、特に30linesはかなりキレイな積み方で、ある種人間らしい積みのゴールのひとつだと思っています。
『HATETRIS ・ヘイテトリス』30段消し解説動画 → https://www.youtube.com/watch?v=Hd5dNdrrEvQ
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はテトリスの中でもかなり難しいテトリスとされています）
ここでは今回のアプローチに関係のあるルールについて少し説明します。
より厳密なルールは公式サイトや、公式のGitリポジトリを参照してください。
通常のテトリスでは何が落ちてくるかはランダムな要素が含まれていることが多いですが、HATETRISでは決まった状況では、必ず同じミノが落ちてきます。 そしてそれは、原則、現在の地形から決まります。（例外はLoopの項目を参照のこと）
選択されるミノは「もし落ちてきたら地形が悪くなるもの」が選ばれます。
HATETRISでは 悪い地形＝フィールドが高い地形 と定義しているので、
つまり、どのように置いてもフィールドが高くなってしまうミノが優先的に落ちてきます。
反対にいうとラインを消去できるミノは、地形を低くする択があると判断され、選択されなくなります。
もし地形の高さが同じになる候補が複数ある場合は SZOILJT の優先順で選ばれます。
ここからわかる重要な戦略が2つあります。
システムは「谷底に置くと地形全体の高さは変わらない」と判断するため、ラインを消去できないミノを安定して選んでくれます。 そうすることで、落ちてくるミノの種類を変えずに、ブロックを安定して積み上げやすくなります。
ラインを消去できないミノが存在する場合は、基本そのミノが選ばれます。 したがって、実際にラインを消そうとするには、すべてのミノでラインを消去できる状態にしなければなりません。 そしてそのときに選ばれるミノは、基本、優先順位が最も高いSミノにルール上なります。 （例外は少し存在します。たとえば、Sミノで2ライン消しできる場合はZミノになります。）
このページでは、それぞれ次のような状況をこのように呼ぶこととします。
- 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
- サイクルの初期状態
まずはじめに、探索で利用する評価関数の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の形を目指すのが良いのかなと、今の自分は考えています。
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を発見したことで探索が完全に停止したため、急遽実装することにしました。 ただ、はじめから盤面情報を残しながら学習していたら、実行時間がかなり伸びてしまっていたかもしれません。
実際に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の盤面に近いため、急速に低下しやすい」と仮定しており、 そのギャップによって次の探索の精度が上がると考えています。
ステップ2で生成した学習データ（地形と精緻化した評価値のペア）を基にネットワークの重みを更新します。 なお学習データとして、直近3サイクルで生成したデータを利用します。
例）現在5サイクル目の場合、学習対象となるデータは、3,4,5サイクル目で生成したデータになります
このステップでの学習は、一般的なNeural Networkのミニバッチ学習と同等です。
- 損失関数：二乗誤差 (Mean Squared Error)
- 最適化アルゴリズム：Adam
- バッチサイズ：8192
- Early stopping: 3epoch連続でlossが悪化した場合（もしくは100epochに到達した場合）に終了して、学習中に最もlossが小さいWeightを採用する
ここまでの説明で、1サイクルの説明は終わりとなります。 "Learn"で生成されたネットワークをもとに、新たに"Search"を開始できます。
最後に、このサイクルをどのような状態から開始するかを説明します。
今回のアプローチでは"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にサマライズして、そのヒントをもとに次のサイクルの探索を行っているのでは？」と解釈しています。 つまり、あくまでヒントでしかないため、うまくいかないサイクルもそこそこ発生していました。
以上、この記事はここで終わりとなります。 最後に一言だけ。
もしこの方法を基礎に改善していく方が現れることは全く問題なく、それはうれしいなと思っています。 ただ、個人的にはできれば、そこには何らかの自分なりの工夫をプラスしてほしいなとも思っています。
この記事が誰かの参考になれば幸いです。