Một bài nghiên cứu mới đã giải quyết một câu hỏi tồn tại lâu đời trong khoa học máy tính bằng cách chứng minh rằng Tetris vẫn khó tính toán ngay cả khi chơi trên những bàn chơi nhỏ một cách đáng ngạc nhiên. Những phát hiện này giải đáp các câu hỏi đã làm bối rối các nhà nghiên cứu trong hơn 15 năm về độ phức tạp toán học của trò chơi giải đố được yêu thích này.
Bí ẩn độ phức tạp trở nên nhỏ hơn
Nhóm nghiên cứu đã chứng minh rằng Tetris vẫn duy trì trạng thái NP-complete ngay cả khi bị giới hạn trên các bàn chơi chỉ có 8 cột hoặc 4 hàng. Điều này thật đáng chú ý vì nó cho thấy độ khó vốn có của trò chơi không đến từ việc có một sân chơi lớn. Ngay cả trên những bàn chơi nhỏ bé này, việc xác định cách tối ưu để chơi một chuỗi các mảnh ghép cho trước vẫn khó như một số vấn đề thách thức nhất trong khoa học máy tính.
Các nhà nghiên cứu đã sử dụng một kỹ thuật toán học gọi là rút gọn từ 3-PARTITION, bao gồm việc khéo léo đóng gói các phần tử vào các container có kích thước bằng nhau. Họ đã cải thiện các phương pháp trước đó bằng cách tìm ra những cách tốt hơn để sắp xếp những thùng toán học này trên các kích thước bàn chơi bị hạn chế.
Lưu ý: NP-complete đề cập đến một lớp các vấn đề được cho là cần thời gian hàm mũ để giải quyết, có nghĩa là thời gian cần thiết tăng lên cực kỳ nhanh khi kích thước vấn đề tăng.
Kết quả độ phức tạp Tetris theo kích thước bảng:
- 8+ cột: NP-complete (khó tính toán)
- 4+ hàng: NP-complete (khó tính toán)
- 2 cột trở xuống: Có thể giải quyết trong thời gian đa thức (dễ)
- 1 hàng: Có thể giải quyết trong thời gian đa thức (dễ)
Khi Tetris trở nên dễ dàng
Mặt khác, nghiên cứu phát hiện rằng các phiên bản Tetris cực kỳ hẹp thực sự có thể được giải quyết một cách hiệu quả. Khi bàn chơi chỉ có 2 cột hoặc 1 hàng, các nhà nghiên cứu đã chứng minh nó trở thành có thể giải quyết trong thời gian đa thức. Điều này tạo ra một ranh giới thú vị nơi Tetris chuyển từ dễ sang khó dựa trên kích thước bàn chơi.
Cuộc thảo luận cộng đồng xung quanh nghiên cứu này đã làm nổi bật một số ý nghĩa thực tế. Một số quan sát viên lưu ý rằng trong khi các kết quả lý thuyết rất hấp dẫn, các triển khai Tetris trong thế giới thực thường sử dụng các phương pháp ngẫu nhiên hóa khác nhau ảnh hưởng đến độ khó của trò chơi theo những cách vượt ra ngoài độ phức tạp tính toán thuần túy.
Các Biến Thể Bàn Cờ Tetris Tiêu Chuẩn:
- Tetris Cổ điển: 10 cột × 20 hàng
- Tetris Jr.: 8 cột
- Tetris Wristwatch: 6 cột
- Biến thể chiều cao: 16-24 hàng
- Biến thể chiều rộng: 6-20 cột trên các phiên bản khác nhau
Nhầm lẫn về ngày tháng và quy trình học thuật
Một cuộc thảo luận phụ thú vị đã nổi lên xung quanh các chi tiết xuất bản của bài báo, với các thành viên cộng đồng nhận thấy sự khác biệt trong chân trang bản quyền hiển thị năm 1992 mặc dù nghiên cứu được thực hiện vào khoảng 2019-2020. Điều này đã khơi mào các cuộc trò chuyện về quy trình xuất bản học thuật và cách các bài báo được nộp khác với các phiên bản cuối cùng được xuất bản, với các số tập và chi tiết trang bị thiếu được điền vào sau trong quá trình đánh giá đồng nghiệp.
Nghiên cứu mở rộng ra ngoài Tetris cổ điển để xem xét các mảnh ghép lớn hơn và các cấu hình bàn chơi khác nhau, cung cấp một khung toán học toàn diện để hiểu các trò chơi giải đố khối rơi. Công trình này kết nối khoảng cách giữa trò chơi giải trí và lý thuyết tính toán nghiêm túc, cho thấy ngay cả những trò chơi có vẻ đơn giản cũng có thể ẩn chứa độ phức tạp toán học sâu sắc.