นักวิจัยที่อิตาลีพิสูจน์ว่าเกมแพ็ก-แมน (Pac-Man) ที่เราเคยเล่นกันนั้นแท้จริงแล้วเป็นปัญหาชนิด NP-hard Giovanni Viglietta จากมหาวิทยาลัยแห่งปิซาทำวิจัยจำแนกเกมคลาสสิก 13 เกมเป็นปัญหาชนิดต่าง ๆ เช่น แพ็ก-แมนหรือสตาร์คราฟต์ (StarCraft) เป็น NP-hard ส่วนปรินซ์ออฟเปอร์เชีย (Prince of Persia) นั้นเป็น PSPACE-complete ในขณะที่ดูม (Doom) เป็นแบบ PSPACE-hard สำหรับคนเกิดไม่ทัน แพ็ก-แมนเป็นเกมเรโทรโดยบริษัท Namco ที่ผู้เล่นอวตารเป็นตัวละครทรงกลมสีเหลืองอ้าปากงับแพ็กดอต เมื่อกินแพ็กดอตหมดก็จะข้ามไปด่านถัดไป […]
Read more