🐼 📵 🙅🏼 كابوم: نقاب غير عادي 👩🏾‍🚒 🙇🏻 👩‍✈️

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

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

فكرة

في الآونة الأخيرة ، كانت لدي فكرة: ماذا لو كان عليك لعب كاسحة الألغام ضد جهاز كمبيوتر أكثر حكمة؟

عادة ، يتم تحديد موقع الألغام في بداية اللعبة (ولكن هناك بعض الحيل هنا - على سبيل المثال ، حتى لا تفقد النقرة الأولى). ولكن ماذا لو لم يتم تحديد موقع المناجم مسبقًا ويمكن للعبة اختيار موقع المناجم بعد بدء اللعبة؟

سيكون ذلك قاسيًا جدًا: إذا نقرت على مربع قد يحتوي على منجم ، فسيحتوي عليه دائمًا! وبالتالي ، يجب أن تثبت مقدمًا أن المربع آمن.

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

من ناحية أخرى ، هناك حالات عندما يكون عليك التخمين:

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

بعبارات أخرى:

, .
, , .
, :
1. , , .
2. , , .

كيفية تنفيذ مثل هذه اللعبة؟ يمكنني محاولة حساب جميع الحقول الممكنة ، ولكن هذا غير واقعي: حتى حقل 10x10 الصغير يعني 2 ^ 100 احتمالات. اختيار فقط تلك التي تحتوي على N دقيقة بالضبط لا يساعد.

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

ثم يمكنني حساب جميع الخيارات لموقع الألغام على الحدود وفقًا للملصقات. التراجع (التراجع) - تقنية جيدة تسمح لك بالفرز عبر جميع المجموعات ، ولكن أيضًا تتراجع سريعًا بمجرد تحديد أن الفرع لا يمكنه الحساب.

الموقعان المحتملان للألغام على الحدود موضحة أعلاه. من خلال دمجها ، سوف نفهم أي الخلايا مضمونة لتكون فارغة أو ملغومة.

أحتاج أيضًا إلى تتبع العدد الإجمالي للألغام. وبالتالي ، يبدو الموقع وكأنه "5 دقائق على الحدود ، 5 دقائق بالخارج". هذا مهم لأنه بخلاف ذلك كان بإمكاني إنشاء الكثير من الألغام على الحدود (أو قليلة جدًا!)

لذا ، لدي جميع الخيارات. ماذا يحدث عندما يقرر اللاعب فتح قفص؟

اختر خيارًا عشوائيًا (خيار يلبي قواعد "قاسية لكن عادلة"). سيحدد هذا موقع الألغام على الحدود.
بعثر بشكل عشوائي أولئك المتبقين خارج الحدود.
إذا كان هناك منجم في الخلية المحددة ، فإن اللعبة قد انتهت.
غير ذلك:
1. تحديد تسمية جديدة للخلية المحددة
2. تكشف عن خلايا إضافية إذا كانت 0
3. , ! .

هذا أمر طبيعي بالنسبة للحقول الصغيرة. عادة لا يوجد سوى عدد قليل من التركيبات الممكنة ... انتظر ، ما هو؟

أوه لا!

بطريقة ما ، تمكنت من فتح 18 مليون موقع منجم محتمل. يلتهم My Firefox 12 غيغابايت من الذاكرة ، ويستغرق فتح الخلية نصف دقيقة. من الواضح أنني بحاجة إلى خوارزمية أفضل.

قد يلاحظ أحدهم أن Minesweeper هي لعبة كاملة NP ، وبالتالي لا يمكن تجنب زيادة الوقت بشكل كبير. وفي الحالة العامة ، هذا صحيح - ستكون هناك مواقف تستغرق حسابها وقتًا طويلاً. ولكن هذا يعمل لمنطقة صغيرة.

لست بحاجة إلى تذكر جميع المجموعات. لست بحاجة حتى إلى حساب جميع المجموعات. كل ما هو مطلوب هو:

تحقق مما إذا كانت الخلية آمنة أو خطيرة أو غامضة ،
(, , ).

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

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

لقد وجدت MiniSat ، وهو حل SAT صغير تم تجميعه من أجل Javascript بواسطة Joel Galenson. يستغرق الملف المترجم 200 كيلوبايت فقط ، لذلك استخدمه.

صيغ CNF

تعمل مذيبات SAT مع الصيغ العادية المقترنة ( CNFs ). صيغة CNF هي "AND of ORs" ، على سبيل المثال:

(a | ~ b | ~ c) & (c | d ~ e) & f

يمكنك تحويل أي صيغة من منطق الجملة (المتغيرات ، أو لا ، ضمنيًا) إلى CNF ، لذا فهي نوع من التنسيق العام.

كيف نستخدمها؟ لنفترض أن لدينا لوحة: إذا قمت بإنشاء متغيرات للخلايا غير المعروفة (باتجاه عقارب الساعة: x1 ، x2 ، x3) ، فسيتعين عليها تلبية المعادلات التالية: ولكن كيف يمكن التعبير عن "مجموع المتغيرات هو 2" في CNF؟ لقد وجدت طريقة ، كما علمت لاحقًا ، تسمى "الترميز ذي الحدين" وهي أبسط ترميز. يجب أن تفكر في كل مجموعات فرعية ممكنة من المتغيرات. على سبيل المثال ، تحتاج إلى الصيغ التالية:

? ? 1
2 ? 1

1 + 2 + 3 = 2
2 + 3 = 1
2 + 3 = 1 ( )

x1 + x2 + x3 = 2

لكل مجموعة فرعية من متغيرين ، واحد على الأقل صحيح. هذا يضمن أن المبلغ أكبر من 1.
(x1 | x2) & (x1 | x3) & (x2 | x3)
متغير واحد على الأقل خطأ. هذا يضمن أن المبلغ أقل من 3.
(~ x1 | ~ x2 | ~ x3)

بالنسبة x2 + x3 = 1لي ، أحتاج إلى مجموعة مماثلة من الصيغ:

أحد المتغيرات على الأقل صحيح: (x2 | x3)
خطأ واحد على الأقل من المتغيرات (~ x2 | ~ x3).

من خلال الجمع بين هذا ، أحصل على صيغة CNF برصيد 6 نقاط. في تنسيق DIMACS القياسي: تنتهي جميع خطوط الموضع بـ 0 ، ويتم تمييز السالب بعلامة الطرح. إذا قمت بتوصيله بـ MiniSat (جربه بنفسك) ، أحصل على: هذا يعني أن MiniSat قد وجدت حلاً حيث x1 و x2 صحيحان و x3 خطأ. وإليك ما سيبدو عليه المجلس: البرنامج بأكمله أكثر تعقيدًا: هذا مجرد حل واحد ، هناك حل آخر. لذلك ، لمعرفة ما إذا كانت x1 أو x2 أو x3 يمكن أن تكون صحيحة (أو خاطئة) ، فأنت بحاجة إلى تقديم المزيد من الطلبات. أريد أن أسأل: "بالنظر إلى الصيغة المذكورة أعلاه ، وكذلك x1 ، هل هذا ممكن؟ ماذا عن الصيغة المذكورة أعلاه ، وكذلك ~ x1 "؟

SAT 1 2 -3

! ! 1
2 . 1

يعني التشفير أنني بحاجة إلى العثور على كل المجموعات الممكنة (على سبيل المثال ، جميع المجموعات الفرعية من 3) لمجموعة من المتغيرات. ومع ذلك ، بالنسبة لهذه المعادلة ، سيكون هناك ما يصل إلى 8 متغيرات فقط ، لذلك عادة ما تكون الصيغة صغيرة بما يكفي بحيث يمكن لـ MiniSat حلها بسرعة.

تتبع دقيقة

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

في الواقع ، فإن الحالة المعاكسة ممكنة أيضًا: إذا كان هناك عدد قليل جدًا من الألغام ، فستنتهي اللعبة ، لأنه لن يكون هناك شيء في المكان.

لذلك ، أود أن أشير في صيغة SAT إلى أن "عدد الألغام لا يقل عن X ولا يزيد عن Y". اعتقدت في البداية أنه يمكنني استخدام الخدعة مع جميع التركيبات. لسوء الحظ ، لا يعمل بشكل جيد للغاية مع الأعداد الكبيرة. إذا كان هناك ، على سبيل المثال ، 20 خلية و 10 دقائق ، ثم بعد توصيل الأرقام بالمعامل ذي الحدين ، نجد أن عدد التركيبات هو بالفعل 6 أرقام!

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

في النهاية ، أدركت الفكرة من مقال بعنوان "ترميز CNF الفعال مع القيود الأساسية المنطقية" ، كتبه أوليفييه بايوت وياسين بوفهاد. نرى شجرة تضيف بشكل متكرر أرقامًا أحادية (أو تفرز البتات بحيث يكون الجميع في البداية):

في نهاية هذا الرسم البياني ، ستحصل على مجموعة مرتبة من متغيرات "الإخراج". للتأكد من أن المجموع ليس أقل من X ، تحقق من أن أول X من المتغيرات الناتجة هو 1. للمطالبة بأن المجموع ليس أكبر من Y ، تحقق من أن آخر N - Y من المتغيرات الناتجة هو 0.

هذا أفضل بكثير من استخدام جميع التركيبات الممكنة ، ومع ذلك ، لا يزال هذا المخطط غير منطقي لأنه يولد جملًا N (N ^ 2). عندما يكون عدد الخلايا المفتوحة حوالي 100 ، تصبح اللعبة بطيئة. يمكننا تحسين اللعبة أكثر.
تقليل الطلبات

أثناء دراسة المشكلة ، لاحظت أنه يمكنني تقليل عدد الاستفسارات إلى حلال. كنت أرغب في تحديد حالة جميع الخلايا (أي للتحقق مما إذا كانت مضمونة أن تكون خطيرة أو آمنة أم لا). فعلت هذا باستخدام حلقة بسيطة. لنفترض أن اللوحة موصوفة بالصيغة F:

حدد ما F & ~ x1إذا كان x1 يمكن أن يكون 0
حدد ما F & x1إذا كان x1 يمكن أن يكون 1
حدد ما F & ~ x2 إذا كان x2 يمكن أن يكون 0
حدد ما F & x2إذا كان x2 يمكن أن يكون 1
إلخ.

ماذا لاحظت؟ إذا حصلت على حل لـ F & ~ x1 ، فسيحتوي أيضًا على قيم جميع المتغيرات الأخرى. هذا يجيب بالفعل على العديد من الأسئلة الأخرى: إذا كان الحل يحتوي على x2 = 0 ، فلا حاجة للسؤال عما إذا كان x2 يمكن أن يكون 0 ، لأنني أعرف ذلك بالفعل. هذا يسمح لي بتقليل عدد الطلبات بحوالي 2-5 مرات.

التخزين المؤقت

هذا لا يحل مشكلة الصيغة الضخمة الناتجة عن دائرة "العد". كما قلت ، فإن عدد الجمل بترتيب N ^ 2. على لوحة كبيرة ، يمكن أن تصل الصيغة إلى 10000 افتراض.

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

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

حالة أخرى: اللعب في الخارج

هل يُسمح لك بالنقر في أي مكان على الخريطة خارج الحدود بين المنطقة المفتوحة وغير المفتوحة من الحقل؟

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

لذلك ، قمت بتغيير اللعبة بحيث تتم معاقبة نقرة خارج الحدود دائمًا. باستثناء بداية اللعبة ، بالطبع ، لأن اللوحة بأكملها تكون "خارج".

ولكن اتضح أن هناك سيناريو آخر: ماذا لو كانت جميع الحقول الحدودية مميتة؟ ليس لديك خيار سوى الكشف عن شيء آخر. هذا الوضع يمكن أن يجعل اللعبة سالكة من البداية. حتى الآن هناك استثناء آخر. يُسمح لك باللعب خارج الحدود إذا:

3 . .
. . .
. . .

الحقل غير مفتوح
قد تكون الخلايا الملغومة موجودة على الحدود (النقر على الخارج يجب أن يكون آمنا) ، أو
يجب أن يكون هناك قنابل في جميع الخلايا على الحدود (يجب عليك النقر في الخارج).

تحديث : تبين أن التغيير مثير للجدل ، لأن التقييد مصطنع إلى حد ما. أضفت مفتاحًا يسمح / يمنع اللعب بهذه الشروط.

كل شيء

يمكنك لعب Kaboom هنا . حاول تشغيل وضع التصحيح: فهو يجعل اللعبة تافهة ، لكنه يظهر جيدًا كيف تعمل.

كود مصدر جيثب . إنه ليس وسيمًا جدًا.

قد تكون مهتمًا أيضًا بلعبة مماثلة من Simon Tatham ، مبتكر PuTTY. نسخته لها تطور مختلف: إنها قابلة للحل دائمًا دون مضاربة.

العب بحكمة!

ما هي الأشياء الأخرى المفيدة للقراءة على مدونة Cloud4Y

→ كيف "كسر" البنك
→ الخصوصية الشخصية؟ لا ، لم يسمعوا
→ The Great Theory of Snowflakes
→ تشخيص اتصالات الشبكة على جهاز توجيه EDGE افتراضي
→تقوم الفيروسات المقاومة لـ CRISPR ببناء ملاجئ لحماية الجينوم من الإنزيمات التي تخترق الحمض النووي.

اشترك في قناة Telegram الخاصة بنا حتى لا تفوتك مقالة أخرى! لا نكتب أكثر من مرتين في الأسبوع وفقط في العمل. نذكرك أن الشركات الناشئة يمكنها الحصول على مليون روبل. من Cloud4Y. الشروط والأحكام لأولئك الذين يرغبون - على موقعنا: bit.ly/2sj6dPK