Внедряване на конзолната игра Minesweeper на стр. Логически алгоритми на бот за играта Minesweeper

Всеки, който работи с операционна система 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, докато няма промени

Метод за създаване и конвертиране на групи

/** * Създава списък от групи от клетки, свързани с една стойност на отворено поле, и също така ги разделя на по-малки, премахвайки дубликати.< 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++) { // проходим по списку групп */ private void setGroups() ( groups.clear(); for (int x = 0; xГрупова група< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем одинаковые группы {groups.remove(j--);break;} Group parent; // I = groups.get(i);Групово дете; // по-малка група if (groupI.size()>groupJ.size()) // определяне на по-голямата и по-малката група по броя на клетките (parent=groupI;child=groupJ;) else (child=groupI;parent=groupJ ; ) if (parent.contains(child)) ( // ако по-големият съдържа по-малкия parent.subtraction(child); // тогава извадете по-малкия от по-големия repeat=true; // запишете факта, че групите са се променили ) else if (groupI.overlaps(groupJ ) > 0) ( // в противен случай ако групите се пресичат if (groupI.getMines()>groupJ.getMines())// определяне на по-голямата и по-малката група по числото на мините (parent=groupI;child=groupJ;) else (child =groupI;parent=groupJ;) Group overlap = parent.getOverlap(child); // след това вземете резултата от пресичането if (overlap != null) ( // и ако има смисъл (в резултат на пресичането бяха разкрити клетки с 0% или 100%) groups.add(overlap); // тогава направете съответните корекции в списъка parent.subtraction(overlap); .изваждане (припокриване);

)

• В резултат на това ще имаме три вида групи.
• броят на мини е нула
• броят на мини е равен на броя на клетките в групата

ненулев брой мини е по-малък от броя на клетките в групата

Съответно всички клетки от първата група могат да бъдат безопасно отворени, а всички клетки от втората група могат да бъдат маркирани. Това е същността на основния алгоритъм.

Ако няма надеждно решение

1. Но често има ситуации, когато няма надеждно решение на ситуацията. Тогава на помощ идва следният алгоритъм. Същността му е използването на теорията на вероятностите. Алгоритъмът работи на два етапа:
2. Определяне на вероятността в отделни клетки, като се вземе предвид влиянието на няколко отворени клетки

Корекция на вероятностите, като се вземе предвид взаимното влияние на групи с общи клетки една върху друга

Нека да разгледаме как работи този метод, като използваме пример за ситуация, в която са отворени само две съседни клетки със стойности 4 и 2. Вероятностите за намиране на мини от клетки 4 и 2 поотделно са 4/7=0,57 и 2/7=. 0,28, съответно.

За да изчислим вероятността да намерим мина в клетка до няколко отворени клетки, използваме формулата за изчисляване на вероятността от поне едно събитие:

Вероятността за настъпване на събитие A, състояща се в настъпване на поне едно от събитията A 1, A 2,..., A n, независими в съвкупността, е равна на разликата между единица и произведението на вероятностите за противоположни събития. A=1- (1-A 1)*(1-A 2)*....*(1-A n)

Трябва обаче да се помни, че сумата от вероятностите във всяка група клетки трябва да бъде равна на броя на мините в групата. Следователно всички стойности във всяка група трябва да бъдат умножени, така че в крайна сметка сумата им да е равна на броя минути. Това число е равно на броя мини в групата, разделен на текущата сума от вероятностите на клетките на групата:

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())( Map клетки= нова HashMap<>(); // цикълът задава една стойност на вероятността във всяка клетка, като взема предвид различните стойности на вероятността в клетка от различни групи for (Group group: groups)( for (Cell cell: group.getList())( Double value; if ((value=cells. get(cell))==null) // ако клетката все още не е в картата cells.put(cell,(double) group.getMines()/ group.size()); след това го добавете със стойността от групата else / /ако вече е в картата, тогава коригираме стойността му според теорията на вероятностите cells.put(cell,Prob.sum(value,(double) group.getMines()/ group.size()) ) // цикълът коригира стойностите, като взема предвид, че сумата от вероятностите в групата трябва да бъде равна на броя на мини в груповото булево повторение;< group.size();i++){ // заносим откорректированные значения из списка в ячейки double value= prob.get(i); group.getList().get(i).setPossibility(value); } } } } while (repeat); for (Cell cell:cells.keySet()){ // перестраховка if (cell.getPossibility()>do( repeat=false; for (Групова група: групи)( // за всяка група Списък<0)cell.setPossibility(0); } }

prob= group.getProbabilities(); // вземете списъка с вероятности на всички клетки в групата в проценти Double sum=0.0;

В последния етап на играта броят на немаркираните мини играе голяма роля. Знаейки този номер, можете да ги замените с груба сила в неизвестни клетки и да маркирате подходящите опции. В процеса на търсене на подходящи опции за всяка клетка, ние броим броя на маркировките. Разделяйки получените стойности на общия брой марки, получаваме вероятността да намерим мини за всяка клетка. Например, в тази ситуация, която изглежда имаше само едно надеждно решение, последният метод (LastTurns) намери 3 клетки с 0% вероятност за намиране на мина.

LastTurns(9,21) провери 144 подходящи комбинации от 293930 възможни и намери 3 клетки с минимална вероятност от 0%

От гледна точка на сложността на разбирането на идеята, този метод е най-лесният, така че все още няма да го анализирам подробно.

Изпълнението му

/** * Независим алгоритъм за изчисление, използващ банална груба сила. Може да се използва само ако броят на неизвестните клетки е не повече от 30 * @return */ public ArrayList GetLastTurns() ( int minesLeft = countMinesLeft(); // брой мини, оставащи немаркирани ArrayList unknownCells = getUnknownCells(); // списък с неизвестни клетки int notOpened = unknownCells.size(); // брой неизвестни клетки Целочислени комбинации = нова 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<>(); // списък с индекси с минималната стойност в possibilities2 за (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 + " %"); ArrayListРезултат = нов ArrayList (minIndices.size());// списък с координати на клетки с минимална вероятност за (int index: minIndices) ( result.add(unknownCells.get(index).getPoint()); ) върнат резултат;

)

Заключение

1. На практика, при достатъчен брой проби, изчислените и действителните стойности на вероятностите за намиране на мина в клетка почти съвпадат. Следната таблица показва резултатите от работата на бота на Minesweeper под Windows XP за една нощ, където
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% вероятно се дължи на факта, че често този процент има клетки, които все още не са били отворени наблизо (например в началото на играта), и „Mineweeper“, адаптиран към играча, понякога премахване на мина изпод отворената клетка. Алгоритъмът на работа е реализиран в java и тестван на стандартен миночистач на Windows (7 и XP), приложение във VK и в играта. Между другото, след няколко дни на „технически проблеми“ при достъп до акаунта ми от моя IP, играта промени правилата за награди за отваряне на част от полето: първоначално връщаше 10% от залога за 10% от отвореното поле, след това 5%, след това 2%, а когато спрях да играя, върнах 5%.