Ĉu vi nur perdas ĉe Tetriso ĉar vi ne ludas optimume aŭ faras erarojn? Eĉ kun ajna kvanto de tempo por pensi pri ĝi, malfavora sekvenco de ŝtonoj ne povas esti konservita. La decida faktoro estas kvin mallarĝaj lenoj kaj nepara nombro. Ni konsideras ludkampon kun \(10\) kolumnoj kaj \(20\) vicoj sen tondujo (teni): Ĉiu nova ŝtono estas desegnita sendepende kaj egale distribuita el la sep tetrominoj . Ĉiu formo konsistas el kvar ligitaj kvadratoj. La tuta epizodo povas esti konata anticipe.
La fakto, ke ludo preskaŭ certe finiĝas, ne signifas, ke ĉiu imagebla sinsekvo de ŝtonoj finiĝas. Pura sinsekvo de O-ŝtonoj estas ludebla senfine: kvin kvadratoj metitaj unu apud la alia forigas du vicojn kaj malplenigas la tabulon. En 7-Sako, ĉiu hazarde miksita sako enhavas ĉiujn sep formojn ĝuste unufoje; nia hazarda argumento ne validas por tio. En Kiel Perdi ĉe Tetriso, Heidi Burgiel montras sinsekvon, ke eĉ perfekta ludado ne helpas: \(S,Z,S,Z,\ldots\) .
S kaj Z estas spegulaj bildoj, ne malsamaj rotacioj de la sama ŝtono. La akompana klarigo priskribas la geometrian ideon, kiun ni prezentas ĉi tie kiel pruvon per kontraŭdiro. La evidenta aserto "iam nur Z-ŝtonoj aperas kaj neniu vico malaperas kun ili" estas malĝusta. Nur kvin identaj, vertikale metitaj S-ŝtonoj disponigas la sekvan aranĝon sur komence malplena tabulo. La samaj literoj indikas la saman ŝtonon; Punktoj markas liberajn spacojn:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eLa meza vico estas kompleta kaj forigita. Se vi spegulas la aranĝon, vi ricevas la saman kontraŭekzemplon por Z-ŝtonoj. La problemo ne estas forigi individuajn vicojn, sed la demando ĉu vi povas kontroli ĉiujn malekvilibrojn, kiuj ŝprucas tra senlima nombro da ŝtonoj. Ni numeru la kolumnojn de \(1\) ĝis \(10\) . Per \(b_i\) ni indikas la totalan nombron de ĉiuj novaj ĉeloj metitaj en kolumno \(i\) , inkluzive de tiuj poste forigitaj.
\(h_i\) kalkulas horizontalajn S aŭ Z ŝtonojn kun meza kolono \(i\) , \(v_i\) vertikalaj ŝtonoj en kolonoj \(i\) kaj \(i+1\) . La nombriloj registras la kurson de la ludo, ne nur la nuntempe videblan stakon. Horizontala ŝtono distribuas siajn ĉelojn en la proporcio \(1,2,1\) super tri kolumnoj, vertikala ŝtono en la proporcio \(2,2\) en du kolumnoj. Ambaŭ spegulaj bildoj havas la saman kolumnekvilibron. Se vi aldonas ĉi tiujn kontribuojn tra ĉiuj allokigoj, vi ricevas por ĉiu kolumno:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Ekster la tabulo ni starigas ĉiujn nombrilojn al \(0\) ; precipe \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Ĉi tiu randkonvencio malhelpas la pesilon kalkuli ŝtonojn, kiuj etendus preter la rando de la ludkampo. Tiaj allokigoj ne estas permesitaj en nia modelo. Se la konsiderata sekvenco S/Z komenciĝas sur jam plenigita tabulo, estu \(a_i\) la komence okupitaj ĉeloj kaj \(c_i\) la nuntempe okupitaj ĉeloj en kolumno \(i\) . Post \(R\) forigitaj vicoj estas:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Dum la ludo funkcias, ĉiuj \(a_i,c_i\) estas inter \(0\) kaj \(20\) . Tial \(|b_i-b_j|\leq40\) validas. Se la tabulo estas komence malplena \(20\) . Ĉiu forigita vico forprenas ĝuste unu ĉelon de ĉiu kolumno. Jen kial la nombro da forigitaj vicoj estas reduktita kiam oni komparas du kolumnojn, eĉ se la nombriloj de la fiksitaj ĉeloj daŭre kreskas. Vi nombras okupatajn ĉelojn anstataŭ stakaltoj; La du grandecoj malsamas kiam temas pri truoj. Se ni skribas ĉi tiun limon ĝenerale kiel \(D\) , ĝi rezultas sur la maldekstra aŭ dekstra rando:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Por la internaj kolonparoj ni aldonas du limigitajn kolondiferencojn: \(b_4-b_3\) kaj \(b_2-b_1\) maldekstre, \(b_7-b_8\) kaj \(b_9-b_{10}\) dekstre. Post enmetado de la kolumna ekvilibro, la nombriloj intere nuligas unu la alian ĝuste. Ĉi tio lasas nur nenegativajn kontribuojn sur ĉiu maldekstra flanko, kiuj estas komune limigitaj per \(2D\) . Ĉi tio ankaŭ donas al ni supran limon por la respektivaj allokigaj nombroj por la du internaj paroj:
$$\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}$$
Se ni aldonas la kvar neegalaĵojn, ĉiu horizontala ŝtono estas kalkulita ekzakte unufoje. La kvar specoj de trans-trakaj vertikalaj allokigoj ankaŭ havas pozitivajn koeficientojn. La horizontalaj ŝtonoj okupas tri kolumnojn kaj tial ne tute konvenas en unu el la du-kolumnaj padoj konsiderataj poste. Por la vertikalaj ŝtonoj, ni distingas la spurojn laŭ la maldekstra kolumno. Ĉar ĉiuj nombriloj estas nenegativaj, neniu el ĉi tiuj kontribuoj povas esti nuligita de alia:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Horizontalaj lokigoj kaj vertikalaj lokigoj kun rekta maldekstra kolumno povas do okazi maksimume \(120\) fojojn sur malplena tabulo aŭ \(240\) fojojn sur iu antaŭplenigita tabulo. Ĉi tio estas supera limo, ne aserto, ke ĝi efektive povas esti atingita. Ĉiukaze, ĉi tiuj evitemaj movoj ne povas esti uzataj senfine ofte. Nun ni supozu, ke vi povus ludi la alternan sinsekvon senfine.
Post la lasta el la finhava nombro da evitemaj movoj, nur vertikalaj lokigoj en kvin fiksaj lenoj estus eblaj: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Identaj formoj konvenas unu en la alian laŭ paŝosimila ŝablono: la fundo renkontas la kongruan supron de la antaŭa ŝtono. Ŝanĝi de S al Z aŭ inverse lasas interspacon unu ĉelon larĝa kaj du ĉelojn profunda. La detalo montras Z-ŝtonon super S-ŝtono; ambaŭ “o” markas la interspacon:
.Z
ZZ
Zo
So
SS
.SAlia vertikala ŝtono en la sama leno ne povas plenigi ĉi tiun interspacon: ĝia dua kolono kolizias kun la najbaraj okupataj ĉeloj. Forigi vicojn ankaŭ ne helpas dum la interspaco estas malfermita, ĉar ambaŭ vicoj ne estas kompletaj. Riparo postulas unu el la jam ekskluditaj krucvojaj aŭ horizontalaj allokigoj. Post la lasta evitema movo, tiaj breĉoj estas konstantaj. Senfina nombro da novaj, disaj interspacoj ne povas ekesti sur finhava tabulo.
Kiel rezulto, povas ekzisti nur finhava nombro da ŝanĝoj en formo sur la trakoj. Komence malplena leno ne ŝanĝas tion: via unua S aŭ Z-ŝtono jam lasas unukolumnan breĉon sur la planko, kiu ne povas esti fermita per plua pura lena ludado. En supozeble senfina ludo, ĉiu leno ankaŭ devas teni senfinan nombron da ŝtonoj. Se leno restus netuŝita ĉe iu punkto, nur finhava nombro da ĉeloj povus esti alĝustigita en la ceteraj lenoj pro la limigitaj kolonekvilibroj.
Ni do atingas tempon en kiu ĉiuj kvin lenoj estas konstante okupitaj kaj firme asignitaj al formo. De ĉi tiu punkto ni kalkulas \(t\) pliajn ŝtonojn kaj kun \(n_j(t)\) la nombron en trako \(j\) . Ĉiu el ĉi tiuj ŝtonoj kontribuas du ĉelojn al ĉiu kolono de sia trako. Ĉar vicoj traktas ĉiujn kolumnojn egale, la diferencoj \(n_j(t)-n_k(t)\) restas limigitaj. Longtempe, ĉiuj kvin lenoj devas ĉiu teni kvinonon de la ŝtonoj:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Se \(k\) el la kvin lenoj estas rezervita por S-ŝtonoj, ilia parto estu ĉirkaŭ \(k/5\) . Tamen, en la alterna sinsekvo estas \(1/2\) : en ĉiu prefikso la nombroj de la S kaj Z-ŝtonoj diferencas je maksimume \(1\) . La divido de la lenoj devus plenumi ambaŭ partojn samtempe. Tamen, parto de duono ne povas esti reprezentita kiel la sumo de tutaj kvinonoj. Ĉi tie kuniĝas la ofteco de alternaj formoj kaj la nepara nombro de same uzataj trakoj. Tio estus deviga:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
La nombro da lenoj estas entjero. Ĉi tiu kontraŭdiro finas la supozon de senfina ludo. La argumento ankaŭ montras kial la tabullarĝo estas parto de ĝi: Kun kvar trajnoj, divido en du S kaj du Z trajnoj ne estus forigita de tiu kontraŭdiro. Por la hazarda pruvo ni bezonas finian bloklongon \(N\) kiu kondukas al perdo sendepende de la nuna tabulo. "Ĉiu strategio perdas iam" sole ne sufiĉas.
La unuformeco sekvas el la finhava nombro da eblaj statoj. Post ĉiu finita lokigo, estas maksimume \(2^{200}\) okupadpadronoj. Estas ankaŭ la informo ĉu S aŭ Z aperas poste, t.e. maksimume \(2^{201}\) ŝtatoj. Se vi travivus \(N=2^{201}\) ŝtonojn, la \(N+1\) statoj antaŭ kaj post ĉi tiuj movoj havus ripeton. Pro la identa tabulo kaj la sama sekva formo, la laŭleĝaj movoj intere estus ripeteblaj ajna nombro da fojoj: la senfina ludo ĵus ekskludita.
La limo ankaŭ nombras neatingeblajn tabulpadronojn kaj ne antaŭdiras praktikan ludolongon. La pli fajna geometria nombrado de Burgiel donas pli malgrandajn saltojn; ĉi tie finia \(N\) sufiĉas. Ĝi validas por ĉiuj permeseblaj komencaj taskoj kaj ambaŭ fazoj de la S/Z-sekvenco. Ni malkomponu la senfinan hazardan vicon en disajn blokojn de longo \(N\) . Ĉiu bloko estas ĝuste la specifita sinsekvo \(S,Z,S,Z,\ldots\) kun probablo \(q=7^{-N}>0\) . La blokoj estas sendependaj. Estas do verŝajne ke neniu el la unuaj \(m\) blokoj enhavas ĉi tiun sinsekvon:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Do kun probableco \(1\) mortiga bloko aperos iam, krom se la ludo finiĝos antaŭe. Ĉi tio ankaŭ validas kun ajna kvanto de tempo por pensi pri ĝi kaj kompleta scio pri la sekvoj. Tio ne rezultigas mallongan praktikan ludotempon, kaj malbona komenco sole ne signifas malvenkon: La sekva animacio montras kvin antaŭkalkulitajn miksitajn sekvencojn, ĉiu el kiuj atingas malplenan tabulon post naŭ senŝanĝaj turlokigoj. Ŝi ne estas universala Tetris-bot.