4次元空間でプレイするテトリスとそれを自動プレイするAIの話
前に作ったゲームの解説的なお話です．
↓過去の記事
↓プレイ動画
はじめに
丁度2か月ほど前に，時間が空いていて，更にサークルで成果物発表会があったので，それに合わせてゲームを1つ作りました．
それが上の頭おかしい「4次元テトリス Tetris Dim.4」です．
DLはこちら↓
https://bitbucket.org/WGGSH/tetrisdim4/downloads/TetrisDim4_Ver0.60.zip
この記事は，4次元テトリスのルール解説と，AIの実装方法についての解説記事です．
4次元テトリスのルール
一般的なテトリスは「10×20」のフィールドで，「7」種類のブロックを回転させて1列全て埋めてラインを消すことを目的とします．
4次元テトリスでは，上記ルールをそのまま次数を2つ上げただけです．
細かい数字まで言うと，
「5×5×5×10」のフィールドで，「7」種類のブロックを「6」つの回転軸で回転させて「5×5×5」の空間を埋めて消すことを目的とします．
次数と，移動方向・回転軸・ブロックの種類の対応表は以下の通りです．
『なんで3次元の方が4次元よりブロックの種類が多いんだ?』
って疑問が出ると思います．
各次数のブロックを描いてみました
2次元
3次元
4次元(少し強引な可視化)
2→3次元
まず，2次元から3次元でブロックが1つ増える点についてみて見ます
上の画像に描かれている3つのブロックは2次元空間では表現できない為，3つ増えます
ところが下の画像ではそれぞれ2次元で2種類だったブロックが3次元になることで1つに統一できます．これは回転軸が増えたためです．
3個の増加と，2この減少，結果的に1つ増えて8種類になります．
3→4次元
では，3次元から4次元ではどうなるのでしょうか．
3次元から4次元になっても，新しい形のブロックパターンが増えることはありません．何故なら，4次元でしか表現できないパターンを作るには，ある1マスから別々の4つの軸の方向へ隣接するブロックが存在する必要があります．2次元から3次元にした時は，これが存在しましたが，3次元から4次元では存在しません．そもそも1つのパターンを構成するブロックの数が4なので，4方向に伸ばすためには構成するブロックが最低5つ必要になります．
対して，3次元で存在していた2つのパターンが4次元で増えた回転によって，同一視できるようになります．
結果，3次元と比べて，1つパターンが減り，合計7種類になります．
回転
上の表では4次元の場合，回転軸が6つと書いていました．
任意の次元数 n次元空間において，2つの軸からなる平面で回転する回転軸は(n-2)!個です．
有名なアレ
数学の教科書にも出てくるアレです(2次元版)
4次元では↓の様になります．この中で，sin,cosを使用する軸を2つ選ぶのですが，その組み合わせが6通り存在します．
という訳で，ここまでで一応4次元の動きについて軽く説明が終わりました(疲れた
こっからAI
さて，ここからAIの実装についてです．
といっても，適当にネットから参考になりそうな記事を拾ってきて4次元テトリスに対応させた程度の事しかしていないのですが...
↓参考にした記事たち
GitHub - takuma7/tetris-ai-generator: This program is to seek strong tetris AI with the power of GA
AIの基本的な考え方
今回作成したAIは「評価関数」を用いています
計算手順は以下の感じです
- ブロックを置くことができる場所を全て探す
- 1で見つけた場所全てに対して，ブロックを置いた後の状態を複数の観点から評価する
- 最も評価の合計点が高い場所が，「置くべき場所」
まぁ凄く単純です．単純ですが4次元にしたことでいくつか問題が浮上しました．
1.ブロックを置くことができる場所を全て探す
コンピュータの計算速度を利用して，全てのパターンをシミュレートします．
そのためには何パターン置くことができるか調べなくてはいけません．
ブロックの置く場所は「移動量」「回転角度」で決定します．
移動量は非常にシンプルです．フィールドサイズが「5×5×5×10」で，10は落下にあたるので，それ以外の「5×5×5」=125通りが上限です．当然，ブロックの形によってこれより少なくなることもあります．
ところが回転は，回転軸が6つと書いたのですが，回転順序が関わってきます．
例として，6つの回転軸をA~Fとすると，Aで90°→Bで90°回した形と，Bで90°→Aで90°回した形は同じになるとは限りません．これは行列の積が順番を変えると結果が変わるのと同じですね．
全ての回転後の姿勢を求めるには，(書く回転軸の角度パターン)^(回転軸の個数)×(回転順序の組み合わせ総数)で求められます．
つまり， (4の6乗)×(6の階乗)=2,949,120通りです(絶望
これに移動量の上限125を掛けるので......1手ごとにシミュレートすべきパターン総数は
368,640,000 通り(最大)
になります。無理です．計算しきれませんでした()
という訳で，大幅な妥協をすることにしました．
移動を妥協したら特定のマスにブロック置けなくなるので，こっちはスルーで，回転パターンを大幅に制限しました．
「6つの回転軸を好きな順番で回す」→「ある決められた3つの回転軸を指定した順番で回す」へと変更しました．
4次元のパズルが活かせていないかもしれませんが...やむを得ずそうしました．
これで2,949,120通り存在した回転パターンは64通りまで減りました(少なっ
移動と合わせても合計で，最大8,000パターンです
2.1で見つけた場所全てに対して，ブロックを置いた後の状態を複数の観点から評価する
ここが「評価」にあたる部分です．1で8000種類置くべき場所を見つけたので，それら全てを以下の判断基準から評価していきます．
- 最もブロックで埋まっている段のブロックの数
- 消した段の数
- Z(落下)座標が上から4マス以内に存在するブロックの数
- ホールの数
- 落下位置のZ座標
- 最大高度
まあこのぐらいにしました．これらに対して，「重み」をつけることで，AIの性格を表現することができるようになります．
1つずつ説明していきます．
1.最もブロックで埋まっている段のブロックの数
4次元テトリスでは1段消すのに125個のブロックが必要です(2次元なら10個)
これを効率よく積んでいくために，最もブロックで埋まっている段を調べて，その数を評価値にします．ブロックを平らに積んで，消すスピードが向上すると考えられます．
2.消した段の数
言うまでもないですね．ブロックを消すことがこのゲームのメインなので．
ここを，4段消せるとき以外は評価を低めに設定したりすると，4段消し(テトリス)を決めやすいAIをつくったりすることができます．
3.Z(落下)座標が上かrあ4マス以内に存在するブロックの数
これは少しわかりづらいですが，ブロックを高く積みすぎると，移動可能な領域が減り，難易度が大幅に向上します．そのため，ある程度高く積むことに対して，負の重みをつけることで可能な限り回避します．
4.ホールの数
ブロックの下に空いているマスがあると，その段を消すためには上の段を消さなければいけません．2次元なら10個のブロックで消すことができますが，この4次元テトリスでは125個必要で，非常に負担がかかります．正直言うと一度ホールをつくったら，それを修復するのはほぼ不可能です．そこで，ホールを作ることに対して負の重みをつけて，回避します．
5.落下位置のZ座標
1と3があるのでこれは無くてもよかったかもしれません．より平らに積んでもらうために，低いところに置くと評価が高くなるようにしています．
6.最大高度
同じく，不要だったかもしれません．これも平らに積むための評価基準です．
これらの評価を用いて，「最も評価の高い移動場所」を決定します．
3.最も評価の合計点が高い場所が，「置くべき場所」
あとは簡単です．2で決めた場所に対してブロックを移動させるだけです．
おわり
以上，4次元テトリスのルールとAIの作成方法についてのメモ兼説明でした．
良かったらプレイしてみてくださいね
DLリンク↓
https://bitbucket.org/WGGSH/tetrisdim4/downloads/TetrisDim4_Ver0.60.zip
