Minesweeper консол тоглоомын хэрэгжилт p. Minesweeper тоглоомын Bot логик алгоритмууд

Windows үйлдлийн системтэй ажилладаг хэн бүхэн Minesweeper тоглоомыг мэддэг. Энэ хэсэгт ижил төстэй хөтөлбөрийг авч үзэх болно.

Тоглоомын төгсгөлд (тоглогч уурхай байрладаг нүдийг нээсний дараа) програмын цонхны жишээг Зураг дээр үзүүлэв. 10.7.

Цагаан будаа. 10.7. Minesweeper програмын цонх

Тоглоомын дүрэм, өгөгдөл танилцуулга

Тоглоомын талбар нь эсүүдээс бүрдэх бөгөөд тус бүр нь мина агуулж болно. Тоглогчийн даалгавар бол бүх уурхайг олж, тугнуудаар тэмдэглэх явдал юм.

Тоглогч хулганы товчлууруудыг ашиглан нүдийг нээж эсвэл дотор нь туг байрлуулж болох бөгөөд ингэснээр нүдэнд мин байгаа гэдгийг илтгэнэ. Хулганы зүүн товчийг дарснаар нүд нээгдэж, баруун товчлуур дээр дарснаар нүдийг шалгана. Хэрэв тоглогч нээсэн үүрэнд уурхай байгаа бол дэлбэрэлт гарч (сапер алдаа гаргасан бөгөөд бидний мэдэж байгаагаар тэр зөвхөн нэг л алдаа гаргадаг) тоглоом дуусна. Хэрэв нүдэнд уурхай байхгүй бол хөрш зэргэлдээх нүднүүдийн уурхайн тоонд тохирох тоо тухайн нүдэнд гарч ирнэ.

Тоглогч аль хэдийн нээгдсэнтэй зэргэлдээх үүрэн дэх уурхайнуудын тооны талаарх мэдээллийг задлан шинжилснээр бүх уурхайг илрүүлж, далбаагаар тэмдэглэх боломжтой. Тугнуудаар тэмдэглэгдсэн нүдний тоонд хязгаарлалт байхгүй. Гэсэн хэдий ч тоглоомыг дуусгахын тулд (ялахын тулд) тугуудыг зөвхөн уурхайтай нүднүүдэд байрлуулах ёстой. Алдаатай сонгогдсон нүдэн дээр хулганы баруун товчийг дарж тэмдэглэгээг арилгаж болно.

Бидний хүн нэг бүр MineSweeper тоглож байсан, эсвэл ядаж тоглохыг оролдсон байх. Тоглоомын логик нь энгийн, гэхдээ нэг удаа тэд алгоритмыг дуусгасны төлөө шагнал амлаж байсан. Миний робот дээр логик нь талбар дээрх нөхцөл байдлаас хамааран ашиглагддаг гурван алгоритмтай байдаг. Гол алгоритм нь уурхайг олох 100 ба 0 хувийн магадлалтай бүх нүдийг олох боломжийг олгодог. Зөвхөн энэ алгоритмыг ашиглан "Мэргэжилтэн" түвшний стандарт мина тээгч хөлөг онгоцонд найдвартай шийдэл байхгүй тохиолдолд дурын нүднүүдийг санамсаргүй байдлаар нээснээр та 33% -ийн хожил авах боломжтой. Гэсэн хэдий ч зарим нэмэлт алгоритмууд энэ утгыг 44% (Windows 7) хүртэл нэмэгдүүлэх боломжтой.

Үндсэн алгоритм

Үндсэн алгоритм нь дараах байдалтай байна. Нэг нээлттэй нүдтэй зэргэлдээ орших үл мэдэгдэх нүднүүд (Cell class) нь бүлэг (Group class) болон үүсгэгддэг бөгөөд энэ нь зэргэлдээ байгаа нүдний утгыг мөн бүртгэдэг.

Зураг дээр дөрвөн бүлгийг харуулсан бөгөөд тэдгээрийн зарим нь давхцаж, зарим нь бүр өөр бүлгүүдийг агуулдаг. (123,1) гэж тэмдэглэе - бүлэг нь 1,2, 3-р нүднүүдээс бүрдэх ба үүнтэй зэрэгцэн тэдгээрийн дотор 1 уурхай байдаг. (5678.2) - дөрвөн үүрэнд 2 уурхай байдаг.

Эхлээд та бүлгүүдийг хөрвүүлэх хэрэгтэй. Үүний тулд:

1. Бид бүлэг бүрийг дараагийн бүлэг бүртэй харьцуулдаг.
2. Хэрэв бүлгүүд ижил байвал хоёр дахь бүлгийг устгана уу.
3. Хэрэв нэг бүлэгт өөр бүлэг багтсан бол томоос жижиг хэсгийг хас. Өөрөөр хэлбэл (5678.2) ба (5.1) хоёр бүлэг байсан бөгөөд одоо (678.1) ба (5.1); (2345.3) ба (5.1) → (234.2) ба (5.1)
4. Бид огтлолцсон бүлгүүдийг, жишээлбэл (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).
5. 1-р алхамаас эхлээд өөрчлөлт хийхгүй болтол давтана

Бүлэг үүсгэх, хөрвүүлэх арга

/** * Нэг нээлттэй талбарын утгатай холбоотой нүднүүдийн бүлгүүдийн жагсаалтыг үүсгэж, жижиг хэсгүүдэд хувааж, давхардлыг арилгана. */ private void setGroups() ( group.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++) { // проходим по списку групп Бүлгийн бүлэг I = group.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; // том бүлэгбүлгийн хүүхэд; // жижиг бүлэг хэрэв (groupI.size()>groupJ.size()) // нүднүүдийн тоогоор том, жижиг бүлгүүдийг тодорхойлох (эцэг эх=groupI;хүүхэд=groupJ;) өөр (хүүхэд=groupI;parent=groupJ) ; ) if (parent.contains(child)) ( // хэрэв том нь жижиг нэгийг агуулж байвал parent.subtraction(child); // дараа нь томоос жижигийг хасна давталт=үнэн; // гэсэн баримтыг тэмдэглэ. бүлгүүд өөрчлөгдсөн ) else if (groupI.overlaps(groupJ ) > 0) ( // эс бөгөөс бүлгүүд огтлолцох бол (groupI.getMines()>groupJ.getMines())// тоогоор нь том, жижиг бүлгүүдийг тодорхойлно. уурхайнуудын (parent=groupI;child=groupJ;) else (хүүхэд =groupI;parent=groupJ;) Group overlap = parent.getOverlap(child) // дараа нь уулзварын үр дүнг авна уу (давхцах != null) (); // хэрэв энэ нь утга учиртай бол (уулзалтын үр дүнд 0% эсвэл 100-тай нүднүүд илэрсэн %) group.add(давхцах) // дараа нь эцэг эхийн жагсаалтад тохирох тохируулга хийх .хасах(давхцах); )

Үүний үр дүнд бид гурван төрлийн бүлэгтэй болно.

• уурхайн тоо 0 байна
• уурхайн тоо нь бүлгийн эсийн тоотой тэнцүү байна
• тэгээс өөр тооны уурхайн тоо нь бүлгийн эсийн тооноос бага байна

Үүний дагуу эхний бүлгийн бүх нүдийг аюулгүйгээр нээж, хоёрдугаар бүлгийн бүх нүдийг тэмдэглэж болно. Энэ бол үндсэн алгоритмын мөн чанар юм.

Хэрэв найдвартай шийдэл байхгүй бол

Гэвч нөхцөл байдалд найдвартай шийдэл байхгүй нөхцөл байдал ихэвчлэн байдаг. Дараа нь дараах алгоритм аврах ажилд ирнэ. Үүний мөн чанар нь магадлалын онолыг ашиглах явдал юм. Алгоритм нь хоёр үе шаттайгаар ажилладаг:

1. Хэд хэдэн нээлттэй эсийн нөлөөг харгалзан бие даасан эсүүдэд магадлалыг тодорхойлох
2. Нийтлэг эсүүдтэй бүлгүүдийн бие биендээ үзүүлэх нөлөөллийг харгалзан магадлалыг тохируулах

Зөвхөн 4 ба 2 гэсэн утгатай зэргэлдээх хоёр нүд нээлттэй байх жишээг ашиглан энэ арга хэрхэн ажилладагийг харцгаая. 0.28 тус тус.

Хэд хэдэн нээлттэй нүдний дэргэдэх нүдэнд уурхай олох магадлалыг тооцоолохын тулд бид дор хаяж нэг үйл явдлын магадлалыг тооцоолох томъёог ашиглана.

А 1, A 2,..., A n үйл явдлуудын дор хаяж нэг нь тохиолдохоос бүрдэх А үйл явдлын магадлал нь нийлбэрээс хамааралгүй бөгөөд нэг ба үржвэрийн хоорондох зөрүүтэй тэнцүү байна. эсрэг үйл явдлын магадлал. A=1- (1-A 1)*(1-A 2)*....*(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())( Газрын зураг эсүүд = шинэ HashMap<>(); // гогцоо нь (Бүлгийн бүлэг: бүлгүүд)( for (Cell cell: group.getList())( Давхар утга; хэрэв бол) өөр өөр бүлгүүдийн нүдн дэх өөр өөр магадлалын утгыг харгалзан нүд бүрт нэг магадлалын утгыг тогтоодог. ((утга=нүд. get(нүд))==null) // хэрэв нүд газрын зургийн эсийн дотор хараахан ороогүй бол.put(cell,(double) group.getMines()/ group.size() //); дараа нь өөр бүлгийн утгаар нэмнэ үү / /хэрэв энэ нь газрын зураг дээр байгаа бол бид түүний утгыг магадлалын онолын эсийн дагуу тохируулна.put(cell,Prob.sum(value,(double) group.getMines()/ group.size()) ) ) // бүлэг дэх магадлалын нийлбэр нь логикийн давталт дахь уурхайнуудын тоотой тэнцүү байх ёстойг харгалзан утгуудыг эргүүлнэ. do( давтах=худал; төлөө (Бүлгийн бүлэг: бүлгүүд)( // бүлэг бүрийн хувьд Жагсаалт prob= group.getProbabilities(); // бүлгийн бүх нүдний магадлалын жагсаалтыг хувиар авна Давхар нийлбэр=0.0; for (Давхар элемент:проб)нийлбэр+=элэм; // түүний нийлбэрийг тооцоолох int mines= group.getMines()*100; // бүлгийн уурхайн тоог нэг зуугаар үржүүлнэ (хувийн хувьд) хэрэв (Math.abs(sum-mines)>1)( // хэрэв тэдгээрийн хоорондын зөрүү их байвал бид тохируулгыг хийнэ repeat=true ; // тохируулгын баримтыг бүртгэх Prob .correct(prob,mines) // (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); хэрэв (cell.getPossibility()<0)cell.setPossibility(0); } }

Сүүлийн хөдөлгөөнүүд

Тоглоомын эцсийн шатанд тэмдэглэгээгүй уурхайн тоо том үүрэг гүйцэтгэдэг. Энэ тоог мэдсэнээр та үл мэдэгдэх нүднүүдэд харгис хүчээр орлуулж, тохирох сонголтыг тэмдэглэж болно. Нүд бүрт тохирох сонголтуудыг хайж олох явцад бид тэмдгийн тоог тоолдог. Үр дүнгийн утгыг нийт тэмдэгтийн тоонд хувааснаар бид нүд тус бүрийн уурхайг олох магадлалыг олж авдаг. Жишээ нь ганцхан найдвартай шийдэлтэй мэт санагдсан энэ нөхцөлд сүүлийн арга (Сүүлчийн эргэлт) уурхай олох 0%-ийн магадлалтай 3 нүдийг олсон.

LastTurns(9,21) боломжит 293930 хослолоос 144 тохирох хослолыг шалгаад хамгийн багадаа 0% магадлалтай 3 нүдийг олжээ.

Санааг ойлгоход төвөгтэй байдлын үүднээс энэ арга нь хамгийн хялбар тул би үүнийг нарийвчлан шинжлэхгүй.

Түүний хэрэгжилт

/** * Харгис хэрцгий хүчийг ашиглан бие даасан тооцооллын алгоритм. Үл мэдэгдэх нүднүүдийн тоо 30-аас ихгүй тохиолдолд л ашиглах боломжтой * @return */ public ArrayList GetLastTurns() ( int minesLeft = countMinesLeft(); // тэмдэглэгээгүй үлдсэн уурхайнуудын тоо ArrayList unknownCells = getUnknownCells(); // үл мэдэгдэх нүднүүдийн жагсаалт int notOpened = unknownCells.size(); // үл мэдэгдэх нүдний тоо Бүхэл тооны хослолууд = new Sequence6().getSequensed(minesLeft, notOpened); // өгөгдсөн тооны ArrayList нүдн дэх өгөгдсөн тооны уурхайн өөр өөр хослолуудын массив жагсаалт = шинэ ArrayList (); // боломжит хослолуудын жагсаалт (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 = шинэ ArrayList<>(); // (int i = 0; i) боломжуудын2 дахь хамгийн бага утга бүхий индексүүдийн жагсаалт< 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 + " %"); ArrayListҮр дүн = шинэ ArrayList (minIndices.size());// хамгийн бага магадлалтай нүдний координатын жагсаалт (int index: minIndices) ( result.add(unknownCells.get(index).getPoint()); ) үр дүнг буцаана; )

Дүгнэлт

Практикт хангалттай тооны дээжтэй бол үүрэнд уурхай олох магадлалын тооцоолсон болон бодит утгууд бараг давхцдаг. Дараах хүснэгтэд Minesweeper дээр Windows XP дээр нэг шөнийн турш ажиллаж байгаа роботын үр дүнг харуулав

1. Тооцоолсон %
2. Тооцоолсон %-тай эсийн нээлтийн нийт тоо
3. Уурхайн цохилтын тоо
4. Бодит %

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% талбайн том зөрүү нь ихэвчлэн энэ хувь нь ойролцоо нээгдээгүй (жишээлбэл, тоглоомын эхэнд) эсүүдтэй байсантай холбоотой байж болох юм, мөн "Минег хамгаалагч" нь тоглогчид тохирсон байдаг. нээгдсэн үүрний доороос уурхайг зайлуулах. Ажлын алгоритмыг java хэл дээр хэрэгжүүлсэн бөгөөд стандарт Windows мина тээгч хөлөг онгоц (7 ба XP), VK болон тоглоом дээрх програм дээр туршиж үзсэн. Дашрамд хэлэхэд, миний IP-ээс данс руугаа нэвтрэх үед хэдэн өдрийн турш "техникийн асуудал" гарсны дараа тоглоом талбайн хэсгийг нээх урамшууллын дүрмийг өөрчилсөн: эхлээд нээлттэй талбайн 10% -ийн бооцооны 10% -ийг буцааж өгсөн. 5%, дараа нь 2%, би тоглохоо больсон үед 5% буцааж өгсөн.