さくさく理解する Godot 入門（ただし2Dに限る）応用編 Q学習【第4回】

３目並べ

■概要

Q学習では、すべての状態とその状態でのすべての行動のQ値をテーブルにする必要がある。なので、囲碁や将棋など、状態数や可能行動数が膨大なものに適用するのは困難が伴う（その解決方法として、状態を離散化したり、ニューラルネットワークと組み合わせるなどの方法があるが、本稿では言及しない）。

というわけで、本稿では、全状態数が少なく、全状態・可能行動Q値をメモリに簡単に保持することが可能な「三目並べ（Tic-tac-toe）」を取り上げることにする。

ゲームに勝った場合の報酬を +1, 負けたら 0, 引き分けは 0.5 とし、10% ε-greedy のQ学習を行う。
三目並べは非常に単純にも関わらず、学習にはかなりの回数（エピソード）、それなりの時間を必要とし、本当に学習が正しく進んでいるのかどうかが不安になる。そこで、学習が進展しているかどうかを評価するために、ランダムプレイヤーを用意し、それに対する勝率を計測するようにした。これは以下の論文を参考にさせていただいた。

参考文献：http://www.net.c.dendai.ac.jp/~ito/「Q学習による三目並べの学習」

なお、例によって本稿の全ソースは github（https://github.com/vivisuke/TicTacToe）にアップしているので、ぜひダウンロードして実際に修正・実行などを行ってほしい。

■画面（UI）作成

本アプリのスクショを下図に示す。

盤面は、背景白色の ColorRect を配置し、TileMap をその子ノードとして配置している。 TileMap は○☓の石表示用で、石画像を TileSet に登録する（下図参照）。

盤面のグリッド・上左部の座標文字描画は下記のスクリプトで行っている。

const LINE_WIDTH = 4.0
const CELL_WIDTH = 96

var font = DynamicFont.new()	# フォントオブジェクト生成

func _ready():
    var font_data:DynamicFontData = preload("res://fonts/arialbd.ttf")
    font.font_data = font_data
    font.size = 40
func _draw():
	# グリッド描画
    draw_line(Vector2(0, 96), Vector2(288, 96), Color.black, LINE_WIDTH)
    draw_line(Vector2(0, 192), Vector2(288, 192), Color.black, LINE_WIDTH)
    draw_line(Vector2(96, 0), Vector2(96, 288), Color.black, LINE_WIDTH)
    draw_line(Vector2(192, 0), Vector2(192, 288), Color.black, LINE_WIDTH)
    # 座標文字描画
    for y in range(3):
        var pos = Vector2(-CELL_WIDTH*0.4, CELL_WIDTH*(y+0.65))
        draw_string(font, pos, "%d" % (y+1))
    for x in range(3):
        var pos = Vector2(CELL_WIDTH*(x+0.35), -CELL_WIDTH*0.15)
        draw_string(font, pos, "abc"[x])

盤面以外は、状態をテキストで表示するための Label と、学習を行うコマンド用に Button を配置しているだけだ。
実験用のアプリ画面なので、見た目を良くするなどの凝ったことは考えず、必要なものを配置するにとどめている。

■初期化処理

盤面データ構造としては、ビットボードを用いている。ビットボードとは、盤面の状態を石の種類ごとに1ビット＊セル数分並べたものだ。三目並べには○と☓の二種類の石しかないので、整数型の bits_O, bits_X の２つの変数（下位9ビットのみ使用する整数）で盤面を表す。
ビットボードは、1セル単位のデータ構造より、終局判定などの必要な処理が高速になることが多い。チェス、オセロ、将棋などでは普通に使われているデータ構造なので、ぜひマスターしておきたいもののひとつだ。

以下にメンバ変数定義の一部を示す。

var bits_O = 0          # O 状態ビットボード
var bits_X = 0          # X 状態ビットボード
var is_victory_table = []       # ビットボード → ３目並びがあるか？
var Q = []              # Q値テーブル

終局したかどうかを高速に判定するために、is_victory_table という配列を用意しておき、盤面状態 bits で石が３つ並んでいるかを計算し、それを is_victory_table[bits] に格納しておく。

上記以外にもメンバ変数は多数あるが、重要なのは Q値テーブルだ。状態・行動ごとのQ値を保持する。行動は、どの場所に石を打つかなので、ビットボードの場所を行動とみなすことにする。

初期化関数である _ready() の実装を下記に示す。

func _ready():
    Q.resize(N_3_POWER_9)   # 全状態：3^9
    build_victory_table()   # 終局判定用テーブル構築
    init_board()            # 盤面初期化
    init_qvlabels()         # Q値表示用ラベル初期化
    update_qvLabels()       # Q値表示
    update_nextLabel()      # 次の手番ラベル更新

処理内容はコメントに書いているとおりだ。

終局判定用テーブルを構築する build_victory_table() の実装を下記に示す。

func is_victory_basic(bits) -> bool:    # 勝利状態か？
    if (bits & 0b111000000) == 0b111000000: return true
    if (bits & 0b000111000) == 0b000111000: return true
    if (bits & 0b000000111) == 0b000000111: return true
    if (bits & 0b100100100) == 0b100100100: return true
    if (bits & 0b010010010) == 0b010010010: return true
    if (bits & 0b001001001) == 0b001001001: return true
    if (bits & 0b100010001) == 0b100010001: return true
    if (bits & 0b001010100) == 0b001010100: return true
    return false
func build_victory_table():     # 終局判定用テーブル構築
    is_victory_table.resize(N_2_POWER_9)
    for bits in range(N_2_POWER_9):
        is_victory_table[bits] = is_victory_basic(bits)

コードは単純で、三目並ぶ可能性のある場所をビットテストし、３つのビットがすべて立っていれば三目並んでいるということなので、テーブル要素を true に設定している。

盤面初期化関数 init_board() の実装を下記に示す。

enum {
    TILE_EMPTY = -1,
    TILE_O,
    TILE_X,
}
func init_board():      # 盤面初期化
    ended = false       # 終局状態
    next = TILE_O       # 次の手番
    bits_O = 0
    bits_X = 0
    for y in N_VERT:
        for x in N_HORZ:
            $Board/TileMap.set_cell(x, y, TILE_EMPTY)

終局状態フラグをOFFに、次の手番を○に、ビットボードの盤面を全空に設定し、 for 文を回して TileMap を空に設定している。

■学習開始

画面に配置した「AI x Rand 100」などのボタンが押下されると、それに接続されたハンドラがコールされる

何回目のエピソード（ラウンド）か、残りのエピソード数、勝敗結果を保持する変数を初期化し、mode を MODE_AI_RAND に設定する。 mode が設定されると、それがフレームごとの処理関数（次節参照）で参照され、mode に応じた処理が行われる。

func _on_AIxRx100Button_pressed():
    nEpisode = 0            # エピソード実行済み回数
    nEpisodeRest = 100      # 何エピソード学習するか
    nAIwon = 0              # AI 勝利数
    nRANDwon = 0            # ランダム勝利数
    nDraw = 0               # 引き分け数
    mode = MODE_AI_RAND