Solvable Sokoban Without a Solver via Diffusion

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

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

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

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

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

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

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