NP-полнота игры Тетрис — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Формальные правила)
(Добавлены игровые действия.)
Строка 9: Строка 9:
 
# ''ориентация'' — поворот на 0°, 90°, 180° или 270° по часовой стрелке относительно ''базовой ориентации'' фигуры (на илл. 1).
 
# ''ориентация'' — поворот на 0°, 90°, 180° или 270° по часовой стрелке относительно ''базовой ориентации'' фигуры (на илл. 1).
 
# ''позиция'' центра фигуры на поле, выбираемая из  <tex>\{1,\dots,m\} \times \{1,\dots,n\}</tex>. Позицией SQ считается местоположение ее левой верхней клетки, так как ее центр лежит на границе четырех клеток, а не внутри одной.
 
# ''позиция'' центра фигуры на поле, выбираемая из  <tex>\{1,\dots,m\} \times \{1,\dots,n\}</tex>. Позицией SQ считается местоположение ее левой верхней клетки, так как ее центр лежит на границе четырех клеток, а не внутри одной.
# значение ''зафиксирована'' или ''не зафиксирована'', определяющее, может ли фигура продолжать двигаться.  
+
# значение ''зафиксирована'' (англ. ''fixed'') или ''не зафиксирована'' (англ. ''unfixed''), определяющее, может ли фигура продолжать двигаться.  
 
В ''исходном'' состоянии фигуры она имеет базовую ориентацию, ее позиция такова, что верхний ряд ее клеток содержится в ряду <math>m</math>, а центр в столбце <math>\lfloor n/2 \rfloor</math>, и она не зафиксирована.
 
В ''исходном'' состоянии фигуры она имеет базовую ориентацию, ее позиция такова, что верхний ряд ее клеток содержится в ряду <math>m</math>, а центр в столбце <math>\lfloor n/2 \rfloor</math>, и она не зафиксирована.
  
Строка 19: Строка 19:
  
 
: '''Игровые действия'''.
 
: '''Игровые действия'''.
//stub//
+
Для фигуры <math>P=\langle t,o,\langle i,j \rangle , fixed \rangle.</math> допустимых действий нет. Для фигуры <math>P=\langle t,o,\langle i,j \rangle , unfixed \rangle.</math> на данном игровом поле <math>B</math> допустимы следующие действия:
 +
# ''Поворот по часовой стрелке''. Новым состоянием фигуры будет <math>R(P,90^{\circ},B)</math>.
 +
# ''Поворот против часовой стрелки''. Новым состоянием фигуры будет <math>R(P,-90^{\circ},B)</math>.
 +
# ''Сдвиг влево''. Если клетки слева от фигуры свободны в <math>B</math>, фигура <math>P</math> может быть сдвинута влево на один столбец. Новым состоянием фигуры будет <math>\langle t,o,\langle i,j - 1 \rangle , unfixed \rangle.</math>
 +
# ''Сдвиг вправо''. Аналогично сдвигу влево; новым состоянием будет <math>\langle t,o,\langle i,j + 1 \rangle , unfixed \rangle.</math>
 +
# ''Снижение'' на один ряд, если все клетки под фигурой свободны в <math>B</math>. Новое состояние — <math>\langle t,o,\langle i - 1,j \rangle , unfixed \rangle.</math>
 +
# ''Фиксация'', если хотя бы одна клетка под фигурой занята в <math>B</math>. Новое состояние — <math>\langle t,o,\langle i,j \rangle , fixed \rangle.</math>
 +
 
 +
''Траекторией'' <math>\sigma</math> фигуры <math>P</math> называется последовательность допустимых действий, начинающихся в исходном состоянии и заканчивающихся действием-фиксацией. Результатом траектории фигуры <math>P</math> на игровом поле <math>B</math> является новое поле <math>B'</math>, определяемое следующим образом:
 +
# Новое поле <math>B'</math> — это поле <math>B</math> с заполненными клетками фигуры <math>P</math>.
 +
# Если фигура зафиксирована таким образом, что для некоторого горизонтального ряда <math>r</math> каждая клетка <math>r</math> в поле <math>B'</math> заполнена, то ряд <math>r</math> ''освобождается''. Для всех <math>r' \geqslant r</math> следует заменить ряд <math>r'</math> в <math>B'</math> рядом <math>r'+1</math> в <math>B'</math>. Ряд <math>m</math> в <math>B'</math> становится пустым. Фиксация одной фигуры может привести к освобождению более чем одного ряда.
 +
# Если исходное состояние следующей фигуры в <math>B'</math> заблокировано, игра заканчивается (игрок ''проигрывает'').
 +
 
 +
Для ''игры'' <math>\langle B_0,P_1,\dots,P_p \rangle</math>, ''последовательностью траекторий'' <math>\Sigma</math> является такая последовательность <math> B_0,\sigma_1,B_1,\dots,\sigma_p,B_p</math>, что для любого <math>i</math> траектория фигуры <math>P_i</math> на поле <math>B_{i-1}</math> приводит к полю <math>B_i</math>. Однако, если существует действие <math>\sigma_q</math> при некотором <math>q \leqslant p</math>, приводящее к проигрышу, то последовательность <math>\Sigma</math> завершается на <math>B_q</math>, а не на <math>B_p</math>.

Версия 00:11, 16 марта 2016

Тетрис — популярная игра, созданная в середине 1980-х математиком Алексеем Пажитновым.

Формальные правила

Игровое поле — расчерченный на клетки прямоугольник размером [math]m[/math] горизонтальных рядов (строк) на [math]n[/math] вертикальных (столбцов). Примем следующую индексацию: снизу вверх и слева направо. [math]\langle i, j \rangle[/math]-я клетка либо свободна, либо занята. В допустимом состоянии поля ни один горизонтальный ряд не заполнен целиком и нет ни одной полностью пустой строки, которая бы лежала ниже занятой клетки. При оценке допустимости некоторых действий будем считать, что все клетки вне игрового поля всегда заняты и тем самым ограничивают поле.

//картинки//

Игровые фигуры — семь различных фигур, получаемых соединением четырех единичных клеток по каким-либо из сторон. Каждая фигура имеет центр (на илл. 2). Состояние фигуры [math]P[/math] — кортеж из четырех элементов, а именно:
  1. тип фигуры — SQ, LG, RG, LS, RS, I или T.
  2. ориентация — поворот на 0°, 90°, 180° или 270° по часовой стрелке относительно базовой ориентации фигуры (на илл. 1).
  3. позиция центра фигуры на поле, выбираемая из [math]\{1,\dots,m\} \times \{1,\dots,n\}[/math]. Позицией SQ считается местоположение ее левой верхней клетки, так как ее центр лежит на границе четырех клеток, а не внутри одной.
  4. значение зафиксирована (англ. fixed) или не зафиксирована (англ. unfixed), определяющее, может ли фигура продолжать двигаться.

В исходном состоянии фигуры она имеет базовую ориентацию, ее позиция такова, что верхний ряд ее клеток содержится в ряду [math]m[/math], а центр в столбце [math]\lfloor n/2 \rfloor[/math], и она не зафиксирована.

Поворот фигуры. Модель поворота — функция [math]R : \langle P,\theta,B \rangle \mapsto P'[/math], где [math]P[/math] и [math]P'[/math] — состояния фигуры, [math]\theta \in \{-90^{\circ},90^{\circ}\}[/math] — угол поворота, а [math]B[/math] — игровое поле. На [math]R[/math] налагаются следующие условия:
  1. Если [math]P = \langle t,o,\langle i,j \rangle,f\rangle[/math] и поворот допустим, то [math]P' = \langle t,(o + \theta) \mod 360^{\circ},\langle i',j' \rangle,f\rangle[/math] для некоторых [math]i'[/math] и [math]j'[/math]. Если поворот недопустим, то [math]P' = P[/math].
  2. При определении допустимости поворота, [math]R[/math] рассматривает окрестность констатного размера у фигуры [math]P[/math] — то есть, только клетки на заданном расстоянии от позиции [math]P[/math] влияют на [math]R[/math], а положение фигуры на игровом поле значения не имеет.
  3. Если все клетки в окрестности [math]P[/math] свободны, то поворот допустим.
  4. Если поворот допустим, то [math]P'[/math] не занимает ни одной клетки, уже занятой в [math]B[/math].
Игровые действия.

Для фигуры [math]P=\langle t,o,\langle i,j \rangle , fixed \rangle.[/math] допустимых действий нет. Для фигуры [math]P=\langle t,o,\langle i,j \rangle , unfixed \rangle.[/math] на данном игровом поле [math]B[/math] допустимы следующие действия:

  1. Поворот по часовой стрелке. Новым состоянием фигуры будет [math]R(P,90^{\circ},B)[/math].
  2. Поворот против часовой стрелки. Новым состоянием фигуры будет [math]R(P,-90^{\circ},B)[/math].
  3. Сдвиг влево. Если клетки слева от фигуры свободны в [math]B[/math], фигура [math]P[/math] может быть сдвинута влево на один столбец. Новым состоянием фигуры будет [math]\langle t,o,\langle i,j - 1 \rangle , unfixed \rangle.[/math]
  4. Сдвиг вправо. Аналогично сдвигу влево; новым состоянием будет [math]\langle t,o,\langle i,j + 1 \rangle , unfixed \rangle.[/math]
  5. Снижение на один ряд, если все клетки под фигурой свободны в [math]B[/math]. Новое состояние — [math]\langle t,o,\langle i - 1,j \rangle , unfixed \rangle.[/math]
  6. Фиксация, если хотя бы одна клетка под фигурой занята в [math]B[/math]. Новое состояние — [math]\langle t,o,\langle i,j \rangle , fixed \rangle.[/math]

Траекторией [math]\sigma[/math] фигуры [math]P[/math] называется последовательность допустимых действий, начинающихся в исходном состоянии и заканчивающихся действием-фиксацией. Результатом траектории фигуры [math]P[/math] на игровом поле [math]B[/math] является новое поле [math]B'[/math], определяемое следующим образом:

  1. Новое поле [math]B'[/math] — это поле [math]B[/math] с заполненными клетками фигуры [math]P[/math].
  2. Если фигура зафиксирована таким образом, что для некоторого горизонтального ряда [math]r[/math] каждая клетка [math]r[/math] в поле [math]B'[/math] заполнена, то ряд [math]r[/math] освобождается. Для всех [math]r' \geqslant r[/math] следует заменить ряд [math]r'[/math] в [math]B'[/math] рядом [math]r'+1[/math] в [math]B'[/math]. Ряд [math]m[/math] в [math]B'[/math] становится пустым. Фиксация одной фигуры может привести к освобождению более чем одного ряда.
  3. Если исходное состояние следующей фигуры в [math]B'[/math] заблокировано, игра заканчивается (игрок проигрывает).

Для игры [math]\langle B_0,P_1,\dots,P_p \rangle[/math], последовательностью траекторий [math]\Sigma[/math] является такая последовательность [math] B_0,\sigma_1,B_1,\dots,\sigma_p,B_p[/math], что для любого [math]i[/math] траектория фигуры [math]P_i[/math] на поле [math]B_{i-1}[/math] приводит к полю [math]B_i[/math]. Однако, если существует действие [math]\sigma_q[/math] при некотором [math]q \leqslant p[/math], приводящее к проигрышу, то последовательность [math]\Sigma[/math] завершается на [math]B_q[/math], а не на [math]B_p[/math].