งานวิจัยฉบับใหม่ได้ตอบคำถามที่ค้างคาในวงการวิทยาการคอมพิวเตอร์มานานด้วยการพิสูจน์ว่า Tetris ยังคงมีความยากทางการคำนวณแม้เมื่อเล่นบนกระดานเกมที่เล็กอย่างน่าแปลกใจ การค้นพบนี้ตอบคำถามที่ทำให้นักวิจัยงงงวยมากกว่า 15 ปีเกี่ยวกับความซับซ้อนทางคณิตศาสตร์ของเกมปริศนาอันเป็นที่รักนี้
ปริศนาความซับซ้อนที่เล็กลง
ทีมวิจัยแสดงให้เห็นว่า Tetris ยังคงมีสถานะ NP-complete แม้เมื่อจำกัดให้เล่นบนกระดานที่มีเพียง 8 คอลัมน์หรือ 4 แถว นี่เป็นสิ่งที่น่าทึ่งเพราะแสดงให้เห็นว่าความยากโดยธรรมชาติของเกมไม่ได้มาจากการมีพื้นที่เล่นที่กว้างใหญ่ แม้บนกระดานเล็กๆ เหล่านี้ การกำหนดวิธีที่เหมาะสมที่สุดในการเล่นลำดับชิ้นส่วนที่กำหนดยังคงยากเท่ากับปัญหาที่ท้าทายที่สุดในวิทยาการคอมพิวเตอร์
นักวิจัยใช้เทคนิคทางคณิตศาสตร์ที่เรียกว่า reduction from 3-PARTITION ซึ่งเกี่ยวข้องกับการจัดเรียงองค์ประกอบลงในภาชนะที่มีขนาดเท่ากันอย่างชาญฉลาด พวกเขาปรับปรุงวิธีการก่อนหน้าด้วยการหาวิธีที่ดีกว่าในการจัดเรียงถังทางคณิตศาสตร์เหล่านี้บนกระดานที่มีขนาดจำกัด
หมายเหตุ: NP-complete หมายถึงกลุ่มของปัญหาที่เชื่อว่าต้องใช้เวลาแบบเอ็กซ์โพเนนเชียลในการแก้ไข หมายความว่าเวลาที่ต้องการจะเพิ่มขึ้นอย่างรวดเร็วมากเมื่อขนาดปัญหาเพิ่มขึ้น
ผลลัพธ์ความซับซ้อนของ Tetris จำแนกตามขนาดกระดาน:
- 8+ คอลัมน์: NP-complete (ยากต่อการคำนวณ)
- 4+ แถว: NP-complete (ยากต่อการคำนวณ)
- 2 คอลัมน์หรือน้อยกว่า: แก้ไขได้ในเวลาพหุนาม (ง่าย)
- 1 แถว: แก้ไขได้ในเวลาพหุนาม (ง่าย)
เมื่อ Tetris กลายเป็นเรื่องง่าย
ในด้านตรงข้าม การศึกษาพบว่า Tetris เวอร์ชันที่แคบมากสามารถแก้ไขได้อย่างมีประสิทธิภาพ เมื่อกระดานเกมมีเพียง 2 คอลัมน์หรือ 1 แถว นักวิจัยพิสูจน์ว่ามันกลายเป็นปัญหาที่แก้ได้ในเวลา polynomial นี่สร้างขอบเขตที่น่าสนใจซึ่ง Tetris เปลี่ยนจากง่ายเป็นยากขึ้นอยู่กับมิติของกระดาน
การอภิปรายในชุมชนรอบงานวิจัยนี้เน้นผลกระทบเชิงปฏิบัติบางประการ ผู้สังเกตการณ์บางคนสังเกตว่าแม้ผลลัพธ์เชิงทฤษฎีจะน่าทึ่ง แต่การใช้งาน Tetris ในโลกแห่งความจริงมักใช้วิธีการสุ่มที่แตกต่างกันซึ่งส่งผลต่อความยากของเกมในแบบที่เกินกว่าความซับซ้อนทางการคำนวณล้วนๆ
รูปแบบกระดาน Tetris มาตรฐาน:
- Tetris คลาสสิก: 10 คอลัมน์ × 20 แถว
- Tetris Jr.: 8 คอลัมน์
- Tetris Wristwatch: 6 คอลัมน์
- รูปแบบความสูงที่แตกต่าง: 16-24 แถว
- รูปแบบความกว้างที่แตกต่าง: 6-20 คอลัมน์ในเวอร์ชันต่างๆ
ความสับสนเรื่องวันที่และกระบวนการทางวิชาการ
การอภิปรายที่น่าขบขันเกิดขึ้นรอบรายละเอียดการตีพิมพ์ของเอกสาร โดยสมาชิกในชุมชนสังเกตเห็นความไม่สอดคล้องในส่วนท้ายลิขสิทธิ์ที่แสดงปี 1992 แม้ว่างานวิจัยจะดำเนินการประมาณปี 2019-2020 สิ่งนี้จุดประกายการสนทนาเกี่ยวกับกระบวนการตีพิมพ์ทางวิชาการและวิธีที่เอกสารที่ส่งมาแตกต่างจากเวอร์ชันสุดท้ายที่ตีพิมพ์ โดยมีหมายเลขเล่มและรายละเอียดหน้าที่หายไปจะถูกเติมในภายหลังระหว่างการตรวจสอบโดยผู้ทรงคุณวุฒิ
งานวิจัยขยายไปเกินกว่า Tetris แบบคลาสสิกเพื่อตรวจสอบชิ้นปริศนาที่ใหญ่กว่าและการกำหนดค่ากระดานที่แตกต่างกัน โดยให้กรอบงานทางคณิตศาสตร์ที่ครอบคลุมสำหรับการเข้าใจเกมปริศนาบล็อกตกลงมา งานนี้เชื่อมช่องว่างระหว่างการเล่นเกมเพื่อความบันเทิงและทฤษฎีการคำนวณที่จริงจัง แสดงให้เห็นว่าแม้เกมที่ดูเรียบง่ายก็สามารถซ่อนความซับซ้อนทางคณิตศาสตร์ที่ลึกซึ้งได้