Zenn
📦

HATETRISのPythonエミュレータを作ってみた

2022/12/21に公開
Python
tetris
pygame
hatetris
tech

この記事はEEIC Advent Calendar 2022 21日目の記事として作成しました

はじめに

こんにちは。EEIC2022の Hirota (@decfrr) です。Advent Calender主催のくらげ君に何か記事を書くように言われたので記事を書きます。

後期にやったことで何か記事を書こう、とぼんやりと考えていました。後期学生実験で取り扱った内容で何か記事を書けば良いかなと思っていましたが、第1,3期の実験で取り扱った内容は公開しづらい内容で、第2期の人工知能演習で作成した成果物は1位を取れなかったのでボツになりました。（成果物は ここ にあります。）

そこで、人工知能の講義レポートの一環として作成したHATETRISのエミュレータについて取り上げることにしました。HATETRISを遺伝的アルゴリズムで解く、という課題です。実装にそれなりの時間がかかったので、若干の愛着があります。

なお、レポートのお題は選択式でしたが、周囲の親しい人間は誰もHATETRISを選んでおらず、誰とも内容について共有できずに非常に悲しい思いをしました。ここに供養します。

HATETRIS とは

HATETRISは、qntm氏が作成した「プレイヤーにとって最も嫌なテトリミノが生成される」テトリスです。

実際にプレイしてもらうのが一番わかりやすいと思いますので、是非プレイしてください → HATETRIS

HATETRISはソースコードが公開されていて、テトリミノ生成アルゴリズムなどを確認することができます。

初見だと1ライン消せるかどうかだと思います。実際、人間の手では30ライン程度が限界のようです。2022年12月21日現在はビームサーチや機械学習を織り交ぜた探索手法によって289ラインが最大のようです。（11月からループが見つかったり、12月にテトリミノ生成アルゴリズムに対して若干の変更があったりした点には注意してください）

日本のランカーの方が執筆した記事も参考になるかと思います。https://gist.github.com/knewjade/24fd3a655e5321c8ebac8b93fa497ed9#loop-infinite-loop

base2048コーデック

まだ本題に入れません。

HATETRISではテトリミノ生成アルゴリズムに一切のランダム性がないため、ある種の競技性(?)が生えています。
プレイ後に表示される謎の文字列（Unicode文字列です）を共有・利用することで、プレイを再現することが出来るようになっています。

例えば、次のUnicode文字列は公式の掲示板で一番初めに投稿されている11ラインの記録です。

ϥقໂɝƐඖДݹஶʈງƷ௨ೲໃܤѢقҾחࢲටฅڗ௨ΡІݪ௨ళȣݹࢴටງ໒௨ஶໃܥ௨റІݮ௨ఴІݥذඡଈݹƍق๓অஒॴแђञඖЅи௨sǶɔۑడПݷޠقԩݹࠉൿຟɓతණງஈশ੬෪অࠑථධٽଫ൝ଆࡨশ૫СܭߜయլݚɶऋഭܭرɤธӃస൯

HATETRISのプレイページの show a replayを選択して上記の文字列を入力してみましょう。11ライン消去されるリプレイが再現されます。

エミュレータを実装する上で、エミュレータを利用して探索を行う観点からもリプレイ再現が不可欠であったため、操作内容をUnicode文字列に変換するエンコーダとUnicode文字列からプレイを再現するデコーダの開発が必要でした。

ので、作りました。

基本的にはHATETRISのソースコードの該当箇所をそのままPythonに置き換えた形になっています。

若干工夫が必要だった点として、HATETRISはbase2048 というqntm氏作成のパッケージをインポートして利用していますが、Pythonには該当するようなパッケージが存在しませんでした。

正確にはPythonにも Base 2048 というパッケージがありますが、こちらはバイトとUnicode文字列の変換に対応しており、uint8のリストとUnicode文字列に対応するqntm氏作成のbase2048パッケージとは異なる挙動をするものでした。

base2048 sample
import base2048

base2048.encode(b'Hello!')
# => 'ϓțƘ໐µ'

base2048.decode('ϓțƘ໐µ')
# => b'Hello!'

Unicode文字列 ↔ uint8Array ↔ バイト という形の変換を行っても、Pythonのbase2048パッケージとUnicode文字列の変換表が異なったためか、想定している動作とはなりませんでした。

というわけで、qntm氏作成のbase2048パッケージをそのまま置き換える形で b2048.py を作成しました。

これらを作成したことで、エミュレータ上でプレイ・探索した操作について、再現用のUnicode文字列を出力したり、逆にUnicode文字列からリプレイ再現が出来るようになりました。

仕様は本家のエンコーダ・デコーダに揃えています。

hatetris/src/replay-codecs/base2048.ts
/**
  New new Base2048 replays!
*/

import * as base2048 from 'base2048'
import * as uint8Array from './uint8Array'

export const encode = (keys: string[]): string =>
  base2048.encode(uint8Array.encode(keys))

export const decode = (string: string): string[] =>
  uint8Array.decode(base2048.decode(string))
HATETRIS-AI/replay_codecs/codec.py
from typing import List
from .uint8array import encode as uint8array_encode
from .uint8array import decode as uint8array_decode
from .b2048 import encode as b2048_encode
from .b2048 import decode as b2048_decode


def encode(keys: List[str]) -> str:
    return b2048_encode(uint8array_encode(keys))


def decode(string: str) -> List[str]:
    return uint8array_decode(b2048_decode(string))

こんな具合に使います。

example.py
from replay_codecs.codec import encode, decode
# encode
# input: list of keyboard events
# output: string of hexadecimal
print(encode(['D', 'D', 'D', 'R', 'U', 'D'])) #'ਹԇ'
# decode
# input: string of hexadecimal
# output: list of keyboard events
print(decode('ਹԇ')) #['D', 'D', 'D', 'R', 'U', 'D']

HATETRISエミュレータ

ようやく本題に入ります。作ったものはここにあります。

https://github.com/decfrr/HATETRIS-AI

実際の使用方法については README.md を参照してください。ここでは実装についていくつか追記します。

盤面・ビジュアライザ部分

レポートのお題は「HATETRISを遺伝的アルゴリズムで解く」でしたので、メインのテトリスパートは遺伝的アルゴリズムが既にある程度実装されているものを参考にさせて頂きました。

hiyuzawa氏のtetris_aiを参考にさせて頂いています。ありがとうございます。

https://github.com/hiyuzawa/tetris_ai

変更点として

  • テトリスの細かな仕様
    • ゲームオーバーの基準
    • テトリミノの回転時の軸など
  • 遺伝的アルゴリズムで使用するパラメータ

を若干変更しています。が、ベースは変えていません。

テトリミノ生成部分

HATETRISのテトリミノ生成アルゴリズムの解説はいくつかありますので、詳細は省きますが、

  • 各テトリミノについて置ける場所を探索
    • 置いた時の地形を見たことあるかどうかの2値(12月16日のアップデートで何回見たことがあるかの最大値に変更されています)
    • 地形が一番高くなるときの最大高さ

をそれぞれ求めます。そして、ループを見たことがあるか（見た回数の最大値）→地形の最大高さの順番でソートします。最後にテトリミノの優先度ランキングでソートして、優先度最大のものが選ばれます。

テトリミノ優先度ランキングは Sミノ→Zミノ→Oミノ→Iミノ→Lミノ→Jミノ→Tミノとなっています。

基本的にはqntm氏のアルゴリズムをベースとしているコードに適用する形で実装しています。一部変更点として、qntm氏は置ける場所を探索する際に置いた後のフィールドの情報などを返していますが、

変更点として

  • 本家では盤面情報を返しているが、テトリミノの情報のみ返すように変更
    • 結局テトリミノを設置して評価することには変わらないので計算量的にはあまり変わらない

という点があります。

他にも遺伝的アルゴリズムを実装していますが、この記事はHATETRISエミュレータがメインの記事なので省略します。

おわりに

遺伝的アルゴリズム

遺伝的アルゴリズムをメインとした課題のはずでしたが、いつの間にかエミュレータ作りに必死になっていました。遺伝的アルゴリズムを調整する暇を食いつぶされてしまったため、結局3ライン消去するのが精一杯でした。是非皆さんも挑戦してみてください。

感想

課題をやるにあたってGitHub等をくまなく探しても使えそうなエミュレータが見当たらなかったため、今回は自作することにしました。実験で忙しい時期になぜそんな重いものを選んだんだと同期に散々言われました。

replay_codecs はある程度コードの綺麗さを意識して実装できましたが、時間に追われたためそれ以外は見るに堪えない部分もあります。リファクタリングしたいですね。

また、いくつか無理やり探索している箇所があり、エミュレータのパフォーマンスとしては少し疑問点が残る個所もあります。今後の改善点です。

プルリクエスト等は気軽にお願いします。

Discussion