「最高落下速度(20G)」かつ「クラシック方式の回転法則」という高難易度環境のテトリスで良い感じに動くゲームAIを作りました。以下はそのデモです。
ソースコードをgithubで公開しています：https://github.com/ir5/tetris20g-ai
ゲームのルール
テトリスは知っている方が多いと思いますが改めて説明すると、10x20くらいのフィールドで次々に空から降ってくるピースを操作して地面に固定させ、横一列にブロックが揃ったら消える、というのを繰り返すゲームです。
”普通の設定”で動くテトリスのゲームAIは世の中にたくさんあるようですが、今回はよりタフな設定でゲームAIを作りたいと思ったので以下のような高難易度要素を取り入れました。
落下速度：20G
普通のテトリスではピースは1マスずつ落下していきますが、これを加速させて最高のスピードにするとフィールドの上部に現れたピースが即座に地面に接地した状態で現れることになります。このような環境を20Gと呼びます。1フレームの間にブロックが20段落ちることからこのような名前が付いています。
即座に地面に接地すると全く動けなくてゲームにならないような気がしますが、実際には接地してから固定されるまでには時間があり、地面の上を転がるように動かすことでピースを所望の位置に運ぶことが出来ます。
20G下ではピースの可動範囲に大幅な制約が加わることになります。例えば以下のような盤面では水色ピースは真ん中に落下した後そこに埋もれてしまい、左右の端に移動することができません。
このような状況に陥らないためには、常に中央を高くした状態でブロックを積んでいくことが重要になります。また、そのため中央付近には穴を作ってしまわないことも重要です。
手法
今回ゲームAIを作るために試した手法は一言で言うと「2マス関係による線形関数で評価関数を表現し、手でアノテーションしたデータを使ってランク学習で評価関数を最適化し、テスト時には2手まで探索して評価値が最も高いものを選ぶようにした」となります。
それぞれの要素について説明していきます。
評価関数
評価関数とはゲームの盤面に対してそれがどれくらい”良い”ものかを表す値を返す関数のことです。テトリスのようなゲームでは精度の高い評価関数があれば探索系の手法と組み合わせることで良い手を選ぶことができます。
落下速度が低速の場合は単純な評価関数だけで十分上手くいくようです。例えばこのブログ記事によると、4つの手製の特徴量について重み付き和を取るだけでほぼ完璧なゲームAIが出来上がったそうです。
しかし今回の設定では地形の判断をそれなりに精密に行う必要がありそうだったので、このような単純な特徴量だけではうまくいかないだろうと判断しました。評価関数で地形の情報を詳細に盛り込むために、今回は以下のような異なる2マスの関係に着目するような評価関数を使うことにしました。
\[
v(f) := \sum_{i,j} w_{ij}\cdot\mathbf{1}[f_i=1, f_j=0]
\]
ここで、$v$ は評価関数、$f$ はフィールド、総和の $i,j$ はフィールドの各マスを表す変数、$w_{ij}$ は評価関数の重みパラメータ、$\mathbf{1}[f_i=1, f_j=0]$ はマス $i$ にブロックがありかつマス $j$ にはブロックがないようなときに1になりそうでないなら0になる関数とします。
この評価関数により、パラメータ $(w_{ij})_{i,j}$ は 200^2=40000 個生まれることになりますが、この中には明らかにどうでもいいものも含まれています。例えばフィールドの右上と左下の関係などどうでもいいに決まっています。よって実際には $i,j$ ペアとしては位置が近いものだけを考えることにすることで、パラメータを8184個に絞っています。
評価関数をこのような形にしようと思ったのは、将棋でn駒関係のような特徴量が結構良い感じに効いているというのをどこかで聞いたことがあったり、ぷよぷよのAIでも2駒関係が使われていたりしたので参考にできそうと思ったためです。
学習
評価関数の形を決めたので、次にそのパラメータ $(w_{ij})_{i,j}$ をどうやって探すのかについて考えます。
今回はランク学習という方法を用いて人間(=僕)のアノテーションデータを使ってパラメータを最適化することにします。
ランク学習とは一般には対象物の順位付けを求めるために用いられる手法ですが、今回のような評価関数を求める目的にも使えます。
いま、人間のアノテーションログがあって、その中にフィールド $f$ から1手打って $f'$ に移ったログがあったとします。これは次のようにも解釈できるはずです：$f$ から次に取りうるフィールドとして $f'$ 以外にも $f'_1,...,f'_n$ があったとき、各 $i$ について $v(f') > v(f'_i)$ が成り立っている。
そこで、各 $(f', f'_i)$ について、$(v(f') - v(f'_i))$ がマイナスならそれに応じたペナルティをかけて、プラスならそんなにペナルティをつけないような損失関数を取るようにして、それで全体を最適化すればうまくいきそうな気がします。
ランク学習ではこのような損失関数として $L(x) := \log(1+\exp(-x))$ のような形の関数が用いられます*2。これは以下のような形状の関数です。
この損失関数で、全ての $(f', f'_i)$ ペアの平均値を取ったものを最小化するようにパラメータ $(w_{ij})_{i,j}$ を最適化することにします。式で書くと以下のような雰囲気です。($N$ は総データ件数)
\[
\frac{1}{N} \sum_f \sum_i L(v(f') - v(f'_i)) \rightarrow minimize
\]
これは非線形最適化問題なので、確率的勾配法(SGD)を使って最適化することができます。
なお、上の説明では1手打った後のフィールド同士を比較するとしましたが、テトリスではネクストを見て打つ手を変えるということをよく行うため、実際には2手打ったフィールド同士を比較しています。
実験と結果
実装はほぼすべて rust を使って行いました。評価関数パラメータの学習部分のみ非線形最適化で若干面倒そうだったので python (+Chainer) を用いています。
学習には約7000手分のアノテーションデータを使い、そのうちの10%を検定に用いました。
これだけの学習データでも2手先読みをすると平均で200~300個くらい異なる候補がありうるので、学習用のデータをナイーブに作ると 8184bits*6000*300*2≒3.6GBくらいになって量が膨大になるので、データのうち80%はランダムに間引きました。
学習には Chainer の MomentumSGD を使いました。学習率は 1e-2 (デフォルトと同じ) です。
性能の評価のために、ゲームオーバーになるまで実行して何手まで生き残れたのかについて見ました。30回試行したところ、結果は以下のようになりました。
- 平均: 7240.7
- 標準偏差: 6103.3
- 最小: 977
- 最大: 26295
ツモを完全ランダムにしたせいで運要素が強いゲームになっているのですが、比較的頑張ってるような気がします。たまに4ライン消しも狙いに行きます。
計算速度に関しては、1秒間に52手ほどの手を選ぶことができました*3。
試したけど上手くいかなかったこと
- 最適化には最初 MomentumSGD ではなく(特に理由なく) Adam を使用していたのですが、最初の数 epoch 以降 validation loss がどんどん上がっていくという現象が発生しました。正則化として weight decay を入れてみたりしたものの効果無し。何が原因なのかいまいちよく分からずじまいです。
- 80%も間引くなら比較候補はランダムよりも判断に悩む手の方が学習に良いのでは？と思い、評価関数が得られた後で、評価値の上位20％の $f'_i$ だけを学習データに入れて再学習させるということをしたのですが、結果はそんなに良くなりませんでした(というか若干悪化しました。) 人が打った手にも悪手が混じっているので、あまり特化させすぎるのも良くない？よく分かりませんが。
まとめ
テトリスのAIを実装した話をしました。今回試した手法は比較的素朴なものであり、以下のような改善点があると思います。
- アルゴリズムを動かしているとある決まったパターンの”愚形”が現れることがある。これは今の評価関数が捉えきれていないパターンがあるということなので、これを補えるようなパターンを特徴量に追加してやることで、性能が向上する可能性がある。
- 人間のデータを使っている限り、人間の性能は越えられないかもしれないので、何らかの自己学習の仕組みを導入する。特に、今は人間の手を真似ているだけで「4ライン消し」のような得点を狙う仕組みが何も入っていない。
とはいえど、これでもまぁまぁ動いていて割と満足してしまったような気もします。
