لا شك أن أي شخص حصل على دورة أساسية في علوم الكمبيوتر قد أمضى وقتًا في تصميم خوارزمية الفرز – رمز يأخذ قائمة غير مرتبة بالعناصر ويضعها بترتيب تصاعدي أو تنازلي. إنه تحدٍ مثير للاهتمام لأن هناك العديد من الطرق للقيام بذلك ولأن الناس قد أمضوا الكثير من الوقت في اكتشاف كيفية حل هذا الأمر بشكل أكثر كفاءة.
يعتبر الفرز أساسيًا لدرجة أن الخوارزميات مدمجة في معظم المكتبات القياسية للغات البرمجة. وفي حالة مكتبة C ++ المستخدمة مع مترجم LLVM ، لم يتم التطرق إلى الكود لأكثر من عقد.
لكن مجموعة DeepMind AI التابعة لشركة Google قد طورت الآن أداة تعلم معزز يمكنها تطوير خوارزميات محسّنة للغاية دون أن يتم تدريبها أولاً على أمثلة التعليمات البرمجية البشرية. كانت الحيلة هي تكوينه للتعامل مع البرمجة مثل لعبة.
إنها مجرد لعبة
DeepMind ، من بين أمور أخرى ، معروف بتطوير البرامج التي تعلم نفسها ممارسة الألعاب. لقد أثبت هذا النهج نجاحه الكبير ، حيث قهر ألعاب متنوعة مثل الشطرنج ، يذهبو ستار كرافت. بينما تختلف التفاصيل اعتمادًا على اللعبة التي يتعامل معها ، يتعلم البرنامج من خلال اللعب بنفسه ويكتشف الخيارات التي تسمح له بزيادة النتيجة إلى الحد الأقصى.
نظرًا لأنه لم يتم تدريبه على الألعاب التي يلعبها البشر ، يمكن لنظام DeepMind اكتشاف أساليب للألعاب التي لم يفكر بها البشر. بالطبع ، نظرًا لأنه يلعب دائمًا ضد نفسه ، فهناك حالات طور فيها نقاط عمياء يمكن للبشر استغلالها.
هذا النهج وثيق الصلة بالبرمجة. تكتب النماذج اللغوية العظيمة رمزًا فعالًا لأنها شاهدت العديد من الأمثلة البشرية. ولكن بسبب ذلك ، من غير المرجح أن يطوروا شيئًا لم يفعله البشر من قبل. إذا كنا نتطلع إلى تحسين الخوارزميات المفهومة جيدًا ، مثل وظائف الفرز ، فإن تأسيس شيء ما على رمز بشري موجود سوف يمنحك ، في أحسن الأحوال ، أداءً مكافئًا. ولكن كيف تحصل على ذكاء اصطناعي لتحديد نهج جديد حقًا؟
اتبع الأشخاص في DeepMind نفس النهج الذي اتبعوه مع لعبة الشطرنج و يذهب: حولوا تحسين الكود إلى لعبة ، طور نظام AlphaDev خوارزميات تجميع x86 التي تعاملت مع زمن انتقال الشفرة على أنها نتيجة وحاولت تقليل هذه النتيجة مع ضمان تشغيل الكود حتى النهاية دون أخطاء. من خلال التعلم المعزز ، يطور AlphaDev تدريجيًا القدرة على كتابة تعليمات برمجية محكمة وذات كفاءة عالية.
داخل AlphaDev
إن القول بأن النظام يحسن زمن الانتقال يختلف تمامًا عن شرح كيفية عمله. مثل معظم أنظمة الذكاء الاصطناعي المعقدة الأخرى ، يتكون AlphaDev من عدة مكونات منفصلة. إحداها هي وظيفة التمثيل ، والتي تتعقب الأداء العام للكود أثناء تطويره. يتضمن هذا الهيكل العام للخوارزمية ، بالإضافة إلى استخدام سجلات x86 والذاكرة.
يضيف النظام تعليمات التجميع بشكل فردي ، يختارها أ البحث عن الأشجار في مونت كارلو– مرة أخرى ، نهج مستعار من أنظمة اللعبة. يسمح جانب “الشجرة” لهذا النهج للنظام بالتركيز بسرعة على منطقة محدودة من مجموعة واسعة من التعليمات المحتملة ، بينما تضيف مونت كارلو درجة من التعليمات العشوائية إلى التعليمات المحددة الذي تم اختياره في هذا الفرع. (لاحظ أن “التعليمات” في هذا السياق تتضمن أشياء مثل السجلات المحددة المختارة لإنشاء تجميع صالح وكامل.)
يقوم النظام بعد ذلك بتقييم حالة رمز التجميع للكمون والصلاحية ويخصص لها درجة ، مقارنتها بدرجة النتيجة السابقة. ومن خلال التعلم المعزز ، يتمسك بالمعلومات حول كيفية عمل الفروع المختلفة للشجرة ، بالنظر إلى حالة البرنامج. بمرور الوقت ، “يتعلم” كيفية الوصول إلى حالة اللعبة الفائزة – فرز مكتمل – بأقصى درجة ، أي أقل زمن انتقال.
الميزة الرئيسية لهذا النظام هي أنه لا يجب أن يتضمن التدريب عينة كود. بدلاً من ذلك ، يقوم النظام بإنشاء أمثلة التعليمات البرمجية الخاصة به ثم يقوم بتقييمها. في هذه العملية ، يتم الإمساك بالمعلومات حول مجموعات التعليمات الفعالة للفرز.
كود مفيد
يمكن أن يتعامل الفرز في البرامج المعقدة مع مجموعات العناصر الكبيرة والتعسفية. ولكن على مستوى المكتبة القياسي ، فهي مبنية من مجموعة كبيرة من الوظائف المحددة للغاية التي تتعامل فقط مع موقف واحد أو عدة مواقف. على سبيل المثال ، هناك خوارزميات منفصلة لفرز ثلاثة عناصر وأربعة عناصر وخمسة عناصر. وهناك مجموعة أخرى من الوظائف التي يمكنها التعامل مع عدد عشوائي من العناصر حتى حد معين ، مما يعني أنه يمكنك استدعاء واحد يقوم بفرز ما يصل إلى أربعة عناصر ، ولكن ليس أكثر.
DeepMind له معلمات AlphaDev في كل من هذه الوظائف ، لكنها تعمل بشكل مختلف تمامًا. بالنسبة للوظائف التي تتعامل مع عدد معين من العناصر ، من الممكن كتابة كود بدون أي فروع حيث تقوم بتنفيذ كود مختلف اعتمادًا على حالة المتغير. نتيجة لذلك ، عادةً ما يتناسب أداء هذا الرمز مع عدد من التعليمات المطلوبة. كان AlphaDev قادرًا على إزالة تعليمات من الفرز 3 و Sort-5 و Sort-8 ، وحتى أكثر من الفرز 6 و Sort-7. كان هناك واحد فقط (الترتيب 4) حيث لم يتمكن من إيجاد طريقة لتحسين الكود البشري. أظهرت عمليات التنفيذ المتكررة للشفرة على أنظمة حقيقية أن عددًا أقل من التعليمات يؤدي إلى أداء أفضل.
يتضمن فرز عدد متفاوت من الإدخالات تفريع الكود ، وتحتوي المعالجات المختلفة على كميات مختلفة من الأجهزة المخصصة للتعامل مع تلك الفروع. بالنسبة لهؤلاء ، تم تقييم الكود بناءً على مدى أدائه على 100 جهاز مختلف. مرة أخرى ، وجد AlphaDev طرقًا لاستخراج أداء إضافي ، وسنرى كيف حدث ذلك في موقف واحد: وظيفة تقوم بفرز ما يصل إلى أربعة عناصر.
في تطبيق مكتبة C ++ الحالية ، يقوم الكود بإجراء سلسلة من الاختبارات لتحديد عدد العناصر التي يجب فرزها واستدعاء وظيفة الفرز المخصصة لهذا العدد من العناصر. الكود المنقح يفعل شيئًا أكثر غرابة. يختبر ما إذا كان هناك عنصرين ويستدعي وظيفة منفصلة لفرزهما إذا لزم الأمر. إذا كانت أكبر من عنصرين ، تطلب الكود فرز العناصر الثلاثة الأولى. إذا كانت هناك ثلاثة عناصر ، فإنها تعرض نتائج هذا النوع.
ومع ذلك ، إذا كان هناك أربعة عناصر يتم فرزها ، فإنه يتم تشغيل رمز متخصص فعال للغاية لإدراج عنصر رابع في المكان المناسب في مجموعة من ثلاثة عناصر مرتبة. يبدو أنه نهج غريب ، لكنه تفوق باستمرار على الكود الموجود.
في الانتاج
نظرًا لأن AlphaDev أنتج رمزًا أكثر كفاءة ، فقد أراد الفريق إعادة دمجها في مكتبة LLVM القياسية C ++. المشكلة هنا هي أن الكود كان في المجمع بدلاً من C ++. لذلك كان عليهم العمل بشكل عكسي وإيجاد كود C ++ الذي سينتج نفس التجميع. بمجرد الانتهاء من ذلك ، تم دمج الكود في سلسلة أدوات LLVM – وهي المرة الأولى التي يتم فيها تغيير أي جزء من الكود منذ أكثر من عقد.
نتيجة لذلك ، يقدر الباحثون أن كود AlphaDev يتم تنفيذه الآن بلايين المرات في اليوم.
الطبيعة ، 2023. DOI: 10.1038 / s41586-023-06004-9 (حول DOIs).
