Minesweeper žaidimo kodas c. Botų loginiai algoritmai žaidimui Minesweeper. Grupių kūrimo ir konvertavimo metodas

Visi, kurie dirba su Operacinė sistema„Windows“, „Minesweeper“ žaidimas yra gerai žinomas. Šiame skyriuje aptariama panaši programa.

Programos lango pavyzdys žaidimo pabaigoje (žaidėjui atidarius langelį, kuriame yra mina) parodytas pav. 10.7.

Ryžiai. 10.7. Minosvaidžio langas

Žaidimo taisyklės ir duomenų pateikimas

Žaidimo lauką sudaro ląstelės, kurių kiekvienoje gali būti mina. Žaidėjo užduotis – surasti visas minas ir jas pažymėti vėliavėlėmis.

Naudodamas pelės mygtukus, žaidėjas gali atidaryti langelį arba įdėti į ją vėliavėlę, taip nurodydamas, kad langelyje yra mina. Ląstelė atidaroma paspaudus kairįjį pelės mygtuką, žymimasis langelis nustatomas paspaudus dešinįjį pelės mygtuką. Jei kameroje yra mina, kurią žaidėjas atidarė, tada įvyksta sprogimas (saperis padarė klaidą, o jis, kaip žinote, daro tik vieną klaidą) ir žaidimas baigiasi. Jei langelyje minos nėra, šiame langelyje rodomas skaičius, atitinkantis gretimose ląstelėse esančių minų skaičių.

Analizuodamas informaciją apie minų skaičių langeliuose, esančiuose šalia jau atidarytų, žaidėjas gali rasti ir pažymėti visas minas. Ląstelių, pažymėtų vėliavėlėmis, skaičiui apribojimų nėra. Tačiau norint užbaigti žaidimą (laimėti), vėliavėlės turi būti nustatytos tik tose ląstelėse, kuriose yra minų. Klaidingai pasirinktą vėliavėlę galima pašalinti dešiniuoju pelės mygtuku spustelėjus langelį, kuriame ji yra.

Tikriausiai kiekvienas iš mūsų yra kada nors žaidęs ar bent jau bandęs žaisti Minesweeper (MineSweeper). Žaidimo logika paprasta, tačiau vienu metu jie netgi pažadėjo atlygį už jo praėjimo algoritmą. Mano robote logika turi tris algoritmus, kurie naudojami atsižvelgiant į situaciją lauke. Pagrindinis algoritmas leidžia rasti visus langelius su 100 ir 0 procentų tikimybe rasti miną. Naudodami tik šį algoritmą ir atsitiktinai atidarydami savavališkus langelius, kai nėra patikimo sprendimo standartiniame „eksperto“ lygyje, galite pasiekti 33% laimėjimo. Tačiau kai kurie papildomi algoritmai leidžia padidinti šią vertę iki 44% („Windows 7“).

Pagrindinis algoritmas

Pagrindinis algoritmas yra toks. Nežinomos ląstelės (Cell class), esančios greta vieno atviro langelio, sudaromos į grupę (Group class), kurioje taip pat yra ląstelės, su kuria ji yra greta, reikšmė.

Paveiksle pavaizduotos keturios grupės, kai kurios iš jų susikerta, o kai kuriose netgi yra kitų grupių. Pažymėkite (123,1) - grupę sudaro 1, 2 ir 3 langeliai ir tuo pačiu metu juose yra 1 min. (5678.2) – keturiose kamerose yra 2 minos.

Pirmiausia turite konvertuoti grupes. Už tai:

1. Kiekvieną grupę lyginame su kiekviena sekančia grupe.
2. Jei grupės yra tos pačios, ištrinkite antrąją.
3. Jei vienoje grupėje yra kita, atimkite mažesnę iš didesnės. Tai yra, buvo dvi grupės (5678,2) ir (5,1), tai tapo (678,1) ir (5,1); (2345.3) ir (5.1) → (234.2) ir (5.1)
4. Susikertančios grupės, pavyzdžiui (123.1) ir (234.2), transformuojamos tokiu principu:
   1. Sukurkite naują susikertančių langelių grupę (23,?)
   2. Apskaičiuokite minučių skaičių nauja grupė, lygus minų skaičiui grupėje, kurioje yra daug minų (234,2), atėmus likusį langelių skaičių kitoje grupėje, atskyrus persidengiančius langelius (1,?). Tai yra, 2-1 = 1. Gauname (23.1)
   3. Jei apskaičiuotas minų skaičius naujoje grupėje (23.1) nėra lygus minų skaičiui grupėje, kurioje yra mažiau minų (123.1), tada sustabdykite konversiją
   4. Iš abiejų susikertančių grupių atimame naujai suformuotą grupę. (123.1)-(23.1) = (1.0), (234.2)-(23.1) = (4.1).
   5. Naujai suformuotos grupės įtraukimas į grupių sąrašą
   Taigi (234,2) ir (123,1) → (1,0) ir (23,1) ir (4,1).
5. Kartokite nuo 1 veiksmo, kol neatliksite jokių pakeitimų

Grupių kūrimo ir konvertavimo metodas

/** * Sukuria langelių grupių, susietų viena atviro lauko reikšme, sąrašą, taip pat skaido jas į smulkesnes, pašalina pasikartojančius. */ 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++) { // проходим по списку групп grupės grupė I = group.get(i); už (int j = i + 1; j< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем tos pačios grupės(groups.remove(j--);break;) Grupės pirminė; // didelė grupė Grupės vaikas; // mažesnė grupė if (groupI.size()>groupJ.size()) // nustatykite didesnes ir mažesnes grupes pagal langelių skaičių (parent=groupI;child=groupJ;) else (child=groupI;parent=groupJ ; ) if (parent.contains(child)) ( // jei didesniame yra mažesnis tėvas.subtraction(child); // tada atimkite mažesnįjį iš didesnio pakartokite=tiesa; // ištaisykite faktą, kad grupės pasikeitė ) else if (groupI.overlaps(groupJ ) > 0) ( // kitaip, jei grupės sutampa if (groupI.getMines()>groupJ.getMines())// nustatykite didesnes ir mažesnes grupes pagal minų skaičius (parent=groupI;child=groupJ;) else (child =groupI;parent=groupJ;) Group overlap = parent.getOverlap(child);// tada imame sankirtos if (persidengimas != null) rezultatą ) ( // ir jei tai prasminga (dėl sankirtos buvo atskleisti langeliai su 0 % arba 100 %) group.add(overlap); // tada atliekame atitinkamus sąrašo koregavimus parent.subtraction(overlap ); vaikas.atimtis(persidengimas); kartoti=tiesa; ) ) ) ) ) while(pakartoti); )

Dėl to turėsime trijų tipų grupes.

• minų skaičius lygus nuliui
• minų skaičius lygus ląstelių skaičiui grupėje
• nulinis minučių skaičius yra mažesnis nei langelių skaičius grupėje

Atitinkamai visas pirmosios grupės langelius galima saugiai atidaryti ir pažymėti iš antrosios grupės. Tai yra pagrindinio algoritmo esmė.

Jei nėra patikimo sprendimo

Tačiau dažnai pasitaiko situacijų, kai nėra patikimo situacijos sprendimo. Tada ateina pagalba sekantis algoritmas. Jos esmė – pasinaudoti tikimybių teorija. Algoritmas veikia dviem etapais:

1. Tikimybės nustatymas atskirose ląstelėse, atsižvelgiant į kelių atvirų ląstelių įtaką
2. Tikimybių korekcija, atsižvelgiant į grupių, turinčių bendras ląsteles, tarpusavio įtaką viena kitai

Panagrinėkime, kaip veikia šis metodas situacijos pavyzdyje, kai atviri tik du gretimi langeliai, kurių reikšmės 4 ir 2. Tikimybė rasti minas iš 4 ir 2 langelių atskirai yra 4/7=0,57 ir 2/7=0,28 , atitinkamai.

Norėdami apskaičiuoti tikimybę rasti miną langelyje šalia kelių atvirų langelių, naudojame bent vieno įvykio tikimybės apskaičiavimo formulę:

Tikimybė, kad įvyks įvykis A, susidedantis iš bent vieno iš įvykių A 1 , A 2 ,..., A n , nepriklausomų visumoje, yra lygi skirtumui tarp vienybės ir tikimybių sandaugos. priešingų įvykių. A=1- (1-A 1)*(1-A 2)*...*(1-A n)

Gretimose ląstelėse pritaikius šią formulę gaunamas rezultatas 1-(1-0,57)*(1-0,28)=0,69.

Tačiau reikia atsiminti, kad kiekvienos langelių grupės tikimybių suma turi būti lygi minų skaičiui grupėje. Todėl visos vertės kiekvienoje grupėje turi būti padaugintos taip, kad galų gale jų suma būtų lygi minučių skaičiui. Šis skaičius yra lygus minų skaičiui grupėje, padalytam iš esamos grupės langelių tikimybių sumos:

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

Dabar tos ląstelės, kurių tikimybė buvo 0,57, turi 0,485, o tos, kurios turi 0,69 → 0,618
Panašų skaičiavimą atliekame ir antrajai grupei, atsižvelgdami į ankstesnės grupės koregavimą.

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

Matome, kad tikimybė bendruose langeliuose vėl pasikeitė, todėl šis kiekvienos grupės koregavimas turi būti kartojamas keletą kartų, kol sistema pasieks tam tikras stabilias reikšmes, kurios bus tikrosios tikimybės rasti minų ląstelėse.

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

… ir tt

Belieka tik pasirinkti vieną iš langelių su mažiausia tikimybe ir atlikti judesį.

Šis metodas kode

/** * Metodas koreguoja minų radimo langeliuose tikimybių reikšmes, atsižvelgiant į kaimyninių langelių tikimybių abipusę įtaką viena kitai */ private void rightPosibilities()( Žemėlapis ląstelės = naujas HashMap<>(); // ciklas kiekviename langelyje nustato vieną tikimybės reikšmę, atsižvelgdamas į skirtingas tikimybes langelyje iš skirtingų grupių, skirtų (Grupė grupė: grupės)( for (Ląstelės langelis: group.getList())) ( Dviguba reikšmė; if ( (value=cells. get(cell))==null) // jei langelio dar nėra žemėlapyje cell.put(cell,(double) group.getMines()/ group.size()); // tada pridėkite ją su reikšme iš grupės else / /jei ji jau yra žemėlapyje, tada koreguojame jos reikšmę pagal tikimybių teoriją cell.put(cell,Prob.sum(value,(double) group.getMines()/ group.size())); ) ) // kilpa koreguoja reikšmes atsižvelgdama į tai, kad tikimybių suma grupėje turi būti lygi minų skaičiui loginėje kartojimo grupėje; do(pakartokite=false; for (Grupių grupė: grupės)( // kiekvienai sąrašo grupei prob=group.getProbabilities(); // paimkite visų grupės langelių tikimybių sąrašą procentais Dviguba suma=0,0; for (double elem:prob)sum+=elem; // apskaičiuokite jo sumą int mines= group.getMines()*100; // kasyklų skaičių grupėje padauginkite iš šimto (dėl procentų) if (Math. abs(sum-mines)>1)( // jei skirtumas tarp jų didelis, tai darome koregavimą pakartokite=tiesa ; // pataisyti koregavimo faktą Prob .correct(prob,mines);//pataisyti sąrašą (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); } }

Paskutiniai judesiai

Paskutiniame žaidimo etape didelį vaidmenį vaidina nepažymėtų minų skaičius. Žinodami šį skaičių, galite pakeisti juos į nežinomas ląsteles žiauria jėga ir pažymėti tinkamas parinktis. Skaičiuodami kiekvienam langeliui tinkamas parinktis, suskaičiuojame ženklų skaičių. Padalinę gautas reikšmes iš bendro ženklų skaičiaus, gauname tikimybę rasti minų kiekvienai ląstelei. Pavyzdžiui, šioje situacijoje, kuri, atrodo, turi tik vieną patikimą sprendimą, paskutinis metodas (LastTurns) rado 3 langelius su 0% tikimybe rasti miną.

LastTurns(9,21) išbandė 144 derinius iš 293930 galimų ir rado 3 langelius su mažiausia 0% tikimybe

Idėjos supratimo sudėtingumo požiūriu šis metodas yra lengviausias, todėl kol kas detaliau jo neanalizuosiu.

Jo įgyvendinimas

/** * Nepriklausomas skaičiavimo algoritmas banaliu surašymu. Galima naudoti tik tuo atveju, jei nežinomų langelių skaičius yra mažesnis nei 30 * @return */ public ArrayList GetLastTurns() ( int minesLeft = countMinesLeft(); // nepažymėtų minų skaičius ArrayList unknownCells = getUnknownCells(); // nežinomų langelių sąrašas int notOpened = unknownCells.size(); // nežinomų langelių skaičius Sveikųjų skaičių deriniai = new Sequence6().getSequensed(minesLeft, notOpened); // masyvas įvairių derinių iš tam tikro skaičiaus minų tam tikrame langelių skaičiuje ArrayList sąrašas = naujas ArrayList (); // galimų derinių sąrašas (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.toArray(comb); // преобразовываем список в массив, и далее работаем с массивом int possibilities2 = new int; // массив по числу неизвестных ячеек, содержащий количество вариантов, где может располагаться мина в заданной ячейке 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; ArrayListminIndexes = naujas ArrayList<>(); // Indeksų su mažiausia reikšme galimybių2 sąrašas (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 / comb.length; System.out.println("LastTurns(" + minesLeft + "," + notOpened + ") проверил " + comb.length + " подходящих комбинаций из " + combinations.length + " возможных и нашел " + minIndices.size() + " ячеек" + " с минимальной вероятностью " + (int) minPossibility + " %"); ArrayListRezultatas = naujas ArrayList (minIndices.size());// langelių koordinačių sąrašas su minimalia tikimybe (int index: minIndexes) ( result.add(unknownCells.get(index).getPoint()); ) grąžina rezultatą; )

Išvada

Praktiškai su pakankamu mėginių skaičiumi apskaičiuotos ir faktinės tikimybės rasti miną ląstelėje beveik sutampa. Šioje lentelėje rodomi roboto, veikiančio „Minesweeper“ sistemoje „Windows XP“, rezultatai vieną naktį, kur

1. Numatomas %
2. Bendras langelių angų skaičius su apskaičiuotu %
3. Patikimų skaičius kasykloje
4. Faktinis %

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

Didelis neatitikimas 20-22% srityje tikriausiai atsirado dėl to, kad dažnai šis procentas turėjo langelių, kurių šalia dar nebuvo atidarytų (pavyzdžiui, žaidimo pradžioje), o Minesweeper prisitaikydavo prie žaidėjas, kartais išimdamas miną iš po atidarytos kameros. Darbo algoritmas buvo įdiegtas „Java“ ir išbandytas standartiniame „Windows Sapper“ (7 ir XP), programoje VK ir žaidime. Beje, po kelių dienų „techninių nesklandumų“ prisijungus prie paskyros iš IP, žaidimas pakeitė atlyginimo už lauko dalies atidarymą taisykles: iš pradžių grąžino 10% statymo už 10% atviro lauko, tada 5%, tada 2%, o kai nustojau žaisti, tada grąžinau 5%.