Codul jocului Minesweeper pe c. Algoritmi logici bot pentru jocul Minesweeper. Metodă de creare și conversie a grupurilor

Toți cei care lucrează cu sistem de operare Windows, jocul Minesweeper este bine cunoscut. Această secțiune discută un program similar.

În Fig. 10.7.

Orez. 10.7. Fereastra pentru minere

Reguli de joc și prezentarea datelor

Terenul de joc este format din celule, fiecare dintre acestea putând conține o mină. Sarcina jucătorului este să găsească toate minele și să le marcheze cu steaguri.

Folosind butoanele mouse-ului, jucătorul poate deschide celula sau poate pune un steag în ea, indicând astfel că există o mină în celulă. Celula este deschisă făcând clic pe butonul stâng al mouse-ului, caseta de selectare este setată făcând clic pe butonul din dreapta al mouse-ului. Dacă există o mină în celula pe care a deschis-o jucătorul, atunci are loc o explozie (sapatorul a făcut o greșeală, iar el, după cum știți, face o singură greșeală) și jocul se termină. Dacă nu există mină în celulă, atunci în această celulă apare un număr corespunzător numărului de mine situate în celulele învecinate.

Analizând informațiile despre numărul de mine din celulele adiacente celor deja deschise, jucătorul poate găsi și semnaliza toate minele. Nu există restricții cu privire la numărul de celule marcate cu steaguri. Totuși, pentru a finaliza jocul (pentru a câștiga), steagurile trebuie puse numai în acele celule care au mine. Un steag selectat eronat poate fi eliminat făcând clic dreapta pe celula în care se află.

Probabil fiecare dintre noi a jucat vreodată, sau cel puțin a încercat să joace Minesweeper (MineSweeper). Logica jocului este simplă, dar la un moment dat chiar au promis o recompensă pentru algoritmul trecerii acestuia. În botul meu, logica are trei algoritmi care sunt utilizați în funcție de situația de pe teren. Algoritmul principal vă permite să găsiți toate celulele cu o probabilitate de 100 și 0% de a găsi o mină. Folosind doar acest algoritm și deschizând la întâmplare celule arbitrare în absența unei soluții fiabile într-un sapper standard la nivel „Expert”, puteți obține 33% din câștiguri. Cu toate acestea, unii algoritmi suplimentari vă permit să creșteți această valoare la 44% (Windows 7).

Algoritm de bază

Algoritmul principal este următorul. Celulele necunoscute (clasa de celule) adiacente unei celule deschise sunt formate într-un grup (clasa de grup), care conține și valoarea celulei căreia este adiacentă.

Figura prezintă patru grupuri, dintre care unele se intersectează, iar unele chiar conțin alte grupuri. Notați (123,1) - grupul este format din celulele 1,2 și 3 și, în același timp, conțin 1 mină. (5678.2) - sunt 2 mine în patru celule.

Mai întâi trebuie să convertiți grupurile. Pentru asta:

1. Comparăm fiecare grup cu fiecare grup ulterior.
2. Dacă grupurile sunt aceleași, atunci ștergeți-l pe al doilea.
3. Dacă un grup conține altul, atunci scădeți cel mai mic din cel mai mare. Adică au fost două grupuri (5678,2) și (5,1), a devenit (678,1) și (5,1); (2345.3) și (5.1) → (234.2) și (5.1)
4. Grupurile care se intersectează, de exemplu (123.1) și (234.2), sunt transformate conform următorului principiu:
   1. Creați un nou grup de celule care se intersectează (23,?)
   2. Calculați numărul de minute în grup nou, egal cu numărul de mine din grupul cu un număr mare de mine (234,2) minus numărul de celule rămase din celălalt grup după separarea celulelor suprapuse (1,?). Adică 2-1 = 1. Se obține (23.1)
   3. Dacă numărul calculat de mine din noul grup (23.1) nu este egal cu numărul de mine din grupul cu mai puține mine (123.1), atunci opriți conversia
   4. Scădem grupul nou format din ambele grupuri care se intersectează. (123,1)-(23,1) = (1,0), (234,2)-(23,1) = (4,1).
   5. Adăugarea grupului nou format la lista de grupuri
   Astfel (234.2) și (123.1) → (1.0) și (23.1) și (4.1).
5. Repetați de la pasul 1 până când nu se fac modificări

Metodă de creare și conversie a grupurilor

/** * Creează o listă de grupuri de celule legate printr-o valoare de câmp deschis și, de asemenea, le împarte în altele mai mici, elimină duplicatele. */ 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 grup I = grupuri.get(i); pentru (int j = i + 1; j< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем aceleași grupuri(groups.remove(j--);break;) Grup părinte; // grup mare Grup copil; // grup mai mic if (groupI.size()>groupJ.size()) // determinăm grupurile mai mari și mai mici după numărul de celule (părinte=grupI;copil=grupJ;) else (copil=grupI;părinte=grupJ ; ) dacă (părinte.conține(copil)) ( // dacă cel mai mare îl conține pe cel mai mic părinte.scădere(copil); // apoi scădeți pe cel mai mic din cel mai mare repetare=adevărat; // remediați faptul că grupurile s-au schimbat ) else if (groupI.overlaps(groupJ ) > 0) ( // în caz contrar, dacă grupurile se suprapun if (groupI.getMines()>groupJ.getMines())// determină grupurile mai mari și mai mici prin numărul de mine (părinte=grupI;copil=grupJ;) else (copil =grupI;părinte=grupJ;) Suprapunere grup = părinte.getOverlap(copil);// atunci luăm rezultatul intersecției dacă (suprapunere != null ) ( // și dacă are sens (ca urmare a intersecției, celulele cu 0% sau 100 au fost dezvăluite %) groups.add(overlap); // atunci facem ajustările corespunzătoare listei parent.subtraction(overlap) );copil.scădere (suprapunere); repetare=adevărat; ) ) ) ) ) în timp ce (repetare); )

Ca rezultat, vom avea trei tipuri de grupuri.

• numărul de mine este zero
• numărul de mine este egal cu numărul de celule din grup
• numărul de minute diferit de zero este mai mic decât numărul de celule din grup

În consecință, toate celulele din primul grup pot fi deschise în siguranță și marcate din al doilea grup. Aceasta este esența algoritmului principal.

Dacă nu există o soluție de încredere

Dar adesea există situații în care nu există o soluție fiabilă pentru situație. Apoi vine ajutorul următorul algoritm. Esența sa este de a folosi teoria probabilității. Algoritmul funcționează în două etape:

1. Determinarea probabilității în celule individuale, având în vedere influența mai multor celule deschise
2. Corectarea probabilităților, ținând cont de influența reciprocă a grupurilor cu celule comune unul asupra celuilalt

Să luăm în considerare cum funcționează această metodă pe exemplul unei situații în care sunt deschise doar două celule adiacente cu valorile 4 și 2. Probabilitățile de a găsi mine din celulele 4 și 2 separat sunt 4/7=0,57 și 2/7=0,28 , respectiv.

Pentru a calcula probabilitatea de a găsi o mină într-o celulă lângă mai multe celule deschise, folosim formula pentru calcularea probabilității a cel puțin unui eveniment:

Probabilitatea ca un eveniment A să se producă, constând în apariția a cel puțin unuia dintre evenimentele A 1 , A 2 ,..., A n , independent în agregat, este egală cu diferența dintre unitate și produsul probabilităților. a evenimentelor opuse. A=1- (1-A 1)*(1-A 2)*....*(1-A n)

În celulele adiacente, după aplicarea acestei formule, rezultatul este 1-(1-0,57)*(1-0,28)=0,69.

Cu toate acestea, trebuie amintit că suma probabilităților din fiecare grup de celule trebuie să fie egală cu numărul de mine din grup. Prin urmare, toate valorile din fiecare grup trebuie înmulțite astfel încât, în final, suma lor să fie egală cu numărul de minute. Acest număr este egal cu numărul de mine din grup, împărțit la suma actuală a probabilităților celulelor grupului:

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

Acum acele celule care au avut o probabilitate de 0,57 au 0,485, iar cele care au 0,69 → 0,618
Efectuăm un calcul similar pentru al doilea grup, ținând cont de ajustarea față de cea precedentă.

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

Vedem că probabilitatea în celulele comune s-a schimbat din nou, așa că această ajustare pentru fiecare grup trebuie repetată de mai multe ori până când sistemul ajunge la niște valori stabile, care vor fi adevăratele probabilități de a găsi mine în celule.

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

… etc.

Rămâne doar să alegeți una dintre celulele cu probabilitatea minimă și să faceți o mișcare.

Această metodă în cod

/** * Metoda corectează valorile probabilităților de găsire a minelor în celule, ținând cont de influența reciprocă a probabilităților celulelor învecinate unele asupra altora */ private void correctPosibilities()( Harta celule = nou HashMap<>(); // bucla setează o singură valoare a probabilității în fiecare celulă, ținând cont de diferitele probabilități din celulă din diferite grupuri pentru (Group group: groups)( for (Cell cell: group.getList())( Valoare dublă; if ( (valoare=celule. get(cell))==null) // dacă celula nu este încă în hartă cells.put(cell,(double) group.getMines()/ group.size()); // apoi adăugăm-o cu valoarea din grup else / /dacă este deja în hartă, atunci îi corectăm valoarea conform teoriei probabilităților cells.put(cell,Prob.sum(value,(double) group.getMines()/ group.size())); ) ) // bucla corectează valorile ținând cont de faptul că suma probabilităților din grup trebuie să fie egală cu numărul de mine din grupul repetitiv boolean; do( repetare=fals; pentru (Grup de grup: grupuri)( // pentru fiecare grup Listă prob=group.getProbabilities(); // ia o listă de probabilități pentru toate celulele din grup în procente Sumă dublă=0,0; pentru (duble elem:prob)sum+=elem; // calculează suma int mines= group.getMines()*100; // înmulțim numărul de mine din grup cu o sută (datorită procentelor) if (Math. abs(sum-mines)>1)( // dacă diferența dintre ele este mare, atunci facem o ajustare repeat=true ; // corectează faptul ajustării Prob .correct(prob,mine);//corectează lista pentru (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); dacă (cell.getPossibility()<0)cell.setPossibility(0); } }

Ultimele mișcări

În etapa finală a jocului, numărul de mine nemarcate joacă un rol important. Cunoscând acest număr, le puteți înlocui în celule necunoscute prin forță brută și puteți marca opțiunile potrivite. În procesul de enumerare a opțiunilor potrivite pentru fiecare celulă, numărăm numărul de note. Împărțind valorile rezultate la numărul total de mărci, obținem probabilitatea de a găsi mine pentru fiecare celulă. De exemplu, în această situație, care pare să aibă o singură soluție de încredere, ultima metodă (LastTurns) a găsit 3 celule cu o probabilitate de 0% de a găsi o mină.

LastTurns(9,21) a testat 144 de combinații potrivite din 293930 posibile și a găsit 3 celule cu o probabilitate minimă de 0%

Din punct de vedere al complexității înțelegerii ideii, această metodă este cea mai ușoară, așa că nu o voi analiza încă în detaliu.

Implementarea sa

/** * Un algoritm de calcul independent prin enumerare banală. Poate fi folosit numai dacă numărul de celule necunoscute este mai mic de 30 * @return */ public ArrayList GetLastTurns() ( int mineLeft = countMinesLeft(); // numărul de mine rămase nemarcate ArrayList unknownCells = getUnknownCells(); // lista de celule necunoscute int notOpened = unknownCells.size(); // numărul de celule necunoscute Combinații întregi = new Sequence6().getSequensed(minesLeft, notOpened); // o matrice de diferite combinații ale unui număr dat de mine într-un anumit număr de celule ArrayList list = nou ArrayList (); // listă de combinații posibile pentru (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; ArrayListminIndices = noua ArrayList<>(); // listă de indici cu valoare minimă în posibilități2 pentru (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 + " %"); ArrayListRezultat = noua ArrayList (minIndices.size());// listă de coordonate ale celulei cu probabilitate minimă pentru (index int: minIndices) ( result.add(unknownCells.get(index).getPoint()); ) returnează rezultat; )

Concluzie

În practică, cu un număr suficient de probe, valorile calculate și reale ale probabilităților de a găsi o mină într-o celulă aproape coincid. Următorul tabel arată rezultatele botului care rulează pe Minesweeper sub Windows XP pentru o noapte, unde

1. % estimat
2. Numărul total de deschideri de celule cu % calculat
3. Numărul de lovituri pe mină
4. % real

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

Discrepanța mare în zona de 20-22% se datorează probabil faptului că de multe ori acest procent avea celule care nu aveau deja cele deschise în apropiere (de exemplu, la începutul jocului), iar Minesweeper ajustat la jucător, scoțând uneori o mină de sub celula deschisă. Algoritmul de lucru a fost implementat în java și testat pe un Windows Sapper standard (7 și XP), o aplicație în VK și pe joc. Apropo, după câteva zile de „probleme tehnice” la accesarea contului meu de pe IP-ul meu, jocul a schimbat regulile de remunerare pentru deschiderea unei părți a terenului: inițial a returnat 10% din pariul pentru 10% din câmpul deschis, apoi 5%, apoi 2%, iar când m-am oprit din joc, apoi am revenit 5%.