-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathresults.tex
111 lines (82 loc) · 6.73 KB
/
results.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
\chapter{Literature Review}
% TODO:
The problem and its variations have been explained, and now the most relevant results from each study to date will be presented. Our initial goal is to understand what makes Tetris complex, so each result will be analyzed in relation to this idea, along with the most notable aspects of the findings.
\section{Tetris is hard, even to approximate}
The first results regarding Tetris complexity were presented in \cite{TIH}. These findings focus on the decision problems associated with the game. For instance, the solution to the \texttheo{height-filled} problem determines the minimum value of $h$ for which the condition $\texttheo{h-height-filled}$ holds. Most importantly, this work establishes the theoretical framework and provides the first formalization of Tetris. The main result is the following:
\begin{theorem}
\textsc{Tetris} is \nph\ to optimize (or approximate) with the objectives, \texttheo{cleared-rows}, \texttheo{tetrises} \texttheo{height-filled} and \texttheo{placed-pieces}. It remains \nph\ even if:
\begin{itemize}
\item The player is restricted to two rotation/translation moves before each piece drops in height.
\item Pieces are restricted to $\{\JJ, \ZZ, \II, \OO\}$ or $\{\LL, \SS, \II, \OO\}$ plus at least one other piece.
\item Losses are not triggered until after filled rows are cleared.
\item Rotations follow any reasonable rotation model.
\end{itemize}
\end{theorem}
The main proof involves a reduction from 3-\textsc{Partition}, which serves as the foundation for many subsequent proofs. Later, a reduction from 3-\textsc{Partition} is explained, following the same approach.
Some variations were introduced in this initial work and appear to be as complex as the main problem. While the proposed variants help in understanding the game's variations, they do not substantially alter the core game mechanics.
\section{Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, ...}
In \cite{TT}, piece variations are explored, specifically considering \textit{k\textsc{-tris}} for $k \geq 1$. Almost all games are solved, as summarized in Table~\ref{tab:tt}, which presents the results in detail. By examining the table, we can observe that the problem becomes NP-hard when $k=2$ (or 3). We will not focus on larger pieces as our objective is to determine what makes Tetris complex, and the table shows that for $k\geq4$ the problems are all \npc. Completing the table would provide valuable information to our purpose, specifically completing row for $k=2$.
\begin{table}[!ht]
\centering
\begin{tabular}{|c || c | c || c | c ||}
\hline
& \multicolumn{2}{| c ||}{\survival} & \multicolumn{2}{| c |}{\clearing} \\
\hline
& with rotation & no rotation & with rotation & no rotation \\
\hline
$k = 1$ & \pp & \pp & \pp & \pp \\
\hline
$k = 2$ & Open & Open & Open & \npc \\
\hline
$k = 3$ & Open & \npc & \npc & \npc\\
\hline
$k = 4$ & \npc & \npc & \npc & \npc\\
\hline
$k > 5$ & \npc & \npc & \npc & \npc\\
\hline
\end{tabular}
\caption{\cite{TT} results with rotation}
\end{table}
\label{tab:tt}
\section{Tetris is NP-hard even with O(1) rows or columns}
In \cite{TCB}, variations of the \textsc{Tetris} game are explored, particularly focusing on game instances where either the height or the width of the board is fixed. Intuitively, fixing the board dimensions should make the problem computationally easier, but the results summarized in Table~\ref{tab:tcb} reveal some interesting findings.
The work reinforces the idea that using a large set of pieces significantly complicates the problem. This is especially evident in the case where the board consists of a single row, which is strongly \nph\ when using $\mathcal{O}(m)$-minos. In the other hand, the problem is in \pp\ when boards with a single column are considered, therefore columns do no play the same role as columns.
Furthermore, the initial configuration of the board, as shown in the table, also influences the complexity of the problem.
\begin{table}[!ht]
\centering
\begin{tabular}{|c | c | c | c | c |}
\hline
Rows & Columns & Empty & Piece Sizes & Complexity \\
\hline
\hline
$1 $ & $O(n) $ & no & $O(n) $ & strongly \nph \\ \hline
$1 $ & $O(n) $ & yes & $O(n) $ & linear \\ \hline
$1 $ & $O(n) $ & no & $k $ & linear \\ \hline
$2 $ & $O(n) $ & yes & $O(n) $ & strongly \nph \\ \hline
$3 $ & $O(n) $ & no & $4 $ & Open \\ \hline
$4 $ & $O(n) $ & no & $4 $ & strongly \nph \\ \hline
$O(n)$ & $1 $ & no & $O(n) $ & linear \\ \hline
$O(n)$ & $2 $ & no & $O(n) $ & polynomial \\ \hline
$O(n)$ & $3 $ & yes & $O(n) $ & strongly \nph \\ \hline
$O(n)$ & $3 - 7$ & no & $4 $ & Open \\ \hline
$O(n)$ & $8+ $ & no & $4 $ & strongly \nph \\ \hline
$O(n)$ & $8 $ & yes & $\leq 65 $ & strongly \nph \\
\hline
\end{tabular}
\caption{\cite{TCB} results table}
\label{tab:tcb}
\end{table}
\section{Complexity of a Tetris variant}
Oscar Temprano explores Tetris with the \textsc{20g} variant, where pieces can be freely moved and rotated in the first row until dropped, after which they become fixed. This paper\cite{CTV}, proves that clearing the board in this variant is \npc by reducing the 3-\textsc{Partition} problem to a specific board-clearing instance, resolving the open problem.
\section{Tetris with Few Piece Types}
In \cite{TWFP}, the authors investigate the computational complexity of Tetris, showing that even when restricted to any pair of standard Tetris pieces, the associated decision problem remains \nph.
\vspace{10px}
\textbf{Main Result:} For every 2-sized subset of \( \{\ALL\} \), Tetris \survival\ and \clearing\ are \nph\ under SRS.
\vspace{10px}
They leave open the problem of determining the complexity when the game is limited to a single piece. How does the shape of a concrete piece influence the complexity of the game?
The results on this work rely on the Super Rotation System(SRS), the game standard for rotating pieces, an important contribution of this work. SRS enables more complex piece rotations, allowing the player to move pieces through configurations that were impossible with simpler rotating models.
\vspace{10px}
Additionally, the \texttheo{20-G} and \texttheo{Hard-Drop} variations are introduced, alongside the corresponding results.
\vspace{10px}
\textbf{Result:} Tetris \texttheo{20-G} and Tetris \texttheo{Hard-Drop} are \npc\ even if the piece set is restricted to \( \{\II, \OO\} \).
\textbf{Result:} If we allow the piece \( \{\TT\} \), the above result can be extended to \nph.