هل تخسر في لعبة Tetris فقط لأنك لا تلعب بالشكل الأمثل أو ترتكب الأخطاء؟ حتى مع وجود أي قدر من الوقت للتفكير في الأمر، لا يمكن حفظ تسلسل غير مناسب من الحجارة. العامل الحاسم هو خمسة ممرات ضيقة وعدد فردي. نحن نعتبر ملعبًا يحتوي على \(10\) أعمدة و \(20\) صفًا بدون حافظة (إمساك): يتم رسم كل حجر جديد بشكل مستقل ويتم توزيعه بالتساوي من الرباعيات السبعة. يتكون كل شكل من أربعة مربعات متصلة. قد تكون الحلقة بأكملها معروفة مسبقًا.
حقيقة أن اللعبة تنتهي بشكل شبه مؤكد لا تعني أن كل تسلسل يمكن تصوره من الحجارة ينتهي. يمكن لعب تسلسل نقي من أحجار O إلى ما لا نهاية: خمس مربعات موضوعة بجانب بعضها البعض تحذف صفين وتفرغ اللوحة. في 7 أكياس، تحتوي كل حقيبة مختلطة بشكل عشوائي على الأشكال السبعة كلها مرة واحدة بالضبط؛ حجة الصدفة لدينا لا تنطبق على هذا. في كيفية الخسارة في لعبة تتريس، تعرض هايدي بورجيل تسلسلًا لا يساعده حتى اللعب المثالي: \(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؛ كلا "o" يمثلان الفجوة:
.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\) ستظهر كتلة مميتة في مرحلة ما، إلا إذا انتهت اللعبة قبل ذلك. وينطبق هذا أيضًا على أي قدر من الوقت للتفكير في الأمر والمعرفة الكاملة بالعواقب. لا يؤدي هذا إلى وقت لعب عملي قصير، والبداية السيئة وحدها لا تعني الهزيمة: تُظهر الرسوم المتحركة التالية خمسة تسلسلات مختلطة محسوبة مسبقًا، يصل كل منها إلى لوحة فارغة بعد تسعة مواضع برج غير متغيرة. إنها ليست روبوت تتريس عالمي.