يصف هذا
المنشور مولد المستوى الخاص
بلعبة اللغز
Linjat . يمكن قراءة المنشور دون تحضير ، لكن من السهل استيعابه إذا كنت تلعب على عدة مستويات. لقد
نشرت شفرة المصدر
على جيثب . كل ما تمت مناقشته في المقالة موجود في
src/main.ccنموذج خطة البريد:
- Linjat هي لعبة منطقية تحتاج فيها إلى إغلاق جميع الأرقام والنقاط في الشبكة بخطوط.
- يتم إنشاء الألغاز إجرائيا باستخدام مزيج من حلالا ، مولد ومحسن.
- يحاول Solver حل الألغاز بالطريقة التي سيقوم بها الشخص ، ويعين لكل لغز تصنيفًا مثيرًا للاهتمام.
- تم تصميم منشئ الألغاز بحيث يمكن بسهولة تغيير جزء واحد من اللغز (الرقم) وفي الوقت نفسه تتغير جميع الأجزاء الأخرى (النقاط) بحيث يظل اللغز قابلاً للحل.
- يقوم محسِّن الألغاز بحل المستويات بشكل متكرر ويولد أشكالًا جديدة من الأشكال الأكثر إثارة للاهتمام الموجودة في الوقت الحالي.
القواعد
لفهم كيفية عمل مولد المستوى ، تحتاج ، لسوء الحظ ، لفهم قواعد اللعبة. لحسن الحظ ، فهي بسيطة جدا. يتكون اللغز من شبكة تحتوي على مربعات فارغة وأرقام ونقاط. مثال:
هدف اللاعب هو رسم خط عمودي أو أفقي عبر كل رقم من الأرقام ، مع مراعاة ثلاثة شروط:
- يجب أن يكون الخط من خلال رقم هو نفس طول الرقم.
- لا يمكن أن تتقاطع الخطوط.
- يجب إغلاق جميع النقاط بخطوط.
مثال الحل:
الصيحة! تصميم اللعبة جاهز وتطبيق واجهة المستخدم ، والشيء الوحيد المتبقي الآن هو العثور على مئات الألغاز الجيدة. وبالنسبة لمثل هذه الألعاب ، عادة ما يكون من غير المنطقي محاولة إنشاء مثل هذه الألغاز يدويًا. هذه هي وظيفة الكمبيوتر.
متطلبات
ما الذي يجعل اللغز لهذه اللعبة جيدة؟ أنا أميل إلى الاعتقاد بأن ألعاب الألغاز يمكن تقسيمها إلى فئتين. هناك ألعاب تستكشف فيها مساحة معقدة للدولة من البداية إلى النهاية (على سبيل المثال ،
Sokoban أو
Rush Hour ) ، والتي قد لا يكون من الواضح فيها ما هي الحالات الموجودة في اللعبة. وهناك ألعاب تُعرف فيها جميع الولايات منذ البداية ، ونصمم تدريجياً مساحة الولاية باستخدام عملية التخلص من الألعاب غير الضرورية (على سبيل المثال ،
سودوكو أو
بيكروس ). تقع لعبتي بالتأكيد في الفئة الثانية.
اللاعبون لديهم متطلبات مختلفة للغاية لهذه الأنواع المختلفة من الألغاز. في الحالة الثانية ، يتوقعون أنه لا يمكن حل اللغز إلا عن طريق خصم ، وأنهم لن يحتاجوا أبدًا إلى العودة / التخمين / التجربة والخطأ
[0] [1] .
لا يكفي معرفة ما إذا كان يمكن حل اللغز فقط عن طريق المنطق. بالإضافة إلى ذلك ، نحن بحاجة إلى أن نفهم بطريقة ما مدى جودة الألغاز التي تم إنشاؤها. خلاف ذلك ، فإن معظم المستويات ستكون مجرد خبث تافهة. في المواقف المثالية ، يمكن أيضًا استخدام هذا المبدأ لإنشاء منحنى تقدم سلس ، بحيث كلما تقدم اللاعب خلال اللعبة ، تصبح المستويات أكثر صعوبة تدريجياً.
حلالا
تتمثل الخطوة الأولى في تلبية هذه المتطلبات في إنشاء محلل ألعاب محسّن لهذا الغرض. يسمح لك حلال التراجع بتحديد ما إذا كان اللغز قابلاً للحل بسرعة وبدقة. بالإضافة إلى ذلك ، يمكن تعديله لتحديد ما إذا كان الحل فريدًا أم لا. لكنه لا يستطيع إعطاء فكرة عن مدى تعقيد اللغز حقًا ، لأن الناس يحلونها بطريقة مختلفة. حلالا يجب تقليد السلوك البشري.
كيف يمكن للشخص حل هذا اللغز؟ فيما يلي بعض التحركات الواضحة التي يعلمها البرنامج التعليمي في اللعبة:
- إذا كان من الممكن الوصول إلى نقطة من رقم واحد فقط ، ثم لإغلاق نقطة ، يجب عليك رسم خط من هذا الرقم. في هذا المثال ، يمكن الوصول إلى النقطة فقط من الثلاثة ، ولكن ليس من النقاط الأربعة:
وهذا يؤدي إلى هذا الموقف:
- إذا لم يكن الخط في اتجاه واحد ، فيجب وضعه في اتجاه آخر. في المثال أعلاه ، لم يعد بالإمكان وضع الأربعة بشكل عمودي ، لذلك نحن نعرف أنه سيكون أفقيًا:
- إذا كان من المعروف أن خط الطول X يجب أن يكون في موضع معين (عمودي / أفقي) ولا توجد مساحة فارغة كافية لوضع خط من الخلايا الفارغة X على كلا الجانبين ، فأنت بحاجة إلى تغطية عدة مربعات في المنتصف. إذا كان الأربعة في المثال الموضح أعلاه ، فلن نعرف ما إذا كان يمتد إلى اليمين أو اليسار. لكننا نعلم أن الخط يجب أن يغطي مربعين متوسطين:
التفكير المماثل هو أساس اللعبة. يبحث اللاعب عن طرق لتمديد سطر واحد صغير ، ثم يفحص الحقل مرة أخرى ، لأنه يمكن أن يوفر له معلومات لصنع استنتاج منطقي آخر. سيكون إنشاء محلل يتبع هذه القواعد كافيًا لتحديد
ما إذا كان بإمكان
أي شخص حل اللغز دون الرجوع.
ومع ذلك ، هذا لا يخبرنا أي شيء عن تعقيد أو اهتمام المستوى. إلى جانب القدرة على التحمل ، نحتاج بطريقة ما إلى تحديد مدى التعقيد.
فكرة أولى واضحة لوظيفة التصنيف: كلما زاد عدد الحركات التي تحتاجها لحل اللغز ، كلما زادت صعوبة ذلك. من المحتمل أن يكون هذا مقياسًا جيدًا في الألعاب الأخرى ، ولكن على الأرجح ، أهم من عدد التحركات المسموح بها لدى اللاعب. إذا تمكن اللاعب من الوصول إلى 10 استنتاجات منطقية ، فمن المرجح أن يجد أحدها بسرعة كبيرة. إذا كان هناك خطوة واحدة صحيحة ، فسوف يستغرق الأمر المزيد من الوقت.
وهذا هو ، كتقريب أولي ، نحتاج إلى أن تكون شجرة القرارات عميقة وضيقة: هناك اعتماد طويل على الحركات من البداية إلى النهاية ، وفي كل لحظة من الزمن ، يوجد عدد صغير من الطرق لتحريك السلسلة إلى أعلى
[2] .
كيف نحدد عرض وعمق الشجرة؟ حل واحد للغز وتقييم الشجرة التي تم إنشاؤها لن يعطي إجابة دقيقة. يؤثر الترتيب الدقيق الذي تتم به التحركات على شكل الشجرة. نحن بحاجة إلى النظر في جميع الحلول الممكنة والقيام بها شيء مثل التحسين لأفضل وأسوأ الحالات. أنا على دراية بتقنية
البحث التقريبي لرسومات البحث في ألعاب الألغاز ، لكن بالنسبة لهذا المشروع ، أردت إنشاء أداة حل واحدة ، وليس بعض البحث الشامل. نظرًا لمرحلة التحسين ، فقد حاولت التأكد من أن وقت تشغيل الملف قد تم قياسه ليس بالثواني ، ولكن بالميللي ثانية.
قررت عدم ذلك. بدلاً من ذلك ، لا يقوم Solver بحركة واحدة فعليًا في كل مرة ، لكنه يحل اللغز في طبقات: عند اتخاذ حالة ، يجد كل التحركات الصحيحة التي يمكن إجراؤها. ثم يطبق كل هذه التحركات في نفس الوقت ويبدأ من جديد في حالة جديدة. بعد ذلك ، يتم استخدام عدد الطبقات والحد الأقصى لعدد الحركات الموجودة على طبقة واحدة كقيم تقريبية لعمق وعرض شجرة البحث ككل.
إليك كيفية حل أحد الألغاز الصعبة باستخدام هذا النموذج. الخطوط المنقطة هي خطوط ممتدة على هذه الطبقة من المحلل ، والخطوط الصلبة هي تلك التي لم تتغير. الخطوط الخضراء هي الطول الصحيح ، الخطوط الحمراء لم تكتمل بعد.
المشكلة التالية هي أن جميع الحركات التي يقوم بها اللاعب يتم إنشاؤها على قدم المساواة. ما أدرجناه في بداية هذا القسم هو مجرد الحس السليم. فيما يلي مثال على قاعدة خصم أكثر تعقيدًا ، حيث سيتطلب البحث عنها مزيدًا من التفكير. النظر في الحقل التالي:
لا يمكن تغطية النقاط في C و D إلا من خلال الخمسة والوسطى الأربعة (وليس هناك رقم واحد يمكنه تغطية كلتا النقطتين في نفس الوقت). هذا يعني أن الأربعة في الوسط يجب أن يغطوا إحدى النقطتين ، وبالتالي لا يمكن استخدامها لتغطية أ. لذلك ، يجب أن تغلق النقطة أ الأربعة في الزاوية اليسرى السفلى.
من الواضح أنه سيكون من الغباء النظر في سلسلة التفكير هذه مساوية للاستنتاج البسيط "لا يمكن الوصول إلى هذه النقطة إلا من هذا الرقم". هل من الممكن إعطاء وزن أكبر لهذه القواعد الأكثر تعقيدًا في وظيفة التقييم؟ لسوء الحظ ، هذا غير ممكن في محلل قائم على الطبقة ، لأنه غير مضمون لإيجاد حل بأقل تكلفة. هذه ليست مشكلة نظرية فقط - في الممارسة العملية يحدث غالبًا أنه يمكن حل جزء من الحقل إما عن طريق حجة واحدة معقدة أو عن طريق سلسلة من التحركات الأكثر بساطة. في الواقع ، يجد محلل يستند إلى طبقة المسار الأقصر وليس الأقل تكلفة ، وهذا لا يمكن أن ينعكس في وظيفة التقييم.
كنتيجة لذلك ، توصلت إلى هذا القرار: لقد غيرت المحلل بحيث تتكون كل طبقة من نوع واحد فقط من التفكير. تتجاوز الخوارزمية قواعد التفكير بترتيب تقريبي من التعقيد. إذا وجدت القاعدة بعض التحركات ، فسيتم تطبيقها ، وينتهي التكرار ، ويبدأ التكرار التالي في القائمة من البداية.
ثم يتم تعيين تقييم: يتم تعيين تكاليف كل طبقة بناءً على قاعدة واحدة تم استخدامها فيه. لا يزال هذا لا يضمن أن الحل سيكون الأكثر تكلفة ، ولكن إذا تم تحديد الأوزان بشكل صحيح ، فلن تجد الخوارزمية على الأقل حلًا مكلفًا إذا كان هناك حل رخيص.
علاوة على ذلك ، إنه يشبه إلى حد كبير الطريقة التي يحل بها الناس الألغاز. يحاولون أولاً إيجاد حلول سهلة ، ويبدأون في تحريك أدمغتهم بنشاط فقط في حالة عدم وجود حركات بسيطة.
مولد كهربائي
حدد القسم السابق ما إذا كان مستوى معين جيدًا أم سيئًا. ولكن هذا لا يكفي ، فنحن ما زلنا بحاجة إلى إنشاء مستويات بطريقة ما حتى يتمكن حلالا من تقييمها. من غير المرجح أن يكون العالم الذي تم إنشاؤه عشوائيًا قابلاً للحل ، ناهيك عن الاهتمام.
الفكرة الرئيسية (ليست جديدة بأي حال) هي الاستخدام البديل للحامل والمولد. لنبدأ بغز ، وهو أمر غير محتمل على الأرجح: ضع فقط رقمين إلى خمسة أرقام في مربعات عشوائية للخلية:
يعمل Solver حتى يتمكن من التطوير أكثر:
ثم يضيف المولد مزيدًا من المعلومات إلى اللغز في شكل نقطة ، وبعد ذلك يستمر تنفيذ المحلل.
في هذه الحالة ، فإن النقطة المضافة إلى حلالا ليست كافية لمزيد من التطوير. بعد ذلك سيستمر المولد في إضافة نقاط جديدة حتى يرضي المحلل:
ثم يواصل حلاله عمله المعتاد:
تستمر هذه العملية إما حتى يتم حل اللغز ، أو حتى يتبقى مزيد من المعلومات لإضافتها (على سبيل المثال ، عندما تحتوي كل خلية يمكن الوصول إليها من الرقم بالفعل على نقطة).
تعمل هذه الطريقة فقط إذا كانت المعلومات الجديدة المضافة لا يمكن أن تجعل أيًا من الاستنتاجات التي تم إجراؤها مسبقًا غير صحيحة. سيكون ذلك صعبًا عند إضافة أرقام إلى الشبكة
[3] . ولكن إضافة نقاط جديدة إلى هذا المجال لديه هذه الخاصية ؛ على الأقل لقواعد المنطق التي أستخدمها في هذا البرنامج.
أين يجب أن تضيف الخوارزمية نقاطًا؟ في النهاية ، قررت إضافتها إلى المساحة الفارغة ، والتي يمكن إغلاقها في الحالة الأولية مع أكبر عدد ممكن من الأسطر ، بحيث تسعى كل نقطة إلى إعطاء أقل قدر ممكن من المعلومات. لم أحاول وضع النقطة على وجه التحديد في المكان الذي قد يكون من المفيد للتقدم في حل اللغز في الوقت الذي تتعطل فيه حلالا. هذا يخلق تأثيرًا مناسبًا للغاية: يبدو أن معظم النقاط الموجودة في بداية اللغز عديمة الفائدة تمامًا ، مما يجعل اللغز أكثر صعوبة مما هو عليه بالفعل. إذا كان كل هذا هو الكثير من التحركات الواضحة التي يمكن للاعب القيام بها ، ولكن لسبب ما لا يعمل أحدها بشكل صحيح. ونتيجة لذلك ، اتضح أن مولد اللغز يتصرف كخنزير.
لا تؤدي هذه العملية دائمًا إلى إنشاء حل ، ولكنها سريعة جدًا (حوالي 50-100 مللي ثانية) ، لذلك لإنشاء مستوى ، يمكنك ببساطة تكراره عدة مرات. لسوء الحظ ، فإنه عادة ما يخلق الألغاز المتواضعة. من البداية ، هناك الكثير من التحركات الواضحة ، يمتلئ الحقل بسرعة كبيرة وتبين أن شجرة القرارات ضحلة إلى حد ما.
محسن
خلقت العملية المذكورة أعلاه الألغاز دون المتوسط. في المرحلة الأخيرة ، استخدم هذه المستويات كأساس لعملية التحسين. وهي تعمل على النحو التالي.
ينشئ المُحسِّن مجموعة تحتوي على ما يصل إلى 10 خيارات لغز. يتم تهيئة التجمع مع لغز عشوائي ولدت جديدة. في كل تكرار ، يختار المحسن لغزًا واحدًا من المجموعة ويقوم بإجراء طفرة.
يحذف الطفرة جميع النقاط ، ثم يغير قليلاً الأرقام (أي يقلل / يزيد من قيمة الرقم المحدد عشوائياً أو ينقل الرقم إلى خلية أخرى في الشبكة). يمكنك تطبيق العديد من الطفرات على الحقل في نفس الوقت. بعد ذلك ، نقوم بتشغيل برنامج Solver في وضع إنشاء المستوى الخاص الموضح في القسم السابق. ويضيف ما يكفي من النقاط إلى اللغز بحيث يصبح قابلا للحل مرة أخرى.
بعد ذلك ، نبدأ حلالا مرة أخرى ، وهذه المرة في الوضع العادي. أثناء هذا التشغيل ، يراقب المحلل أ) عمق شجرة القرار ، ب) وتيرة الحاجة إلى أنواع مختلفة من القواعد ، ج) عرض شجرة القرار في نقاط مختلفة في الوقت المناسب. يتم تقييم اللغز بناءً على المعايير الموضحة أعلاه. تفضل وظيفة التقييم إيجاد حلول عميقة وضيقة ، كما تضيف مستويات التعقيد المتزايد وزناً أكبر إلى الألغاز التي تتطلب قواعد منطقية أكثر تعقيدًا.
ثم يتم إضافة لغز جديد إلى حمام السباحة. إذا كان المجمع يحتوي على أكثر من 10 ألغاز ، فسيتم التخلص من الأسوأ.
تتكرر هذه العملية عدة مرات (استغرقت عملية تكرار ما يقرب من 10000 إلى 50000). بعد ذلك ، يتم حفظ الإصدار الأعلى تصنيفًا من اللغز في قاعدة بيانات مستوى اللغز. إليك ما يبدو عليه تقدم أفضل لغز في تشغيل التحسين:
حاولت استخدام طرق أخرى لتنظيم التحسين. في إصدار واحد ، تم استخدام التلدين المحاكى ؛ بينما كان البعض الآخر عبارة عن خوارزميات وراثية مع عمليات متقاطعة مختلفة. لم يتم تنفيذ أي من الحلول وكذلك خوارزمية ساذجة مع مجموعة من الخيارات التي تعود إلى الأعلى.
حل واحد فريد من نوعه
عندما يكون للغز حل فريد من نوعه ، تنشأ صعوبة مثيرة للاهتمام. هل من الممكن السماح للاعب بافتراض وجود حل واحد واستخلاص النتائج بناءً على هذا؟ هل سيكون من الإنصاف إذا اقترح مولد اللغز أن اللاعب فعل ذلك؟
في منشور على HackerNews ، قلت إن هناك أربعة خيارات للتعامل مع هذا الموقف:
- أعلن تفرد الحل منذ البداية واجبر المولد على إنشاء مستويات تتطلب هذا النوع من التفكير. هذا قرار سيء لأنه يعقد فهم القواعد. وعادة ما تكون هذه هي التفاصيل ينسى الناس.
- لا تضمن تفرد القرار: يحتمل أن يكون لديك العديد من القرارات واتخاذها كلها. في الواقع ، هذا لا يحل المشكلة ، لكنه يدفعها بعيداً.
- فقط افترض أن هذا حدث نادر جدًا ، وهو أمر غير مهم من الناحية العملية. (هذا هو الحل الذي تم استخدامه في التنفيذ الأولي.)
- تغيير مولد اللغز بحيث لا يولد الألغاز التي من خلالها معرفة تفرد الحل من شأنه أن يساعد. (ربما الحل الصحيح ، ولكن يتطلب عملا إضافيا.)
في البداية ، اخترت الخيار الأخير ، وكان ذلك خطأ فظيعًا. اتضح أنني أخذت في الحسبان طريقة واحدة فقط أدت بها تفرد الحل إلى تسرب المعلومات ، وهو في الواقع نادر جدًا. لكن هناك آخرون. كان أحدهم حاضرًا في الواقع على كل مستوى قمت بإنشائه وغالبًا ما أدى إلى حقيقة أن الحل أصبح تافهاً. لذلك ، في مايو 2019 ، قمت بتغيير أوضاع Hard و Expert باستخدام الخيار الثالث.
أكثر الحالات المزعجة هي شيطان مع خط متقطع في هذا المجال:
لماذا يمكن للاعب الماكرة جعل مثل هذا الاستنتاج؟ يمكن أن تغطي أي شيطان أي من المربعات الأربعة المجاورة. لا يوجد لدى أي منهم نقاط ، لذلك لا يتعين تغطيتها بخط. والمربع أدناه لا يحتوي على تراكبات مع أي أرقام أخرى. إذا كان هناك حل واحد ، فيجب أن يكون هذا هو الحال عندما تغطي الأرقام الأخرى المربعات الثلاثة المتبقية ، ويغلق الاثنان المربع تحته.
يكمن الحل في إضافة بضع نقاط إضافية عند التعرف على مثل هذه الحالات:
حالة شائعة أخرى هي شرطة ذات خط منقط في هذا الحقل:
لا تختلف المربعات إلى اليسار وأعلى الاثنين. لا أحد منهم لديه نقطة ، ولا يمكن الوصول إلى أي شخص من أي رقم آخر. أي حل يغطيه الشيطان المربع العلوي سيكون له حل مطابق لإغلاق المربع الأيسر والعكس صحيح. إذا كان هناك حل فريد من نوعه ، فلا يمكن أن يكون هذا ، ويجب أن يكون الشيطان قد غطى المربع السفلي.
قررت هذا النوع من الحالات في الطريق "إذا كان مؤلمًا ، فلا تلمسه". طبق Solver هذه القاعدة في مرحلة مبكرة من قائمة الأولويات وعين مثل هذا الوزن السلبي لمثل هذه التحركات. عادة ما يتم تجاهل الألغاز التي تحتوي على هذه الميزة بواسطة المُحسِّن ، ويتم تجاهل الباقي القليلة في مرحلة التحديد النهائي لمستويات اللعبة المنشورة.
هذه ليست قائمة كاملة ، أثناء اختبار اللعب مع البحث المتعمد عن الأخطاء ، وجدت العديد من القواعد الأخرى للحلول الفريدة. لكن معظمهم بدا نادرًا وكانوا كافيين للعثور عليه ، لذلك لم يبسطوا اللعبة كثيرًا. إذا قام شخص ما بحل اللغز باستخدام هذا المنطق ، فلن ألومه عليه.
استنتاج
في البداية ، تم تطوير اللعبة كتجربة في الجيل الإجرائي من الألغاز. تم تصميم اللعبة ومولدها جنبًا إلى جنب ، لذلك يصعب تطبيق التقنيات نفسها مباشرة على الألعاب الأخرى.
السؤال الذي ليس لدي إجابة عليه: هل استثمار هذه الجهود في الجيل الإجرائي له ما يبرره؟ . , - . , .
, , . : .
الملاحظات
[0] , , . , , . .
[1]
Solving Minesweeper and making it better .
[2] , / — , , . ,
, Rush Hour , , . , Rush Hour — , - .
[3] . , , . .