読者です 読者をやめる 読者になる 読者になる

4次元空間でプレイするテトリスとそれを自動プレイするAIの話

前に作ったゲームの解説的なお話です.

 

↓過去の記事

wgg.hatenablog.jp

↓プレイ動画

www.youtube.com

はじめに

丁度2か月ほど前に,時間が空いていて,更にサークルで成果物発表会があったので,それに合わせてゲームを1つ作りました.

それが上の頭おかしい「4次元テトリス Tetris Dim.4」です.

DLはこちら↓

https://bitbucket.org/WGGSH/tetrisdim4/downloads/TetrisDim4_Ver0.60.zip

この記事は,4次元テトリスのルール解説と,AIの実装方法についての解説記事です.

 

f:id:wgg00sh:20160514185110p:plain

 

4次元テトリスのルール

一般的なテトリスは「10×20」のフィールドで,「7」種類のブロックを回転させて1列全て埋めてラインを消すことを目的とします.

 

4次元テトリスでは,上記ルールをそのまま次数を2つ上げただけです.

細かい数字まで言うと,

「5×5×5×10」のフィールドで,「7」種類のブロックを「6」つの回転軸で回転させて「5×5×5」の空間を埋めて消すことを目的とします.

次数と,移動方向・回転軸・ブロックの種類の対応表は以下の通りです.

 

f:id:wgg00sh:20160713224515p:plain

 

『なんで3次元の方が4次元よりブロックの種類が多いんだ?』

って疑問が出ると思います.

各次数のブロックを描いてみました

 

2次元

f:id:wgg00sh:20160713224809p:plain

3次元
f:id:wgg00sh:20160713224825p:plain
4次元(少し強引な可視化)

f:id:wgg00sh:20160713224852p:plain

 

 

2→3次元

まず,2次元から3次元でブロックが1つ増える点についてみて見ます

f:id:wgg00sh:20160713225120p:plain

f:id:wgg00sh:20160713225113p:plain

上の画像に描かれている3つのブロックは2次元空間では表現できない為,3つ増えます

ところが下の画像ではそれぞれ2次元で2種類だったブロックが3次元になることで1つに統一できます.これは回転軸が増えたためです.

 

3個の増加と,2この減少,結果的に1つ増えて8種類になります.

 

3→4次元

では,3次元から4次元ではどうなるのでしょうか.

f:id:wgg00sh:20160713225608p:plain

 

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)!個です.

 

有名なアレ

f:id:wgg00sh:20160713230612p:plain

数学の教科書にも出てくるアレです(2次元版)

 

4次元では↓の様になります.この中で,sin,cosを使用する軸を2つ選ぶのですが,その組み合わせが6通り存在します.

f:id:wgg00sh:20160713230647p:plain

 

という訳で,ここまでで一応4次元の動きについて軽く説明が終わりました(疲れた

 

 

 こっからAI

さて,ここからAIの実装についてです.

といっても,適当にネットから参考になりそうな記事を拾ってきて4次元テトリスに対応させた程度の事しかしていないのですが...

↓参考にした記事たち

nanamb.blog25.fc2.com

コンピュータにテトリスをプレイさせる AIテトリス

GitHub - takuma7/tetris-ai-generator: This program is to seek strong tetris AI with the power of GA

Future AI Tetris Page

 

AIの基本的な考え方

今回作成したAIは「評価関数」を用いています

計算手順は以下の感じです

  1. ブロックを置くことができる場所を全て探す
  2. 1で見つけた場所全てに対して,ブロックを置いた後の状態を複数の観点から評価する
  3. 最も評価の合計点が高い場所が,「置くべき場所」

 

まぁ凄く単純です.単純ですが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種類置くべき場所を見つけたので,それら全てを以下の判断基準から評価していきます.

 

  1. 最もブロックで埋まっている段のブロックの数
  2. 消した段の数
  3. Z(落下)座標が上から4マス以内に存在するブロックの数
  4. ホールの数
  5. 落下位置のZ座標
  6. 最大高度

 

まあこのぐらいにしました.これらに対して,「重み」をつけることで,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