"माइनस्वीपर" कैसे हल करें (और इसे बेहतर बनाएं)


माइनस्वीपर सरल नियमों के साथ एक सरल खेल है, हालांकि इसके कुछ विन्यास दिलचस्प कठिनाइयों का निर्माण करते हैं। इस लेख में, हम बढ़ती जटिलता के साथ एक माइनस्वीपर सॉल्वर बनाएंगे, और इस पर प्रतिबिंबित करेंगे कि मदद के स्तर में क्रमिक वृद्धि के साथ खेल की गतिशीलता कैसे बदलती है। अंत में, हम बहुत अधिक दिलचस्प गेमप्ले के साथ खेल का एक नया संस्करण विकसित करेंगे।

स्थानीय तर्क: शून्य पड़ोसी खदानें


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

यह तर्क पूरी तरह से स्थानीय है: अगली कार्रवाई का फैसला करने के लिए केवल एक सेल जानकारी को ध्यान में रखा जाता है।

ऐसी स्थिति के साथ आना मुश्किल है जिसमें खेल इस स्वचालित मदद के बिना भी बदतर हो जाएगा। इस तरह का खेल खेलने की कोशिश करें कि यह कैसे हो जाता है कि यह स्वचालित रूप से खुलने वाली कोशिकाओं के बिना जाता है [मूल लेख में, सभी उदाहरण इंटरैक्टिव हैं] :


पर्यावरण पर आधारित स्थानीय विचार


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

इन नियमों में, एक सेल को ध्यान में रखा जाता है, साथ ही पड़ोसी कोशिकाओं की स्थिति (खुली / जाँच की जाती है)।

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


इस तरह के स्वचालन का एक दिलचस्प दुष्प्रभाव है - बॉक्स की जांच करने पर तुरंत घातक परिणाम हो सकते हैं।

अन्यथा, हम उन स्थितियों का अनुभव कर सकते हैं जिन्हें तीन श्रेणियों में विभाजित किया जा सकता है:

  1. स्वचालित नियमों को लागू करके खेलों को पूरी तरह से हल किया गया
  2. जटिल परिस्थितियों में तर्क के लिए अधिक कोशिकाओं की आवश्यकता होती है
  3. खेल के राज्य जिसमें कोई तार्किक तरीका आगे नहीं है - खिलाड़ी केवल संयोग से चुन सकता है, संभवतः संभावनाओं को ध्यान में रखते हुए।

स्थिति 1 सुंदर लगती है, लेकिन विशेष रूप से दिलचस्प नहीं अगर यह बहुत बार उठती है। क्या ऐसे गेम बिना स्वचालित समाधान के बेहतर होंगे? शायद नहीं; ऐसे गेम मैन्युअल रूप से हल किए जाने पर भी बहुत सरल होते हैं, और खिलाड़ी को विशेष रूप से ऐसे गेम खेलने में दिलचस्पी नहीं होती है, जिनमें कोई कठिनाई न हो। हालांकि, ज़ाहिर है, प्रतिक्रिया खेल में हमेशा कठिनाई होती है: आपको जल्द से जल्द कार्य करने की आवश्यकता होती है।

स्थिति 2 मुझे बहुत आकर्षक लगती है। हम तार्किक स्थितियों को हल करने, सटीक लक्ष्य पर कम समय बिताने और सही बटन दबाने पर अधिक ध्यान केंद्रित करते हैं। यह सैपर को एक सक्रिय पहेली की तरह बनाता है।

सिचुएशन 3 पूरी तरह से सारी मस्ती को नष्ट कर देती है। हालांकि, मैंने सुना है कि कुछ लोग यादृच्छिकता के साथ गेम खेलना पसंद करते हैं ।

क्या स्थिति 3 से छुटकारा पाना संभव है?

संपूर्ण समाधान: ग्लोबल रीजनिंग


खेल की स्थिति के लिए आवश्यक सभी तार्किक स्थितियों के एल्गोरिदम का पता लगाने के लिए, हमें खेल के सभी राज्यों के लिए एक संपूर्ण खोज करने की आवश्यकता है। माइनस्वीपर एक NP- पूर्ण कार्य साबित होता है। नीचे खेल के राज्य का एक छोटा लेकिन दिलचस्प और उदाहरण है, जिसका केवल एक तार्किक समाधान है, लेकिन इसे खोजने के लिए आपको खेल की स्थिति को ध्यान में रखना चाहिए:


क्या खेल के पूरे राज्य स्थान को खोजना संभव है? राज्य के कितने रूप हैं?

दिए गए:

डब्ल्यू = क्षेत्र की चौड़ाई

h = फ़ील्ड ऊंचाई

k = मिनटों की संख्या

एन = डब्ल्यू

फिर संभावित राज्यों की संख्या है

s= startpmatrixnk endpmatrix


मानक स्तर "शुरुआती", "एमेच्योर" और "पेशेवर" के लिए यह हमें देता है:

sb= startpmatrix8∗810 endpmatrix=1514732141616


si= startpmatrix16∗1640 endpmatrix=1.050∗1047


se= startpmatrix30∗1699 endpmatrix=5.602∗10104


हम समझते हैं कि एक भोली दृष्टिकोण यहां पूरी तरह से अनुचित है। आइए देखें कि एक भोली एल्गोरिथ्म कैसे दिख सकता है और पता लगा सकता है कि क्या यह किसी ऐसी चीज में अनुकूलित किया जा सकता है जो काम करता है।

Naive एल्गोरिथ्म


एल्गोरिथ्म का कार्य क्षेत्र की दी गई स्थिति के लिए आवश्यक सभी तार्किक स्थितियों को खोजना है। समाधानों पर सावधानीपूर्वक विचार करके इसे लागू करना मुश्किल होगा; कंप्यूटर बहुत जल्दी बेवकूफी भरे काम करता है।

हम "बेवकूफ़" क्या कर सकते हैं: सभी शेष खानों के लिए खदान की स्थिति के सभी संभावित क्रमचय उत्पन्न करें। यदि इस तरह का क्रमांकन सभी खुले नंबरों से मेल खाता है, तो यह गेम का सही समाधान होगा। फिर हम सभी संभावित क्रमपरिवर्तन का अध्ययन करते हैं, सभी संभव समाधानों को पाते हैं, लेकिन फिर भी यह नहीं जानते कि कौन सा सही है

यदि सभी संभावित समाधानों में कुछ सामान्य है, या तो खुली कोशिकाओं में, या खानों के रूप में चिह्नित कोशिकाओं के बीच, तो हम समझते हैं कि यह सामान्य वर्तमान क्षेत्र के लिए सही निर्णय का हिस्सा होना चाहिए। और वास्तव में: सही समाधान बनाना असंभव है जिसमें ऐसे मिलान तत्व नहीं हैं, अन्यथा हमने उन्हें खोज लिया होता।

इस प्रकार, हम क्षेत्र की वर्तमान स्थिति के लिए आवश्यक सभी तार्किक स्थितियों का पता लगा सकते हैं।

प्रतिबंधों के साथ और बिना सेल


उपरोक्त एल्गोरिथ्म में एक स्पष्ट समस्या है: उन राज्यों की संख्या जो इसे जांचने की आवश्यकता है। लेकिन सभी कोशिकाएं समान नहीं होती हैं। किसी संख्या के आगे अनियोजित कोशिकाएँ स्पष्ट रूप से उस संख्या तक सीमित होती हैं। हम इन कोशिकाओं को सीमित कहेंगे। शेष कोशिकाओं को हम असीमित कहेंगे।

यदि हम उपरोक्त एल्गोरिथ्म को लागू करते हैं, लेकिन हम केवल प्रतिबंधित कोशिकाओं के राज्यों के स्थान में खोज करेंगे, और जैसे ही हम प्रतिबंध को तोड़ेंगे, हम वापस जाएंगे, तो कई खेलों में हम सभी तार्किक परिस्थितियों को उचित मात्रा में हल कर सकते हैं:


असीमित कोशिकाओं के मामले में, हम यह नहीं पता कर सकते हैं कि खदान कहाँ स्थित हैं, और तार्किक रूप से हम तुरंत इसके बारे में जानते हैं। इसका मतलब है कि आप उन्हें गणना से बाहर कर सकते हैं और खुले नंबरों के बगल में केवल खानों के स्थान पर विचार कर सकते हैं।

हालांकि, हम जानते हैं कि एक निश्चित संख्या में खानें कई असीमित कोशिकाओं में प्रवेश कर सकती हैं; यदि 6 मिनट और 4 प्रतिबंधित कोशिकाएं हैं, तो सीमित कोशिकाओं में अधिकतम 4 खानें हो सकती हैं, अर्थात असीमित कोशिकाओं में कम से कम 2 मिनट अवश्य होने चाहिए। उसी तर्क से, हम कभी-कभी यह निर्धारित कर सकते हैं कि सभी असीमित कोशिकाएँ खाली होनी चाहिए या सभी में खदानें होनी चाहिए।

नीचे दिखाए गए मामले में, हम सभी खानों की स्थिति जानते हैं, इसलिए एआई को यह समझने में सक्षम होना चाहिए कि शेष कोशिकाओं पर कब्जा नहीं किया गया है:


निम्नलिखित मामले में, हम सभी खानों की स्थिति नहीं जानते हैं, लेकिन हम समझ सकते हैं कि शेष खदान को ऊपरी बाईं ओर दो कोशिकाओं में से एक में रखा जाना चाहिए। इसका मतलब है कि निचले दाएं कोने में शेष सेल मुक्त है:


यादृच्छिक संस्करण


यदि हम स्वचालित रूप से वैश्विक सॉल्वर चलाते हैं, तो हमें माइनस्वीपर का एक बेतरतीब ढंग से अनुकूलित संस्करण मिलेगा:


आप इस संस्करण में गेम को तीन श्रेणियों में विभाजित कर सकते हैं:

  1. खेल जिसमें खिलाड़ी मनमानी पसंद करता है और जीतता है।
  2. खेल जिसमें खिलाड़ी मनमानी पसंद करता है और हार जाता है।
  3. खेलों में एआई को बहुत समय की आवश्यकता होती है, और खिलाड़ी वास्तव में तर्क का उपयोग कर सकते हैं।

जाहिर है, यह मौका का खेल है। ऐसे खेलों की क्या अपील है? तर्क के संदर्भ में, ऊपर दिखाया गया खेल इस प्रकार है:


लेकिन कौन सा यादृच्छिक खेल बेहतर है? ऐसा लगता है कि यादृच्छिकता के साथ अन्य खेलों का अर्थ खिलाड़ी के कार्यों और जीतने / खोने के बीच एक जटिल संबंध के अस्तित्व में है। लॉटरी नंबर खींचने के लिए, जटिल मशीनों का उपयोग किया जाता है जो किसी संख्या का चयन करने की जल्दी में नहीं होते हैं और इस नंबर को दिखाने के लिए एक पूरा शो बनाते हैं।

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

क्या हम एक अलग प्रकार के खेल के साथ आ सकते हैं?

नियतात्मक संस्करण


अब हमारे पास एक AI है जो किसी दिए गए खेल राज्य से सभी तार्किक चरणों का निर्धारण करने में सक्षम है। कभी-कभी वह तार्किक कदम नहीं उठा पाएगा। ऐसी स्थितियों में, खिलाड़ी को अनुमान लगाना होगा और अगर वह भाग्यशाली नहीं है तो वह हार सकता है।

यदि हम एक और नियम जोड़ते हैं तो क्या होगा? जब खेल के पास कोई तार्किक तरीका नहीं है, तो हम मदद मांग सकते हैं। यदि एआई सहमत होता है कि खिलाड़ी कुछ भी नहीं कर सकता है, तो वह उसकी सहायता के लिए आता है। अन्यथा, खिलाड़ी तुरंत हार जाता है। यह दिलचस्प हो सकता है। यह किस तरह की मदद हो सकती है? शायद आपको खानों की मौजूदगी की परवाह किए बिना एक सेल खोलने की जरूरत है:


इस प्रकार, हम पूरी तरह से उन परिस्थितियों से छुटकारा पा लेते हैं जिनमें कोई भी संयोग से हार सकता है।

हालांकि, एक अपवाद है: अभी भी पतित स्थितियों की संभावना है जिसमें वैश्विक सॉल्वर समय की उचित मात्रा में गणना पूरा नहीं कर सकता है। दुर्भाग्य से, यह अनिवार्य परिणाम है कि माइनस्वीपर कार्य एनपी-पूर्ण है।

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

निष्कर्ष में


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

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

Source: https://habr.com/ru/post/hi453800/


All Articles