(cache)遺伝的アルゴリズムでテトリスのAIを強くする

学校の宿題でつくってみた。未完成だし不完全だしもうちょっとよくできるだろうと思うけれども、遺伝的アルゴリズムでプログラムが強くなっていく様を見るのは面白い。

#1. 問題先日海外旅行に行ったのだが、飛行機の中でできるテトリスに夢中になってしまった。僕自身はテトリスマスターなどではなく初心者に毛が生えた程度で、機内のランキングでもやっとこさ8位にノミネートできるといった具合である。この時に、ふと、自分よりもうまくテトリスをプレイしてくれるプログラムを作ろうと思った。そのようなプログラムがあれば、プログラムが指示する配置の仕方を参考にでき、自身のテトリス力向上にも役立つと考えたのだ。

そこで今回は強いテトリスのAIを作ることを目標にする。

##1.1. テトリスのルールテトリスのルールとしては以下のようなものを使用する。テトリミノ

テトリミノの形は上図のような棒形, 正方形, S字, Z字, J字, L字, T字の7種類があり、回転ができる。
テトリミノが来る順番は完全にランダムである。
1ラインを消すと40ポイント、2ライン同時に消すと120ポイント、3ライン同時に消すと300ポイント、4ライン同時に消すと1200ポイントのスコア（以下、評価関数のスコアと区別するためにゲームスコアと呼ぶ）が貯まるとする。
ゲーム盤は10×20の大きさとする。

また、簡単のために以下の制限を設ける。

テトリスが接地してからの遊び時間は無い。
ホールド機能は無い。
次に来るテトリミノのみ分かる。
実際のゲームの中でその位置まで動かせるかどうかは考慮しない。

特に1, 4の制約により実際のゲームと多少異なる可能性が出てくるが今回は考慮しないこととする。

これらのルールに従い、AIはテトリスを進めていくこととする。今回作成するAIは全探索を行い評価関数（次節で説明）のスコアが最も高いものを選択していくことで高いゲームスコアを目指すことにする。

##1.2. 評価関数全探索の際に用いる評価関数について説明をする。ここは今回の問題の中心をなす話題である。評価関数のパラメータとしては以下のようなパラメータを考慮する。（パラメータの選定に際してはBai Li氏のブログエントリ¹を参考にした。）

クリア行数
- 一度にクリアできる行数が多いほど最終的なゲームスコアが高くなるため、これは配置位置の選定には重要な要素である。
高さペナルティ
- テトリミノが積み上がっていってしまうといずれゲームオーバーになる。そのため高さを抑えるような要素が必要である。スコア計算の際には高さをペナルティとして減ずるようにする。
ホールペナルティ
- ホールとは四隅が囲われた部分のことである。ホールが存在するとそれだけ行のクリアを阻むためペナルティとして減ずることにする。
封鎖ペナルティ
- ホールに覆いかぶさるように存在するブロックのことを封鎖と呼ぶことにする。この封鎖の存在もホールの生成を招くためペナルティとして減ずることにする。

以上のパラメータを用いて、評価関数のスコアを以下のように決定する。

スコア =  A*(クリアできる行数)
        + B*(次のテトリミノの最大の高さ)
        + C*(テトリミノを積んだ後の全体のホールの数)
        + D*(テトリミノを積んだ後の全体の封鎖の数)

今回解決する問題を改めて換言すると、これら評価関数のパラメータ値の係数A〜Dを求めることである。

#2. 解決方針今回はA〜Dを求める方法として遺伝的アルゴリズムを使用することにする。いずれも実数値である。A〜Dをビット化したものを並べることで遺伝子とする。また、A〜Dを求める際は遺伝子を適当な場所で切って解釈するようにする。

#3. 実装

ソースコード：takuma7 / tetris-ai-generator

Makefile
main.h
main.c
ga.h
ga.c
tetris.h
tetris.c

作成したプログラムのソースコードは上のような構成になっている。ga.*は遺伝的アルゴリズムの実装である。遺伝的アルゴリズムの具体的な実装は伊庭²を参考にし、複数の値に対応するように特に遺伝子型のencode, decodeを改変した。

遺伝的アルゴリズムの使用に際しパラメータは以下のようにした。

#define GRAY 1              /* グレイコードかバイナリコードの指定。グレイコードなら1, バイナリコードなら0 */
#define MAX (10)            /* 扱う実数の最大値 */
#define MIN (-10)           /* 扱う実数の最小値 */
#define LENGTH (10)         /* 遺伝子のコード長 */
#define POP 100             /* 個体数 */
#define CODE_MAX 1          /* 各遺伝子コードの最大値。これが１ならコードは0か1になる。ビットストリングの場合は１で固定 */
#define GAP 0.9             /* 一回の生殖で子供と入れ替わる割合 */
#define ELITE_RATE 1.0      /* そのまま残る数のうち、エリートの割合 */
#define P_MUTATE 0.0        /* 突然変異率。LENGTHの逆数程度がよい */
#define P_CROSS 1.0         /* 交叉確率 */
#define GENERATION 10       /* GAを計算する世代数 */
#define SELECTION_METHOD 1  /* 1はルーレット 2はトーナメント*/
#define TOURNAMENT_SIZE 5   /* トーナメントサイズ。トーナメントの時だけ意味がある  */

tetris.*はテトリス部分の実装である。テトリスについては本質的な基本部分のみ実装し、実際にゲームとしてプレイできるところまでは実装していない。

#4. コンパイル・実行方法展開フォルダ内で

make

と入力した後に

./generate_tetris_ai

を実行すると結果が表示される。 #5. 結果実行結果をout.txtに記録しておく。最後の出力は以下のようになった。

#   parents  xsite  gtype       A   B   C   D  fitness
0   (  1,  1)  39  [0100111101011101001011011011000001100110] -0.820  -3.066  +1.406  -8.672  +4606.667
1   ( 34, 52)  13  [0100111101011101001011011011000000010111] -0.820  -3.066  +1.406  -9.492  +3300.000
2   ( 42, 57)   6  [0100011101011101001011011011000000100110] -0.449  -3.066  +1.406  -8.848  +3266.667
3   ( 41,  0)  33  [0100111101011101001011011011000001000110] -0.820  -3.066  +1.406  -7.598  +3013.333
4   (  0, 41)  33  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +2920.000
5   (  2,  2)  39  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +2873.333
6   (  0, 60)  30  [0100111101011101001011011011000010010010] -0.820  -3.066  +1.406  -5.566  +2826.667
7   ( 29,  2)  13  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +2760.000
8   ( 40,  2)  16  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +2720.000
9   ( 25,  0)  17  [0100111101011101001011011011000000000110] -0.820  -3.066  +1.406  -9.922  +2620.000
10  (  0,  0)  39  [0100111101011101001011011011000000000110] -0.820  -3.066  +1.406  -9.922  +2520.000
11  (  9, 35)  31  [0100111101011101001011011011000001010110] -0.820  -3.066  +1.406  -8.047  +2440.000
12  (  4, 15)  12  [0100111101011101101010010111000010010010] -0.820  -2.891  +7.949  -5.566  +2280.000
13  ( 40, 16)  16  [0110101011001000001011011011000000100110] -4.023  -5.078  +1.406  -8.848  +2173.333
14  ( 52, 34)  13  [0110101101011101001001111010000000100110] -3.945  -3.066  -3.457  -8.848  +2080.000
15  ( 17,  0)  23  [0100011101011101001011011011000000000110] -0.449  -3.066  +1.406  -9.922  +2020.000
16  ( 35,  9)  31  [0100011000011111001011011011000001010110] -0.332  -3.203  +1.406  -8.047  +1993.333
17  (  7,  7)  39  [0100011000011111001001111010000000100110] -0.332  -3.203  -3.457  -8.848  +1946.667
18  ( 17, 44)   6  [0100011101011101001011011011000000010110] -0.449  -3.066  +1.406  -9.473  +1940.000
19  ( 12,  6)  13  [0100111101011111001001111010000010000110] -0.820  -3.203  -3.457  -5.098  +1926.667
20  ( 57, 42)   6  [0100011000011100001011011011000000100110] -0.332  -2.578  +1.406  -8.848  +1813.333
21  ( 51, 41)  23  [0100111101011101001011010111000000000110] -0.820  -3.066  +2.031  -9.922  +1680.000
22  (  1, 12)  25  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +1660.000
23  ( 16, 40)  16  [0100011000011100000001010111000010010110] -0.332  -2.520  -2.051  -5.547  +1620.000
24  ( 77, 38)  21  [0110101011001000000001011011000000100101] -4.023  -5.020  -1.426  -8.887  +1486.667
25  ( 35, 35)  39  [0100111101011101001011011011000001010110] -0.820  -3.066  +1.406  -8.047  +1460.000
26  (  3,  3)  39  [0100111101011100000100010111000000100110] -0.820  -2.539  -7.969  -8.848  +1413.333
27  ( 16,  1)  18  [0100011000011100001011011011000001100110] -0.332  -2.578  +1.406  -8.672  +1413.333
28  ( 40,  7)   3  [0100011000011111001001111010000000100110] -0.332  -3.203  -3.457  -8.848  +1373.333
29  (  0, 13)  12  [0100111101011101001011011011000001000110] -0.820  -3.066  +1.406  -7.598  +1373.333
30  ( 26,  1)  36  [0100111101011000101010010111000000000110] -0.820  -4.766  +7.949  -9.922  +1360.000
31  ( 15, 12)  38  [0100111101011101101010010111000010010010] -0.820  -2.891  +7.949  -5.566  +1326.667
32  (  2, 40)  16  [0100111101011101001011011011000001100110] -0.820  -3.066  +1.406  -8.672  +1306.667
33  ( 38, 77)  21  [0100111101011101001011010111100010100111] -0.820  -3.066  +2.090  -6.152  +1293.333
34  ( 11, 31)   1  [0100011000011100000001010111000010010110] -0.332  -2.520  -2.051  -5.547  +1286.667
35  (  9, 25)  11  [0100111101011101001011010111000010010110] -0.820  -3.066  +2.031  -5.547  +1260.000
36  (  0, 38)  33  [0100111101011101001011011011000000100101] -0.820  -3.066  +1.406  -8.887  +1220.000
37  ( 25,  9)  11  [0100111101011101001011011011000001010110] -0.820  -3.066  +1.406  -8.047  +1213.333
38  (  8, 21)  18  [0100111101011101001011010011000000100100] -0.820  -3.066  +2.324  -8.906  +1213.333
39  ( 15,  4)  12  [0100111101011101001011011011000001010110] -0.820  -3.066  +1.406  -8.047  +1206.667
40  ( 19, 92)   0  [0100011101001000010101110011000000100100] -0.449  -5.137  -2.676  -8.906  +1200.000
41  ( 80, 46)  33  [0100111101011101001011010111000010010010] -0.820  -3.066  +2.031  -5.566  +1186.667
42  ( 29, 56)  38  [0100011101001000010101110011000000100100] -0.449  -5.137  -2.676  -8.906  +1180.000
43  ( 12, 56)  21  [0100111101011101001011011011000000100101] -0.820  -3.066  +1.406  -8.887  +1160.000
44  ( 62, 31)  16  [0100111000011000100001010111000010010110] -0.938  -4.707  -2.051  -5.547  +1146.667
45  ( 12, 15)  38  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +1140.000
46  (  4,  4)  39  [0100111101011101001011011011000001010110] -0.820  -3.066  +1.406  -8.047  +1120.000
47  (  5, 10)  37  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +1113.333
48  ( 56, 29)  38  [0100011000011100001010010111000010010010] -0.332  -2.578  +7.949  -5.566  +1113.333
49  ( 13, 60)  31  [0100111101011101001011011011000010010010] -0.820  -3.066  +1.406  -5.566  +1106.667
50  ( 64, 33)  22  [1110111101011101001011010011000000100100] +4.180  -3.066  +2.324  -8.906  +1093.333
51  ( 44, 17)   6  [0100111101011101001011011011000000100110] -0.820  -3.066  +1.406  -8.848  +1093.333
52  ( 31, 11)   1  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +1066.667
53  ( 70, 41)   7  [0100111101011000101010010111000000000110] -0.820  -4.766  +7.949  -9.922  +1066.667
54  ( 46, 80)  33  [0100011000011000101010010111000010010010] -0.332  -4.766  +7.949  -5.566  +1026.667
55  ( 68, 48)  21  [0100111101011101001011011011000000010110] -0.820  -3.066  +1.406  -9.473  +966.667
56  ( 60,  0)  30  [0100111101011000101010010111000000000110] -0.820  -4.766  +7.949  -9.922  +960.000
57  (  6,  6)  39  [0100011000011111001001111010000010000110] -0.332  -3.203  -3.457  -5.098  +946.667
58  ( 38,  0)  33  [0100111101011101001011011011000000000110] -0.820  -3.066  +1.406  -9.922  +933.333
59  (  8,  1)   8  [0100111101011101001011011011000001100110] -0.820  -3.066  +1.406  -8.672  +886.667
60  ( 53, 71)  19  [0100111101011000101011010011000000100100] -0.820  -4.766  +2.324  -8.906  +873.333
61  ( 74, 23)  14  [0100111101011101001011011011000001100110] -0.820  -3.066  +1.406  -8.672  +866.667
62  ( 45, 20)  15  [0100111000011000001011011011000001010110] -0.938  -4.941  +1.406  -8.047  +853.333
63  ( 80,  1)  36  [0100111101011101001011010111000010010110] -0.820  -3.066  +2.031  -5.547  +833.333
64  ( 21,  8)  18  [1110111101011101001011011011000000100110] +4.180  -3.066  +1.406  -8.848  +833.333
65  ( 15, 25)   9  [0100111101011101001011010111000010010110] -0.820  -3.066  +2.031  -5.547  +826.667
66  ( 71, 53)  19  [0100111101011101001010010111000000000110] -0.820  -3.066  +7.949  -9.922  +826.667
67  (  1,  8)   8  [0100111101011101001011011011000000100110] -0.820  -3.066  +1.406  -8.848  +813.333
68  ( 41, 70)   7  [0100111101011101001000010111000000100100] -0.820  -3.066  -7.969  -8.906  +800.000
69  (  0, 25)  17  [0100111101011101001011010111000010010110] -0.820  -3.066  +2.031  -5.547  +786.667
70  ( 23, 74)  14  [0100111101011101001011010111000010010010] -0.820  -3.066  +2.031  -5.566  +766.667
71  (  1, 80)  36  [0100111101011101001011011011000001100010] -0.820  -3.066  +1.406  -8.691  +753.333
72  ( 56, 12)  21  [0100111101001101001011011011000000010110] -0.820  -6.953  +1.406  -9.473  +753.333
73  ( 12,  1)  25  [0100111101011101001011011011000001100110] -0.820  -3.066  +1.406  -8.672  +726.667
74  ( 31, 62)  16  [0100011000011100001010010111000010010010] -0.332  -2.578  +7.949  -5.566  +706.667
75  ( 92, 19)   0  [0100111101011101001011011011000000100110] -0.820  -3.066  +1.406  -8.848  +673.333
76  ( 78,  0)   0  [0100111101011101001011011011000000000110] -0.820  -3.066  +1.406  -9.922  +640.000
77  ( 33, 64)  22  [0100111101011101000101110111100010100111] -0.820  -3.105  -2.910  -6.152  +633.333
78  (  7, 51)  16  [0100011000011111001011011011000001010110] -0.332  -3.203  +1.406  -8.047  +633.333
79  ( 88, 69)  12  [0100111011001101001011010111000010010110] -0.898  -6.953  +2.031  -5.547  +586.667
80  (  6, 12)  13  [0100011000011101001011011011000000010110] -0.332  -3.066  +1.406  -9.473  +580.000
81  ( 28, 15)  27  [0100111101011101001011011011000010010010] -0.820  -3.066  +1.406  -5.566  +506.667
82  ( 51,  7)  16  [0100111101011101001001111010000000100110] -0.820  -3.066  -3.457  -8.848  +473.333
83  (  5,  5)  39  [0100111101011101001011011011000000010111] -0.820  -3.066  +1.406  -9.492  +466.667
84  ( 48, 68)  21  [0100011000011101001011011011000001010110] -0.332  -3.066  +1.406  -8.047  +460.000
85  ( 13,  0)  12  [0100111101011101001011011011000000000110] -0.820  -3.066  +1.406  -9.922  +453.333
86  ( 60, 13)  31  [0100111101011000101010010111000001000110] -0.820  -4.766  +7.949  -7.598  +406.667
87  ( 69, 88)  12  [0100111101011000000001010111100010100111] -0.820  -5.000  -2.109  -6.152  +313.333
88  (  0, 17)  23  [0100111101011101001011011011000000100110] -0.820  -3.066  +1.406  -8.848  +273.333
89  ( 25, 15)   9  [0100111101011101101010010111000010010010] -0.820  -2.891  +7.949  -5.566  +273.333
90  ( 10,  5)  37  [0100111101011100000100010111000000010111] -0.820  -2.539  -7.969  -9.492  +266.667
91  (  2, 29)  13  [0100111101011100000100010111000000010110] -0.820  -2.539  -7.969  -9.473  +240.000
92  (  0, 78)   0  [0100011000011000101010010111000010010010] -0.332  -4.766  +7.949  -5.566  +240.000
93  (  8,  8)  39  [0100111101011101001011011011000000100110] -0.820  -3.066  +1.406  -8.848  +213.333
94  (  1, 16)  18  [0100111101011101001011011011000000100110] -0.820  -3.066  +1.406  -8.848  +213.333
95  (  1, 26)  36  [0100111101011101001011011011000001100110] -0.820  -3.066  +1.406  -8.672  +200.000
96  ( 15, 28)  27  [0100111101011101101010010111000000100110] -0.820  -2.891  +7.949  -8.848  +193.333
97  (  7, 40)   3  [0100111101011101001011011011000001100110] -0.820  -3.066  +1.406  -8.672  +146.667
98  ( 41, 51)  23  [0100111101011000101010010111100010100111] -0.820  -4.766  +7.891  -6.152  +120.000
99  ( 20, 45)  15  [0100111101011101101010010111000010010010] -0.820  -2.891  +7.949  -5.566  +53.333
total mutate 0
 10, 4606.666667, 1229.933333, 53.333333, -0.820312, -3.066406, 1.406250, -8.671875, [0100111101011101001011011011000001100110]

この結果から

A = -0.820312  （消去可能ライン数への係数）
B = -3.066406  （次のテトリミノの最大高さへの係数）
C = +1.406250  （ホール数への係数）
D = -8.671875  （封鎖数への係数）

とすれば強いAIになることがわかった。これはなかなか意外な結果である。普通に考えればラインを消すことに正の評価を行い、ホールはむしろ減らす方向に、つまり負の評価を行うべきであると思われるが、今回の実験結果が示すことは必ずしもそのような結果になっていない。

#6. 展望

今回は遺伝的アルゴリズムを使用して単純化されたルールのテトリスのAIを強くしてみる試みであった。今後はホールド機能や遊び時間、未来3つ程度のテトリミノの情報などを考慮した高度なAIの開発が望まれる。また、今回の結果だけにしても、このAIがどのようにテトリスをプレイするのか可視化するのも面白いと思われる。

Bai Li, Coding a Tetris AI using a Genetic Algorithm, URL: http://luckytoilet.wordpress.com/2011/05/27/coding-a-tetris-ai-using-a-genetic-algorithm/ ↩
伊庭斉志, Cによる探索プログラミング, オーム社 ↩