🌍 🍆 🤙🏿 माइनस्वीपर गेम के लिए बॉट लॉजिक एल्गोरिदम 🈸 ♿️ 😴

संभवतः हम में से प्रत्येक ने कभी "माइनस्वीपर" ("माइनस्वीपर") खेलने की कोशिश की है। खेल का तर्क सरल है, लेकिन एक समय में उन्होंने इसके पारित होने के एल्गोरिदम के लिए एक इनाम का भी वादा किया। मेरे बॉट में, तर्क में तीन एल्गोरिदम हैं जिनका उपयोग क्षेत्र की स्थिति के आधार पर किया जाता है। मूल एल्गोरिथ्म आपको एक खदान को खोजने की 100- और 0 प्रतिशत संभावना वाली सभी कोशिकाओं को खोजने की अनुमति देता है। केवल इस एल्गोरिथ्म का उपयोग करना और विशेषज्ञ स्तर पर एक मानक सैपर में एक विश्वसनीय समाधान की अनुपस्थिति में यादृच्छिक पर यादृच्छिक कोशिकाओं को खोलना, 33% जीत हासिल की जा सकती है। हालांकि, कुछ अतिरिक्त एल्गोरिदम आपको इस मान को 44% (विंडोज 7) तक बढ़ाने की अनुमति देते हैं।

मूल एल्गोरिथ्म

मुख्य एल्गोरिथ्म इस प्रकार है। एक ओपन सेल से सटे अज्ञात सेल (सेल क्लास) एक समूह (ग्रुप क्लास) में बनते हैं, जो उस सेल के मूल्य को भी रिकॉर्ड करता है जिसके पास यह है।

आंकड़ा चार समूहों को दिखाता है, जिनमें से कुछ प्रतिच्छेद करते हैं, और कुछ में अन्य समूह भी होते हैं। हम दर्शाते हैं (123.1) - समूह में 1,2 और 3 कोशिकाएं हैं, और एक ही समय में उनमें 1 खदान है। (5678.2) - चार कोशिकाओं में 2 खदानें हैं।

पहले आपको समूहों को परिवर्तित करने की आवश्यकता है। ऐसा करने के लिए:

प्रत्येक समूह की तुलना प्रत्येक बाद वाले समूह से करें।
यदि समूह समान हैं, तो दूसरे को हटा दें।
यदि एक समूह में दूसरा है, तो छोटे को बड़े से घटाएं। यही है, दो समूह थे (5678.2) और (5.1), बन गए (678.1) और (5.1); (2345.3) और (5.1) → (234.2) और (5.1)
उदाहरण के लिए समूह (123.1) और (234.2), निम्न सिद्धांत के अनुसार रूपांतरित हैं:
1. अन्तर्विभाजक कोशिकाओं का एक नया समूह बनाएँ (23;)
2. हम नए समूह में खानों की संख्या की गणना करते हैं समूह में खानों की संख्या के बराबर (234.2) एक दूसरे समूह में कोशिकाओं की शेष संख्या को घटाते हुए एक दूसरे समूह में अंतर कोशिकाओं को अलग करने के बाद (1?)। अर्थात् 2-1 = 1. हमें मिलता है (23.1)
3. यदि नए समूह (23.1) में खानों की गणना की गई संख्या कम खानों (123.1) के साथ समूह में खानों की संख्या के बराबर नहीं है, तो हम रूपांतरण रोक देते हैं
4. दोनों अन्तर्विभाजक समूहों से नवगठित समूह को घटाएँ। (123.1) - (23.1) = (1.0), (234.2) - (23.1) = (4.1)।
5. नवगठित समूह को समूहों की सूची में जोड़ें
इस प्रकार, (234.2) और (123.1) → (1.0) और (23.1) और (4.1)।
चरण 1 से दोहराएँ जब तक कोई परिवर्तन नहीं किया जाता है।

समूह बनाने और बदलने की विधि

/** *    ,     ,       ,  . */ private void setGroups() { groups.clear(); for (int x = 0; x < width; x++) for (int y = 0; y < height; y++) field[x][y].setGroup(groups); //   boolean repeat; do{ repeat=false; for (int i = 0; i < groups.size() - 1; i++) { //     Group groupI = groups.get(i); for (int j = i + 1; j < groups.size(); j++) { //       Group groupJ=groups.get(j); if (groupI.equals(groupJ)) //    {groups.remove(j--);break;} Group parent; //   Group child; //   if (groupI.size()>groupJ.size()) //       -  {parent=groupI;child=groupJ;} else {child=groupI;parent=groupJ;} if (parent.contains(child)) { //     parent.subtraction(child); //      repeat=true; //     } else if (groupI.overlaps(groupJ) > 0) { //     if (groupI.getMines()>groupJ.getMines())//       -  {parent=groupI;child=groupJ;} else {child=groupI;parent=groupJ;} Group overlap = parent.getOverlap(child);//     if (overlap != null) { //      (      0%  100%) groups.add(overlap); //       parent.subtraction(overlap); child.subtraction(overlap); repeat=true; } } } } } while(repeat); }

परिणामस्वरूप, हमें तीन प्रकार के समूह मिलते हैं।

खानों की संख्या शून्य है
खानों की संख्या समूह में कोशिकाओं की संख्या के बराबर है
समूह में कोशिकाओं की संख्या से कम शून्य शून्य संख्या

तदनुसार, पहले समूह से सभी कोशिकाओं को सुरक्षित रूप से खोला जा सकता है, और दूसरे समूह से चिह्नित किया जा सकता है। यह मुख्य एल्गोरिथ्म का सार है।

अगर कोई विश्वसनीय उपाय नहीं है

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

व्यक्तिगत कोशिकाओं में प्रायिकता की परिभाषा, कई खुली कोशिकाओं के प्रभाव को ध्यान में रखते हुए
संभावना समायोजन, एक दूसरे पर आम कोशिकाओं के साथ समूहों के पारस्परिक प्रभाव को ध्यान में रखते हुए

आइए विचार करें कि यह विधि उस स्थिति के उदाहरण पर कैसे काम करती है जब केवल 4 और 2 वाले दो पड़ोसी कोशिकाएँ खुली हों। कोशिकाओं 4 और 2 से खानों को खोजने की संभावनाएँ क्रमशः 4/7 = 0.57 और 2/7 = 0.28 हैं।

कई खुली कोशिकाओं के बगल में एक सेल में खदान की संभावना की गणना करने के लिए, हम किसी एक घटना की संभावना की गणना के लिए सूत्र का उपयोग करते हैं:

ईवेंट ए की घटना की संभावना, ए ₁ , ए ₂ , ..., ए _{एन के} कम से कम एक की उपस्थिति में शामिल है, कुल में स्वतंत्र, इकाई और विपरीत घटनाओं की संभावनाओं की उत्पाद के बीच अंतर के बराबर है। A = 1- (1-A ₁ ) * (1-A ₂ ) * .... * (1-A _n )

इस फॉर्मूले को लागू करने के बाद आसन्न कोशिकाओं में, परिणाम 1- (1-0.57) * (1-0.28) = 0.69 है।

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

4 / (0.57 + 0.57 + 0.57 + 0.69 + 0.69 + 0.69 + 0.69) = 0.895
0.57 * 0.895 = 0.485 0.69 * 0.895 = 0.618

अब जिन कोशिकाओं में 0.57 की संभावना थी उनमें 0.485 और वे 0.69 → 0.618 हैं
दूसरे समूह के लिए इसी तरह की गणना पिछले एक से खाते के समायोजन को ध्यान में रखकर की जाती है।

2 / (0.28 + 0.28 + 0.28 + 0.618 + 0.618 + 0.618 + 0.618) = 0.604
0.28 * 0.604 = 0.169 0.618 * 0.604 = 0.373

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

4 / (0.485 + 0.485 + 0.485 + 0.373 + 0.373 + 0.373 + 0.373) = 1.357
0.485 * 1.357 = 0.658 0.373 * 1.357 = 0.506
2 / (0.169 + 0.169 + 0.169 + 0.506 + 0.506 + 0.506 + 0.506) = 0.79
0.169 * 0.79 = 0.134 0.506 * 0.79 = 0.4

... आदि।

यह केवल उन कोशिकाओं में से एक का चयन करने के लिए रहता है जिनमें न्यूनतम संभावना होती है और एक चाल होती है।

कोड में यह विधि

 /** *          ,          */ private void correctPosibilities(){ Map<Cell,Double>cells= new HashMap<>(); //        ,          for (Group group : groups){ for (Cell cell: group.getList()){ Double value; if ((value=cells.get(cell))==null) //       cells.put(cell,(double) group.getMines()/ group.size()); //        else //    ,        cells.put(cell,Prob.sum(value,(double) group.getMines()/ group.size())); } } //      ,             boolean repeat; do{ repeat=false; for (Group group : groups){ //    List<Double> prob= group.getProbabilities(); //          Double sum=0.0; for (Double elem:prob)sum+=elem; //    int mines= group.getMines()*100; //        (- ) if (Math.abs(sum-mines)>1){ //     ,    repeat=true; //    Prob.correct(prob,mines); //   for (int i=0;i< group.size();i++){ //        double value= prob.get(i); group.getList().get(i).setPossibility(value); } } } } while (repeat); for (Cell cell:cells.keySet()){ //  if (cell.getPossibility()>99)cell.setPossibility(99); if (cell.getPossibility()<0)cell.setPossibility(0); } }

अंतिम चाल

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

LastTurns (9,21) ने 293,930 में से 144 उपयुक्त संयोजनों की जाँच की और 0% की न्यूनतम संभावना के साथ 3 कोशिकाएं पाईं

विचार को समझने की जटिलता के दृष्टिकोण से, यह विधि सबसे आसान है, इसलिए मैं अभी तक विस्तार से इसका विश्लेषण नहीं करूंगा।

इसका क्रियान्वयन

 /** *      .          30 * @return */ public ArrayList<Point> getLastTurns() { int minesLeft = countMinesLeft(); //     ArrayList<Cell> unknownCells = getUnknownCells(); //    int notOpened = unknownCells.size(); //    Integer[] combinations = new Sequence6().getSequensed(minesLeft, notOpened); //            ArrayList<String> list = new ArrayList<String>(); //    for (int i = 0; i < combinations.length; i++) { //                 String combination = Integer.toBinaryString(combinations[i]); //      ,     if (combination.length() < notOpened) { //    "0"    ,        String prefix = ""; for (int k = combination.length(); k < notOpened; k++) prefix += "0"; combination = prefix + combination; } for (int j = 0; j < notOpened; j++) { //      if (combination.charAt(j) == '1') unknownCells.get(j).setMine(); if (combination.charAt(j) == '0') unknownCells.get(j).setUnknown(); } if (test()) list.add(combination); //         ,       } clear(unknownCells); //       String[] comb = new String[list.size()]; list.toArray(comb); //    ,      int[] possibilities2 = new int[notOpened]; //     ,   ,        for (int i = 0; i < comb.length; i++) //    possibilities2[] for (int j = 0; j < notOpened; j++) if (comb[i].charAt(j) == '1') possibilities2[j]++; //        ,       1 int min = Integer.MAX_VALUE; ArrayList<Integer> minIndices = new ArrayList<>(); //       possibilities2[] for (int i = 0; i < possibilities2.length; i++) { if (possibilities2[i] == min) minIndices.add(i); if (possibilities2[i] < min) { min = possibilities2[i]; minIndices.clear(); minIndices.add(i); } unknownCells.get(i).setPossibility(100*possibilities2[i]/comb.length); //        } double minPossibility = 100.0 * possibilities2[minIndices.get(0)] / comb.length; System.out.println("LastTurns(" + minesLeft + "," + notOpened + ")  " + comb.length + "    " + combinations.length + "    " + minIndices.size() + " " + "    " + (int) minPossibility + " %"); ArrayList<Point> result = new ArrayList<Point>(minIndices.size());//       for (int index : minIndices) { result.add(unknownCells.get(index).getPoint()); } return result; }

निष्कर्ष

व्यवहार में, पर्याप्त संख्या में नमूनों के साथ, सेल में एक खदान की संभावनाओं की गणना और वास्तविक मूल्य लगभग मेल खाते हैं। निम्न तालिका एक रात के लिए विंडोज XP के तहत "माइनस्वीपर" पर बॉट के परिणामों को दिखाती है, जहां

परिकलित%
गणना की गई% के साथ सेल खुलने की कुल संख्या
प्रति खदानों की संख्या
वास्तविक%

1।	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2।	31	55	117	131	304	291	303	339	507	435	479	1201	152	146	118	143	164	141	367	3968	145	63	47	26	92
3।	1	4	9	6	20	19	27	29	56	43	60	147	15	25	14	20	33	26	65	350	14	5	12	4	23
4।	3	7	7	4	6	6	8	8	11	9	12	12	9	17	11	13	20	18	17	8	9	7	25	15	25

1।	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
2।	18	10	24	18	9	11	6	135	8	2	4	2	1	3	16		2	2			1				462
3।	1	9	2	3	3	2	1	43	1	0	1	0	0	1	4		1	1			0				210
4।	5	37	11	30	33	18	16	31	12	0	25	0	0	33	25		50	50			0				45

20-22% के क्षेत्र में एक बड़ी विसंगति शायद इस तथ्य के कारण है कि अक्सर इस प्रतिशत में ऐसी कोशिकाएं थीं जो पहले से ही पास नहीं थीं (उदाहरण के लिए, खेल की शुरुआत में), और माइनस्वीपर खिलाड़ी के लिए समायोजित, कभी-कभी खुले हुए सेल के तहत एक खदान को हटाते हुए। ऑपरेशन एल्गोरिथ्म जावा में लागू किया गया था और एक मानक विंडोज सैपर (7 और एक्सपी), वीके में एक आवेदन और एक गेमर पर परीक्षण किया गया था। वैसे, "तकनीकी समस्याओं" के कई दिनों के बाद, जब मेरे आईपी से मेरे खाते तक पहुँचने के लिए, गेमर ने क्षेत्र के भाग को खोलने के लिए पारिश्रमिक के नियमों को बदल दिया: शुरू में मैंने 10% बोली खुले मैदान के 10%, फिर 5%, फिर 2%, और जब मैंने वापस ली खेलना बंद कर दिया, फिर 5% लौटाया।

माइनस्वीपर गेम के लिए बॉट लॉजिक एल्गोरिदम

मूल एल्गोरिथ्म

अगर कोई विश्वसनीय उपाय नहीं है

अंतिम चाल

निष्कर्ष

More articles: