اللغز الرياضي داخل لعبة إطلاق النار الأسطورية في التسعينيات Quake 3

لم يكن الأمر سهلاً على مطوري الألعاب في التسعينيات. نظرًا لأن قدراتهم الحاسوبية كانت محدودة للغاية، كان عليهم كتابة التعليمات البرمجية الخاصة بهم بأكبر قدر ممكن من الكفاءة. لنأخذ على سبيل المثال لعبة إطلاق النار من منظور الشخص الأول Quake III Arena، والتي تسمى عادةً Quake 3، حيث يتنقل اللاعبون في عالم ثلاثي الأبعاد، لذلك كان على المبرمجين العثور على أذكى الطرق للتعامل مع الرسومات ثلاثية الأبعاد والحسابات المرتبطة بها.

تم إصدار Quake 3 عام 1999 وتعتبر واحدة من أفضل ألعاب الكمبيوتر في وقتها. وكان لها تأثير دائم على الصناعة. لم يكن هذا الإرث بسبب القصة، بل لأن Quake 3 كانت واحدة من أولى ألعاب إطلاق النار من منظور الشخص الأول متعددة اللاعبين. يمكن للاعبين توصيل أجهزة الكمبيوتر الخاصة بهم عبر كابلات الشبكة أو الإنترنت للمنافسة في الوقت الفعلي.

ترك رمز اللعبة علامة أيضًا. لقد تضمنت خوارزمية فعالة للغاية لا تزال تدهش الخبراء وتثير فضول العلماء.

حول دعم الصحافة العلمية

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

رمز غريب

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

إذا طلبت منك حساب الجذر التربيعي العكسي لـ 26 بدون آلة حاسبة، فمن المحتمل أن تظل عالقًا لفترة من الوقت – وبصراحة، كنت سأفعل ذلك أيضًا. وبالعودة إلى التسعينيات، واجهت أجهزة الكمبيوتر نفس التحدي. وعلى الرغم من قدرتهم على معالجة الأرقام، إلا أن العملية تطلبت قدرًا كبيرًا من قوة المعالجة، وهو ما قد يعني أن الحساب يستغرق الكثير من الوقت. كانت إحدى المشاكل هي الجذر التربيعي نفسه؛ آخر كان التقسيم. ولهذا السبب بحث مبرمجو Quake 3 عن طريقة أفضل للعثور على هذا الجذر التربيعي العكسي. وبالفعل، كشفت شفرة المصدر الخاصة بهم عن حل مبتكر.

الأمر المذهل هو أن المطورين لم يعلنوا أبدًا عن حيلتهم. إذا لم يكن كود مصدر Quake 3 مفتوح المصدر، فربما ظلت طريقتهم مخفية إلى الأبد. ولكن بمجرد إصداره، لاحظ المتحمسون الفضوليون ذلك. عندما اكتشفوا مقتطف التعليمات البرمجية لحساب الجذر التربيعي العكسي، أصيبوا بالحيرة – كان من الصعب متابعته، ولم تكن التعليقات المصاحبة للمطورين مفيدة بشكل خاص. ولكن تدريجيًا اكتشف الناس كيفية عمل الكود.

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

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

لا شيء من هذا يعتبر جديدا أو جديدا. لكن الأمر المثير للإعجاب هو أنه عادة ما تكون هناك حاجة إلى أربع إلى خمس تكرارات للعملية قبل أن تكون النتيجة قريبة بدرجة كافية من الحل الفعلي. تتطلب هذه العملية الكثير من القوة الحاسوبية. في Quake 3، تم اختيار قيمة البداية – أي العدد المقدر المستخدم في الخطوة الأولى من العملية – بذكاء بحيث لا يلزم سوى خطوة تحسين واحدة فقط.

البحث عن رقم سحري

تتوافق خطوات التحسين مع ما يسمى بطريقة نيوتن-رافسون، والتي تقارب القيم التي تنتج عندها الوظيفة ناتجًا يساوي 0، أو جذر الوظائف، عبر العديد من التكرارات. قد يبدو هذا غير بديهي في البداية، حيث أننا نريد حساب الجذر التربيعي العكسي وليس أي صفر فقط. لكن المبرمجين يستخدمون خدعة: فهم يحددون الوظيفة التي سيتم تقريبها على أنها الفرق بين قيمة التقدير الأولية والنتيجة الفعلية. ومن خلال طريقة نيوتن-رافسون، يصبح الخطأ أصغر تدريجيًا، مما يسمح للمرء بالاقتراب أكثر من الحل الدقيق.

للتفكير في ذلك، تخيل أنك تريد حساب الجذر التربيعي العكسي لـ 2.5. تبدأ الخوارزمية بتخمين معين: لنفترض 3.1. لتحديد الفرق عن الحل الفعلي، يمكنك تربيع القيمة الأولية وتقسيم واحد على النتيجة. إذا كان 3.1 هو الجذر التربيعي العكسي لـ 2.5، فإن 1 مقسومًا على 3.1 تربيع سيكون 2.5. النتيجة الفعلية هي 0.1. وبالتالي فإن الفرق هو 2.4.

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

المفتاح هو كيفية حساب القيمة الأولية لخطوات نيوتن. تعمل خوارزمية الطريقة بشكل أساسي في ثلاث خطوات:

1. خذ الرقم المحدد الذي سيتم حساب جذره التربيعي العكسي وقم بتحويله إلى عنوان الذاكرة المقابل (موقع في البيانات المخزنة على الكمبيوتر).

2. يتم خفض هذه القيمة إلى النصف وطرحها من القيمة السداسية العشرية 0x5f3759df. هذه هي القيمة الأولية لطريقة نيوتن.

3. بعد ذلك، قم بتنفيذ خطوة نيوتن.

والأمر الغامض بشكل خاص هو السلسلة المشفرة 0x5f3759df، والتي دخلت منذ ذلك الحين في تاريخ علوم الكمبيوتر باسم “الرقم السحري”. وهذا هو السبب وراء ضرورة تكرار واحد فقط للحصول على حل تقريبي للجذر التربيعي العكسي الذي ينتج عنه خطأ بنسبة 0.175 بالمائة على الأكثر.

وبمجرد توفر كود البرنامج كمصدر مفتوح، حير الخبراء حول أصل هذا الرقم السحري. في بحث تقني نُشر عام 2003، كتب عالم الكمبيوتر كريس لومونت: “من أين تأتي هذه القيمة، ولماذا يعمل الكود؟”

الرقم الست عشري 0x5f3759df يتوافق مع 1,597,463,007 بالتدوين العشري. من خلال تحليل الخطوات الفردية لرمز البرنامج، أدرك لومونت أنه يمكنه الحصول على 1,597,463,007 من خلال حسابات معينة. ولجعل هذه العملية الحسابية أبسط، إليك طريقة لتمثيل العملية الحسابية المعنية:

القيم ³⁄₂، 2²³ و127 تأتي من تحويل تمثيلات الأرقام إلى C. لكن أصل 0.0450465 أقل وضوحًا.

قام لومونت رياضيًا بالتحقق من القيمة التي تعطي النتيجة المثلى للمدخلات المختلفة. بمعنى آخر: ما هي قيمة البداية التي تقترب بشكل أفضل من الجذر التربيعي العكسي وبالتالي يجب أن تؤدي إلى أصغر خطأ؟ ووصل إلى قيمة 1,597,465,647 وهي تقريباً:

يتوافق هذا مع القيم الموجودة في كود مصدر Quake 3. والنتيجة قريبة جدًا من القيم الموجودة هناك.

عندما قارن لومونت نتائجه مع النتائج الأصلية، واجه مفاجأة. في خطوتين من طريقة نيوتن-رافسون، كان الثابت المحسوب يعمل بشكل أفضل: الحد الأقصى للخطأ المحتمل كان أصغر من القيمة الموجودة في الكود الأصلي. كتب لومونت: “ومع ذلك، فمن المثير للدهشة، أنه بعد تكرار نيوتن مرة واحدة، أصبح الحد الأقصى للخطأ النسبي أعلى”. “مما يثير السؤال مرة أخرى: كيف تم اشتقاق ثابت الكود الأصلي؟”

في حساباته، لم يفكر عالم الكمبيوتر إلا في الرقم الذي سيعطي نظريًا أفضل قيمة ممكنة، متجاهلاً عدد خطوات نيوتن. بحثًا عن ثابت أفضل، كرر لومونت حساباته وقام بالتحسين للحصول على أفضل حل ممكن لخطوة نيوتن واحدة. ووصل إلى قيمة 1,597,463,174 وهي تقريباً:

وعندما وضع هذه النتيجة تحت الاختبار العملي، فقد أسفرت في الواقع عن نتائج أفضل قليلاً من الرقم السحري الموجود في كود Quake 3.

وأشار لومونت في ورقته إلى أنه نظرًا لأن كلا الثابتين تقريبيان، فإن أيًا منهما يعد خيارًا جيدًا في الممارسة العملية. وأضاف أنه يأمل في مقابلة المؤلف الأصلي للثابت لمعرفة كيفية اشتقاق الرقم السحري.

بدأت المجتمعات عبر الإنترنت في البحث بلا هوادة عن هذا الشخص الغامض. كان عالم الكمبيوتر Rys Sommefeldt مكرسًا بشكل خاص لهذا الجهد، وهو أول من اتصل بجون كارماك، المطور الرئيسي للعبة Quake 3. ولم يكن كارماك متأكدًا من هوية من قام بترميز هذا المقتطف ولم يكن بإمكانه سوى تقديم التخمينات.

اتصل سومفيلدت ببعض أبرز المطورين في التسعينيات، الذين اقترح كل منهم مؤلفين محتملين آخرين دون المطالبة بالتأليف لأنفسهم. ويبدو الآن أن جريج والش، الذي عمل لدى شركة تصنيع أجهزة الكمبيوتر Ardent Computer في أواخر الثمانينات، هو من أدخل الرقم السحري إلى خوارزمية الجذر التربيعي العكسي. ثم وجدت طريقها إلى خوارزمية Quake 3 عبر عدة أفراد آخرين. ولكن كيف تم تحديد الرقم السحري بالضبط لا يزال غير واضح حتى يومنا هذا.

هذا ليس نتيجة مرضية بشكل خاص. ومع ذلك، فإن قصة كود Quake 3 – أو على الأقل الجزء الذي يدور حول الجذر التربيعي العكسي – رائعة للغاية. إنه لأمر مدهش مقدار الجهد والقدرات العقلية التي بذلت في البرمجة الفعالة في ذلك الوقت، وهو اتجاه غالبًا ما يتم تجاهله اليوم بفضل قوة الحوسبة الحالية.

ظهرت هذه المقالة في الأصل في سبيكتروم دير فيسنشافت وتم استنساخها بإذن.