Minesweeper консол тоглоомын хэрэгжилт p. Minesweeper тоглоомын Bot логик алгоритмууд. Энэ аргыг кодонд оруулсан болно
Бидний хүн нэг бүр MineSweeper тоглож байсан, эсвэл ядаж тоглохыг оролдсон байх. Тоглоомын логик нь энгийн, гэхдээ нэг удаа тэд алгоритмыг дуусгасны төлөө шагнал амлаж байсан. Миний робот дээр логик нь талбар дээрх нөхцөл байдлаас шалтгаалан ашиглагддаг гурван алгоритмтай байдаг. Гол алгоритм нь уурхайг олох 100 ба 0 хувийн магадлалтай бүх нүдийг олох боломжийг олгодог. Зөвхөн энэ алгоритмыг ашиглан "Мэргэжилтэн" түвшний стандарт мина тээгч хөлөг онгоцонд найдвартай шийдэл байхгүй тохиолдолд дурын нүднүүдийг санамсаргүй байдлаар нээснээр та 33% -ийн хожил авах боломжтой. Гэсэн хэдий ч зарим нэмэлт алгоритмууд энэ утгыг 44% хүртэл өсгөж чадна (Windows 7). Үндсэн алгоритм
Үндсэн алгоритм нь дараах байдалтай байна. Нэг нээлттэй нүдтэй зэргэлдээх үл мэдэгдэх нүднүүд (Cell class) нь бүлэг (Group class) болон үүсгэгддэг бөгөөд энэ нь зэргэлдээ байгаа нүдний утгыг мөн бүртгэдэг.
Зураг дээр дөрвөн бүлгийг харуулсан бөгөөд тэдгээрийн зарим нь давхцаж, зарим нь бүр өөр бүлгүүдийг агуулдаг. (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) дараах зарчмын дагуу хувиргадаг.
- огтлолцсон нүднүүдийн шинэ бүлэг үүсгэх (23,?)
- Бид уурхайнуудын тоог тооцоолдог шинэ бүлэг, олон тооны уурхайтай бүлгийн уурхайн тооноос (234.2) огтлолцсон нүднүүдийг (1,?) салгасны дараа нөгөө бүлэгт үлдсэн эсийн тоог хассантай тэнцүү байна. Энэ нь 2-1 = 1. Бид (23.1) авна.
- Хэрэв шинэ бүлгийн уурхайнуудын тооцоолсон тоо (23.1) нь цөөн уурхайтай бүлгийн уурхайнуудын тоотой (123.1) тэнцүү биш байвал бид өөрчлөлтийг зогсооно.
- Бид огтлолцсон хоёр бүлгээс шинээр үүссэн бүлгийг хасна. (123.1)-(23.1) = (1.0), (234.2)-(23.1) = (4.1).
- Шинээр байгуулагдсан бүлгийг бүлгүүдийн жагсаалтад нэмнэ үү
- 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(давхцах); // дараа нь бид эцэг эхийн жагсаалтад зохих тохируулга хийнэ.subtraction(давхцах); хүүхэд .хасах(давхцах); давтах=үнэн; ) ) ) ) while(давхах); )
Үүний үр дүнд бид гурван төрлийн бүлэгтэй болно.
- уурхайн тоо 0 байна
- уурхайн тоо нь бүлгийн эсийн тоотой тэнцүү байна
- тэгээс өөр тооны уурхайн тоо нь бүлгийн эсийн тооноос бага байна
Хэрэв найдвартай шийдэл байхгүй бол
Гэвч нөхцөл байдалд найдвартай шийдэл байхгүй нөхцөл байдал ихэвчлэн байдаг. Дараа нь дараах алгоритм аврах ажилд ирнэ. Үүний мөн чанар нь магадлалын онолыг ашиглах явдал юм. Алгоритм нь хоёр үе шаттайгаар ажилладаг:- Хэд хэдэн нээлттэй эсийн нөлөөг харгалзан бие даасан эсүүдэд магадлалыг тодорхойлох
- Нийтлэг эсүүдтэй бүлгүүдийн бие биендээ үзүүлэх нөлөөллийг харгалзан магадлалыг тохируулах
Хэд хэдэн нээлттэй нүдний дэргэдэх нүдэнд уурхай олох магадлалыг тооцоолохын тулд бид дор хаяж нэг үйл явдлын магадлалыг тооцоолох томъёог ашиглана.
А 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())( Газрын зураг
Сүүлийн хөдөлгөөнүүд
Тоглоомын эцсийн шатанд тэмдэглэгээгүй уурхайн тоо том үүрэг гүйцэтгэдэг. Энэ тоог мэдсэнээр та үл мэдэгдэх нүднүүдэд харгис хүчээр орлуулж, тохирох сонголтыг тэмдэглэж болно. Нүд бүрт тохирох сонголтуудыг хайж олох явцад бид тэмдгийн тоог тоолдог. Үр дүнгийн утгыг нийт тэмдэгтийн тоонд хувааснаар бид нүд тус бүрийн уурхайг олох магадлалыг олж авдаг. Жишээ нь ганцхан найдвартай шийдэлтэй мэт санагдсан энэ нөхцөлд сүүлийн арга (Сүүлчийн эргэлт) уурхай олох 0%-ийн магадлалтай 3 нүдийг олсон.LastTurns(9,21) боломжит 293930 хослолоос 144 тохирох хослолыг шалгаад хамгийн багадаа 0% магадлалтай 3 нүдийг олжээ.
Санааг ойлгоход төвөгтэй байдлын үүднээс энэ арга нь хамгийн хялбар тул би үүнийг нарийвчлан шинжлэхгүй.
Түүний хэрэгжилт
/** * Харгис хэрцгий хүчийг ашиглан бие даасан тооцооллын алгоритм. Үл мэдэгдэх нүднүүдийн тоо 30-аас ихгүй тохиолдолд л ашиглах боломжтой * @return */ public ArrayList
Дүгнэлт
Практикт хангалттай тооны дээжтэй бол үүрэнд уурхай олох магадлалын тооцоолсон болон бодит утгууд бараг давхцдаг. Дараах хүснэгтэд Minesweeper дээр Windows 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% талбайн том зөрүү нь ихэвчлэн энэ хувь нь ойролцоо нээгдээгүй (жишээлбэл, тоглоомын эхэнд) эсүүдтэй байсантай холбоотой байж болох юм, мөн "Минег хамгаалагч" нь тоглогчид тохирсон байдаг. нээгдсэн үүрний доороос уурхайг зайлуулах. Ажлын алгоритмыг java хэл дээр хэрэгжүүлсэн бөгөөд стандарт Windows мина тээгч хөлөг онгоц (7 ба XP), VK болон тоглоом дээрх програм дээр туршиж үзсэн. Дашрамд хэлэхэд, миний IP-ээс миний данс руу нэвтрэх үед хэдэн өдрийн турш "техникийн асуудал" гарсны дараа тоглогч талбайн хэсгийг нээхдээ урамшууллын дүрмийг өөрчилсөн: эхлээд тэр нээлттэй талбайн 10% -ийн бооцооны 10% -ийг буцааж өгсөн. 5%, дараа нь 2%, би тоглохоо больсон үед 5% буцааж өгсөн.
Windows үйлдлийн системтэй ажилладаг хэн бүхэн Minesweeper тоглоомыг мэддэг. Энэ хэсэгт ижил төстэй хөтөлбөрийг авч үзэх болно.
Тоглоомын төгсгөлд (тоглогч уурхай байрладаг нүдийг нээсний дараа) програмын цонхны жишээг Зураг дээр үзүүлэв. 10.7.
Цагаан будаа. 10.7. Minesweeper програмын цонх
Тоглоомын дүрэм, өгөгдөл танилцуулга
Тоглоомын талбар нь эсүүдээс бүрдэх бөгөөд тус бүр нь мина агуулж болно. Тоглогчийн даалгавар бол бүх уурхайг олж, тугнуудаар тэмдэглэх явдал юм.
Тоглогч хулганы товчлууруудыг ашиглан нүдийг нээж эсвэл дотор нь туг байрлуулж болох бөгөөд ингэснээр нүдэнд мин байгаа гэдгийг илтгэнэ. Хулганы зүүн товчийг дарснаар нүд нээгдэж, баруун товчлуур дээр дарснаар нүдийг шалгана. Хэрэв тоглогч нээсэн үүрэнд уурхай байгаа бол дэлбэрэлт гарч (сапер алдаа гаргасан бөгөөд бидний мэдэж байгаагаар тэр зөвхөн нэг л алдаа гаргадаг) тоглоом дуусна. Хэрэв нүдэнд уурхай байхгүй бол хөрш зэргэлдээх нүднүүдийн уурхайн тоонд тохирох тоо тухайн нүдэнд гарч ирнэ.
Тоглогч аль хэдийн нээгдсэнтэй зэргэлдээх үүрэн дэх уурхайнуудын тооны талаарх мэдээллийг задлан шинжилснээр бүх уурхайг илрүүлж, далбаагаар тэмдэглэх боломжтой. Тугнуудаар тэмдэглэгдсэн нүдний тоонд хязгаарлалт байхгүй. Гэсэн хэдий ч тоглоомыг дуусгахын тулд (ялахын тулд) тугуудыг зөвхөн уурхайтай нүднүүдэд байрлуулах ёстой. Алдаатай сонгогдсон нүдэн дээр хулганы баруун товчийг дарж тэмдэглэгээг арилгаж болно.