Czy przegrywasz w Tetris tylko dlatego, że nie grasz optymalnie lub popełniasz błędy? Nawet przy jakiejkolwiek ilości czasu do namysłu nie da się uratować niekorzystnej sekwencji kamieni. Decydującym czynnikiem jest pięć wąskich pasów ruchu i liczba nieparzysta. Rozważamy pole gry z \(10\) kolumnami i \(20\) rzędami bez schowka (przytrzymaj): Każdy nowy kamień jest losowany niezależnie i równomiernie rozłożony z siedmiu tetromino . Każdy kształt składa się z czterech połączonych kwadratów. Cały odcinek może być znany z góry.
Fakt, że gra prawie na pewno się kończy, nie oznacza, że kończy się każda możliwa sekwencja kamieni. Czystą sekwencję O-kamień można rozgrywać w nieskończoność: pięć kwadratów umieszczonych obok siebie usuwa dwa rzędy i opróżnia planszę. W 7-Bagach każda losowo wymieszana torebka zawiera wszystkie siedem kształtów dokładnie raz; nasz argument dotyczący szansy nie ma tu zastosowania. W Jak przegrać w Tetris Heidi Burgiel pokazuje sekwencję, w której nawet doskonała gra nie pomaga: \(S,Z,S,Z,\ldots\) .
S i Z są odbiciami lustrzanymi, a nie różnymi obrotami tego samego kamienia. Załączone wyjaśnienie opisuje ideę geometryczną, którą przedstawiamy tutaj jako dowód przez sprzeczność. Oczywiste twierdzenie, że „w pewnym momencie pojawiają się tylko kamienie Z i wraz z nimi nie znika żaden rząd” jest błędne. Tylko pięć identycznych, pionowo ułożonych kamieni S zapewnia następujący układ na początkowo pustej planszy. Te same litery oznaczają ten sam kamień; Kropki oznaczają wolne miejsca:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eŚrodkowy rząd jest kompletny i usunięty. Jeśli odzwierciedlisz układ, otrzymasz ten sam kontrprzykład dla kamieni Z. Problemem nie jest usuwanie pojedynczych rzędów, ale kwestia tego, czy uda się zapanować nad wszystkimi brakami równowagi, które powstają na nieograniczonej liczbie kamieni. Ponumerujmy kolumny od \(1\) do \(10\) . Przez \(b_i\) oznaczamy całkowitą liczbę wszystkich nowych komórek umieszczonych w kolumnie \(i\) , łącznie z tymi później usuniętymi.
\(h_i\) zlicza poziome kamienie S lub Z ze środkową kolumną \(i\) , \(v_i\) pionowe kamienie w kolumnach \(i\) i \(i+1\) . Liczniki rejestrują przebieg gry, a nie tylko aktualnie widoczny stos. Kamień poziomy rozkłada swoje komórki w proporcji \(1,2,1\) w trzech kolumnach, kamień pionowy w proporcji \(2,2\) w dwóch kolumnach. Obydwa odbicia lustrzane mają ten sam balans kolumn. Jeśli zsumujesz te wkłady we wszystkich miejscach docelowych, otrzymasz kwotę za każdą kolumnę:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Na zewnątrz planszy ustawiamy wszystkie liczniki na \(0\) ; w szczególności \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Ta konwencja krawędzi uniemożliwia wadze liczenie kamieni, które wystają poza krawędź pola gry. Takie miejsca docelowe nie są dozwolone w naszym modelu. Jeżeli rozważana sekwencja S/Z zaczyna się na już zapełnionej planszy, niech \(a_i\) będzie początkowo zajętymi komórkami, a \(c_i\) aktualnie zajętymi komórkami w kolumnie \(i\) . Po \(R\) usuniętych wierszach jest:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Tak długo jak gra jest uruchomiona, wszystkie \(a_i,c_i\) znajdują się pomiędzy \(0\) a \(20\) . Dlatego obowiązuje \(|b_i-b_j|\leq40\) . Jeśli plansza jest początkowo pusta \(20\) . Każdy usunięty wiersz zabiera dokładnie jedną komórkę z każdej kolumny. Dlatego przy porównywaniu dwóch kolumn liczba usuniętych wierszy jest zmniejszana, nawet jeśli liczniki ustawionych komórek nadal rosną. Liczysz zajęte komórki zamiast wysokości stosu; Obydwa rozmiary różnią się otworami. Jeśli zapiszemy tę granicę ogólnie jako \(D\) , wynika to z lewej lub prawej krawędzi:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
W przypadku par kolumn wewnętrznych dodajemy dwie ograniczone różnice w kolumnach: \(b_4-b_3\) i \(b_2-b_1\) po lewej stronie, \(b_7-b_8\) i \(b_9-b_{10}\) po prawej stronie. Po wstawieniu salda kolumny, liczniki pomiędzy nimi znoszą się dokładnie. Pozostawia to tylko nieujemne wkłady po każdej lewej stronie, które są wspólnie ograniczone przez \(2D\) . Daje nam to również górną granicę odpowiednich numerów rozmieszczenia dla dwóch par wewnętrznych:
$$\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}$$
Jeśli dodamy cztery nierówności, każdy poziomy kamień zostanie policzony dokładnie raz. Cztery typy rozmieszczeń pionowych w poprzek torów mają również dodatnie współczynniki. Poziome kamienie zajmują trzy kolumny i dlatego nie pasują całkowicie do żadnej z dwukolumnowych ścieżek rozważanych później. Dla kamieni pionowych rozróżniamy ślady według lewej kolumny. Ponieważ wszystkie liczniki są nieujemne, żaden z tych wkładów nie może zostać anulowany przez inny:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Dlatego też rozmieszczenia poziome i pionowe z prostą lewą kolumną mogą wystąpić maksymalnie \(120\) razy na pustej planszy lub \(240\) razy na dowolnej wstępnie wypełnionej planszy. Jest to górna granica, a nie twierdzenie, że faktycznie można ją osiągnąć. W każdym razie tych uników nie można stosować nieskończenie często. Załóżmy teraz, że możesz odtwarzać sekwencję naprzemienną w nieskończoność.
Po ostatnim ze skończonej liczby ruchów wymijających możliwe byłoby jedynie rozmieszczenie pionowe na pięciu stałych pasach: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Identyczne kształty dopasowują się do siebie schodkowo: dół styka się z pasującą górą poprzedniego kamienia. Zmiana z S na Z i odwrotnie pozostawia lukę o szerokości jednej komórki i głębokości dwóch komórek. Szczegół przedstawia kamień Z nad kamieniem S; oba „o” oznaczają przerwę:
.Z
ZZ
Zo
So
SS
.SInny pionowy kamień na tym samym pasie nie może wypełnić tej luki: jego druga kolumna zderzyłaby się z sąsiednimi zajętymi celami. Usuwanie wierszy również nie pomaga, dopóki luka jest otwarta, ponieważ oba wiersze nie są kompletne. Naprawa wymaga jednego z już wykluczonych rozmieszczeń poprzecznych lub poziomych. Po ostatnim uniku takie luki są trwałe. Na skończonej planszy nie może powstać nieskończona liczba nowych, rozłącznych luk.
W rezultacie może nastąpić tylko skończona liczba zmian w formie na torach. Początkowo pusty pas tego nie zmienia: Twój pierwszy kamień S lub Z pozostawia już pojedynczą kolumnę na podłodze, której nie można zamknąć dalszą grą na czystej linii. W rzekomo nieskończonej grze na każdym pasie musi znajdować się nieskończona liczba kamieni. Jeśli w pewnym momencie pas miałby pozostać nietknięty, na pozostałych pasach można by umieścić tylko skończoną liczbę komórek ze względu na ograniczone salda kolumn.
Dochodzimy zatem do momentu, w którym wszystkie pięć pasów ruchu jest stale zajęte i trwale przypisane do jakiejś formy. Od tego momentu liczymy \(t\) więcej kamieni i przy \(n_j(t)\) liczbę na ścieżce \(j\) . Każdy z tych kamieni wnosi dwie komórki do każdej kolumny swojego toru. Ponieważ usunięcie wierszy traktuje wszystkie kolumny jednakowo, różnice \(n_j(t)-n_k(t)\) pozostają ograniczone. W dłuższej perspektywie każdy z pięciu pasów będzie musiał pomieścić jedną piątą kamieni:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Jeśli \(k\) z pięciu pasów jest zarezerwowane dla kamieni S, ich udział powinien wynosić około \(k/5\) . Natomiast w kolejności naprzemiennej jest to \(1/2\) : w każdym przedrostku numery kamieni S i Z różnią się co najwyżej \(1\) . Podział pasów musiałby spełniać obie części jednocześnie. Jednakże połowy nie można przedstawić jako sumy całych piątych. W tym miejscu spotykają się częstotliwość naprzemiennych form i nieparzysta liczba jednakowo używanych utworów. To byłoby obowiązkowe:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Liczba pasów jest liczbą całkowitą. Ta sprzeczność kończy założenie o nieskończonej grze. Argument pokazuje również, dlaczego szerokość deski jest jej częścią: w przypadku czterech pociągów sprzeczność ta nie wyklucza podziału na dwa składy S i dwa Z. Do losowego dowodu potrzebujemy skończonej długości bloku \(N\) , która prowadzi do straty niezależnie od aktualnej płytki. Samo stwierdzenie „każda strategia w pewnym momencie przegrywa” nie wystarczy.
Jednorodność wynika ze skończonej liczby możliwych stanów. Po każdym ukończonym miejscu docelowym występuje co najwyżej \(2^{200}\) wzorców obłożenia. Pojawia się też informacja, czy jako następny pojawia się S czy Z, czyli maksymalnie \(2^{201}\) stanów. Jeśli miałbyś przeżyć \(N=2^{201}\) kamienie, stany \(N+1\) przed i po tych ruchach miałyby powtórzenie. Ze względu na identyczną planszę i ten sam kształt następnego, legalne ruchy pomiędzy nimi można powtarzać dowolną liczbę razy: gra nieskończona jest po prostu wykluczona.
Limit uwzględnia także nieosiągalne układy plansz i nie przewiduje praktycznej długości gry. Dokładniejsze liczenie geometryczne Burgiela daje mniejsze granice; tutaj wystarczy skończony \(N\) . Dotyczy to wszystkich dopuszczalnych przypisań początkowych i obu faz ciągu S/Z. Rozłóżmy nieskończony ciąg losowy na rozłączne bloki o długości \(N\) . Każdy blok ma dokładnie określoną sekwencję \(S,Z,S,Z,\ldots\) z prawdopodobieństwem \(q=7^{-N}>0\) . Bloki są niezależne. Jest zatem prawdopodobne, że żaden z pierwszych \(m\) bloków nie zawiera tej sekwencji:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Zatem z prawdopodobieństwem \(1\) w pewnym momencie pojawi się śmiercionośny blok, chyba że gra zakończy się wcześniej. Dotyczy to również dowolnej ilości czasu na przemyślenie i pełną wiedzę na temat całej sekwencji kamieni. Nie skutkuje to krótkim praktycznym czasem gry. Sam brak koncentracji i zły start nie oznacza porażki; zaskakujące powroty są z pewnością możliwe. Zatem – nie zniechęcajcie się i cieszcie się ponadczasową grą.