حلا جمال ابراهيم
ما هو مكعب روبيك Rubik’s Cube؟
مكعب روبيك Rubik’s Cube عبارة عن أحجية كلاسيكية ثلاثية الأبعاد، صُمّمت عام 1974 من قبل المخترع إرنو روبيك Rubik Ernő.
يحوي المكعب 6 أوجه يمكن تدويرها بزاوية 90 درجة في أي من الاتجاهين للوصول إلى الهدف المطلوب؛ وهو الحصول على مربعات بنفس اللون على كل وجه من المكعب.
لمكعب روبيك ما يقارب 4.3 × 1019 تكوينات مختلفة ممكنة، ومع ذلك يوجد حالة واحدة فقط هي حالة الهدف المراد الوصول لها.
في هذا المقال سنركّز على حل مكعب روبيك 2x2x2 وهو مكعب صغير يتكون من 8 مكعبات أصغر، مقارنةً بـ 26 مكعباً في المكعبات التقليدية.
سنمثّل الحركات اعتماداً على دوران الأوجه، ويُرمز إلى الأوجه بالأحرف التالية F, B, L, R, U, D حيث كل وجه يمكن تدويره باتجاهين، إما مع دوران عقارب الساعة أو عكس دوران عقارب الساعة، وبالتالي لدينا 12 حركة ممكنة للأوجه.
خوارزمية التعلّم المعزز Deep Reinforcement:
التعلّم المعزز (Reinforcement Learning) هو مجال من مجالات التعلّم الآلي (Machine Learning)، تتعلّم فيه الآلة كيفية التصرف في بيئة معينة بهدف تأدية عمل معين.
شكّل التعلّم المعزز (Reinforcement Learning) نجاحاً في العديد من التطبيقات، منها حل ألغاز لعبة الشطرنج، وهذا هو سبب استخدامنا لهذه الخوارزمية.
تعتمد خوارزمية التعلّم المعزز (Reinforcement Learning) على التعلّم العميق (Deep Learning) في حل المشاكل، أي أنها تستخدم الشبكات العصبية العميقة (Deep Neural Networks) في عملية تدريب النموذج للتنبؤ بالنتيجة.
عادةً لمثل هذه الألغاز فضاء حالة كبير جداً، إلا أنَّ مكعب روبيك يتميز بفضاء حالة صغير، ويعود السبب في ذلك إلى صعوبة تحديد فيما إذا كانت الحركة الجديدة تقربّنا من الحل أم لا.
عملنا في هذا المقال هو محاولة لإعادة ابتكار الأساليب التي حددتها الورقة البحثية التابعة لشركة DeepCube باستخدام مكعب صغير بدلاً من مكعب روبيك 3x3x3 التقليدي.
بالإضافة إلى النموذج الأصلي، درّب الباحثون أيضاً ثلاث شبكات عصبية أخرى بطبقات ومجموعات تدريب مختلفة الأحجام لاختبار أدائها. استخدموا كل واحدة من هذه النماذج لزيادة ثلاث خوارزميات مختلفة لحل المكعب، اعتمدت اثنتان منها على خوارزمية Monte Carlo Tree Search أو تُعرف اختصاراً (MCTS) وهي إحدى خوارزميات صنع القرار، تُمثّل فيها المشكلة باستخدام الأشجار، حيث تشير العقد إلى الحالات (عناصر المشكلة)، بينما تشير الفروع إلى التفاعلات (الأحداث) التي تنقل المشكلة من حالة إلى أخرى.
مرحلة التدريب:
بهدف تدريب النموذج، استخدم الباحثون خوارزمية تعلّم autodidactic iteration ADI الخاضعة للإشراف.
في كل عملية تدريب، تتخذ الخوارزمية مسار عكسي، حيث تنطلق من نقطة الحل لتنفيذ عدة حركات عشوائية، مستخدمة نتيجة كل حركة كدخل للشبكة العصبية (DNN)
بارامترات الشبكة:
الدخل هو v
الخرج هو p: عبارة عن متجه (شعاع) لاحتمالات إجراء كل الحركات الـ 12 الممكنة للأوجه.
يقدم المخطط نظرة عامة مرئية على عملية إنشاء مجموعة التدريب لخوارزمية ADI، وهي المفتاح لتطوير خوارزمية RL ناجحة في حل مثل هذه المشاكل.
لقد أنشأ الباحثون عينات تدريب N = k × l من خلال البدء بمكعب محلول، وتحريكه k مرة لإنشاء سلسلة من k مكعب، ثم تكرار هذه العملية l مرة.
خوارزمية ADI المستخدمة:
الحلول:
الحل الأساسي يسمى Greedy نستخدم فيه شعاع الاحتمالات الذي تدربت عليه الشبكة سابقاً.
نبدأ تحريك المكعب انطلاقاً من وضعه الحالي باستخدام الشبكة المُدرّبة، فنحصل على شعاع خرج p بناءً على نتيجة الحركات.
تعمل خوارزمية Greedy على حل المشكلة عن طريق اختيار الحل المحلي الأمثل في كل مرحلة. تجد هذه الخوارزمية أحياناً الحلول المثلى العالمية، لكن في بعض الأحيان يمكن أن تتوصّل إلى حلول أقرب أو أسوأ من المستوى العالمي الأمثل. وذلك لأن اختيار الحل الأمثل المحلي قد لا يضمن أنها تؤدي إلى أفضل حل عالمي. من الأمثلة عليها خوارزمية Dijkstra، والتي تُستخدم للعثور على أقصر مسار بين العقد في الرسم البياني.
تتكرر الخوارزمية N مرة. خلال كل تكرار، تُطبّق الخوارزمية كل الحركات الـ 12 الممكنة على المكعب، حتى يصل المكعب إلى 12 حالة مختلفة. تتحقق الخوارزمية إذا كانت هذه الحالات مناسبة باستخدام المعادلة التالية:
حيث Kociemba هي خوارزمية مُخصّصة للتأكد من أن الحالة التي وصل إليها المكعب مناسبة وتحقق الغاية المطلوبة أم لا.
ويشير n إلى عدد الحالات، فكلما كانت قيمته كبيرة، ازداد وقت تنفيذ الخوارزمية، وبالتالي سيؤثر سلباً على الأداء.
بعد التحقق، تُحدد خوارزمية Greedy الحركة التي تنقل المكعب إلى حالة جديدة بحيث تكون قيمتها أقل من أو تساوي الحالة الحالية.
تُستدعى خوارزمية Kociemba من أجل كل حالة مختلفة يمكن الوصول إليها من الحالة الحالية. لذلك، فإن العدد الإجمالي لمرات تنفيذ التابع هو n × 12 × N = 12 nN
الطريقة الثانية تسمى Vanilla MCTS
هي الإصدار الأساسي من خوارزمية MCTS، تتكون من 4 خطوات، كما هو موضح في الشكل:
- التحديد Selection: تبدأ هذه المرحلة من أعلى عقدة في الشجرة، ثم تُحدّد العقدة في المستويات التالية بناءً على معطيات المشكلة، تختار الخوارزمية من خلال ما يسمى سياسة الشجرة Tree Policy، ويتوقف التحديد Selection عند الوصول إلى عقدة لم تُستكشف بالكامل بعد، كما هو موضح في الشكل السابق؛ لم يتم توسيع جميع الحركات الممكنة إلى عقد جديدة بعد.
- التوسّع Expansion: تتضمّن هذه الخطوة إضافة عقدة جديدة واحدة أو أكثر من آخر عقدة تم اختيارها في الخطوة السابقة.
- الطرح Rollout: يبدأ الطرح من كل من هذه العقد المضافة، وبناءً على متوسط عمق الشجرة، يستمر الطرح حتى النهاية أو حتى الوصول إلى أعمق مستوى ممكن.
- النسخ الاحتياطي Backup: تُنسخ نتيجة خطوة الطرح السابقة احتياطياً إلى العقد التي اُختيرت في المرحلة الأولى عن طريق تحديث المعطيات الخاصة بكل منها.
بعد توقف الخوارزمية، تُحدّد الحركة النهائية بناءً على الإحصاءات الأخيرة في الشجرة الناتجة.
العنصران الرئيسيان في MCTS هما سياسة الشجرة وسياسة الطرح the Tree and Rollout policies. لأنهما يحددان معاً كيفية بناء الشجرة وما الحركات التي يجب أن تُركّز عليها الخوارزمية.
في مكعب روبيك Rubik’s Cube تعتمد الخوارزمية على كل من القيمة والشعاع التي تدربت عليها الشبكة سابقاً، حيث تستخدم القيمة التي ترجعها الشبكة Q0 كتهيئة لحالة جديدة.
المصادر:
