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

يعتبر الفرز أساسيًا لدرجة أن الخوارزميات مدمجة في معظم المكتبات القياسية للغات البرمجة. أيضًا ، في مكتبة C ++ المستخدمة مع مترجم LLVM ، لم يتم التطرق إلى الكود منذ أكثر من عقد.

لكن فريق DeepMind AI التابع لشركة Google قد طور الآن أداة تعلم معزز يمكنها إنشاء خوارزميات محسّنة للغاية دون أن يتم تدريبها أولاً على أمثلة التعليمات البرمجية البشرية. الحيلة هي إعداد البرمجة للتفكير فيها على أنها لعبة.

إنها كلها لعبة

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

نظرًا لأنه لم يتم تدريبه على الألعاب التي يلعبها البشر ، يمكن لنظام DeepMind اكتشاف طرق للألعاب التي لن يفكر بها البشر. بالطبع ، نظرًا لأنها تلعب دائمًا ضد نفسها ، فهناك أوقات تخلق فيها نقاطًا عمياء يمكن للبشر استغلالها.

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

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

داخل AlphaDev

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

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

يقوم النظام بتقييم حالة كود التجميع من أجل زمن الوصول والصلاحية ، ويقارنها مع النتيجة السابقة ، ويخصص لها درجة. ومن خلال التعلم المعزز ، يتعلق الأمر بمعلومات حول كيفية نزول الفروع المختلفة للشجرة نظرًا لحالة البرنامج. بمرور الوقت ، “تتعلم” كيفية تحقيق حالة لعبة ناجحة – نشر مكتمل – بأقصى درجة ، أي أقل زمن انتقال.

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

كود مفيد

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

قام DeepMind بتعيين AlphaDev على كل من هذه الوظائف ، لكنها تعمل بشكل مختلف تمامًا. بالنسبة للوظائف التي تتعامل مع عدد محدود من العناصر ، يمكن كتابة الكود بدون فروع تنفذ تعليمات برمجية مختلفة بناءً على حالة المتغير. نتيجة لذلك ، يتم قياس أداء هذا المؤشر عادةً باستخدام خوارزميات متعددة مطلوبة. كان AlphaDev قادرًا على إزالة تعليمات واحدة من كل من الصف 3 والصف 5 والصف 8 وتقليل الصف 6 والصف 7. واحد فقط (التسلسل 4) لم يجد طريقة لتحسين الكود البشري. أظهر التشغيل المتكرر للشفرة على أجهزة الكمبيوتر الحقيقية أن عددًا أقل من التعليمات يؤدي إلى أداء أفضل.

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

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

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

قيد التحضير

نظرًا لأن AlphaDev أنتج كودًا أكثر كفاءة ، أراد الفريق إعادة تجميعها في مكتبة LLVM القياسية C ++. كانت المشكلة هنا أن الكود كان في التجميع بدلاً من C ++. لذلك ، كان عليهم العمل بشكل عكسي وإيجاد كود C ++ الذي أنتج نفس التجميع. بمجرد الانتهاء من ذلك ، تم دمج الكود في سلسلة أدوات LLVM – وهي المرة الأولى منذ عقد من الزمن التي تم فيها تعديل بعض التعليمات البرمجية.

نتيجة لذلك ، يقدر الباحثون أن كود AlphaDev يتم تنفيذه الآن تريليونات المرات في اليوم.

الطبيعة ، 2023. DOI: 10.1038 / s41586-023-06004-9 (حول DOIs).