Vous perdez à Tetris uniquement parce que vous ne jouez pas de manière optimale ou que vous faites des erreurs ? Même en prenant le temps d’y réfléchir, une séquence de pierres défavorable ne peut pas être sauvée. Le facteur décisif est cinq voies étroites et un nombre impair. Nous considérons un terrain de jeu avec \(10\) colonnes et \(20\) lignes sans presse-papiers (hold) : chaque nouvelle pierre est tirée indépendamment et également répartie à partir des sept tétrominos . Chaque forme se compose de quatre carrés connectés. L’intégralité de l’épisode peut être connue à l’avance.
Le fait qu’un jeu se termine presque certainement ne signifie pas que toutes les séquences de pierres imaginables se terminent. Une pure séquence de pierres O peut être jouée à l'infini : cinq cases placées les unes à côté des autres suppriment deux rangées et vident le plateau. Dans 7-Bag, chaque sac mélangé au hasard contient les sept formes exactement une fois ; notre argument du hasard ne s’applique pas à cela. Dans Comment perdre à Tetris, Heidi Burgiel montre une séquence que même un jeu parfait n'aide pas : \(S,Z,S,Z,\ldots\) .
S et Z sont des images miroir, et non des rotations différentes de la même pierre. L' explication qui l'accompagne décrit l'idée géométrique que nous présentons ici comme preuve par contradiction. L’affirmation évidente selon laquelle « à un moment donné, seules les pierres Z apparaissent et aucune rangée ne disparaît avec elles » est fausse. Seules cinq pierres S identiques, placées verticalement, fournissent la disposition suivante sur un plateau initialement vide. Les mêmes lettres désignent la même pierre ; Les points marquent les espaces libres:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eLa rangée du milieu est terminée et supprimée. Si vous reproduisez la disposition, vous obtenez le même contre-exemple pour les pierres Z. Le problème n’est pas de supprimer des rangées individuelles, mais de savoir si l’on peut contrôler tous les déséquilibres qui surviennent sur un nombre illimité de pierres. Numérotons les colonnes de \(1\) à \(10\) . Par \(b_i\) nous désignons le nombre total de toutes les nouvelles cellules placées dans la colonne \(i\) , y compris celles supprimées ultérieurement.
\(h_i\) compte les pierres horizontales S ou Z avec la colonne du milieu \(i\) , \(v_i\) les pierres verticales dans les colonnes \(i\) et \(i+1\) . Les pions enregistrent le déroulement du jeu, pas seulement la pile actuellement visible. Une pierre horizontale répartit ses cellules dans le rapport \(1,2,1\) sur trois colonnes, une pierre verticale dans le rapport \(2,2\) sur deux colonnes. Les deux images miroir ont le même équilibre de colonnes. Si vous additionnez ces contributions sur tous les emplacements, vous obtenez pour chaque colonne:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
En dehors du tableau, nous mettons tous les compteurs à \(0\) ; en particulier \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Cette convention de bord empêche la balance de compter des pierres qui s'étendraient au-delà du bord du terrain de jeu. De tels placements ne sont pas autorisés dans notre modèle. Si la séquence S/Z considérée commence sur un tableau déjà rempli, soit \(a_i\) les cellules initialement occupées et \(c_i\) les cellules actuellement occupées dans la colonne \(i\) . Après que \(R\) les lignes supprimées soient:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Tant que le jeu est en cours d'exécution, tous \(a_i,c_i\) sont compris entre \(0\) et \(20\) . Par conséquent, \(|b_i-b_j|\leq40\) s'applique. Si le tableau est initialement vide \(20\) suffit. Chaque ligne supprimée supprime exactement une cellule de chaque colonne. C'est pourquoi le nombre de lignes supprimées est réduit lorsqu'on compare deux colonnes, même si les compteurs des cellules définies continuent de croître. Vous comptez les cellules occupées au lieu des hauteurs de pile ; Les deux tailles diffèrent en ce qui concerne les trous. Si nous écrivons cette limite généralement sous la forme \(D\) , elle se traduit sur le bord gauche ou droit:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Pour les paires de colonnes internes, nous ajoutons deux différences de colonnes restreintes : \(b_4-b_3\) et \(b_2-b_1\) à gauche, \(b_7-b_8\) et \(b_9-b_{10}\) à droite. Après avoir inséré le solde de la colonne, les compteurs intermédiaires s'annulent exactement. Cela ne laisse que des contributions non négatives sur chaque côté gauche, qui sont conjointement délimitées par \(2D\) . Cela nous donne également une limite supérieure pour les numéros de placement respectifs pour les deux paires internes.:
$$\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}$$
Si l’on additionne les quatre inégalités, chaque pierre horizontale est comptée exactement une fois. Les quatre types de placements verticaux croisés ont également des coefficients positifs. Les pierres horizontales occupent trois colonnes et ne s'intègrent donc pas complètement dans l'un des chemins à deux colonnes envisagés plus loin. Pour les pierres verticales, on distingue les traces selon la colonne de gauche. Puisque tous les compteurs sont non négatifs, aucune de ces contributions ne peut être annulée par un autre.:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Les placements horizontaux et verticaux avec une colonne de gauche droite peuvent donc se produire au maximum \(120\) fois sur un plateau vide ou \(240\) fois sur n'importe quel plateau pré-rempli. Il s’agit d’une limite supérieure et non d’une affirmation selon laquelle elle peut réellement être atteinte. Quoi qu’il en soit, ces mouvements d’évasion ne peuvent pas être utilisés indéfiniment. Supposons maintenant que vous puissiez jouer la séquence alternée indéfiniment.
Après le dernier des mouvements d'évitement en nombre fini, seuls les placements verticaux dans cinq voies fixes seraient possibles : \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Des formes identiques s'emboîtent les unes dans les autres selon un motif en escalier : le bas rencontre le haut assorti de la pierre précédente. Le passage de S à Z ou vice versa laisse un espace d'une cellule de largeur et de deux cellules de profondeur. Le détail montre une pierre Z sur une pierre S ; les deux "o" marquent l'écart:
.Z
ZZ
Zo
So
SS
.SUne autre pierre verticale dans la même ruelle ne peut combler ce vide : sa deuxième colonne entrerait en collision avec les cellules occupées voisines. La suppression de lignes n'aide pas non plus tant que l'espace est ouvert, car les deux lignes ne sont pas complètes. Une réparation nécessite l'un des placements transversaux ou horizontaux déjà exclus. Après le dernier mouvement d’évasion, ces écarts sont permanents. Un nombre infini de nouveaux espaces disjoints ne peuvent pas apparaître sur un plateau fini.
En conséquence, il ne peut y avoir qu’un nombre fini de changements de forme sur les voies. Une voie initialement vide n'y change rien : votre première pierre S ou Z laisse déjà un espace d'une seule colonne sur le sol qui ne peut pas être comblé par un jeu de voie pur supplémentaire. Dans un jeu supposément infini, chaque piste doit également contenir un nombre infini de pierres. Si une voie devait rester intacte à un moment donné, seul un nombre fini de cellules pourrait être logé dans les voies restantes en raison des équilibres limités des colonnes.
Nous arrivons donc à un moment où les cinq voies sont occupées en permanence et fermement affectées à une forme. À partir de ce point, nous comptons \(t\) plus de pierres et avec \(n_j(t)\) le numéro dans la piste \(j\) . Chacune de ces pierres apporte deux cellules à chaque colonne de sa piste. Étant donné que les suppressions de lignes traitent toutes les colonnes de la même manière, les différences \(n_j(t)-n_k(t)\) restent limitées. À long terme, les cinq voies doivent contenir chacune un cinquième des pierres:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Si \(k\) des cinq voies sont réservées aux pierres S, leur part devrait être d'environ \(k/5\) . Cependant, dans la séquence alternée, c'est \(1/2\) : dans chaque préfixe, les numéros des pierres S et Z diffèrent d'au plus \(1\) . La division des voies devrait remplir les deux parties en même temps. Cependant, une part de moitié ne peut pas être représentée comme la somme de cinquièmes entiers. C’est là que se rejoignent la fréquence des formes alternées et le nombre impair de morceaux également utilisés. Ce serait obligatoire:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Le nombre de voies est un nombre entier. Cette contradiction met fin à l’hypothèse d’un jeu infini. L'argument montre également pourquoi la largeur du panneau en fait partie : avec quatre trains, une division en deux trains S et deux trains Z ne serait pas exclue par cette contradiction. Pour la preuve aléatoire, nous avons besoin d'une longueur de bloc finie \(N\) qui entraîne une perte quelle que soit la carte actuelle. « Chaque stratégie perd à un moment donné » ne suffit pas.
L'uniformité découle du nombre fini d'états possibles. Après chaque placement terminé, il existe au maximum \(2^{200}\) modèles d'occupation. Il existe également des informations indiquant si S ou Z apparaît ensuite, c'est-à-dire un maximum de \(2^{201}\) états. Si vous deviez survivre à \(N=2^{201}\) pierres, les états \(N+1\) avant et après ces mouvements auraient une répétition. En raison du plateau identique et de la même forme suivante, les mouvements légaux intermédiaires seraient répétables un nombre illimité de fois : le jeu infini serait simplement exclu.
La limite prend également en compte les modèles de plateau inaccessibles et ne prédit pas la durée pratique du jeu. Le comptage géométrique plus fin de Burgiel donne des limites plus petites ; ici un \(N\) fini suffit. Elle s'applique à toutes les affectations initiales autorisées et aux deux phases de la séquence S/Z. Décomposons la séquence aléatoire infinie en blocs disjoints de longueur \(N\) . Chaque bloc est exactement la séquence spécifiée \(S,Z,S,Z,\ldots\) avec probabilité \(q=7^{-N}>0\) . Les blocs sont indépendants. Il est donc probable qu'aucun des premiers blocs \(m\) ne contienne cette séquence:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Ainsi, avec une probabilité \(1\) un bloc mortel apparaîtra à un moment donné, à moins que le jeu ne se termine avant cette date. Cela s’applique également si l’on prend le temps d’y réfléchir et d’en connaître pleinement les conséquences. Cela n'entraîne pas un temps de jeu court et un mauvais départ ne signifie pas à lui seul une défaite : L'animation suivante montre cinq séquences mixtes précalculées, dont chacune atteint un plateau vide après neuf placements de tour inchangés. Ce n’est pas un robot Tetris universel.