RetailAI AdventurersAdvent Calendar 2023

遺伝的アルゴリズムを用いたテトリス

Last updated at 2023-12-10Posted at 2023-12-10

はじめに

Retail AI Adventurers Advent Calendar 2023の11日目の投稿です．
昨日は@ido_shunさんのDev Containerで開発環境の年末大掃除を行うでした．
本日は遺伝的アルゴリズムを用いたテトリスについて記述します．このテーマにした理由は以下です．

シンプルで伝統的なアルゴリズムを体系的に学びたかった．
最近，生成AIと進化的アルゴリズムが注目されており，これからも活きてくるアルゴリズムと考えられるため．

どこにミノを置くか？

テトリスの概要やルールについては割愛いたします．今回はテトリスの基本的なルール(ランダムに落ちてくるミノを積み上げて，行すべてをブロックで埋めると，その行を消去する)を前提としています．正式なものはこちらをご確認ください．
さて，突然ですが下図のような状況のとき，皆さんは①〜③のどこにミノを置きますか？

私であれば③に置きます．これに関しては感覚的に理解してくださる方も多いと思います．この感覚的に良い位置，悪い位置をうまく定義して，どこにミノを置くのが最も適切なのかを求めるようにします．最適な場所に置くために，今回は以下を評価項目としました．今回は簡単のため4項目としていますが，もっと色々な観点を追加できると思います．

$x1$: 消すことのできる行数
$x2$: 積み上がるブロックの高さ
$x3$: 「隣接する列に積み上がっているブロックの高低差」の合計
$x4$: デッドスペースの数

そして，評価値を$E$として，以下のように表現します(※正確には少し異なります．)．

E = w1 * x1 + w2 * x2 + w3 * x3 + w4 * x4

要するに，今の盤面と落ちてくるミノを照らし合わせて，「できるだけブロックを消し，なるべく高さを抑え，なるべくデコボコにならず，デッドスペースを作らない」ように置く向きと場所を決定します．先程の例で，①だと溝が深くなる，②だとデッドスペースができる，というように感覚的に捉えていたものを，ここからは評価値$E$で比較していきます．

ミノが落ちてくる間に，置くことのできるミノの向き，場所全パターンに対して$E$を算出し，$E$が最も良いものを最適な置き場所として，そこにミノを置くようにします．

これを繰り返すことで，テトリスゲーム自体を長く続けることができ，ゲームオーバーまでのスコア(※)が上がることが期待できます．(※) スコア = (一度に消した行数 ** 2)の合計．

ここで重要なのは，$w1$~$w4$の値をどうするかです．つまり上記4項目のどれを重要視して置く場所を決定するかがチューニングするポイントとなり，ここに遺伝的アルゴリズムを導入します．

遺伝的アルゴリズムを導入

遺伝的アルゴリズムを用いて，最も優れた$w1$~$w4$の算出を試みます．遺伝的アルゴリズムの概要についてはこちらをご覧ください．各パラメータに範囲を設けて，その範囲内で値をセットしてテトリスを行ない，最終スコアがどうなるかを見ていきます．

今回は以下のようなアルゴリズムで$w1$~$w4$を継承させていきます．

30パターンの組み合わせ(個体): $w1$~$w4$をランダムに作成する．
各個体が$E$に従ってミノを置くテトリスを5回ずつ実施し，最終スコアの平均を取る．
ここでスコアに応じて以下の操作を行なう．
1. スコア上位20%の6個体はそのまま次の世代に引き継ぐ．(選択)
2. 下位20%の6個体は次世代には引き継がない．(淘汰)
3. 下位20%の6個体を除いた24個体で，12組のペアを作り，それぞれで使っていた$w1$~$w4$のいずれか2つを入れ替える．(交叉)
4. 3-3の中で，新しく個体を作るとき，20%の確率で$w1$~$w4$のいずれか1個の数値をランダムな値に変更する．(突然変異)
新しくできた30個体で，2，3を実施する．

これを25回(世代)繰り返し，最終的に最もスコアの良かった$w1$~$w4$を最適なパラメータとして採用します．

結果

テトリスの様子

下図には，最初の世代のパラメータと，最後の世代のパラメータでテトリスをさせたときの動きを示しています．どうでしょうか．最初の世代では，ただひたすらミノを積み上げているように見えるのに対し，最後の世代はうまくブロックを消している様子がわかると思います．

最初の世代↓

最後の世代↓

スコアの推移

各世代ごとの30個体の平均スコアの推移は下図のようになりました．今回は同じことを4回試行してみたため，色別でグラフを示しています．いずれの試行においても，最初の世代では$w1$~$w4$がランダムな値であるため，ほとんどブロックを消すことができず，どの個体もスコアはほぼゼロです．ですが，世代を経るごとにスコアが伸びていることがわかります．シンプルにパラメータを入れ替える作業をしただけなのに，だんだんテトリスができるようになっています．面白いですね．まだまだ伸びしろはありそうですし，今回の4つの評価項目以外の要素を加えることでますます賢くなると考えられます．

パラメータの推移

世代ごとの最高スコアと各パラメータの関係も確認すると，ある世代から，最高スコアを出した個体の$w2$と$w3$が一定の値に落ち着いていました．つまりこのことから，「どうやら$w2$と$w3$が重要なパラメータで，隣の列との高低差がないようなるべく平らに積み上げていくようにすれば，良いスコアが出た」という見立てで，突然現れた強者個体，もしくはその子どもがそのまま最終世代まで生き残ってテトリスを行なってくれていたようです．他のパラメータは世代ごとに色々な値を取っていたので，極めて重要な評価項目ではなかったと考えられます．
代表して，世代ごとの最高スコアを出したときの$w3$の推移を下図に示しています(縦軸は内部で使った相対値です)．ざっくり，どこかに値が落ち着いていることを確認していただけたらと思います．

Discussion

以下2点については議論の余地があると考えています．今回はテトリスを題材にしましたが，もう少し抽象的に考えて，進化的アルゴリズムの改善案を表面的ですが記載します．

評価値について

今回はシンプルな線形結合のネットワークで評価値$E$を表し，パラメータのみを最適化しました．これについては決めうちで行なっており，ネットワーク構造が果たして良いのかどうかが論点になるでしょう．パラメータに加えて，最適なネットワーク構造を探索するNEATアルゴリズムがあり，これを用いることで発展が見込めると考えられます．実は評価値$E$を算出するにあたり，隠れ層を設けたほうが，より適切なネットワーク構造になったかもしれません．

継承のアルゴリズムについて

今回は私が好き勝手に決めたアルゴリズムをもとに次世代に継承させました．継承のさせ方さえも，決めうちではなく自発的に最適なものを見つけていくことが可能だと考えます．大規模言語モデルを用いれば，プログラムの入出力は保ちつつ，アルゴリズムの変更も可能です．アルゴリズム自体に賢く突然変異を起こすことで，閉じた世界から放たれ，新たな環境で継承を始めるため，これまでとは違った挙動を示すことが予想されます．

まとめ

今回は比較的多くの人になじみのあるテトリスを題材に遺伝的アルゴリズムを実装しました．遺伝的アルゴリズムを使って求めた$w1$~$w4$は，PCに数日間ただひたすらテトリスをやらせて，ようやく得た値です．4つのパラメータを求めることだけに，かなりの時間を費やしました．正味決めうちで設定した値でも，ある程度賢くテトリスをやってくれます．ですが，人の勘や経験，度胸で値を決めるのではなく，このような手段を使ってパラメータを求めて，ある程度賢いものをつくることができるということを知っていただけたら嬉しいです．

冒頭でも一言書きましたが，今後テトリスに限らず，生成AIでも活用されたり，モデルのパラメータを更新したりすることがあると思います．そのときに活用できれば良いと思います．

参考

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up