Наверное каждый из нас когда-нибудь играл, или по крайней мере пробовал играть в «Сапёр» («MineSweeper»). Логика игры проста, но в свое время за алгоритм ее прохождения даже обещали вознаграждение. В моем боте логика имеет три алгоритма, которые используются в зависимости от ситуации на поле. Основной алгоритм позволяет находить все ячейки со 100- и 0-процентной вероятностью нахождения мины. Используя только этот алгоритм и открывая наугад произвольные ячейки при отсутствии достоверного решения в стандартном сапере на уровне «Эксперт» можно достичь 33% выигрышей. Однако некоторые дополнительные алгоритмы позволяют поднять это значение до 44% (Windows 7).

Основной алгоритм


Основной алгоритм состоит в следующем. Неизвестные ячейки (класс Cell), прилегающие к одной открытой ячейке формируются в группу (класс Group), в которую записывается также значение ячейки, к которой она прилегает.

На рисунке обозначены четыре группы, некоторые из которых пересекаются, а некоторые и вовсе содержат другие группы. Обозначим (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() { groups.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++) { // проходим по списку групп Group groupI = groups.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; // большая группа Group child; // меньшая группа 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); child.subtraction(overlap); repeat=true; } } } } } while(repeat); }


В итоге у нас получатся три вида групп.
  • количество мин равно нулю
  • количество мин равно количеству ячеек в группе
  • ненулевое количество мин меньше количества ячеек в группе
Соответственно все ячейки из первой группы можно смело открывать, а из второй группы отмечать. В этом суть основного алгоритма.
Если нет достоверного решения
Но часто встречаются ситуации, когда нет достоверного решения ситуации. Тогда на помощь приходит следующий алгоритм. Его суть состоит в использовании теории вероятности. Алгоритм работает в два этапа:
  1. Определение вероятности в отдельных ячейках, учитывая влияние нескольких открытых ячеек
  2. Корректировка вероятностей, учитывая взаимное влияние групп с общими ячейками друг на друга
Рассмотрим как работает этот метод на примере ситуации, когда открыты всего две соседние ячейки со значениями 4 и 2. Вероятности нахождения мин от ячеек 4 и 2 по отдельности равны 4/7=0,57 и 2/7=0,28 соответственно.


Для вычисления вероятности нахождения мины в ячейке рядом с несколькими открытыми ячейками используем формулу расчета вероятности хотя бы одного события:
Вероятность наступления события А, состоящего в появлении хотя бы одного из событий А 1 , А 2 ,..., А n , независимых в совокупности, равна разности между единицей и произведением вероятностей противоположных событий. А=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(){ Mapcells= new 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())); } } // цикл корректирует значения с учетом того, что сумма вероятностей в группе должна быть равна количеству мин в группе boolean repeat; do{ repeat=false; for (Group group: groups){ // для каждой группы List prob= group.getProbabilities(); // берем список вероятностей всех ячеек в группе в процентах Double sum=0.0; for (Double elem:prob)sum+=elem; // вычисляем ее сумму int mines= group.getMines()*100; // умножаем количество мин в группе на сто (из-за процентов) if (Math.abs(sum-mines)>1){ // если разница между ними велика, то проводим корректировку repeat=true; // фиксируем факт корректировки Prob.correct(prob,mines); // корректируем список for (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); } }

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


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

C точки зрения сложности понимания идеи этот метод самый легкий, поэтому подробно разбирать его пока не буду.

Его реализация

/** * Самостоятельный алгоритм расчета путем банального перебора. Можно использовать только если количество неизвестных ячеек не больше 30 * @return */ public ArrayListGetLastTurns() { int minesLeft = countMinesLeft(); // количество оставшихся непомеченными мин ArrayList unknownCells = getUnknownCells(); // список неизвестных ячеек int notOpened = unknownCells.size(); // количество неизвестных ячеек Integer combinations = new Sequence6().getSequensed(minesLeft, notOpened); // массив различных комбинаций из заданного количества мин в заданном количестве ячеек ArrayList list = new ArrayList(); // список возможных комбинаций for (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; ArrayList minIndices = new ArrayList<>(); // список индексов с минимальным значением в possibilities2 for (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 + " %"); ArrayListResult = new ArrayList(minIndices.size());// список координат ячеек с минимальной вероятностью for (int index: minIndices) { result.add(unknownCells.get(index).getPoint()); } return result; }

Вывод
На практике при достаточном числе выборок расчетные и фактические значения вероятностей нахождения мины в ячейке почти совпадают. В следующей таблице приведены результаты работы бота на «Сапер» под 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 и ХР), приложении в VK и на игруне. К слову сказать, после нескольких дней «технических неполадок» при доступе на мой аккаунт с моего IP игрун изменил правила вознаграждения за открытие части поля: изначально возвращал 10% ставки за 10% открытого поля, потом 5%, потом 2%, а когда я перестал играть, то вернул 5%.

Всем, кто работает с операционной системой Windows, хорошо знакома игра "Сапер". В этом разделе рассматривается аналогичная программа.

Пример окна программы в конце игры (после того, как игрок открыл клетку, в которой находится мина) приведен на рис. 10.7.

Рис. 10.7 . Окно программы "Сапер"

Правила игры и представление данных

Игровое поле состоит из клеток, в каждой из которых может быть мина. Задача игрока - найти все мины и пометить их флажками.

Используя кнопки мыши, игрок может открыть клетку или поставить в нее флажок, указав тем самым, что в клетке находится мина. Клетка открывается щелчком левой кнопки мыши, флажок ставится щелчком правой. Если в клетке, которую открыл игрок, есть мина, то происходит взрыв (сапер ошибся, а он, как известно, ошибается только один раз) и игра заканчивается. Если в клетке мины нет, то в этой клетке появляется число, соответствующее количеству мин, находящихся в соседних клетках.

Анализируя информацию о количестве мин в клетках, соседних с уже открытыми, игрок может обнаружить и пометить флажками все мины. Ограничений на количество клеток, помеченных флажками, нет. Однако для завершения игры (для выигрыша) флажки должны быть установлены только в тех клетках, в которых есть мины. Ошибочно установленный флажок можно убрать, щелкнув правой кнопкой мыши в клетке, в которой он находится.