Ви програєте в Tetris лише тому, що не граєте оптимально або робите помилки? Навіть маючи певний час на роздуми, несприятливу послідовність каменів неможливо зберегти. Вирішальним фактором є п'ять вузьких смуг і непарна кількість. Ми розглядаємо ігрове поле з \(10\) стовпчиками та \(20\) рядками без буфера обміну (утримання): кожен новий камінь малюється незалежно та рівномірно розподілений із семи тетроміно . Кожна фігура складається з чотирьох з'єднаних квадратів. Весь епізод може бути відомий заздалегідь.
Той факт, що гра майже напевно закінчується, не означає, що закінчується кожна мислима послідовність каменів. Чисту послідовність О-каменів можна грати нескінченно: п’ять квадратів, розташованих поруч, видаляють два ряди та спустошують дошку. У 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\) смертоносний блок з’явиться в якийсь момент, якщо гра не закінчиться раніше. Це також стосується будь-якої кількості часу на обдумування та повного знання всієї послідовності каменів. Це не призводить до короткого практичного ігрового часу. Сам по собі нецілеспрямований, поганий старт не означає поразки; дивовижні повернення, звичайно, можливі. Тож не впадайте у відчай і насолоджуйтеся вічною грою.