こんにちは。knewjade です。
先日、HATETRISで31ラインだった世界記録を66ラインまで伸ばすことができました。 （2022/05/29に86ラインまで更新されました。） そのときの作業や思考の記録を残そうと思います。
2022-11-26: 289ラインに更新したため、新しい解説記事を公開しました。
https://gist.github.com/knewjade/24fd3a655e5321c8ebac8b93fa497ed9
HATETRIS は、そのとき一番必要のないミノが落ちてくる特徴を持つ、非公式のテトリスのひとつです。 ラインをなかなか揃えられないように、落ちてくるミノが調整されるため、スコア（消したライン数）を伸ばすのが難しいテトリスとなっています。
その一方で、そのときの地形によって落ちてくるミノが決まるため、 ランダムに落ちてくる通常のテトリスよりも再現性が高いのが特徴です。 リプレイと同じ位置に置き続けると、必ず同じ結果が得られるようになっています。 そのため、コンピュータでの探索が比較的しやすくなっています。
ちなみに、自分が41Lの記録を出した後に「過去と同じ地形が出現したら、落ちてくるミノがその前と変える」というルールが増えました。 一応自分は、このルールが発動することはないと考えています（正しいかはわからないです）。
現時点で世界記録である66Lのリプレイは、自分のツイートやトップページに載っているので、ぜひ見てみてください。
このページには、基本的にコンピュータを使った探索方法が書かれています。
ただし「探索アルゴリズムの説明」よりも、66Lの記録を出すまでに「どんなことを考えて、どういうことを調べたのか」、その過程を中心に書きました。
そのため、技術的にもっと良い方法・改善できるポイントはたくさんあると思いながら書いています。
そして今後、記録を更新する人が現れるといいなと思いながら、いろいろなことを書き残しました。
第1目標は探索できる局面数を増やすこと
計算をなるべく早くするなど、まずは基本的な探索性能を上げるのを目指しました。 計算速度やメモリ使用量の感覚はやってみないとわからない側面があると考えているので、 それを実装しながら決めるアプローチで取り組み始めました。
機械学習のようなアプローチは、まず一通り探索性能をあげてから考えても遅くないと思いました。 （今回は最終的に使いませんでした。）
探索プログラムはC++で書いています。
自分はこれまでにも、テトリス界隈でいろいろとつくっていたため、 自作のテトリス探索用のライブラリを持っていました（テトリスAI:ZetrisのPC Finderなど）。 以前、それを高速化しようと手を入れて放置していたので、ひとまず完成させました。
このライブラリに特徴があるとすれば、Bitboardをベースにしていることです。 64bitでフィールド6段を表現していて、HATETRISの高さは16なので、変数3つ分で1つのフィールドを表現できます。
そのうえで、とりあえず様子見でビームサーチをしました。 意図としては、まず問題の難しさを把握したかったので、書きやすくてそこそこ良さそうなビームサーチにしました。
概要はこちらのスライドとほぼ同じになります。 https://www.slideshare.net/threepipes_s/hatetrisai-190245892
評価値は次の式で、最小化を目指します。
holes + 2 * enclosed_holes + (100 - lines) * 1000000
holes= 空白のうち、上方向に1つでもブロックが存在する穴の個数enclosed_holes= holesのうち、さらにどこを辿っても最上段に到達できない、完全に閉じた穴の個数lines= それまでに消したライン数
意図は、シンプルに「ライン数」が良い解を重要視して、その中でなるべく穴を減らそうとしています。
ちなみに enclosed_holes の計算は、バグでほぼ値を返していないことに後ほど気づいたので、何を探索していたか今となっては不明です。
先ほど紹介したスライドでは、さらに高さを評価しています。しかし、これは時期尚早だと考えたので外しています。
その理由として、地形は高くても綺麗に積み込んでいれば、通常のテトリスでの 4列REN のように、後から少しずつ消せる可能性があるためです。
実際、HATETRISでは地形の高さによって落ちてくるミノが決まるため、都合の良いミノである間に積み込んでおくパターンはよくみられます。
そして、ビーム幅は100万地形にしています。
動きのイメージとしては、次のような感じです。
現在の地形リスト
→ 1手先の地形に展開
→ 地形が重複していなければスコアを計算してリストに保存 (元の約15倍の個数になる)
→ スコア上位100万個を取り出す
→ 空になるまで処理を続ける
この時点で、当時の世界記録タイである31Lを得られました。 実行時間はたしか12時間かかっていないくらいだった気がします（覚えていない）。
この結果をみて直感で、理論値は40L丁度かその手前くらいではと、この時点では考えていました。 終わってみると、思いのほかまだ先がありました。
ビームサーチしたことで、HATETRISのある特徴に気づきました。 それは「手が進めば進むほど局面数が減少していく」ことです。 通常のテトリスの場合、ラインを消すこと自体はとても簡単なので、うまくプレイすればゲームオーバーにならず、次のミノを置く場所も基本的に減りません。 HATETRISの場合は、そのライン消去が難しすぎるため、うまく置いても地形が高くなっていきます。 その結果、置く場所が減っていきます。
そのため、ゲームオーバー直前の局面であれば、全探索で確実なスコアを計算できると思いました。
この最終局面の全探索では、深さ優先探索をしています。 感覚的には大体、フィールドの残りが6段くらい、スコアが残り10ほどであれば、数分で結果を得られます。
これを31Lの結果の途中から探しなおしたところ、+1Lする手順がみつかり、当時の世界記録となりました。
ひとまず世界記録がみつかって、気分的にも一区切りつきました。 それまでのアプローチ的に過去の手順を参考にする機会がなく、ふと調べてみようと思いたって、2017年にみつかった31Lのリプレイを見ました。
そのとき32Lと同じ、特徴的な地形が現れていることに気づきました。
HATETRISは基本的に掘ることができないため、フィールド上部の地形が同じだと、その後も同じように展開できることが多いです。 そして、この地形が現れた瞬間のスコアが、以下の通りでした。
- 31Lの手順 → スコア13
- 32Lの手順 → スコア11
そのため、前半は31Lの手順、後半は32Lの手順とすることで、記録を伸ばせることが確定していました。 つまり32Lの手順では、後半の展開だけで31Lの記録を +3L していたことになります。
前半は適当にしか探していなかったので、妥当な結果ではあります。 この出来事により、探索中の地形も一度は目で確認しながら作業を進めるようになりました。
34Lの結果を受けて、様子見で書いたビームサーチが流石に適当すぎたので、実装を洗練させました。
具体的に大きく変わったのは、以下の点です。
- Transposition Tableを書いて、同一局面で一番良いスコアが次の探索に反映されるようにした
- もう少し複雑な探索用に書き始めたが、しばらくはビームサーチでも十分そうに思えたので、混ぜる形になった。
- 自分のPCスペックの都合上、メモリを12GBくらいしか使えないので、なるべくメモリに値を保持しないつくりにした
- 一般的なゲームAIとは異なり、実行時間に制約がないので、ちょっとしたことであれば再計算する方針
- メモリ上では、前の手の情報をハッシュ値でしか持たない(64bit)
- 良いスコアとなる地形をみつけても、その瞬間の情報では、手順を再現できない状態になった
- 途中の探索フィールドをすべてファイルに保存しておくことで、後からハッシュ値をもとに前後の手順を復元させる
- その結果、実行のたびに500～600GBくらいの中間成果物をつくることに
その結果、ビーム幅を1200万地形に増やせることになりました。基本的な動きはそこまで変わっていません。
ところで、このタイミングでビームサーチではなく、より有効な手を深く読むような探索手法に変えようか悩みましたが、最終的にはしませんでした。 理由としては、以下の通りです。
- 評価値の精度が高くないと、むしろ探索結果が悪くなる可能性がありそう
- ビームサーチとは異なり、探索の終わりどころが難しくなりそう
- 初期フィールドを変えながら、ビームサーチを繰り返し手動で起動することで、本質的にやりたいことは実現できると考えた
※ 45Lをみつけた今、個人的に記録を超えるのに注力すべきは「評価値の精度をあげる＋このあたり」な気がしています。でも大変そうです。
それを踏まえて、ビームサーチ数回 + 後半の全探索で、41Lの手順は見つかりました。 ちなみに、空のフィールドから最後まで1回のビームサーチで40Lが見つかったので、数回起動した効果は思ったほどありませんでした。
ここまでずっと、ほぼ穴の個数しか数えていない評価値だったので、これを何とかしようと思いました。 新しい特徴量は、とりあえず良さそうなものを小さい幅のビームサーチで試して、感覚的に選ぶことにしました。 最終的には、以下の特徴量に落ち着きました。
- フィールドの表面で一番低いところより上に限定した holes, enclosed_holes
- 7種のミノでラインを消去できる地形であるか。できる地形ならミノの種類ごとに固定のボーナスをもらう
- それまでに消したライン数に応じたボーナス
評価値の重みはどのくらいが良いかわからなかったので、 実数値型GAで「小さめのビーム幅でよりライン数を消せる重み」を探しました。
この時点でビーム幅1万でも、32Lは見つけられるようになっています(探索時間も2分弱)。
このように評価値を調整したうえで、41Lと同くビーム幅を1200万地形で実行しました。 その結果、残念ながら41Lから改善しませんでした。
その一方で、得られた手順が異なっていたことや、31Lの出来事もあったため、結果を目視で確認していたところ、 同じ地形が何回か出現していることにも気づきました。
そこで、機械探索で綺麗に求めるのは諦めて、 「ベースを自分で考える→機械でさらに良い解がないか確認する」方針に切り替えました。
現時点の最高記録である45Lの記録は、大きく3つの構成になっています。
- スタートから、画像の地形まで
- 画像の地形から、元にもどるループ
- ループ途中から、ゲームオーバーまで
具体的にどのように探したかというと、以下の通りです。
- 空のフィールドからのビームサーチで、表面が画像のようになる低い地形がないか、ざっくり探す
- これまでの探索結果で良さそうなパターンをピックアップする (画像以外の表面で良さそうなものも一通り確認)
- 全探索やビームサーチをつかって、最終局面での手順を確定させる
それぞれ専用のアルゴリズムを使ったわけでもないので、本当にベストかはわかりませんが、最終的に改善できなかったため、そのときのベストを公開しました。
2か月ほど経って、過去のソースコードを眺めていたら改善点がそこそこ見つかったので、調べなおしてみようと思って再開しました。 45Lからの変更点は以下の3つです。
- 評価値の変更
- ビーム幅 2500万地形
- バグの修正
ここでは1.について書いていきます。
34Lまで: 「穴の個数が少ない」方向に探索します
- 赤: holes
- オレンジ: enclosed holes
- 現在のスコア (消去したライン数)
45Lまで: 「穴の個数を少なくて、消去しやすい」方向に探索します
- 赤: 地形の表面に限定した"holes"
- オレンジ: 地形の表面に限定した"enclosed holes"
- ピースの種類ごとのライン消去ボーナス (この地形ではすべての種類でボーナスをもらえる)
- 現在のスコア (消去したライン数)
どちらの地形も"enclosed holes"は2つです。 しかし、2つ目の地形は下から3段目を揃えるのが難しいため、今後の展開に不利になると考えました。 そこで「"enclosed holes"が含むライン数」をスコアに反映することにしました。
ちなみにこの"enclosed holes"を素直にカウントした場合、一時的に蓋をする展開に弱くなります（"Donating"のようなテクニック）。
HATETRISのルール上、ライン消去できないピースが優先的に選択されます。 そして、どのピースでも消去できる地形の場合、優先度が一周して、SZのどちらかが選択される可能性が高いです。 そこで、SZを置くことで"enclosed"を解消できる穴は、カウントしないようにしています。
この特徴量を、45Lの評価値に加えます。 そのうえで、各特徴量の重みを再調整しました。
記録が66Lとなり、45Lのときにあった、明らかに改善できそうな余地もなくなってきた感覚があります。 とは言え、まだ上はある気はしています。
そんな感じで、誰かが更新してくれることを期待しています。 そのときに、この経緯が役に立ってくれればうれしいです。