Produksyon 

Pagpapatupad ng console game na Minesweeper sa p. Bot logic algorithm para sa larong Minesweeper. Ang pamamaraang ito sa code

Marahil bawat isa sa atin ay naglaro na, o kahit man lang ay sinubukang maglaro, ng MineSweeper. Ang lohika ng laro ay simple, ngunit sa isang pagkakataon ay nangako pa sila ng gantimpala para sa algorithm para sa pagkumpleto nito. Sa aking bot, ang logic ay may tatlong algorithm na ginagamit depende sa sitwasyon sa field. Ang pangunahing algorithm ay nagbibigay-daan sa iyo upang mahanap ang lahat ng mga cell na may 100 at 0 porsyento na posibilidad na makahanap ng isang minahan. Gamit lamang ang algorithm na ito at pagbubukas ng mga arbitrary na cell nang random sa kawalan ng isang maaasahang solusyon sa isang karaniwang minesweeper sa antas ng "Expert", makakamit mo ang 33% na panalo. Gayunpaman, maaaring itaas ng ilang karagdagang algorithm ang halagang ito sa 44% (Windows 7).

Pangunahing algorithm


Ang pangunahing algorithm ay ang mga sumusunod. Ang hindi kilalang mga cell (Cell class) na katabi ng isang bukas na cell ay nabuo sa isang grupo (Group class), na nagtatala din ng halaga ng cell kung saan ito katabi.

Ang figure ay nagpapakita ng apat na grupo, ang ilan ay nagsasapawan, at ang ilan ay naglalaman pa ng iba pang mga grupo. Tukuyin natin ang (123,1) - ang grupo ay binubuo ng mga cell 1,2 at 3, at sa parehong oras mayroong 1 minahan sa kanila. (5678.2) - mayroong 2 mina sa apat na cell.

Una kailangan mong i-convert ang mga pangkat. Para dito:

  1. Inihahambing namin ang bawat pangkat sa bawat susunod na pangkat.
  2. Kung ang mga grupo ay pareho, pagkatapos ay tanggalin ang pangalawa.
  3. Kung ang isang pangkat ay naglalaman ng isa pa, pagkatapos ay ibawas ang mas maliit sa mas malaki. Ibig sabihin, mayroong dalawang grupo (5678.2) at (5.1), ngayon (678.1) at (5.1); (2345.3) at (5.1) → (234.2) at (5.1)
  4. Binabago namin ang mga intersecting na grupo, halimbawa (123,1) at (234,2), ayon sa sumusunod na prinsipyo:
    1. Lumikha ng isang bagong pangkat ng mga intersecting na mga cell (23,?)
    2. Kinakalkula namin ang bilang ng mga minahan bagong grupo, katumbas ng bilang ng mga mina sa pangkat na may malaking bilang ng mga mina (234.2) na binawasan ang natitirang bilang ng mga cell sa kabilang grupo pagkatapos paghiwalayin ang mga intersecting na mga cell (1,?). Ibig sabihin, 2-1 = 1. Nakukuha natin ang (23.1)
    3. Kung ang kalkuladong bilang ng mga mina sa bagong pangkat (23.1) ay hindi katumbas ng bilang ng mga mina sa pangkat na may mas kaunting mga mina (123.1), pagkatapos ay ihihinto namin ang pagbabago.
    4. Ibinabawas namin ang bagong nabuong grupo mula sa magkabilang intersecting na grupo. (123.1)-(23.1) = (1.0), (234.2)-(23.1) = (4.1).
    5. Idagdag ang bagong nabuong grupo sa listahan ng mga grupo
    Kaya (234.2) at (123.1) → (1.0) at (23.1) at (4.1).
  5. Ulitin mula sa hakbang 1 hanggang sa walang pagbabagong ginawa

Paraan para sa paglikha at pag-convert ng mga grupo

/** * Lumilikha ng isang listahan ng mga pangkat ng mga cell na nauugnay sa isang solong halaga bukas na larangan, at hinahati-hati din ang mga ito sa mas maliliit at inaalis ang mga duplicate. */ private void setGroups() ( groups.clear(); para sa (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++) { // проходим по списку групп Grupo ng grupo I = groups.get(i); para sa (int j = i + 1; j< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем одинаковые группы {groups.remove(j--);break;} Group parent; // malaking grupo Grupong bata; // smaller group if (groupI.size()>groupJ.size()) // matukoy ang mas malaki at mas maliliit na grupo sa bilang ng mga cell (parent=groupI;child=groupJ;) else (child=groupI;parent=groupJ ; ) if (parent.contains(child)) ( // kung ang mas malaki ay naglalaman ng mas maliit na parent.subtraction(child); // pagkatapos ay ibawas ang mas maliit sa mas malaki repeat=true; // itala ang katotohanan na nagbago ang mga grupo ) else if (groupI.overlaps(groupJ ) > 0) ( // otherwise if the groups intersect if (groupI.getMines()>groupJ.getMines())// matukoy ang mas malaki at maliliit na grupo ayon sa numero of mine (parent=groupI;child=groupJ;) else (child =groupI;parent=groupJ;) Group overlap = parent.getOverlap(child); // pagkatapos ay kunin ang resulta ng intersection kung (overlap != null) ( // at kung ito ay may katuturan (bilang resulta ng intersection, ang mga cell na may 0% o 100 ay ipinahayag %) groups.add(overlap); .subtraction(overlap); )


Bilang resulta, magkakaroon tayo ng tatlong uri ng mga grupo.
  • ang bilang ng mga minahan ay zero
  • ang bilang ng mga mina ay katumbas ng bilang ng mga cell sa grupo
  • ang hindi zero na bilang ng mga mina ay mas mababa kaysa sa bilang ng mga cell sa grupo
Alinsunod dito, ang lahat ng mga cell mula sa unang pangkat ay maaaring ligtas na mabuksan, at lahat ng mga cell mula sa pangalawang pangkat ay maaaring mamarkahan. Ito ang kakanyahan ng pangunahing algorithm.
Kung walang maaasahang solusyon
Ngunit madalas may mga sitwasyon na walang maaasahang solusyon sa sitwasyon. Pagkatapos ang sumusunod na algorithm ay dumating sa pagsagip. Ang esensya nito ay ang paggamit ng probability theory. Ang algorithm ay gumagana sa dalawang yugto:
  1. Ang pagtukoy ng posibilidad sa mga indibidwal na mga cell, isinasaalang-alang ang impluwensya ng ilang mga bukas na mga cell
  2. Pagsasaayos ng mga probabilidad, isinasaalang-alang ang magkaparehong impluwensya ng mga pangkat na may mga karaniwang cell sa bawat isa
Tingnan natin kung paano gumagana ang pamamaraang ito gamit ang halimbawa ng isang sitwasyon kung saan dalawang magkatabi na mga cell na may mga halaga 4 at 2 ang bukas Ang mga posibilidad na makahanap ng mga mina mula sa mga cell 4 at 2 nang magkahiwalay ay 4/7=0.57 at 2/7=. 0.28, ayon sa pagkakabanggit.


Upang kalkulahin ang posibilidad na makahanap ng minahan sa isang cell sa tabi ng ilang bukas na mga cell, ginagamit namin ang formula para sa pagkalkula ng posibilidad ng hindi bababa sa isang kaganapan:
Ang posibilidad ng paglitaw ng isang kaganapan A, na binubuo sa paglitaw ng hindi bababa sa isa sa mga kaganapan A 1, A 2,..., A n, independiyente sa pinagsama-samang, ay katumbas ng pagkakaiba sa pagitan ng isa at ng produkto ng ang mga posibilidad ng magkasalungat na pangyayari. A=1- (1-A 1)*(1-A 2)*....*(1-A n)
Sa mga katabing cell, pagkatapos ilapat ang formula na ito, ang resulta ay 1-(1-0.57)*(1-0.28)=0.69.


Gayunpaman, dapat tandaan na ang kabuuan ng mga probabilidad sa bawat pangkat ng mga cell ay dapat na katumbas ng bilang ng mga mina sa grupo. Samakatuwid, ang lahat ng mga halaga sa bawat pangkat ay dapat na i-multiply upang sa huli ang kanilang kabuuan ay katumbas ng bilang ng mga minuto. Ang numerong ito ay katumbas ng bilang ng mga mina sa pangkat, na hinati sa kasalukuyang kabuuan ng mga probabilidad ng mga cell ng grupo:
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

Ngayon ang mga cell na may posibilidad na 0.57 ay mayroong 0.485, at ang mga may posibilidad na 0.69 → 0.618
Nagsasagawa kami ng isang katulad na pagkalkula para sa pangalawang pangkat, na isinasaalang-alang ang mga pagsasaayos mula sa nauna.
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

Nakikita namin na ang posibilidad sa pangkalahatang mga cell ay nagbago muli, kaya ang naturang pagsasaayos para sa bawat pangkat ay kailangang ulitin nang maraming beses hanggang sa maabot ng system ang ilang mga matatag na halaga, na siyang magiging tunay na posibilidad ng paghahanap ng mga mina sa mga cell.
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

… atbp.


Ang natitira na lang ay pumili ng isa sa mga cell na may kaunting posibilidad at gumawa ng isang hakbang.

Ang pamamaraang ito sa code

/** * Ang pamamaraan ay gumagawa ng mga pagsasaayos sa mga probabilidad ng paghahanap ng mga mina sa mga cell, na isinasaalang-alang ang mutual na impluwensya ng mga probabilities ng magkalapit na mga cell sa isa't isa */ private void correctPosibilities())( Map cells= bagong HashMap<>(); // Ang loop ay nagtatakda ng iisang probability value sa bawat cell, na isinasaalang-alang ang iba't ibang probability value sa isang cell mula sa iba't ibang grupo para sa (Group group: groups)( for (Cell cell: group.getList())( Double value; if ((value=cells. get(cell))==null) // kung wala pa ang cell sa map cells.put(cell,(double) group.getMines()/ group.size() // pagkatapos ay idagdag ito ng halaga mula sa iba pang pangkat / /kung ito ay nasa mapa na, pagkatapos ay inaayos namin ang halaga nito ayon sa probability theory cells.put(cell,Prob.sum(value,(double) group.getMines()/ group.size()) ) ) // itinatama ng cycle ang mga value na isinasaalang-alang na ang kabuuan ng mga probabilities sa grupo ay dapat na katumbas ng bilang ng mga mina sa group boolean repeat; do( repeat=false; for (Group group: groups)( // for each group List prob= group.getProbability(); // kunin ang listahan ng mga probabilities ng lahat ng mga cell sa grupo sa porsyento na Double sum=0.0; para sa (Double elem:prob)sum+=elem; // kalkulahin ang kabuuan nito int mines= group.getMines()*100; // i-multiply ang bilang ng mga mina sa pangkat ng isang daan (dahil sa mga porsyento) kung (Math.abs(sum-mines)>1)( // kung malaki ang pagkakaiba sa pagitan ng mga ito, pagkatapos ay gagawa tayo ng pagsasaayos na repeat=true ; // itala ang katotohanan ng pagsasaayos Prob .correct(prob,mines);< 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); kung (cell.getPossibility()<0)cell.setPossibility(0); } }

Mga huling galaw
Sa huling yugto ng laro, ang bilang ng mga hindi namarkahang mina ay may malaking papel. Alam ang numerong ito, maaari mong palitan ang mga ito ng brute force sa hindi kilalang mga cell at markahan ang naaangkop na mga opsyon. Sa proseso ng paghahanap sa mga angkop na opsyon para sa bawat cell, binibilang namin ang bilang ng mga marka. Hinahati ang mga nagresultang halaga sa kabuuang bilang ng mga marka, nakukuha namin ang posibilidad na makahanap ng mga mina para sa bawat cell. Halimbawa, sa sitwasyong ito, na tila mayroon lamang isang maaasahang solusyon, ang huling paraan (LastTurns) ay nakakita ng 3 mga cell na may 0% na posibilidad na makahanap ng minahan.


Sinuri ng LastTurns(9,21) ang 144 na angkop na kumbinasyon sa 293930 posible at nakakita ng 3 cell na may minimum na posibilidad na 0%

Mula sa punto ng view ng pagiging kumplikado ng pag-unawa sa ideya, ang pamamaraang ito ay ang pinakamadali, kaya hindi ko pa ito susuriin nang detalyado.

Ang pagpapatupad nito

/** * Independiyenteng algorithm ng pagkalkula gamit ang banal na brute force. Magagamit lang kung ang bilang ng mga hindi kilalang cell ay hindi hihigit sa 30 * @return */ public ArrayList GetLastTurns() ( int minesLeft = countMinesLeft(); // bilang ng mga mina na natitira walang markang ArrayList unknownCells = getUnknownCells(); // list of unknown cells int notOpened = unknownCells.size(); // number of unknown cells Integer combinations = new Sequence6().getSequensed(minesLeft, notOpened); // isang hanay ng iba't ibang kumbinasyon ng isang naibigay na bilang ng mga mina sa isang naibigay na bilang ng mga cell ng ArrayList list = bagong ArrayList (); // listahan ng mga posibleng kumbinasyon para sa (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 = bagong ArrayList<>(); // listahan ng mga indeks na may pinakamababang halaga sa mga posibilidad2 para sa (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 + " %"); ArrayListResulta = bagong ArrayList (minIndices.size());// listahan ng mga cell coordinates na may pinakamababang posibilidad para sa (int index: minIndices) ( result.add(unknownCells.get(index).getPoint()); ) return result; )

Konklusyon
Sa pagsasagawa, na may sapat na bilang ng mga sample, ang kinakalkula at aktwal na mga halaga ng mga posibilidad na makahanap ng minahan sa isang cell ay halos nag-tutugma. Ipinapakita ng sumusunod na talahanayan ang mga resulta ng bot na tumatakbo sa Minesweeper sa ilalim ng Windows XP para sa isang gabi, kung saan
  1. Tinantyang %
  2. Kabuuang bilang ng mga cell opening na may kalkuladong %
  3. Bilang ng mga hit bawat minahan
  4. Aktwal na %
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

Ang malaking pagkakaiba sa 20-22% na lugar ay marahil dahil sa ang katunayan na ang porsyento na ito ay may mga cell na hindi pa nakabukas sa malapit (halimbawa, sa simula ng laro), at ang "Mineweeper" ay inangkop sa player, kung minsan. pag-alis ng isang minahan sa ilalim ng nakabukas na selda. Ang algorithm ng trabaho ay ipinatupad sa java at nasubok sa isang karaniwang Windows minesweeper (7 at XP), isang application sa VK at sa laro. Sa pamamagitan ng paraan, pagkatapos ng ilang araw ng "mga teknikal na problema" kapag na-access ang aking account mula sa aking IP, binago ng laro ang mga panuntunan ng gantimpala para sa pagbubukas ng bahagi ng field: sa una ay ibinalik nito ang 10% ng taya para sa 10% ng open field, pagkatapos 5%, pagkatapos ay 2%, at nang tumigil ako sa paglalaro, pagkatapos ay ibinalik ang 5%.

Ang sinumang nagtatrabaho sa Windows operating system ay pamilyar sa larong Minesweeper. Tinatalakay ng seksyong ito ang isang katulad na programa.

Ang isang halimbawa ng window ng programa sa dulo ng laro (pagkatapos buksan ng player ang cell kung saan matatagpuan ang minahan) ay ipinapakita sa Fig. 10.7.

kanin. 10.7. Window ng programa ng Minesweeper

Mga panuntunan sa laro at presentasyon ng data

Ang larangan ng paglalaro ay binubuo ng mga cell, na ang bawat isa ay maaaring maglaman ng minahan. Ang gawain ng manlalaro ay hanapin ang lahat ng mga mina at markahan ang mga ito ng mga flag.

Gamit ang mga pindutan ng mouse, ang player ay maaaring magbukas ng isang cell o maglagay ng isang bandila sa loob nito, sa gayon ay nagpapahiwatig na ang cell ay naglalaman ng isang minahan. Ang cell ay binuksan sa pamamagitan ng pag-click sa kaliwang pindutan ng mouse, ang checkbox ay nasuri sa pamamagitan ng pag-click sa kanan. Kung mayroong isang minahan sa cell na binuksan ng manlalaro, pagkatapos ay isang pagsabog ang nangyayari (nagkamali ang sapper, at siya, tulad ng alam natin, ay nagkakamali lamang) at natapos ang laro. Kung walang minahan sa isang cell, may lalabas na numero sa cell na iyon na tumutugma sa bilang ng mga mina sa mga kalapit na cell.

Sa pamamagitan ng pagsusuri ng impormasyon tungkol sa bilang ng mga mina sa mga cell na katabi ng mga bukas na, ang player ay maaaring makakita at markahan ang lahat ng mga mina na may mga flag. Walang mga paghihigpit sa bilang ng mga cell na minarkahan ng mga flag. Gayunpaman, upang makumpleto ang laro (upang manalo), ang mga flag ay dapat lamang ilagay sa mga cell na may mga mina. Maaaring alisin ang isang maling napiling checkbox sa pamamagitan ng pag-right click sa cell kung saan ito matatagpuan.