🖲️ 👏🏿 🧚🏿 कबूम: एक असामान्य सैपर 🤴🏽 ⛲️ 👠

एक बच्चे के रूप में, मैं अपने पिता के काम में सप्ताह में तीन बार एक-डेढ़ घंटे बैठता था। मुझे एक कंप्यूटर पर जाने की अनुमति दी गई थी, जहां मनोरंजन से केवल एक सैपर और पेंट था। मैं जल्दी से ड्राइंग करके थक गया था, लेकिन पूरे क्षेत्र को खोलने की इच्छा और विस्फोट नहीं होने से मुझे इस खेल को खेलने के लिए नए और नए तरीकों की तलाश करने के लिए प्रेरित किया। कई साल बाद, मैं गलती से एक दिलचस्प लेख पर एक सैपर के क्लोन के बारे में ठोकर खा गया, और पास नहीं हो सका। मेरा सुझाव है कि आप इसके साथ खुद को परिचित करें। यह काबूम के विकास के बारे में एक कहानी है, जो अपने स्वयं के उत्साह के साथ पौराणिक माइनस्वीपर खेल का एक क्लोन है।

कंप्यूटर गेम के मानकों से काफी पहले माइनस्वीपर दिखाई दिया। लेकिन यह मुझे लगता है कि ज्यादातर लोग उन खेलों को याद करते हैं जो विंडोज के पुराने संस्करणों का हिस्सा थे। मैं माइनस्वीपर में कभी अच्छा नहीं था, लेकिन मैंने इसे समय-समय पर खेला। कुछ लोग अधिक गंभीरता से खेलते हैं । और जो लोग खुद को खुश करना चाहते हैं, उनके लिए मैं माइनस्वीपर - द मूवी देखने की सलाह देता हूं ।

विचार

हाल ही में, मेरे पास एक विचार था: क्या होगा यदि आपको एक समझदार कंप्यूटर के खिलाफ माइनस्वीपर खेलना है?

आमतौर पर, खानों का स्थान खेल की शुरुआत में निर्धारित किया जाता है (लेकिन यहां कुछ ट्रिक्स हैं - उदाहरण के लिए, इसलिए आप पहले क्लिक को नहीं खो सकते हैं)। लेकिन क्या होगा अगर खानों का स्थान पहले से निर्धारित नहीं किया गया था और खेल शुरू होने के बाद खेल खानों का स्थान चुन सकता है?

यह बहुत क्रूर होगा: यदि आप एक वर्ग पर क्लिक करते हैं जिसमें एक खदान हो सकती है, तो यह हमेशा इसमें शामिल होगा! इस प्रकार, आपको पहले से साबित करना होगा कि वर्ग सुरक्षित है।

ऊपर की छवि में, एक डॉट के साथ चिह्नित कोशिकाओं में, कोई खानों की गारंटी नहीं है, और एक विस्मयादिबोधक चिह्न के साथ चिह्नित कोशिकाओं को एक होने की गारंटी है। प्रश्न चिह्न का मतलब अनिश्चितता है: शायद अगर आप अधिक सेल खोलते हैं, तो आप गणना कर सकते हैं कि कोई खदान वहां छिपी है या नहीं।

दूसरी तरफ, ऐसी स्थितियां हैं जब आपको अनुमान लगाना होगा:

निम्न कोशिकाओं में से एक में एक खदान है। लेकिन किस में, यह समझना असंभव है। आपको उनमें से एक को चुनना होगा। लेकिन जिस शर्त के अनुसार मैंने अभी बात की, उसका मतलब होगा निश्चित मृत्यु! मैं चाहता था कि खेल क्रूर हो, लेकिन अब यह स्पष्ट रूप से हार रहा है।
इसलिए, मैं विचार को थोड़ा बदल दूंगा। आप अनुमान लगा सकते हैं, लेकिन केवल अगर कोई सुरक्षित कोशिकाएं नहीं बची हैं। इस प्रकार, खेल क्रूर, लेकिन उचित होगा।

दूसरे शब्दों में:

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

ऐसे खेल को कैसे लागू किया जाए? मैं सभी संभावित क्षेत्रों की गणना करने की कोशिश कर सकता था, लेकिन यह अवास्तविक है: यहां तक कि एक छोटे 10x10 फ़ील्ड का मतलब 2 ^ 100 संभावनाएं हैं। केवल उन लोगों का चयन करना जिनमें एन मिनट होता है, मदद नहीं करते हैं।

सौभाग्य से, मुझे पूरे क्षेत्र के बारे में चिंता करने की आवश्यकता नहीं है। हम टैग्स से सटे लैंड माइंस के बारे में कुछ नहीं जानते हैं। मैं केवल उन लोगों में दिलचस्पी रखता हूं जो सीमा पर हैं, बाकी को दुर्घटना से काफी निर्धारित किया जा सकता है।

फिर मैं लेबल के अनुसार सीमा पर खानों के स्थान के लिए सभी विकल्पों की गणना कर सकता हूं। बैकट्रैकिंग (बैकट्रैकिंग) - एक अच्छी तकनीक जो आपको सभी संयोजनों के माध्यम से क्रमबद्ध करने की अनुमति देती है, लेकिन साथ ही साथ जल्दी से पीछे हटती है जैसे ही हम यह निर्धारित करते हैं कि एक शाखा गणना नहीं कर सकती है।

सीमा पर खानों के दो संभावित स्थानों को ऊपर दिखाया गया है। उन्हें मिलाकर, हम समझेंगे कि कौन से कोशिकाओं को खाली या खनन करने की गारंटी है।

मुझे खानों की कुल संख्या को ट्रैक करने की भी आवश्यकता है। इस प्रकार, स्थान वास्तव में "सीमा पर 5 मिनट, बाहर 5 मिनट" जैसा दिखता है। यह महत्वपूर्ण है क्योंकि अन्यथा मैं सीमा पर बहुत अधिक खदानें बना सकता था (या बहुत कम!)

तो, मेरे पास सभी विकल्प हैं। जब कोई खिलाड़ी पिंजरा खोलने का फैसला करता है तो क्या होता है?

एक यादृच्छिक विकल्प चुनें ("क्रूर लेकिन उचित" नियमों को संतुष्ट करता है)। यह सीमा पर खानों के स्थान का निर्धारण करेगा।
सीमा के बाहर बचे हुए लोगों को बेतरतीब ढंग से तितर-बितर करना।
यदि चयनित सेल में एक खदान है, तो खेल खत्म हो गया है।
अन्यथा:
1. पहचाने गए सेल के लिए एक नया लेबल परिभाषित करें
2. अतिरिक्त कोशिकाओं को प्रकट करें यदि यह 0 है
3. , ! .

छोटे खेतों के लिए यह सामान्य है। आमतौर पर केवल कुछ संभव संयोजन होते हैं ... प्रतीक्षा करें, यह क्या है?

अरे नहीं!

किसी तरह, मैं 18 मिलियन संभव खदान स्थानों को अनलॉक करने में कामयाब रहा। मेरा फ़ायरफ़ॉक्स मेमोरी के 12 गीगाबाइट्स को नष्ट करता है, और एक सेल खोलने में आधा मिनट लगता है। जाहिर है, मुझे एक बेहतर एल्गोरिथम चाहिए।

कोई यह नोटिस कर सकता है कि माइनस्वीपर एक एनपी-पूर्ण गेम है , और इसलिए तेजी से बढ़ते समय से बचा नहीं जा सकता है। और सामान्य मामले में, यह सच है - ऐसे पद होंगे जो गणना करने में बहुत समय लेंगे। लेकिन एक छोटे से क्षेत्र के लिए यह काम करता है।

मुझे सभी संयोजनों को याद रखने की आवश्यकता नहीं है। मुझे सभी संयोजनों की गणना करने की भी आवश्यकता नहीं है। एक आवश्यक तरीका है:

जांचें कि क्या सेल सुरक्षित, खतरनाक या अस्पष्ट है,
(, , ).

स्वयं विकल्पों को आज़माने के बजाय, मैं सैट सॉल्वर का उपयोग करने जा रहा हूँ । ये ऐसे उपकरण हैं जो एक सूत्र को तार्किक चर से लेते हैं और उन मानों के समूह की तलाश करते हैं जो सूत्र को सत्य बनाते हैं। इस तरह के एक काल्पनिक, लेकिन हमारे कार्य के लिए काफी वैध तरीका है।

सॉफ्टवेयर का एक अधिक शक्तिशाली वर्ग एसएमटी सॉल्वर्स है जो मूल्यों और सूत्रों की एक विस्तृत श्रृंखला के साथ काम करता है, जैसे कि फर्स्ट-ऑर्डर लॉजिक (क्वांटिफायर), सरणियां, पूर्णांक, और इसी तरह। यह कम से कम पूर्णांक के लिए कुछ समीकरणों को परिभाषित करने में मदद करेगा। लेकिन मुझे कुछ ऐसा चाहिए जो ब्राउज़र में काम करता हो। लोग ब्राउज़र में Z3Prover जैसे कुछ परिष्कृत उपकरणों को पोर्ट करने में कामयाब रहे , लेकिन WebAssembly संस्करण का वजन है17 एमबी , और यह बहुत ज्यादा है।

मुझे मिनीसैट मिला , एक छोटा सैट सॉल्वर, जो जोएल गैलेंसन द्वारा जावास्क्रिप्ट के लिए संकलित किया गया था। संकलित फ़ाइल केवल 200 किलोबाइट लेती है, इसलिए मैं इसका उपयोग करता हूं।

CNF सूत्र

SAT सॉल्वर्स कंजंक्टिव नॉर्मल फॉर्मूलों ( CNFs ) के साथ काम करते हैं । उदाहरण के लिए, CNF का सूत्र "OR का एक" है:

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

आप वाक्य तर्क के किसी भी सूत्र (चर, और, या, नहीं, निहितार्थ) को CNF में बदल सकते हैं, इसलिए यह एक सार्वभौमिक प्रारूप की तरह है।

हम इसका प्रयोग कैसे करते हैं? मान लीजिए हमारे पास एक बोर्ड है: अगर मैं अज्ञात कोशिकाओं (दक्षिणावर्त: X1, x2, x3) के लिए चर बनाता हूं, तो उन्हें निम्नलिखित समीकरणों को पूरा करना होगा: लेकिन CNF में "चर का योग 2" कैसे व्यक्त किया जाए? मुझे एक विधि मिली, जैसा कि मैंने बाद में सीखा, "द्विपद कोडिंग" कहा जाता है और सबसे सरल कोडिंग है। आपको चर के सभी संभावित सबसेट पर विचार करना चाहिए। उदाहरण के लिए, आपको निम्न सूत्रों की आवश्यकता है:

? ? 1
2 ? 1

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

x1 + x2 + x3 = 2

2 चर के प्रत्येक सबसेट के लिए, कम से कम एक सच है। यह सुनिश्चित करता है कि राशि 1 से अधिक है।
(x1 | x2) & (x1 | x3) & (x2 | x3)
कम से कम एक चर गलत है। यह सुनिश्चित करता है कि राशि 3 से कम है।
(~ x1 | ~ x2 | ~ x3)

x2 + x3 = 1मेरे लिए मुझे इसी तरह के फॉर्मूले की जरूरत है:

चर में से कम से कम एक सही है: (x2 | x3)
कम से कम एक चर गलत है (~ x2 | ~ x3)।

इसे मिलाकर, मुझे 6 अंकों के साथ एक सीएनएफ फॉर्मूला मिलता है। मानक DIMACS प्रारूप में: सभी स्थिति रेखाएं 0 से समाप्त होती हैं, और ऋणावेश के साथ ऋणात्मकता चिह्नित होती है। अगर मैं इसे मिनीसैट से कनेक्ट करता हूं (इसे स्वयं प्रयास करें), मुझे मिलता है: इसका मतलब है कि मिनीसैट ने एक समाधान पाया जहां एक्स 1 और एक्स 2 सत्य हैं और एक्स 3 झूठे हैं। यहाँ बोर्ड कैसा दिखेगा: पूरा कार्यक्रम थोड़ा और जटिल है: यह सिर्फ एक समाधान है, एक और है। इसलिए, यह पता लगाने के लिए कि क्या X1, x2, x3 सही (या गलत) हो सकता है, आपको अधिक अनुरोध करने की आवश्यकता है। मुझे यह पूछने की आवश्यकता है: “उपरोक्त सूत्र, साथ ही साथ X1 को देखते हुए, क्या यह संभव है? उपरोक्त सूत्र के बारे में कैसे, साथ ही ~ एक्स 1 "?

SAT 1 2 -3

! ! 1
2 . 1

एन्कोडिंग का मतलब है कि मुझे चर के एक सेट के सभी संभावित संयोजनों (उदाहरण के लिए, 3 के सभी सबसेट) को खोजने की आवश्यकता है। हालांकि, इस समीकरण के लिए केवल 8 चर होंगे, इसलिए सूत्र आमतौर पर काफी छोटा होता है ताकि मिनीसैट जल्दी से इसे हल कर सके।

न्यूनतम ट्रैकिंग

दुर्भाग्य से, यह एक पूर्ण समाधान नहीं है! मुझे अभी भी ट्रैक करने की आवश्यकता है कि कितनी खदानें बची हैं। कुछ संयोजन असंभव हैं, क्योंकि अन्यथा आप अनुमति से अधिक खदानें बना सकते हैं, और जीतना असंभव होगा।

वास्तव में, विपरीत मामला भी संभव है: यदि बहुत कम खदानें हैं, तो खेल समाप्त हो जाएगा, क्योंकि जगह के लिए कुछ भी नहीं होगा।

इसलिए, मुझे SAT के फॉर्मूले में संकेत देना होगा कि "खानों की संख्या X से कम नहीं है और Y से अधिक नहीं है"। पहले मैंने सोचा कि मैं सभी संयोजनों के साथ चाल का उपयोग कर सकता हूं। दुर्भाग्य से, यह बड़ी संख्या में बहुत अच्छी तरह से काम नहीं करता है। यदि कहते हैं, 20 कोशिकाएं और 10 मिनट हैं, तो द्विपदीय गुणांक से संख्याओं को जोड़ने के बाद , हमें पता चलता है कि संयोजनों की संख्या पहले से ही 6 अंक है!

इसलिए मुझे पता चला कि SAT फार्मूला में चर का योग सांकेतिक शब्दों में बदलना करने के कई अन्य तरीके हैं। आपको एक स्कीमा बनाने की जरूरत है जो अलग-अलग वैरिएबल को मिलाएगी। उदाहरण के लिए देखें, StackExchange पर यह उत्तर या यह एक ।

अंत में, मुझे ओलिवियर बाइलॉट और यासीन बुफहाद द्वारा लिखित "प्रभावी सीएनएफ एन्कोडिंग विथ बूलियन कार्डिनैलिटी कॉन्स्ट्रेक्ट्स " नामक एक लेख से इस विचार का एहसास हुआ । हम एक ऐसा पेड़ देखते हैं जो पुनरावर्ती संख्याओं को जोड़ता है (या बिट्स को सॉर्ट करता है ताकि हर कोई शुरुआत में हो)

इस आरेख के अंत में, आपको "आउटपुट" चर का एक सॉर्ट सेट मिलेगा। यह पुष्टि करने के लिए कि योग X से कम नहीं है, जाँचें कि परिणामी चर का पहला X 1. हैं। यह दावा करने के लिए कि योग Y से अधिक नहीं है, यह जाँचें कि परिणामी चर का अंतिम N - Y 0. है।

यह सभी संभव संयोजनों का उपयोग करने से बहुत बेहतर है हालाँकि, यह योजना अभी भी तर्कहीन है क्योंकि यह वाक्य still (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 के क्रम में है। एक बड़े बोर्ड पर, सूत्र 10,000 मान्यताओं तक हो सकता है।

सौभाग्य से, अधिकांश समय हम कई कोशिकाओं का सही अर्थ जानते हैं। यदि सेल खाली या गारंटीकृत भरा हुआ है, तो मान कभी नहीं बदलेगा! इसका मतलब है कि हम इसे कैश कर सकते हैं और इसे एसएटी फॉर्मूला में शामिल नहीं कर सकते हैं। एक बार जब हम सेल की स्थिति निर्धारित करते हैं, तो हमें अब इसे फिर से गणना में शामिल करने की आवश्यकता नहीं होगी। जब तक वे अपरिभाषित हैं, तब तक सेल का उपयोग किया जाएगा।

यह अनुकूलन थोड़ा खतरनाक है: हमारे पास अब पूरे बोर्ड की शुद्धता की पुष्टि करने वाला कोई फार्मूला नहीं है। यदि बाकी सब कुछ योजना के अनुसार काम करता है, तो यह कोई समस्या नहीं है, लेकिन यह त्रुटि ट्रैकिंग को जटिल कर सकता है।

एक और मामला: विदेश में खेलना

क्या आपको क्षेत्र के खुले और खुले क्षेत्र के बीच की सीमा के बाहर के नक्शे पर कहीं भी क्लिक करने की अनुमति है?

प्रारंभ में, मुझे लगा कि यह अनुमान लगाने के समान था: यदि कोई सुरक्षित सेल नहीं हैं, तो आप बस क्षेत्र पर कहीं भी क्लिक कर सकते हैं। लेकिन कुछ को यह अजीब लगता है कि यह एक खाली पिंजरे के उद्घाटन की गारंटी देता है।

इसलिए, मैंने खेल को बदल दिया ताकि सीमा के बाहर एक क्लिक हमेशा सजा रहे। खेल की शुरुआत के अपवाद के साथ, ज़ाहिर है, क्योंकि तब पूरा बोर्ड "बाहर" है।

लेकिन यह पता चला है कि एक और परिदृश्य है: क्या होगा यदि सभी सीमा क्षेत्र घातक हैं? आपके पास कुछ और प्रकट करने के अलावा कोई विकल्प नहीं है। यह स्थिति खेल को शुरू से ही अगम्य बना सकती है। तो अब एक और अपवाद है। आपको सीमाओं से बाहर खेलने की अनुमति है यदि:

3 . .
. . .
. . .

मैदान खुला नहीं है
खनन की गई कोशिकाएं सीमा पर स्थित हो सकती हैं (बाहर की तरफ क्लिक करना सुरक्षित होना चाहिए), या
सीमा पर सभी कक्षों में बम होने चाहिए (आपको बाहर क्लिक करना होगा)।

अद्यतन : प्रतिबंध विवादास्पद है क्योंकि प्रतिबंध कुछ हद तक कृत्रिम है। मैंने एक स्विच जोड़ा जो इन शर्तों के साथ खेलने की अनुमति / निषेध करेगा।

यह सब है

आप यहां काबूम खेल सकते हैं । डिबगिंग मोड चालू करने का प्रयास करें: यह गेम को तुच्छ बनाता है, लेकिन यह अच्छी तरह से दिखाता है कि यह कैसे काम करता है। जीथुब

स्रोत कोड । वह बहुत सुंदर नहीं है। आप पुट्टी के निर्माता साइमन टाथम से भी इसी तरह के खेल में दिलचस्पी ले सकते हैं । इसके संस्करण में एक अलग मोड़ है: यह हमेशा अटकलों के बिना हल करने योग्य है। बुद्धिमानी से खेलते हैं! Cloud4Y ब्लॉग पर पढ़ने के लिए और क्या उपयोगी हो सकता है → बैंक कैसे "टूट गया" → व्यक्तिगत गोपनीयता? नहीं, उन्होंने नहीं सुना → द ग्रेट थ्योरी ऑफ़ स्नोफ्लेक्स → एक वर्चुअल एज रूटर पर नेटवर्क कनेक्शन का निदान →

CRISPR- प्रतिरोधी वायरस जीनोम को डीएनए-मर्मज्ञ एंजाइमों से बचाने के लिए आश्रयों का निर्माण करते हैं।

हमारे टेलीग्राम चैनल की सदस्यता लें ताकि आपको एक और लेख याद न हो! हम सप्ताह में दो बार से अधिक और केवल व्यापार पर नहीं लिखते हैं। हम आपको याद दिलाते हैं कि स्टार्टअप को 1 मिलियन रूबल मिल सकते हैं। Cloud4Y से। हमारी वेबसाइट पर चाहने वालों के लिए नियम और शर्तें: bit.ly/2sj6dPK