Вы проигрываете в тетрис только потому, что играете неоптимально или допускаете ошибки? Даже имея какое-то время подумать, неблагоприятную последовательность камней невозможно спасти. Решающий фактор – пять узких полос и нечетное число. Рассмотрим игровое поле с \(10\) столбцами и \(20\) строками без буфера обмена (удерживать): Каждый новый камень рисуется независимо и равномерно распределяется из семи тетромино . Каждая фигура состоит из четырех соединенных квадратов. Весь эпизод может быть известен заранее.
Тот факт, что игра почти наверняка заканчивается, не означает, что заканчивается каждая мыслимая последовательность камней. В чистую последовательность O-камней можно играть бесконечно: пять квадратов, расположенных рядом друг с другом, удаляют два ряда и очищают доску. В 7-Bag каждый случайно смешанный мешок содержит все семь фигур ровно один раз; наш случайный аргумент к этому не применим. В книге «Как проиграть в тетрисе» Хайди Бургель показывает последовательность, в которой даже идеальная игра не помогает: \(S,Z,S,Z,\ldots\) .
S и Z — зеркальные изображения, а не разные повороты одного и того же камня. Сопровождающее объяснение описывает геометрическую идею, которую мы представляем здесь как доказательство от противного. Очевидное утверждение «в какой-то момент появляются только камни Z и вместе с ними не исчезает ни один ряд» неверно. Всего пять одинаковых, вертикально расположенных S-камней обеспечивают следующее расположение на изначально пустой доске. Те же буквы обозначают один и тот же камень; Точками отмечены свободные места.:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eСредняя строка завершена и удалена. Если отразить расположение, вы получите тот же контрпример для Z-камней. Проблема не в удалении отдельных рядов, а в том, сможете ли вы контролировать все дисбалансы, возникающие на неограниченном количестве камней. Пронумеруем столбцы от \(1\) до \(10\) . Через \(b_i\) мы обозначаем общее количество всех новых ячеек, помещенных в столбец \(i\) , включая те, которые позже были удалены.
\(h_i\) подсчитывает горизонтальные камни S или Z со средним столбцом \(i\) , \(v_i\) вертикальные камни в столбцах \(i\) и \(i+1\) . Счетчики фиксируют ход игры, а не только видимый в данный момент стек. Горизонтальный камень распределяет свои ячейки в соотношении \(1,2,1\) по трем столбцам, вертикальный камень в соотношении \(2,2\) по двум столбцам. Оба зеркальных изображения имеют одинаковый баланс столбцов. Если сложить эти вклады по всем местам размещения, вы получите по каждому столбцу:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
За пределами доски мы устанавливаем все счетчики на \(0\) ; в частности \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Это соглашение о краях не позволяет весам учитывать камни, которые выходят за пределы игрового поля. В нашей модели такие размещения не разрешены. Если рассматриваемая последовательность S/Z начинается на уже заполненной доске, пусть \(a_i\) — первоначально занятые ячейки, а \(c_i\) занятые в данный момент ячейки в столбце \(i\) . После \(R\) удаленных строк:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Пока игра запущена, все \(a_i,c_i\) находятся между \(0\) и \(20\) . Поэтому применяется \(|b_i-b_j|\leq40\) . Если доска изначально пуста \(20\) . Каждая удаленная строка забирает ровно одну ячейку из каждого столбца. Именно поэтому количество удаленных строк при сравнении двух столбцов уменьшается, даже если счетчики ячеек набора продолжают расти. Вы считаете занятые ячейки вместо высоты стопки; Два размера различаются, когда дело касается отверстий. Если мы запишем этот предел обычно как \(D\) , он будет получен на левом или правом краю.:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Для пар внутренних столбцов мы добавляем две ограниченные разницы столбцов: \(b_4-b_3\) и \(b_2-b_1\) слева, \(b_7-b_8\) и \(b_9-b_{10}\) справа. После вставки баланса столбца счетчики между ними точно компенсируют друг друга. Это оставляет только неотрицательные вклады в каждой левой части, которые совместно ограничены \(2D\) . Это также дает нам верхний предел для соответствующих чисел размещения для двух внутренних пар.:
$$\begin{aligned}2v_4+h_4+h_5&=(b_4-b_3)+(b_2-b_1)\\&\leq2D,\\2v_6+h_6+h_7&=(b_7-b_8)+(b_9-b_{10})\\&\leq2D.\end{aligned}$$
Если сложить четыре неравенства, каждый горизонтальный камень будет учтен ровно один раз. Четыре типа поперечного вертикального размещения также имеют положительные коэффициенты. Горизонтальные камни занимают три колонны и поэтому не вписываются полностью ни в одну из двухколонных дорожек, рассмотренных ниже. Для вертикальных камней выделяем следы по левому столбцу. Поскольку все счетчики неотрицательны, ни один из этих вкладов не может быть отменен другим.:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Таким образом, горизонтальное размещение и вертикальное размещение с прямым левым столбцом могут происходить максимум \(120\) раз на пустой доске или \(240\) раз на любой предварительно заполненной доске. Это верхняя граница, а не утверждение, что она действительно может быть достигнута. В любом случае эти уклончивые ходы нельзя использовать бесконечно часто. Теперь предположим, что вы можете воспроизводить попеременную последовательность бесконечно.
После последнего из конечного числа уклончивых ходов будут возможны только вертикальные размещения на пяти фиксированных полосах: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Идентичные формы ступенчато вписываются друг в друга: нижняя часть соответствует верхней части предыдущего камня. Изменение с S на Z или наоборот оставляет пробел шириной в одну ячейку и глубиной в две ячейки. На детали изображен Z-камень над S-камнем; обе буквы «о» обозначают пробел:
.Z
ZZ
Zo
So
SS
.SДругой вертикальный камень в той же дорожке не сможет заполнить этот пробел: его второй столбец столкнулся бы с соседними занятыми клетками. Удаление строк также не помогает, пока существует пробел, поскольку обе строки не являются полными. Для ремонта требуется одно из уже исключенных поперечных или горизонтальных размещений. После последнего уклончивого хода такие разрывы становятся постоянными. На конечной доске не может возникнуть бесконечное количество новых, непересекающихся пробелов.
В результате на гусеницах может быть лишь конечное число изменений формы. Изначально пустая дорожка этого не меняет: ваш первый камень S или Z уже оставляет на полу дыру в одну колонну, которую невозможно закрыть дальнейшей игрой на чистой дорожке. В предположительно бесконечной игре на каждой дорожке должно быть также бесконечное количество камней. Если бы полоса в какой-то момент осталась нетронутой, на оставшихся дорожках можно было бы разместить только конечное число ячеек из-за ограниченного баланса столбцов.
Таким образом, мы достигаем момента времени, когда все пять полос постоянно заняты и прочно закреплены за формой. С этого момента мы считаем \(t\) больше камней и с помощью \(n_j(t)\) число на дорожке \(j\) . Каждый из этих камней вносит две ячейки в каждый столбец своей дорожки. Поскольку при удалении строк все столбцы обрабатываются одинаково, различия \(n_j(t)-n_k(t)\) остаются ограниченными. В долгосрочной перспективе на всех пяти дорожках должно быть по пятой части камней.:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Если \(k\) из пяти дорожек зарезервировано для S-камней, их доля должна быть около \(k/5\) . Однако в поочередной последовательности это \(1/2\) : в каждом префиксе номера камней S и Z отличаются не более чем \(1\) . Разделение полос должно было бы выполнить обе части одновременно. Однако долю половины нельзя представить как сумму целых пятых. Здесь сходятся частота чередующихся форм и нечетное количество одинаково используемых треков. Это было бы обязательно:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Количество полос является целым числом. Это противоречие кладет конец предположению о бесконечной игре. Этот аргумент также показывает, почему ширина доски является его частью: при четырех поездах это противоречие не исключает разделения на два поезда S и два поезда Z. Для случайного доказательства нам нужна конечная длина блока \(N\) , которая приводит к потерям независимо от текущей доски. Одного лишь утверждения «Каждая стратегия в какой-то момент проигрывает» недостаточно.
Равномерность следует из конечного числа возможных состояний. После каждого завершенного размещения существует не более \(2^{200}\) шаблонов занятости. Также имеется информация о том, появится ли S или Z следующим, т. е. максимум состояний \(2^{201}\) . Если бы вам пришлось пережить \(N=2^{201}\) камней, состояния \(N+1\) до и после этих ходов будут повторяться. Из-за идентичной доски и одной и той же следующей фигуры допустимые ходы между ними можно было бы повторять любое количество раз: бесконечная игра просто исключена.
Предел также учитывает недостижимые шаблоны доски и не предсказывает практическую продолжительность игры. Более тонкий геометрический подсчет Бургеля дает меньшие границы; здесь достаточно конечного \(N\) . Это относится ко всем допустимым начальным назначениям и обеим фазам последовательности S/Z. Разложим бесконечную случайную последовательность на непересекающиеся блоки длины \(N\) . Каждый блок представляет собой в точности указанную последовательность \(S,Z,S,Z,\ldots\) с вероятностью \(q=7^{-N}>0\) . Блоки независимы. Поэтому вполне вероятно, что ни один из первых блоков \(m\) не содержит этой последовательности.:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Таким образом, с вероятностью \(1\) в какой-то момент появится смертельный блок, если игра не закончится раньше этого времени. Это касается и любого количества времени на обдумывание и полного знания всей последовательности камней. Это не приводит к сокращению практического игрового времени. Несосредоточенный и плохой старт сам по себе не означает поражения; неожиданные возвращения, безусловно, возможны. Так что – не расстраивайтесь и наслаждайтесь вечной игрой.