गेम एल्गोरिदम को हल करना (बटनिया, रोशनी-आउट संस्करण)

Question

मैं एक गेम एल्गोरिदम के लिए एक सुलभता कार्य बनाने की कोशिश कर रहा हूं। असल में एक ऐसा फ़ंक्शन जो किसी दिए गए गेम के लिए सही या गलत देता है, अगर यह हल करने योग्य है या नहीं।

यह गेम Buttonia.com है (जो अभी तक एल्गोरिदम लागू नहीं करता है), एक प्रकार का रोशनी-आउट गेम। असल में आपके पास बटन का ग्रिड होता है, जिनमें से प्रत्येक दबाए जाने पर, इसके कुछ पड़ोसियों की स्थिति बदल देगा। वर्तमान में मैं एक यादृच्छिक गेम कॉन्फ़िगरेशन उत्पन्न करता हूं और फिर यथासंभव हेरिस्टिक को लागू करता हूं। शेष ब्रूट फोर्स सर्च द्वारा तय किया जाता है।

मेरी प्रगति अब तक मॉडल के मॉडल के लिए समीकरणों की एक प्रणाली बनाने के लिए थी। - (button_1 + button_2 + ... + button_X)% 2

button_A = 1: प्रत्येक बटन राज्य बार विषम संख्या में बदलने के लिए एक नीचे राज्य में समाप्त करने की जरूरत है के रूप में, यह समीकरण इस होगा है

बटन_एक्स के माध्यम से बटन_1 बटन_ए पर प्रभाव वाले बटनों के राज्य हैं। कुछ बटन तुरंत हल किए जा सकते हैं, अगर वे दूसरों पर निर्भर नहीं हैं। बाकी के लिए, मैं एक कॉन्फ़िगरेशन का प्रयास करता हूं जब तक कि मुझे कोई संघर्ष न हो और फिर ट्रैक न करें।

वर्तमान में यह एल्गोरिदम गेम की छोटी कॉन्फ़िगरेशन के लिए व्यावहारिक है। मैंने इसे 3x3 गेम से 10x10 के आकार तक परीक्षण किया है। जहां 6x6 व्यावहारिक खेल के लिए ऊपरी सीमा के पास है।

समीकरणों ने इसे व्यावहारिक बनाकर, ब्रूट-बल से खोज स्थान को काट दिया। समीकरणों की प्रणाली को हल करने का एक पूरी तरह से गणितीय तरीका हो सकता है। ascii में

---

नमूना 3x3 खेल (buttonia.com/?game=2964 से):

||# 
-o- 
+#| 

Legend: 
o = affect only self 
- = affect left and right neighbors 
| = affect above and below neighbors 
+ = affect left, right, above and below neighbors 
# = affect all 8 surrounding neighbors 

समाधान, प्रेस इन: (0,0), (2,0), (1, 2), (0, 1), (1, 1), इस खेल के लिए (2,1)

समीकरण:

Button_0_0 = 1 - (0) % 2 
Button_1_0 = 1 - (Button_2_0) % 2 
Button_2_0 = 1 - (0) % 2 
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2 
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2 
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2 
Button_0_2 = 1 - (Button_1_2) % 2 
Button_1_2 = 1 - (Button_0_2) % 2 
Button_2_2 = 1 - (Button_1_2) % 2 

संभावित समाधान:

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

-1 = -1*B00 + 0*B10 + 0*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22 
-1 = 0*B00 + -1*B10 + -1*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22 

चर्चित यहाँ समाधान:: तो पहले दो समीकरणों क्रमशः बदल जाएगा Gaussian Elimination with custom operators

करीब हो रही है। लगभग पूर्ण समाधान पोस्ट करने के लिए लगभग तैयार: Inverting binary networks

Answer 1

यह एफ , क्षेत्र दो तत्वों 0 और युक्त अधिक रेखीय समीकरण की एक प्रणाली है 1.

तुम बस सामान्य रेखीय समीकरण की तरह इसे हल कर सकते हैं, लेकिन आप गणित सापेक्ष क्या करना है 2 ।

संपादित करें: इस मामले के लिए रेखीय बीजगणित बिल्कुल वास्तविक संख्या की तरह काम करता है, को छोड़कर आप आपरेशनों को बदलने के लिए है कि:

• जोड़ और घटाव अनन्य बन या, यानी 0 + 0 = 0 , 0 + 1 = 1, 1 + 1 = 0.

• गुणा हो जाता है और: 0 * = 0 0, 0 * 1 = 0, 1 * 1 = 1

• डिवीजन ही संभव है एक के बाद: 0/1 = 0, 1/1 = 1.

सभी अपने समीकरणों में गुणांक और अज्ञात संभावित मान हैं या तो 0 या 1.

तो सापेक्ष थप्पड़ मारा नहीं है आपके द्वारा लिखे गए समीकरणों के बाहर, यह संचालन में निहित है।

यदि समीकरणों की आपकी प्रणाली हल करने योग्य नहीं है तो आपको समीकरण 0 = 1 मिलेगा, जो स्पष्ट रूप से हल करने योग्य नहीं है।

Answer 2

यादृच्छिक स्थिति से शुरू करने के बजाय, यादृच्छिक स्विच फ़्लिप करके प्रारंभिक स्थिति क्यों न उत्पन्न करें, यानी एक हल राज्य से पीछे की ओर एक प्रारंभिक स्थिति में काम करें। इस तरह आप केवल हल करने योग्य पहेली उत्पन्न करते हैं।

Answer 3

चूंकि यह समय-सीमित समस्या नहीं है (अच्छी तरह से, यह मानते हुए कि यह एक दिन से भी कम समय में किया जा सकता है), मैं शायद एक गहराई तक सीमित चौड़ाई-पहली खोज के लिए जाऊंगा, प्रत्येक स्तर पर एक संभावित कदम उठाएगा और फिर प्रत्येक चाल से प्रत्येक चाल चलती है।

यह धीमा हो जाएगा, हालांकि अगर कोई है तो जवाब खोजने की गारंटी दी जाती है!

Answer 4

यह लगभग रैखिक समीकरणों (मोड 2 को छोड़कर) की तरह दिखता है, ताकि आप उनको हल करने के लिए सामान्य तकनीकों में से एक को अनुकूलित कर सकें - उदा। मैट्रिक्स फॉर्म (wikipedia) में सिस्टम की पंक्ति में कमी।

Answer 5

मान लीजिए कि आपने समीकरणों की एक प्रणाली बनाई है और उन्हें उतना ही हल किया है जितना आप कर सकते हैं, लेकिन समीकरण के बाईं ओर सभी पंक्तियों के साथ कुछ पंक्तियां समाप्त हो गई हैं (मैं एक संवर्धित मैट्रिक्स के रूप में समीकरणों का प्रतिनिधित्व कर रहा हूं) मान लीजिए कि आप Z2 अंगूठी में सिस्टम को हल करने का प्रयास किया (जो इस विशेष उदाहरण के लिए व्यावहारिक शब्दों में है कि केवल एक ही परिवर्तन है कि 1 + 1 = 0, बाकी सब कुछ वही रहता है ... ergo एकमात्र ऑपरेटर जो हमें चाहिए XOR है) और समाप्त निम्नलिखित मैट्रिक्स के साथ:

1001 1 
0100 1 
0011 0 
0000 0 

आप इस उदाहरण में देख सकते हैं, 4 पंक्ति जिसका अर्थ है कि हम इसके लिए एक जवाब नहीं मिला है सब 0 है। हालांकि इस तरह से सोचें: सभी 0 की एक पंक्ति का अर्थ है कि वह चर समाधान को प्रभावित नहीं करता है। यह वास्तव में शब्दों की एक खराब पसंद है ... इसका मतलब है कि उनके पास कोई मूल्य हो सकता है (और हम यहां भाग्यशाली हैं, क्योंकि सभी मानों का मतलब 1 या 0 है, वास्तविक संख्याओं के विपरीत ... तो इसका मतलब है कि हमारे पास 2 है इस प्रणाली के लिए समाधान)।

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

button_0 + button_3 = 1 

लेकिन हम जानते हैं कि बटन 3 कुछ भी हो सकता है (क्योंकि लाइन 3 सभी 0 है)। इस बिंदु पर बटन 3 तो अब हम जानते हैं कि इसका मतलब है

button_0 + 0 = 1 

तो हम एक तथ्य यह है कि button_0 1 है के लिए पता 0 (पंक्ति 3 पर सबसे दायीं ओर का स्तंभ इस बिंदु पर 0 है)।इसलिए इस प्रणाली में हालांकि हम सीधे बटन_3 नहीं ढूंढ पाए, फिर भी हमारे पास एक वैध समाधान है।

ऊपर उत्पन्न मैट्रिक्स सॉल्यूबिलिटी की जांच के लिए पर्याप्त है। एक पंक्ति सभी 0s हैं, तब यह अनिवार्य रूप से कह रही है कि

nothing = nothing 

या, बेहतर कल्पना करने के लिए क्यों यह काम करता है,

0x = 0 

जो समझ में आता है, सिस्टम अभी भी मान्य है। लेकिन हम एक पंक्ति है कि सभी 0s दायीं बिट को छोड़कर, यानी

0000 1 

कि

0x = 1 

जो असंभव है इसलिए अब हम जानते हैं कि इस प्रणाली हल नहीं किया जा सकता है कह रही है की जाएगी सामना करते हैं, चूंकि हम इस तरह की असंभव स्थिति को हल नहीं कर सकते हैं।

इसलिए संक्षेप में, समीकरण जितना संभव हो उतना समीकरण को हल करने और हल करने के लिए, चिंता न करें अगर आप वास्तव में यह पता नहीं लगा सकते कि कुछ चर क्या हैं, जब तक आप सामना नहीं करते हैं, किसी भी समय, असंभव पंक्ति मैंने अभी उल्लेख किया है कि खेल हल करने योग्य है।

लेकिन अगर हम सिस्टम को सबसे कम समाधान चाहते हैं तो क्या होगा? यहां हमें सभी संभावित समाधानों की जांच करनी होगी। हमारे पास बटन_3 है जो कि कोई मान हो सकता है, इसका मतलब है कि कॉलम 3 में से कोई भी मतलब है कि जिस पंक्ति में यह पाया जाता है, वह बटन_3 से प्रभावित होता है। तो मान लीजिए कि हम जांचना चाहते हैं कि बटन_3 का उपयोग करने वाला समाधान छोटा होगा या नहीं। हम एक और मैट्रिक्स बनाते हैं, लेकिन बटन_3 को 1 पर सेट करें (चूंकि हमने पहले स्थापित किया था कि यह कुछ भी हो सकता है, और हमारे पास पहले से 0 था, इसलिए अब हम 1 की जांच करते हैं)। अब हम निम्नलिखित मैट्रिक्स के साथ अंत:

1001 1 
0100 1 
0011 0 
0001 1 

हम जानते हैं कि हम कर सकते हैं जितना कम करने और अब इस मैट्रिक्स के साथ अंत:

1000 0 
0100 1 
0010 1 
0001 1 

यह अभी भी एक मान्य समाधान है, लेकिन हम देख सकते हैं कि समाधान लंबा है (2 बटन प्रेस के बजाय 3 की आवश्यकता है) इसलिए हम इसे छोड़ दें। हमें उन सभी पंक्तियों को सेट करने के लिए प्रत्येक क्रमपरिवर्तन के लिए ऐसा करना है जो हमें 0 से 1 तक मिलते हैं। इसलिए यदि हमारे पास एक्स पंक्तियां हैं जो सभी 0 थीं, तो सिस्टम में x^2 समाधान हैं, और हमें उन सभी को जांचना होगा।