เกมที่สร้างแรงบันดาลใจให้กับนักคณิตศาสตร์: Tetris, Super Mario และหมากรุกควอนตัม

รูปแกะสลักที่ยอดเยี่ยม

Tetris ในตำนานถูกสร้างขึ้นในยุค 80 ของศตวรรษที่ผ่านมาโดย Alexey Pajitnov นักคณิตศาสตร์

ทำงานที่ศูนย์คอมพิวเตอร์ของ Academy of Sciencesสหภาพโซเวียต: ศึกษา AI การจดจำคำพูดของมนุษย์ด้วยคอมพิวเตอร์ และในขณะเดียวกันก็สนใจปริศนา แนวคิดของ Tetris เกิดขึ้นจากเกมกระดาน "Pentamino" - Pajitnov ตัดสินใจสร้างเวอร์ชันของเกมกระดานสำหรับคอมพิวเตอร์ แต่ตัดสินใจเลือกอีกทางเลือกหนึ่งซึ่งองค์ประกอบประกอบด้วยสี่ช่องสี่เหลี่ยม (แทนที่จะเป็นห้าช่อง) ดังเช่นใน “เพนตามิโน”)

Pajitnov เปิดตัวหนึ่งในเกมรุ่นแรกบนไมโครคอมพิวเตอร์โซเวียต "Electronics-60"

เป้าหมายของ Tetris คือการเคลื่อนที่และหมุนการล้มรูปทรงเรขาคณิตเพื่อสร้างแถวที่สมบูรณ์ที่ด้านล่างของสนามแข่งขันและให้คะแนน จากมุมมองเชิงปฏิบัติ นี่คือเกมแห่งความเร็วและสมาธิของปฏิกิริยา แต่นักคณิตศาสตร์มองจากมุมที่ต่างออกไป นักวิทยาศาสตร์วิเคราะห์ความซับซ้อนในการคำนวณของอัลกอริธึม Tetris และพิจารณาว่ามันอยู่ในคลาสของ NP-complete ซึ่งเป็นพหุนามที่ไม่สามารถกำหนดได้ ไม่มีอัลกอริธึมการแก้ปัญหาที่มีประสิทธิภาพสำหรับสิ่งเหล่านี้ 

ปัญหาสำคัญอยู่ที่จำนวนสำหรับการหาทางออกในการคำนวณนั้นเพิ่มขึ้นอย่างทวีคูณด้วยจำนวนตัวแปรที่เพิ่มขึ้น (ขนาดของปัญหา) ตัวอย่างเช่น หากมีสี่พารามิเตอร์ จำเป็นต้องมีการวนซ้ำ 16 ครั้ง และถ้าเป็น 100 ก็จะเท่ากับ 2 ^ 100 ซึ่งมากกว่าอะตอมในจักรวาล (!) คอมพิวเตอร์ทั่วไปสามารถทำซ้ำหลายพันล้านครั้งต่อวินาทีเมื่อได้รับการปรับแต่งอย่างเหมาะสม ดังนั้นเขาจึงสามารถแก้ปัญหา NP เล็กๆ ได้อย่างง่ายดายด้วยการแจงนับ และเมื่อตัวแปรกลายเป็นมากกว่า 15 อย่างเห็นได้ชัด เขาจะหยุดแก้ปัญหา

สำหรับ Tetrisขนาดงานของเกมคลาสสิคมีขนาดเล็ก: ในขั้นตอนที่แยกจากกันมีภูมิทัศน์ปัจจุบันในกระจก (สนามเด็กเล่น) - นี่คือพารามิเตอร์ไม่ส่งผลกระทบต่อจำนวนการคำนวณอย่างมีนัยสำคัญ มีข้อมูลเกี่ยวกับตัวเลขปัจจุบันและตัวเลขถัดไป - นี่คือตัวแปรสองกลุ่ม: สำหรับแต่ละตัวเลขมีการวางแนวในอวกาศได้สูงสุดสี่ (แม้ว่าจะเป็นสี่เหลี่ยมจัตุรัส - เพียงตัวเดียว) และพิกัด "ลงจอด" สูงสุด 10 พิกัด ตัวเลข. การย้ายแต่ละครั้งมี 40 สถานะ สองสถานะมี 1,600 ไม่มีข้อมูลเพิ่มเติม นี่เป็นปัญหา NP เล็กน้อย แม้ว่า Tetris อาจซับซ้อน: เพิ่มจำนวนเซลล์เป็น 100 และตรวจสอบให้แน่ใจว่าผู้เล่นไม่เพียงรู้ว่าตัวเลขต่อไปจะเป็นอย่างไร แต่ยังรวมถึงเซลล์ถัดไปอีกร้อยเซลล์ด้วย จากนั้นจะมีปัญหา

คุณไม่รู้จักเกม NP ที่สมบูรณ์เกมอื่นเช่นกันจากข่าวลือ: เรือกวาดทุ่นระเบิด, ซูโดกุ, แท็ก และแม้แต่ Super Mario เวอร์ชันที่ไม่ใช่เชิงพาณิชย์ แม้ว่ากฎจะเรียบง่าย แต่ภายใต้เงื่อนไขบางประการ มิติของมันจะเพิ่มขึ้น แต่คอมพิวเตอร์ก็ไม่สามารถเสนอวิธีแก้ปัญหาที่เหมาะสมได้ ทำไมนักคณิตศาสตร์ถึงสนใจ? เนื่องจากการเลือกเส้นทางที่ดีที่สุด การเพิ่มประสิทธิภาพกระบวนการหรือกำหนดเวลาก็เป็นปัญหาของคลาส NP เช่นกัน 

"มาริโอ" แบบคลาสสิกมีลักษณะเช่นนี้

เกมลอจิกเป็นพื้นที่ทดสอบที่สะดวกอย่างยิ่งอัลกอริธึมการทดสอบและการใช้งานซอฟต์แวร์ ปริศนาส่วนใหญ่มักจะ "บริสุทธิ์" โดยไม่มีข้อยกเว้นหลายประเภทสำหรับกฎที่มีอยู่ในปัญหาในทางปฏิบัติ พื้นที่สถานะของปัญหาดังกล่าวมีมิติที่ปรับได้ และคุณสมบัติไม่เปลี่ยนแปลงเมื่อปรับขนาด (ตัวอย่างเช่น แท็ก 2x2, 4x4, 3x6) รัฐทั้งหมดมีการอธิบายในลักษณะเดียวกัน ตามกฎแล้วคำอธิบายทางคณิตศาสตร์ของปริศนานั้นไม่ซับซ้อนเท่ากับปัญหาชีวิต

เวลาของของเล่น "ควอนตัม"

ปัญหาเดียวกันเกี่ยวกับกระเป๋าเป้ (วิธีใส่สิ่งของต่างๆ ให้มากขึ้น)ในพื้นที่จำกัด) ค่อนข้างชวนให้นึกถึงเกม Tetris และผลลัพธ์ที่มีประสิทธิภาพจะเป็นประโยชน์สำหรับบริษัทโลจิสติกส์ เพราะจะช่วยให้พวกเขาไม่เปลืองทรัพยากร หากพบอัลกอริธึม "เร็วพหุนาม" สำหรับปัญหาหรือเกมเหล่านี้ ปัญหาอื่น ๆ จากคลาส NP ก็สามารถแก้ไขได้เช่นเดียวกับ "เร็ว" ตามทฤษฎีแล้ว คอมพิวเตอร์ควอนตัมจะช่วยในเรื่องนี้ แต่จนถึงขณะนี้มีเพียงต้นแบบของคอมพิวเตอร์เหล่านี้ในอนาคตเท่านั้น ในปี 2018 แนวคิดใหม่ได้รับการคิดค้นขึ้นเพื่ออธิบายสถานะปัจจุบันของการผลิตโปรเซสเซอร์ควอนตัม - ยุค NISQ (ยุคควอนตัมระดับกลางที่มีเสียงดัง) หรือเวลาของเทคโนโลยีย่อยควอนตัม

ในขณะที่นักวิทยาศาสตร์กำลังทำงานเพื่อปรับปรุงควอนตัมกระบวนการ ผู้บริหารของบริษัทกำลังมองหาอะนาล็อกสมัยใหม่ที่ช่วยเพิ่มประสิทธิภาพการทำงานของการผลิต “สิ่งทดแทน” ดังกล่าวได้กลายเป็นอัลกอริทึมที่ได้รับแรงบันดาลใจจากควอนตัม ซึ่งพบวิธีแก้ปัญหาที่เหมาะสมที่สุด 95-99% ในคอมพิวเตอร์ทั่วไป ในรัสเซีย QuSolve กำลังทำสิ่งนี้ - งานที่บริษัทกำลังดำเนินการอยู่ในคลาส NP และนักคณิตศาสตร์พัฒนาและปรับปรุงอัลกอริทึมสำหรับการแก้ปัญหาทางธุรกิจ ใน QuSolve เพื่อทดสอบตัวแก้ปัญหา (ตัวแก้ปัญหา) พวกเขาใช้แท็กซึ่งช่วยค้นหาข้อผิดพลาดสองสามข้อในอัลกอริทึมและทำการเพิ่มส่วนต่อประสานของแพ็คเกจซอฟต์แวร์

นักวิทยาศาสตร์สมัยใหม่ไม่ได้ทำอะไรเลยนอกจากคุณกำลังคิดถึงวิธีปรับปรุงและเพิ่มประสิทธิภาพทุกอย่างหรือไม่? ไม่แน่นอน ในเวลาว่างพวกเขายังคงคิดค้นเกมต่อไป ผู้พัฒนาสามารถเปลี่ยนเกมส่วนใหญ่ให้เป็น NP ได้แล้ว โดยเพิ่มความมหัศจรรย์เล็กน้อยของปรากฏการณ์ทางกายภาพควอนตัม 

นี่คือลักษณะที่เทคโนโลยีควอนตัมปรากฏขึ้นในช่วง 10 ปีที่ผ่านมาหมากฮอส การต่อสู้ทางทะเลควอนตัม และโอเอกซ์ควอนตัม หมากรุกควอนตัมได้รับความนิยมเป็นพิเศษซึ่งมีการจัดทัวร์นาเมนต์และแชมป์จะได้รับรางวัลปรมาจารย์ "เกมควอนตัม" ใหม่ส่วนใหญ่สร้างขึ้นบนหลักการพื้นฐานของกลศาสตร์ควอนตัม - การซ้อนทับ

ตัวอย่างเช่นตัวหมากรุกสามารถเข้ามาได้หลายตำแหน่งบนกระดานในเวลาเดียวกัน ซึ่งหมายความว่าการป้องกันและการโจมตีทำได้ยากขึ้น ทำให้เกมคาดเดาไม่ได้และน่าตื่นเต้น ในปี 2559 พวกเขายังถ่ายทำหนังสั้นที่แสดงเกมควอนตัมหมากรุกระหว่าง Stephen Hawking และ Paul Rudd นักแสดงที่รู้จักกันในบทบาท Ant-Man ใน Marvel Cinematic Universe

ภาพหน้าจอของเกม นี่คือลักษณะของกระดานออนไลน์ในเกมระหว่างฮอว์คิงและรัดด์ จากนั้นนักแสดงก็เอาชนะนักฟิสิกส์ในตำนาน

เราไม่รู้ว่าเกมเหล่านี้จะเป็นแบบนี้ในอนาคตหรือไม่เป็นเรื่องธรรมดาเหมือนโอเอกซ์ เตตริส และแท็ก แต่สิ่งเหล่านี้จะเป็นแรงบันดาลใจให้นักคณิตศาสตร์สร้างอัลกอริธึมเฉพาะสำหรับการแก้ปัญหาทางธุรกิจในทางปฏิบัติและการพัฒนาเทคโนโลยีอย่างแน่นอน ไม่ต้องสงสัยเลย 

อ่านเพิ่มเติม:

รูปร่างของทางช้างเผือกไม่ได้เป็นอย่างที่เราคิดกันมาตลอด นักวิทยาศาสตร์ค้นพบ

พบซุปเปอร์เอิร์ธสองก้อนที่ขอบเขตเอื้ออาศัยได้ หนึ่งในนั้นมีอุณหภูมิกำลังสบาย

พบหลุมดำทำลายสถิติดาวใกล้โลก