テトリスに対するオンラインアルゴリズムの開発

テトリスに対する
オンラインアルゴリズム
豊橋技術科学大学
情報工学専攻2年
猿渡慎也
テトリスとは
 世界的に有名なパズルゲーム
 最初に幅Wの盤面が与えられる
 盤面に現れるテトロミノを操作し
うまく横1行を揃えると行が消える
 ゲームオーバーになるまでにどれ
だけ行を消せたかを競う
テトリスの難しい点
将来どのテトロミノが
出てくるか分からない
この場合、
この3行を消せた
テトリスの難しい点
未来のテトロミノを知った
上で最適な置き方が出来
れば．．．
実は5行も消せていた
テトリスの定式化
テトリスは将来どんなテトロミノが与えられるか分
からない問題、すなわちオンライン問題である
 入力:テトロミノ列σ
 出力:σに対し消せる行数
 目的:出力の最大化
研究目的
どんなテトロミノ列に対しても、なるべく
多くの行を消せるオンラインアルゴリズ
ムの開発(ただし盤面の高さは無制限)
 なぜ盤面の高さを無制限に？
 必ずゲームオーバーにさせるテトロミノ列を作れるアルゴ
リズムが存在 [J.Brzustowski,1992]
 本研究では、テトロミノが積み上がってしまうのは諦
め、なるべく多く行を消すことを目指す
テトリスに対する競合比の定義
OPT  
競合比  lim sup
ALG 
| |

: テトロミノ列
ALG  : オンラインアルゴリズ
ムが消す行数
OPT   : 最適オフラインアルゴリズムが消す行数
競合比の定義について
一般的に競合比としては
OPTσ 
max
σ
ALGσ 
を用いることが多いが、なぜ lim sup？
例：短いテトロミノ列が与えられたとき
 σ=(
)の場合
ALG(σ )  1
OPT ( ) |  | なので、
OPT ( )
max
5

ALG( )
OPT (σ )
lim sup
 2.5(解析は後述 )
ALG(σ )
|σ |
ある ALGによる配置
lim sup と max
OPT  
ALG 
max(|σ|が小さいとき、特異な結果が現れる場合がある)
lim sup
このような漸近的競合比は
ビンパッキング問題にもよく用いられている
σ
 そのようなmaxは、アルゴリズムの性能を表すのに適切か？
 普通プレイヤーはかなりの数のテトロミノを配置する。ならば
lim supによる漸近的な競合比の方が、性能評価として適切と
考えた
関連研究及び本研究の成果

必ずゲームオーバーにする
テトロミノをある2種類に制限したとき、競合比1
テトロミノ列を作れる組合せ
[J.Brzustowski,1992]
組合せ
盤面の幅
競合比
組合せ
盤面の幅
[J.Brzustowski,1992]
偶数
特に難しい
偶数
偶数
競合比
-
未解決
-
未解決
・
・
・
未解決
偶数
4-
未解決
2.5
偶数
4-
未解決
1.6
設定
 盤面の幅W=4
 テトロミノはLSとRSのみ現れる
用語
 レーン
2
 2列毎に区切った盤面
 レーンの高さ
2
6
 各レーンで一番上の
テトロミノがある行の高さ
左レーンの高さ
5
4
3
2
1
左レーン
4
3
2
1
右レーン
競合比2.5以下のアルゴリズム
アルゴリズムの動作
ステップ1. 最初の1個は図のように配置
アルゴリズムの動作
ステップ2. それ以降はLSは左レーンに、
RSは右レーンに図の向きにして配置
問題点
 ステップ1と2だけだと、同じテトロミノばかりが
現れたとき
1行も消せない
アルゴリズムの動作
ステップ3. 左右のレーンの高さ差がある閾値を
越えるとテトロミノに関係なく低い方に配置
高さ差が
閾値以上
競合比の評価
アルゴリズムにより発生する盤面
LS/ 0行消えた
LS
LS/0
S1
LS/?
RS/ 0行消えた
RS
S0
RS/2
RS
/ 2行消えた
RS
RS/0
S7
RS/?
盤面の変化を状態遷移図で表す
LS/?
レーン内にテトロミノを配置するとき
 補題
低い方のレーンの高さより下の行は、
今後変化しない。
この補題により、区別すべき盤面は
6
有限個となった
5
4
低い方の
レーンの高さ
3
2
1
変化しない
(1~3行目)
例
=
=
どちらの盤面も
右端の盤面と同じと見なせる！
状態遷移図(閾値=5のとき)
このアルゴリズムの競合比
OPT  
競合比  lim sup
ALG 
| |
 競合比の算出のために、
ALG(σ)とOPT(σ)を評価する
OPT(σ)の上界
 テトロミノはどちらも4つのブロックから成る
 また幅4の盤面では、1行は4ブロックで消える
 よって消せる行数は、高々 |σ| である。
 OPTといえどもこれは越えられないので、上界は
OPT( )  
である。
定義：閉路の効率
1周する間に消せた行数
1周する際のテトロミノ数
2
0
0
0
閉路の効率 
全ての閉路の効率の中で、
最小のものを
η とする
テトロミノ数=2
0
1
0
2
消せた行数=2
この閉路の効率=1
1
テトロミノ数=5
消せた行数=2
この閉路の効率=2/5
ALG(σ)の下界
盤面の全状態数 mに対し m  σ である
テトロミノ列 σが与えられたとき、
ALG( )      m
である。
ALG(σ)の下界
 証明
盤面の全状態数 mに対し十分長いテトロミノ列
が
与えられたとする。こ
のとき遷移する状態の列をSとする。
| S |, すなわち状態遷移の回数は |  | である。
m   より、必ず
Sには複数回現れる状態が存在する。
S
ALG(σ)の下界
 証明続き
同じ状態が現れるということは閉路が存在するという
ことである。 Sからこのような閉路を取り除き、
閉路の集合 Cと、Cを除かれて短くなった列S 'に分割する。
S
C
S'
ALG(σ)の下界
 証明続き
ALG( )  S を辿って消せる行数
 Cを辿って消せる行数 S ' を辿って消せる行数
|C |
  | ci | i
i 1
|C |
   | ci |
i 1
  | S |  | S ' |
ci  C ,
i : ciの効率 
ALG(σ)の下界
 証明続き
S 'に閉路は存在せず、同じ状態は現れない。
よって| S ' | mである。
| S | は |  | に等しいと示したので
ALG( )   | S |  | S ' |
  |  | m 
が得られる。□
競合比の上界の算出
OPT 
競合比  lim sup
ALG 
| |

1
 lim sup


| |     m 
競合比 
1

閾値による競合比の変化
 閾値5以上20以下の場合(η=2/5)
 競合比2.5以下
OPT ( )
 また閾値5のとき lim sup
 2 となる例を発見。
ALG( )
| |
よってこの場合、競合比は2以上であることも分かった
またLSとT字型の場合では、競合比1.6の
アルゴリズムを示すことができた
最後に
 まとめ
 テトリスをテトロミノ列に対して消せる行数を最大
化するオンライン最適化問題として定式化した
 テトロミノがLS,RSの2種類で盤面の幅が4のとき、
競合比2.5以下のアルゴリズムを示した
 テトロミノがLS,Tの2種類で盤面の幅が4のとき、
競合比1.6以下のアルゴリズムを示した
 今後の課題
 競合比の真の値を求める
 他のテトロミノの組合せについて調べる

Download Report