遺伝的アルゴリズムでテトリス風ゲームをPLAYさせる

はじめに

以前、PyTorchという機械学習ライブラリを試したことがあるが、合わせて遺伝的アルゴリズムというものにも興味があり、それを使って書かれたAI(ゲームを自動で操作するプログラム)がどんどん上手になるという動画をみた。

非常に面白いので試しに何か真似て作ってみたいと思い、では何を題材にするかと悩んだらまあ、無理なく書けそうなテトリスを作ってみようということにしたのがきっかけ。

とりあえず実際のPLAY動画

第1世代はほぼランダムなので1行も消去できないのが当たり前ぐらいのレベルだが、次の世代ですでに上手にPLAYできてしまっていることに驚いた。その後も4世代ぐらいでほぼ成長は止まる。Networkのモデルが単純なものだからパラメータ数も少ないので当然といえば当然か。

ソースはこちら

Pygame

Python のGUIが伴うゲーム開発ライブラリは数多くあるがPygameというのが扱いやすいように感じたので今回はこれを用いる。画面が開く簡単なサンプルを以下に示す。このプログラムで左上にカウンターがあり、方向KEY+スペースを押すたびにそのキーが表示される簡単なもの。

import pygame
import sys


def main():
    pygame.init()  # pygameを初期化数する
    screen = pygame.display.set_mode((640, 480))  # 画面サイズを640, 480に
    pygame.display.set_caption("tetris_ai")
    clock = pygame.time.Clock()  # フレームレート(描画頻度)を更新するためのタイマー
    font = pygame.font.SysFont("Arial", 40)

    i = 0
    while True:   # ゲームのメインループ
        i = i + 1
        screen.fill((0, 0, 0))  # マイループで画面を真っ黒に一度する
        screen.blit(font.render(str(i), True, (255, 255, 255)), (40, 40))  # 左上に積算のカウンターを表示する
        for event in pygame.event.get():  # イベントは一括で取得
            if event.type == pygame.QUIT:  # 終了ボタンを押したときにpygameを閉じるのはお作法
                pygame.quit()
                sys.exit()
            if event.type == pygame.KEYDOWN:  # これよりキーボードのイベントを捕捉
                if event.key == pygame.K_RIGHT:  # 右が押された場合...
                    show_press_key(screen, font, "RIGHT")
                if event.key == pygame.K_LEFT:
                    show_press_key(screen, font, "LEFT")
                if event.key == pygame.K_UP:
                    show_press_key(screen, font, "UP")
                if event.key == pygame.K_DOWN:
                    show_press_key(screen, font, "DOWN")
                if event.key == pygame.K_SPACE:
                    show_press_key(screen, font, "SPACE")

        pygame.display.update()  # 描画を更新する
        clock.tick(3)  # フレームレートを3 (秒間3回更新するぐらいの頻度に設定)


def show_press_key(screen, font, key):
    screen.blit(font.render(key, True, (255, 255, 255)), (40, 100))


if __name__ == "__main__":
    main()

とりあえず普通に遊べるテトリスを作る

AIでといっても一人で普通に遊べるテトリスを作らなければ話にならない。。ということで作ってみる。テトリスの仕様などは wikipedia で詳しい

プログラムは簡単に以下の4つのファイルで構成した。プログラム自体は色々と雑なところはご了承を…

  • play.py 〜 PLAY版メイン処理
  • field.py 〜 10×20のマスで構成される盤面を管理するクラス
  • tetrimino.py 〜 4つのブロックで構成される7種類の塊 (テトリミノと呼ぶらしい)を管理するクラス
  • block.py 〜 1つのブロックを管理するクラス

遺伝的アルゴリズムでPLAYしながらスキルを成長させる

上の実際にPlayできるプログラムに加え以下のプログラムを追加する

  • main.py 〜 AI(遺伝的アルゴリズム)版メイン処理
  • network.py 〜 個々の個体のPyTorchモデル (9入力1出力の1層の線形モデル)
  • population.py 〜 複数の個体で構成される世代を管理する. 世代の更新等も行う

基本的には各盤面の状況を加味して次のブロックが配置できる全ての候補に置いてスコア(期待値)が最も高い場所に配置し続ける単純なもの。

スコアに関してはいろいろな文献を参考にさせてもらったがコード的にはfield.pyの以下の部分がそれに相当する

    ddef get_field_score(self, candidate_blocks=None):
        """ 盤面の評価値を返す
        :param candidate_blocks: 現在の盤面に特定のテトリミノが次に配置されたと仮定した状況で評価する
        :return: 9つの1次元配列 (Numpy array型)
        https://ichi.pro/identeki-arugorizumu-de-tetorisu-gb-no-sekai-kiroku-o-yaburu-118795294920347
        戻り配列詳細:
        0: 高さ総合計
        1: 穴数合計
        2: 少なくとも1つ以上穴のある列数
        3: 行遷移数
        4: 列遷移数
        5: 凸凹数
        6: ブロックが1つも無い列数
        7: 最大井戸高さ
        8: 消去行数
        """
        area = np.array(self.get_bit_field(candidate_blocks))
        peaks = self.get_peaks(area)
        highest_peak = np.max(peaks)
        agg_height = np.sum(peaks)

        holes = self.get_holes(peaks, area)
        n_holes = np.sum(holes)
        n_cols_with_holes = np.count_nonzero(np.array(holes) > 0)

        row_transitions = self.get_row_transition(area, highest_peak)
        col_transitions = self.get_col_transition(area, peaks)

        bumpiness = self.get_bumpiness(peaks)

        num_pits = np.count_nonzero(np.count_nonzero(area, axis=0) == 0)

        wells = self.get_wells(peaks)
        max_wells = np.max(wells)

        cleard = area.min(axis=1).sum()

        return np.array([agg_height, n_holes, n_cols_with_holes,
                         row_transitions, col_transitions, bumpiness, num_pits, max_wells, cleard])

おわり

とりあえずなんちゃってな遺伝的アルゴリズムは実装できたので満足。おそらく、次のブロックまで考慮して、とか、一度に複数ライン消去等のボーナスを積極的に獲得するようなスコア値等の調整すればまた異なったPLAYスタイルがみえつつ、頭打ちだった成長も限界突破するような気がするのでまた暇なときに触ってみよう。