Sebuah makalah penelitian baru telah menyelesaikan pertanyaan yang sudah lama ada dalam ilmu komputer dengan membuktikan bahwa Tetris tetap sulit secara komputasional bahkan ketika dimainkan pada papan permainan yang sangat kecil. Temuan ini menjawab pertanyaan yang telah membingungkan para peneliti selama lebih dari 15 tahun tentang kompleksitas matematis dari permainan puzzle yang digemari ini.
Misteri Kompleksitas Menjadi Lebih Kecil
Tim peneliti menunjukkan bahwa Tetris mempertahankan status NP-complete-nya bahkan ketika dibatasi pada papan dengan hanya 8 kolom atau 4 baris. Ini luar biasa karena menunjukkan bahwa kesulitan inheren permainan tidak berasal dari memiliki area bermain yang besar. Bahkan pada papan sekecil ini, menentukan cara optimal untuk memainkan urutan potongan tertentu tetap sesulit beberapa masalah paling menantang dalam ilmu komputer.
Para peneliti menggunakan teknik matematis yang disebut reduksi dari 3-PARTITION, yang melibatkan pengepakan elemen secara cerdas ke dalam wadah berukuran sama. Mereka memperbaiki metode sebelumnya dengan menemukan cara yang lebih baik untuk mengatur wadah matematis ini pada ukuran papan yang terbatas.
Catatan: NP-complete merujuk pada kelas masalah yang diyakini memerlukan waktu eksponensial untuk diselesaikan, artinya waktu yang dibutuhkan tumbuh sangat cepat seiring bertambahnya ukuran masalah.
Hasil Kompleksitas Tetris berdasarkan Ukuran Papan:
- 8+ kolom: NP-complete (secara komputasional sulit)
- 4+ baris: NP-complete (secara komputasional sulit)
- 2 kolom atau kurang: Dapat diselesaikan dalam waktu polinomial (mudah)
- 1 baris: Dapat diselesaikan dalam waktu polinomial (mudah)
Ketika Tetris Menjadi Mudah
Di sisi lain, studi ini menemukan bahwa versi Tetris yang sangat sempit sebenarnya dapat diselesaikan secara efisien. Ketika papan permainan hanya memiliki 2 kolom atau 1 baris, para peneliti membuktikan bahwa permainan menjadi dapat diselesaikan dalam waktu polinomial. Ini menciptakan batas yang menarik di mana Tetris bertransisi dari mudah ke sulit berdasarkan dimensi papan.
Diskusi komunitas seputar penelitian ini telah menyoroti beberapa implikasi praktis. Beberapa pengamat mencatat bahwa meskipun hasil teoretis ini menarik, implementasi Tetris di dunia nyata sering menggunakan metode randomisasi yang berbeda yang mempengaruhi kesulitan gameplay dengan cara yang melampaui kompleksitas komputasional murni.
Variasi Papan Tetris Standar:
- Tetris Klasik: 10 kolom × 20 baris
- Tetris Jr.: 8 kolom
- Tetris Wristwatch: 6 kolom
- Variasi tinggi: 16-24 baris
- Variasi lebar: 6-20 kolom di berbagai edisi
Kebingungan Tanggal dan Proses Akademik
Diskusi sampingan yang menghibur muncul seputar detail publikasi makalah, dengan anggota komunitas memperhatikan ketidaksesuaian dalam footer hak cipta yang menunjukkan 1992 meskipun penelitian dilakukan sekitar 2019-2020. Ini memicu percakapan tentang proses penerbitan akademik dan bagaimana makalah yang diajukan berbeda dari versi akhir yang diterbitkan, dengan nomor volume dan detail halaman yang hilang diisi kemudian selama peer review.
Penelitian ini meluas melampaui Tetris klasik untuk memeriksa potongan puzzle yang lebih besar dan konfigurasi papan yang berbeda, menyediakan kerangka matematis yang komprehensif untuk memahami permainan puzzle blok jatuh. Karya ini menjembatani kesenjangan antara permainan rekreasional dan teori komputasional serius, menunjukkan bagaimana bahkan permainan yang tampak sederhana dapat menyimpan kompleksitas matematis yang mendalam.