Bot -logiska algoritmer för spelet Minesweeper. Botlogiska algoritmer för spelet "Minesvepare. Kod för spelet Minesvepare i c

Alla som jobbar med operativ system Windows, spelet "Minesweeper" är mycket bekant. Detta avsnitt behandlar ett liknande program.

Ett exempel på programfönstret i slutet av spelet (efter att spelaren har öppnat cellen där gruvan finns) visas i fig. 10.7.

Ris. 10.7... Programfönster för Minesvepare

Spelregler och datapresentation

Spelplanen består av celler, som var och en kan innehålla en gruva. Spelarens uppgift är att hitta alla gruvor och markera dem med flaggor.

Med musknapparna kan spelaren öppna cellen eller sätta en flagga i den och därmed indikera att det finns en gruva i cellen. Cellen öppnas genom att klicka på vänster musknapp, kryssrutan ställs in genom att klicka på höger. Om det finns en gruva i cellen som spelaren öppnar, inträffar en explosion (sappern gjorde ett misstag, och han, som du vet, gör misstag bara en gång) och spelet slutar. Om det inte finns någon gruva i en cell, visas ett nummer i denna cell, motsvarande antalet gruvor i angränsande celler.

Genom att analysera informationen om antalet gruvor i cellerna intill de redan öppna kan spelaren upptäcka och markera alla gruvor med flaggor. Det finns ingen gräns för antalet flaggade celler. Men för att kunna slutföra spelet (för att vinna) måste flaggorna endast installeras i de celler där det finns gruvor. En felaktigt markerad kryssruta kan tas bort genom att högerklicka i cellen där den finns.

Förmodligen har vi alla någonsin spelat, eller åtminstone försökt spela "Minesveparen" ("MineSweeper"). Spelets logik är enkel, men på en gång lovade de till och med en belöning för algoritmen för att klara det. I min bot har logiken tre algoritmer som används beroende på situationen på fältet. Den grundläggande algoritmen låter dig hitta alla celler med 100 och 0 procents sannolikhet att hitta en gruva. Om du bara använder denna algoritm och slumpmässigt öppnar slumpmässiga celler i avsaknad av en tillförlitlig lösning i en standard sapper på "Expert" -nivå kan du uppnå 33% av vinsterna. Vissa ytterligare algoritmer låter dig dock höja detta värde till 44% (Windows 7).

Grundläggande algoritm

Huvudalgoritmen är följande. Okända celler (klasscell) intill en öppen cell bildas till en grupp (klassgrupp), i vilken värdet på cellen som den ligger intill också skrivs.

Figuren visar fyra grupper, varav några skär varandra, och vissa innehåller till och med andra grupper. Låt oss beteckna (123,1) - gruppen består av celler 1,2 och 3, och samtidigt finns det en gruva i dem. (5678.2) - det finns 2 gruvor i fyra celler.

Först måste du omvandla grupperna. För detta:

1. Vi jämför varje grupp med varje efterföljande grupp.
2. Om grupperna är desamma tar du bort den andra.
3. Om en grupp innehåller en annan, dra sedan den mindre från den större. Det vill säga att det fanns två grupper (5678.2) och (5.1), nu (678.1) och (5.1); (2345.3) och (5.1) → (234.2) och (5.1)
4. Överlappande grupper, till exempel (123,1) och (234,2), transformeras enligt följande princip:
   1. Skapa en ny grupp av skärande celler (23,?)
   2. Vi beräknar antalet gruvor i den nya gruppen lika med antalet gruvor i gruppen med ett stort antal gruvor (234,2) minus det återstående antalet celler i den andra gruppen efter separering av de skärande cellerna (1,?). Det vill säga 2-1 = 1. Vi får (23,1)
   3. Om det beräknade antalet minuter i den nya gruppen (23.1) inte är lika med antalet minuter i gruppen med färre minuter (123.1), stoppa sedan konverteringen
   4. Subtrahera den nybildade gruppen från båda korsande grupperna. (123.1) - (23.1) = (1.0), (234.2) - (23.1) = (4.1).
   5. Lägg till den nybildade gruppen i listan över grupper
   Så (234.2) och (123.1) → (1.0) och (23.1) och (4.1).
5. Vi upprepar från steg 1 tills inga ändringar görs.

Metod för att skapa och transformera grupper

/ ** * Skapar en lista med grupper av celler som är länkade med ett värde i ett öppet fält och bryter dem också till mindre, tar bort dubbletter. * / private void setGroups () (groups.clear (); för (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++) { // проходим по списку групп Gruppgrupp I = groups.get (i); för (int j = i + 1; j< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем одинаковые группы {groups.remove(j--);break;} Group parent; // большая группа Group child; // меньшая группа if (groupI.size()>groupJ.size ()) // definiera en större och mindre grupp med antalet celler (förälder = gruppI; barn = gruppJ;) annat (barn = gruppI; förälder = gruppJ;) om (förälder.innehåller (barn)) ( / / om den större innehåller den mindre förälder. subtraktion (underordnad); // subtrahera sedan den mindre från den större upprepa = sant; // fixa faktum för gruppändringar) annars om (groupI.overlaps (groupJ) > 0) (// annars om grupperna överlappar om (groupI.getMines ()> groupJ.getMines ()) // definierar en större och mindre grupp med antalet minuter (förälder = gruppI; barn = gruppJ;) annat ( barn = gruppI; förälder = gruppJ;) Gruppöverlappning = förälder .getOverlap (barn); // då tar vi resultatet av korsningen om (överlappning! = null) (// och om det är vettigt (som ett resultat av korsning, celler med 0% eller 100% avslöjades) grupper.add (överlappning); // gör sedan lämpliga justeringar i listan överordnad.subtraktion (överlappning); barn.subtraktion (överlappning); upprepa = sant;))) )) medan (upprepa); )

Som ett resultat kommer vi att ha tre typer av grupper.

• antalet gruvor är noll
• antalet gruvor är lika med antalet celler i gruppen
• icke-noll antal gruvor mindre än antalet celler i gruppen

Följaktligen kan alla celler från den första gruppen öppnas säkert, och de från den andra gruppen kan markeras. Detta är kärnan i huvudalgoritmen.

Om det inte finns någon pålitlig lösning

Men situationer uppstår ofta när det inte finns någon tillförlitlig lösning på situationen. Då kommer följande algoritm till undsättning. Dess väsen ligger i användningen av sannolikhetsteorin. Algoritmen fungerar i två steg:

1. Bestämning av sannolikheten i enskilda celler, med tanke på påverkan av flera öppna celler
2. Justering av sannolikheter, med hänsyn tagen till ömsesidigt inflytande av grupper med gemensamma celler på varandra

Låt oss överväga hur denna metod fungerar på exemplet på en situation när endast två närliggande celler med värden 4 och 2. är öppna. Sannolikheten att hitta gruvor från cellerna 4 och 2 separat är 4/7 = 0,57 och 2/7 = 0,28 , respektive.

För att beräkna sannolikheten för att hitta en gruva i en cell bredvid flera öppna celler använder vi formeln för att beräkna sannolikheten för minst en händelse:

Sannolikheten för att en händelse A inträffar, som består i uppkomsten av minst en av händelserna A 1, A 2, ..., A n, oberoende i aggregatet, är lika med skillnaden mellan enhet och produkt av produkten sannolikheten för motsatta händelser. A = 1- (1-A 1) * (1-A 2) * .... * (1-A n)

I angränsande celler, efter tillämpning av denna formel, är resultatet 1- (1-0,57) * (1-0,28) = 0,69.

Det bör dock komma ihåg att summan av sannolikheterna i varje cellgrupp måste vara lika med antalet gruvor i gruppen. Därför måste alla värden i varje grupp multipliceras så att deras summa i slutändan är lika med antalet gruvor. Detta antal är lika med antalet gruvor i gruppen dividerat med den nuvarande summan av sannolikheterna för cellerna i gruppen:

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

Nu har de celler som hade en sannolikhet på 0,57 0,485 och de som 0,69 → 0,618
Vi gör en liknande beräkning för den andra gruppen, med hänsyn till justeringarna från den föregående.

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

Vi ser att sannolikheten i de gemensamma cellerna har förändrats igen, därför måste en sådan justering för varje grupp upprepas flera gånger tills systemet kommer till några stabila värden, vilket är de sanna sannolikheterna för att hitta gruvor i cellerna.

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.

Det återstår bara att välja en av cellerna med minsta sannolikhet och göra ett drag.

Denna metod i kod

/ ** * Metoden korrigerar sannolikheterna för att hitta gruvor i celler, med hänsyn tagen till det ömsesidiga inflytandet från granncellernas sannolikheter på varandra * / private void correctPosabilities () (karta celler = ny HashMap<>(); // slingan anger ett enda sannolikhetsvärde i varje cell, med hänsyn till olika sannolikheter i cellen från olika grupper för (Gruppgrupp: grupper) (för (Cell cell: group.getList ()) (Dubbelvärde; if ((value = cells.get (cell)) == null) // om cellen inte redan finns i cellerna .put map (cell, (dubbel) group.getMines () / group.size ()); // lägg sedan till den med ett värde från gruppen annars // om den redan finns på kartan, justera sedan dess värde enligt teorin om sannolikhetsceller.put (cell, Prob.sum (värde, (dubbel) group.getMines () / group.size ());)) // slingan justerar värdena med hänsyn till att summan av sannolikheterna i gruppen ska vara lika med antalet minuter i gruppens booleska upprepning; gör (upprepa = falskt; för (Gruppgrupp: grupper) (// för varje grupplista prob = group.getProbabilities (); // ta en lista över sannolikheter för alla celler i gruppen i procent Dubbel summa = 0,0; för (Dubbel elem: prob) summa + = elem; // beräkna dess summa int mines = group.getMines () * 100; // multiplicera antalet minuter i gruppen med hundra (på grund av procentsatser) om (Math.abs (summines)> 1) (// om skillnaden mellan dem är stor, justerar vi repeat = true;/ / fixa det faktum att justera Prob. korrekt (prob, gruvor); // korrigera listan för (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); } }

Sista drag

I spelets slutskede spelar antalet omärkta gruvor en viktig roll. Genom att känna till det här numret kan du kraftfullt tvinga in dem i okända celler och markera lämpliga alternativ. I processen med att räkna upp lämpliga alternativ för varje cell räknar vi antalet märken. Genom att dividera de resulterande värdena med det totala antalet märken får vi sannolikheten att hitta gruvorna för varje cell. Till exempel, i denna situation, som bara verkar ha en tillförlitlig lösning, hittade den sista metoden (LastTurns) tre celler med 0% sannolikhet att hitta en gruva.

LastTurns (9.21) kontrollerade 144 matchande kombinationer av 293930 möjliga och hittade 3 celler med en minsta sannolikhet på 0%

Ur komplexiteten att förstå idén är denna metod den enklaste, så jag kommer inte att analysera den i detalj för tillfället.

Dess genomförande

/ ** * En oberoende beräkningsalgoritm genom en banal sökning. Kan endast användas om antalet okända celler inte är mer än 30 * @return * / public ArrayList GetLastTurns () (int minesLeft = countMinesLeft (); // antal gruvor kvar omarkerade ArrayList unknownCells = getUnknownCells (); // lista över okända celler int notOpened = unknownCells.size (); // antal okända celler Heltalskombinationer = ny sekvens6 (). getSequensed (minesLeft, notOpened); // en rad olika kombinationer av ett givet antal gruvor i ett givet antal celler ArrayList list = new ArrayList (); // lista över möjliga kombinationer för (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 = new ArrayList<>(); // lista över index med minimivärdet i möjligheter2 för (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 + " %"); ArrayListResultat = ny ArrayList (minIndices.size ()); // lista över cellkoordinater med minsta sannolikhet för (int index: minIndices) (result.add (unknownCells.get (index) .getPoint ());) returresultat; )

Produktion

I praktiken, med ett tillräckligt antal prover, sammanfaller de beräknade och faktiska värdena för sannolikheterna för att hitta en gruva i en cell nästan. Följande tabell visar resultaten av boten som körs på Minesweeper under Windows XP för en natt, var

1. Beräknad%
2. Totalt antal cellöppningar med beräknad%
3. Antal träffar per gruva
4. Faktisk%

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

Den stora skillnaden i området 20-22% beror troligen på att denna procentsats ofta hade celler som inte redan hade öppna i närheten (till exempel i början av spelet), och Minesveparen anpassades till spelaren, ibland tar jag bort en gruva från cellen som öppnas. Arbetsalgoritmen implementerades i java och testades på en standard Windows sapper (7 och XP), en applikation i VK och på ett spel. Förresten, efter flera dagar av "tekniska problem" när han fick tillgång till mitt konto från min IP -adress, ändrade spelaren belöningsreglerna för att öppna en del av fältet: initialt returnerade han 10% av insatsen för 10% av det öppna fältet, sedan 5%, sedan 2%, och när jag slutade spela, sedan tillbaka 5%.