Bạn chỉ thua Tetris vì chơi không tối ưu hoặc mắc lỗi? Dù có dành bao nhiêu thời gian để suy nghĩ thì cũng không thể cứu vãn được một chuỗi đá bất lợi. Yếu tố quyết định là năm làn đường hẹp và số lẻ. Chúng tôi xem xét một sân chơi có \(10\) cột và \(20\) hàng không có khay nhớ tạm (giữ): Mỗi viên đá mới được rút ra độc lập và phân bổ đều từ bảy tetrominoes . Mỗi hình bao gồm bốn hình vuông được kết nối. Toàn bộ tập phim có thể được biết trước.
Việc một trò chơi gần như chắc chắn kết thúc không có nghĩa là mọi chuỗi quân cờ có thể tưởng tượng được đều kết thúc. Một chuỗi quân chữ O thuần túy có thể được chơi vô tận: năm ô vuông đặt cạnh nhau sẽ xóa hai hàng và làm trống bảng. Trong 7-Túi, mỗi túi được trộn ngẫu nhiên chứa tất cả bảy hình dạng đúng một lần; lập luận cơ hội của chúng tôi không áp dụng cho điều này. Trong How to Lose at Tetris, Heidi Burgiel cho thấy một trình tự mà ngay cả việc chơi hoàn hảo cũng không giúp ích được gì: \(S,Z,S,Z,\ldots\) .
S và Z là hình ảnh phản chiếu, không phải các góc quay khác nhau của cùng một hòn đá. Lời giải thích kèm theo mô tả ý tưởng hình học mà chúng tôi trình bày ở đây như một bằng chứng phản chứng. Tuyên bố rõ ràng “tại một thời điểm nào đó chỉ có những viên đá Z xuất hiện và không có hàng nào biến mất cùng với chúng” là sai. Chỉ cần năm viên đá chữ S giống hệt nhau, được đặt theo chiều dọc sẽ mang lại sự sắp xếp sau đây trên một tấm bảng trống ban đầu. Các chữ cái giống nhau chỉ cùng một loại đá; Dấu chấm đánh dấu không gian trống:
a.b.c.d.e.
aabbccddee
.a.b.c.d.eHàng giữa đã hoàn thành và bị xóa. Nếu bạn phản chiếu cách sắp xếp này, bạn sẽ có được phản ví dụ tương tự đối với đá Z. Vấn đề không phải là xóa từng hàng riêng lẻ mà là câu hỏi liệu bạn có thể kiểm soát tất cả sự mất cân bằng phát sinh trên số lượng đá không giới hạn hay không. Hãy đánh số các cột từ \(1\) đến \(10\) . Bằng \(b_i\) chúng tôi biểu thị tổng số tất cả các ô mới được đặt trong cột \(i\) , bao gồm cả những ô bị xóa sau đó.
\(h_i\) đếm các viên đá S hoặc Z nằm ngang với cột giữa \(i\) , \(v_i\) các viên đá dọc ở cột \(i\) và \(i+1\) . Bộ đếm ghi lại diễn biến của trò chơi, không chỉ ngăn xếp hiện có. Một viên đá nằm ngang phân bố các ô của nó theo tỷ lệ \(1,2,1\) trên ba cột, một viên đá thẳng đứng theo tỷ lệ \(2,2\) trong hai cột. Cả hai hình ảnh phản chiếu đều có cùng độ cân bằng cột. Nếu bạn cộng những khoản đóng góp này trên tất cả các vị trí, bạn sẽ nhận được cho mỗi cột:
$$b_i=2v_{i-1}+2v_i+h_{i-1}+2h_i+h_{i+1}.$$
Bên ngoài bảng, chúng tôi đặt tất cả các bộ đếm thành \(0\) ; cụ thể là \(v_0=v_{10}=h_0=h_1=h_{10}=h_{11}=0\) . Quy ước về cạnh này ngăn không cho cân đếm những viên đá vượt ra ngoài rìa của sân chơi. Những vị trí như vậy không được phép trong mô hình của chúng tôi. Nếu chuỗi S/Z đang được xem xét bắt đầu trên một bảng đã được lấp đầy, hãy đặt \(a_i\) là các ô được chiếm ban đầu và \(c_i\) là các ô hiện đang được chiếm trong cột \(i\) . Sau khi \(R\) hàng bị xóa là:
$$c_i=a_i+b_i-R,$$
$$b_i-b_j=(c_i-c_j)-(a_i-a_j).$$
Miễn là trò chơi đang chạy, tất cả \(a_i,c_i\) đều nằm trong khoảng từ \(0\) đến \(20\) . Vì vậy \(|b_i-b_j|\leq40\) được áp dụng. Nếu ban đầu bảng trống \(20\) là đủ. Mỗi hàng bị xóa sẽ lấy đi chính xác một ô từ mỗi cột. Đây là lý do tại sao số lượng hàng bị xóa sẽ giảm khi so sánh hai cột, ngay cả khi bộ đếm của các ô đã đặt tiếp tục tăng. Bạn đếm các ô bị chiếm thay vì chiều cao ngăn xếp; Hai kích thước khác nhau khi nói đến lỗ. Nếu chúng ta viết giới hạn này nói chung là \(D\) , kết quả là ở cạnh trái hoặc phải:
$$2v_2+h_2+h_3=b_2-b_1\leq D,$$
$$2v_8+h_8+h_9=b_9-b_{10}\leq D.$$
Đối với các cặp cột bên trong, chúng tôi thêm hai cột khác biệt bị hạn chế: \(b_4-b_3\) và \(b_2-b_1\) ở bên trái, \(b_7-b_8\) và \(b_9-b_{10}\) ở bên phải. Sau khi chèn số dư vào cột, các bộ đếm ở giữa sẽ triệt tiêu lẫn nhau một cách chính xác. Điều này chỉ để lại những đóng góp không âm ở mỗi vế trái, được giới hạn chung bởi \(2D\) . Điều này cũng cung cấp cho chúng tôi giới hạn trên cho số vị trí tương ứng cho hai cặp bên trong:
$$\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}$$
Nếu cộng bốn bất đẳng thức lại thì mỗi viên đá ngang được tính đúng một lần. Bốn loại vị trí dọc đường chéo cũng có hệ số dương. Các khối đá nằm ngang chiếm ba cột và do đó không hoàn toàn khớp với một trong các đường dẫn hai cột được xem xét sau này. Đối với các khối đá thẳng đứng, ta phân biệt đường đi theo cột bên trái. Vì tất cả các bộ đếm đều không âm nên không có đóng góp nào trong số này có thể bị hủy bởi một bộ đếm khác.:
$$\sum_{i=2}^{9}h_i+2(v_2+v_4+v_6+v_8)\leq6D.$$
Do đó, vị trí nằm ngang và vị trí dọc có cột thẳng bên trái có thể xuất hiện tối đa \(120\) lần trên một bảng trống hoặc \(240\) lần trên bất kỳ bảng nào được điền sẵn. Đây là giới hạn trên, không phải là khẳng định rằng nó thực sự có thể đạt được. Trong mọi trường hợp, những chiêu thức né tránh này không thể được sử dụng thường xuyên. Bây giờ hãy giả sử rằng bạn có thể chơi chuỗi xen kẽ vô thời hạn.
Sau lần di chuyển né tránh cuối cùng, chỉ có thể có các vị trí dọc trong năm làn cố định: \((1,2),(3,4),(5,6),(7,8),(9,10)\) . Các hình dạng giống hệt nhau khớp với nhau theo mô hình giống như bậc thang: phần dưới gặp phần trên phù hợp của viên đá trước đó. Thay đổi từ S sang Z hoặc ngược lại để lại một khoảng trống rộng một ô và sâu hai ô. Chi tiết thể hiện một viên đá Z trên một viên đá S; cả hai chữ “o” đều đánh dấu khoảng cách:
.Z
ZZ
Zo
So
SS
.SMột viên đá thẳng đứng khác trong cùng một làn đường không thể lấp đầy khoảng trống này: cột thứ hai của nó sẽ va chạm với các ô bị chiếm đóng lân cận. Việc xóa các hàng cũng không giúp ích gì miễn là khoảng trống còn mở vì cả hai hàng đều chưa hoàn chỉnh. Việc sửa chữa yêu cầu một trong các vị trí nằm ngang hoặc đường chéo đã bị loại trừ. Sau động thái né tránh cuối cùng, những khoảng trống như vậy là vĩnh viễn. Vô số khoảng trống mới, rời rạc không thể xuất hiện trên một bảng hữu hạn.
Kết quả là chỉ có thể có một số lượng hữu hạn những thay đổi về hình thức trên đường ray. Làn đường trống ban đầu không thay đổi điều này: viên đá S hoặc Z đầu tiên của bạn đã để lại một khoảng trống một cột trên sàn mà không thể đóng lại bằng cách chơi làn đường thuần túy tiếp theo. Trong một trò chơi được cho là vô tận, mỗi làn đường cũng phải chứa vô số viên đá. Nếu một làn đường vẫn không bị ảnh hưởng tại một số điểm thì chỉ có một số lượng ô hữu hạn có thể được bố trí trong các làn còn lại do số lượng cột bị hạn chế.
Do đó, chúng tôi đạt đến một thời điểm mà tại đó tất cả năm làn đường đều được chiếm giữ vĩnh viễn và được ấn định chắc chắn vào một biểu mẫu. Từ thời điểm này trở đi, chúng tôi đếm \(t\) nhiều viên đá hơn và với \(n_j(t)\) số trong đường đua \(j\) . Mỗi viên đá này đóng góp hai ô vào mỗi cột trên đường đi của nó. Vì việc xóa hàng xử lý tất cả các cột như nhau nên sự khác biệt \(n_j(t)-n_k(t)\) vẫn còn hạn chế. Về lâu dài, cả năm làn đường mỗi làn phải giữ 1/5 số đá:
$$\frac{n_j(t)}{t}\longrightarrow\frac15.$$
Nếu \(k\) trong số năm làn được dành riêng cho đá S, thì phần của chúng sẽ vào khoảng \(k/5\) . Tuy nhiên, trong chuỗi xen kẽ đó là \(1/2\) : trong mỗi tiền tố, số lượng đá S và Z khác nhau nhiều nhất là \(1\) . Việc phân chia làn đường sẽ phải thực hiện cả hai phần cùng một lúc. Tuy nhiên, một nửa phần không thể được biểu diễn dưới dạng tổng của toàn bộ phần năm. Đây là nơi tần số của các dạng xen kẽ và số lẻ các bản nhạc được sử dụng như nhau kết hợp với nhau. Điều đó sẽ là bắt buộc:
$$\frac{k}{5}=\frac12\quad\Longrightarrow\quad k=\frac52.$$
Số làn đường là một số nguyên. Sự mâu thuẫn này chấm dứt giả định về một trò chơi vô hạn. Lập luận cũng cho thấy tại sao chiều rộng bảng lại là một phần của nó: Với bốn đoàn tàu, việc phân chia thành hai đoàn tàu S và hai đoàn tàu Z sẽ không bị loại trừ bởi mâu thuẫn này. Đối với bằng chứng ngẫu nhiên, chúng ta cần độ dài khối hữu hạn \(N\) dẫn đến mất mát bất kể bảng hiện tại. “Mọi chiến lược đều thua ở một thời điểm nào đó” thôi là chưa đủ.
Tính đồng nhất suy ra từ số lượng hữu hạn các trạng thái có thể. Sau mỗi vị trí hoàn thành, có tối đa \(2^{200}\) kiểu sử dụng. Ngoài ra còn có thông tin về việc S hay Z xuất hiện tiếp theo, tức là tối đa \(2^{201}\) trạng thái. Nếu bạn sống sót sau các quân \(N=2^{201}\) thì trạng thái \(N+1\) trước và sau những nước đi này sẽ có sự lặp lại. Bởi vì bảng giống hệt nhau và hình dạng tiếp theo giống nhau, các nước đi hợp pháp ở giữa sẽ có thể lặp lại bao nhiêu lần: trò chơi vô hạn chỉ bị loại trừ.
Giới hạn này cũng tính các mẫu bàn cờ không thể đạt được và không dự đoán độ dài trò chơi thực tế. Việc đếm hình học tốt hơn của Burgiel cho các giới hạn nhỏ hơn; ở đây một \(N\) hữu hạn là đủ. Nó áp dụng cho tất cả các phép gán ban đầu được phép và cả hai giai đoạn của chuỗi S/Z. Chúng ta hãy phân tách chuỗi ngẫu nhiên vô hạn thành các khối có độ dài rời nhau \(N\) . Mỗi khối chính xác là chuỗi được chỉ định \(S,Z,S,Z,\ldots\) với xác suất \(q=7^{-N}>0\) . Các khối là độc lập. Do đó, có thể không có khối \(m\) đầu tiên nào chứa chuỗi này:
$$\mathbb P(\text{kein Treffer in }m\text{ Blöcken})=(1-q)^m\longrightarrow0.$$
Vì vậy, với xác suất \(1\) một khối chết người sẽ xuất hiện vào một thời điểm nào đó, trừ khi trò chơi kết thúc trước thời điểm đó. Điều này cũng áp dụng với bất kỳ khoảng thời gian nào để suy nghĩ về nó và nhận thức đầy đủ về hậu quả. Điều này không dẫn đến thời gian trò chơi thực tế ngắn và chỉ khởi đầu tồi tệ không có nghĩa là thất bại: Hoạt ảnh sau đây hiển thị năm chuỗi hỗn hợp được tính toán trước, mỗi chuỗi sẽ đạt đến một bảng trống sau chín vị trí tháp không thay đổi. Cô ấy không phải là một bot Tetris phổ quát.