CayleyPy تطبّق الشبكات العصبونية على مكعبات روبيك التي يبقى فيها «عدد الله» مجهولًا

يضم مكعب روبيك 3×3×3 نحو 4,3×10^19 حالة مسموحة، ومنذ عام 2010 يُعرف أن أيًّا منها يمكن حلّه في 20 حركة على الأكثر وفق مقياس HTM. توصّل توماس روكيكي وزملاؤه إلى هذه النتيجة عبر استعراض كامل لفضاء الحالات. أما المكعبان 4×4×4 و5×5×5 والمكعبات الكبيرة والميغامنكس، فلا يزال قطر رسم كيلي البياني الخاص بها غير معروف بدقة. ويحاول مشروع CayleyPy مقاربة هذه الألغاز من زاوية مختلفة: البحث بالشبكات العصبونية بدلًا من البحث الشامل. ونشر أحد أعضاء الفريق على Habr تحليلًا لخط المعالجة ولنتائج المسابقات.

اللغز بوصفه رسمًا بيانيًا

الصياغة بسيطة. رؤوس رسم كيلي البياني هي الحالات المسموحة للغز، وأضلاعه هي الحركات المسموحة. وهكذا يتحول الحل بأقل عدد من الحركات إلى مسألة أقصر مسار من الرأس الحالي إلى الحالة المحلولة. أما قطر الرسم البياني، أي أكبر قيمة لأقصر المسافات بين جميع أزواج الرؤوس، فهو «عدد الله».

كان هذا الحساب ممكنًا للمكعب 3×3×3، وإن تطلّب موارد حاسوبية كبيرة واستعانة بالتناظرات لتقليص الفضاء. ومع كبر اللغز يتغير الوضع. فللمكعب 4×4×4 نحو 7,4×10^45 حالة، وللمكعب 5×5×5 نحو 2,8×10^74. ولا يمكن هنا اجتياز الرسم البياني كاملًا. ويبقى الاعتماد على الأساليب الاستدلالية، والتقديرات العليا والدنيا، والبحث عن حلول شبه مثلى تضيّق تدريجيًا الفجوة مع الحل الأمثل المجهول.

ماذا يفعل CayleyPy

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

وبحسب الإعلان، يتناول المؤلف في مقاله ثلاثة أمور:

• بنية خط المعالجة العصبوني في CayleyPy؛
• نتائج المسابقات التي انتهت بالفعل؛
• شروط المسابقات الجارية الخاصة بالمكعبات الكبيرة، وهو يشارك فيها بصفته عضوًا في الفريق.

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

لماذا يهم هذا النهج خارج نطاق المكعبات

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

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

ماذا يفعل المهندس الممارس بهذا

إذا كنت تعمل في البحث والأساليب الاستدلالية، فإن مستودع CayleyPy المفتوح على GitHub ومسابقات Kaggle يوفران منصة جاهزة لاختبار أفكارك على مسألة يمكن قياس جوابها بعدد الحركات. ومن المعقول أن تبدأ بالألغاز الصغيرة التي يُعرف قطرها، فتقارن تقدير المسافة الصادر عن الشبكة العصبونية بالقيمة الدقيقة. ثم تنتقل إلى المكعبات الكبيرة، حيث تتنافس أطوال الحلول التي يُعثر عليها.

وينبغي للقراء أن يضعوا في الحسبان قيدًا: هذا عرض كتبه أحد المشاركين في المشروع، وليس بحثًا مستقلًا. وأي ادعاء بالتفوق على البحث الكلاسيكي يجب التحقق منه من جداول النتائج المحددة ومن أنواع المحلّلات (solvers) التي جرت المقارنة معها.