الألعاب التي تلهم علماء الرياضيات: تتريس وسوبر ماريو والشطرنج الكمي

تماثيل رائعة

تم إنشاء لعبة تتريس الأسطورية في الثمانينات من القرن الماضي على يد أليكسي باجيتنوف. عالم رياضيات

عمل في مركز الكمبيوتر بأكاديمية العلوماتحاد الجمهوريات الاشتراكية السوفياتية: درس الذكاء الاصطناعي، والتعرف الحاسوبي على الكلام البشري، وفي الوقت نفسه كان مهتماً بالألغاز. ولدت فكرة تتريس بفضل لعبة اللوحة "بنتامينو" - قرر باجيتنوف إنشاء نسخة من اللعبة اللوحية للكمبيوتر، لكنه استقر على خيار آخر، حيث تتكون العناصر من أربعة مربعات (بدلاً من خمسة) ، كما في "بنتامينو").

أصدر باجيتنوف أحد الإصدارات الأولى من اللعبة على الكمبيوتر المصغر السوفيتي "Electronics-60"

الهدف من لعبة تتريس هو التحرك وتدوير السقوطأشكال هندسية لتكوين صفوف كاملة في أسفل الملعب، وتسجيل النقاط. من الناحية العملية، هذه لعبة تعتمد على سرعة رد الفعل والتركيز، لكن علماء الرياضيات ينظرون إلى هذا من زاوية مختلفة. قام العلماء بتحليل التعقيد الحسابي لخوارزمية تتريس وقرروا أنها تنتمي إلى فئة NP-Complete - متعددة الحدود غير حتمية؛ لا توجد خوارزميات حل فعالة لمثل هذه الأمور.

المشكلة الرئيسية هي أن مقدارلإيجاد حل للحساب ينمو بشكل كبير مع زيادة عدد المتغيرات (حجم المشكلة). على سبيل المثال ، إذا كان هناك أربعة معلمات ، فستكون هناك حاجة إلى 16 تكرارًا ، وإذا كان 100 ، فعندئذٍ 2 ^ 100 ، وهو أكثر من ذرات في الكون (!). يمكن للكمبيوتر العادي ، عند ضبطه بشكل صحيح ، إجراء عدة مليارات من هذه التكرارات في الثانية. وفقًا لذلك ، يمكنه بسهولة حل مشكلات NP الصغيرة عن طريق التعداد ، وعندما تصبح المتغيرات أكثر من 15 بشكل ملحوظ ، سيتوقف عن حلها.

أما تتريس.حجم مهمة اللعبة الكلاسيكية صغير: في خطوة منفصلة ، يوجد منظر طبيعي حالي في الزجاج (حقل اللعب) - هذه معلمة ، ولا تؤثر بشكل كبير على مقدار الحسابات. توجد معلومات حول الشكل الحالي والشكل التالي - هاتان مجموعتان من المتغيرات: لكل رقم أربعة اتجاهات كحد أقصى (على الرغم من المربع - واحد فقط) في الفضاء و 10 إحداثيات كحد أقصى لـ "هبوط" الأرقام. كل حركة بها 40 حالة ، اثنتان بها 1600 ، لا يوجد مزيد من المعلومات ، هذه مشكلة NP صغيرة. على الرغم من أن Tetris يمكن أن تكون معقدة: قم بزيادة عدد الخلايا إلى 100 وتأكد من أن اللاعب لا يعرف فقط ما سيكون الرقم التالي ، ولكن أيضًا مائة من الأرقام التالية ، فستكون هناك مشاكل.

أنت لا تعرف ألعاب NP الكاملة الأخرى أيضًامن الإشاعات: كاسحة ألغام، سودوكو، العلامة وحتى نسخة غير تجارية من سوبر ماريو. على الرغم من بساطة قواعدها، في ظل ظروف معينة، يزداد حجمها، لا يستطيع الكمبيوتر تقديم حل مثالي. لماذا يهتم علماء الرياضيات؟ نظرًا لأن اختيار أفضل طريق أو تحسين العملية أو الجدول الزمني يعد أيضًا من مشكلات فئة NP. 

بدا "ماريو" الكلاسيكي هكذا

تعتبر الألعاب المنطقية بمثابة أرض اختبار مناسبة للغايةاختبار الخوارزميات وتنفيذ البرمجيات الخاصة بهم. غالبًا ما تكون الألغاز "نقية"، دون أنواع مختلفة من الاستثناءات للقواعد المتأصلة في المشكلات العملية. تحتوي مساحة الحالة لمثل هذه المشكلات على بُعد قابل للتعديل، ولا تتغير الخصائص عند القياس (على سبيل المثال، العلامات 2x2، 4x4، 3x6). يتم وصف جميع الدول بنفس الطريقة. كما أن الوصف الرياضي للألغاز، كقاعدة عامة، ليس معقدًا مثل مشاكل الحياة.

زمن اللعب "الكمومية"

نفس المشكلة فيما يتعلق بحقيبة الظهر (كيفية ملاءمة المزيد من الأشياءفي مساحة محدودة) تذكرنا تمامًا بلعبة تتريس، وستكون النتيجة الفعالة مفيدة لشركات الخدمات اللوجستية، لأنها ستسمح لها بعدم إهدار الموارد. إذا تم العثور على خوارزمية "سريعة متعددة الحدود" لأي من هذه المسائل أو الألعاب، فيمكن حل أي مشكلة أخرى من فئة NP بنفس السرعة. من الناحية النظرية، ستساعد أجهزة الكمبيوتر الكمومية في ذلك، ولكن حتى الآن لا يوجد سوى نماذج أولية لأجهزة الكمبيوتر المستقبلية هذه. وفي عام 2018، تم اختراع مفهوم جديد لوصف الحالة الحالية لإنتاج المعالجات الكمومية - عصر NISQ (عصر الكم المتوسط ​​الحجم الصاخب)، أو عصر التقنيات دون الكم.

بينما يعمل العلماء على تحسين الكمالعمليات ، يبحث المسؤولون التنفيذيون في الشركة عن نظائرها الحديثة التي تساعد في تحسين عمل الإنتاج. أصبح مثل هذا "البديل" خوارزميات مستوحاة من الكم والتي تجد الحل الأمثل بنسبة 95-99٪ على أجهزة الكمبيوتر التقليدية. في روسيا ، تقوم QuSolve بذلك - المهام التي تعمل عليها الشركة تنتمي إلى فئة NP ، ويقوم علماء الرياضيات بتطوير وتحسين الخوارزميات لحل مشاكل الأعمال. في QuSolve ، لاختبار أداة الحل الخاصة بهم (solver) ، استخدموا العلامات ، والتي ساعدت في العثور على بعض الأخطاء في الخوارزمية وإضافة إضافات إلى واجهة حزمة البرامج.

هل العلماء المعاصرون لا يفعلون شيئًا حقًا سوىهل تفكر في كيفية تحسين وتحسين كل شيء؟ بالطبع لا. وفي أوقات فراغهم، يواصلون اختراع الألعاب. لقد تمكن المطورون بالفعل من تحويل معظم الألعاب إلى NP، مما أضاف القليل من سحر الظواهر الفيزيائية الكمومية. 

هكذا ظهرت التقنيات الكمومية خلال السنوات العشر الماضية.لعبة الداما، والمعركة البحرية الكمومية، وتيك تاك تو الكم. اكتسب الشطرنج الكمي شعبية خاصة، حيث تقام البطولات، ويتم منح البطل لقب Grandmaster. معظم "الألعاب الكمومية" الجديدة مبنية على المبدأ الأساسي لميكانيكا الكم - التراكب.

على سبيل المثال ، يمكن أن تكون قطع الشطرنجعدة أماكن على اللوحة في نفس الوقت ، مما يعني أنه من الصعب الدفاع والهجوم - وهذا يجعل اللعبة غير متوقعة ومذهلة. في عام 2016 ، قاموا بتصوير فيلم قصير أظهر لعبة الشطرنج الكمي بين ستيفن هوكينغ وبول رود ، الممثل المعروف عن دوره في فيلم Ant-Man في Marvel Cinematic Universe.

لقطة شاشة اللعبة. هذا ما بدت عليه اللوحة عبر الإنترنت في اللعبة بين هوكينج ورود. ثم تغلب الممثل على الفيزيائي الأسطوري

لا نعرف ما إذا كانت هذه الألعاب ستكون هكذا في المستقبلشائعة مثل لعبة tic-tac-toe، وtetris، وtag، ولكنها بالتأكيد ستلهم علماء الرياضيات لإنشاء خوارزميات فريدة لحل مشكلات العمل العملية وتطوير التكنولوجيا. ليس هناك شك في ذلك. 

قراءة المزيد:

لقد وجد العلماء أن شكل مجرة ​​درب التبانة ليس على الإطلاق ما كنا نعتقده طوال الوقت

تم العثور على اثنين من الأرض الفائقة على حافة المنطقة الصالحة للسكن: أحدهما لديه درجة حرارة مريحة

العثور على ثقب أسود يدمر سجل نجم بالقرب من الأرض