Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Алгорифм логики бота для игры «Сапёр»

Anna | 2.06.2014 | нет комментариев
Наверное всякий из нас когда-нибудь играл, либо по крайней мере пробовал играть в «Сапёр» («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) ds_permark! while(repeat); }

В результате у нас получатся три вида групп.

  • число мин равно нулю
  • число мин равно числу ячеек в группе
  • ненулевое число мин поменьше числа ячеек в группе

Соответственно все ячейки из первой группы дозволено отважно открывать, а из 2-й группы подмечать. В этом суть основного алгорифма.

Если нет подлинного решения

Но Зачастую встречаются обстановки, когда нет подлинного решения обстановки. Тогда на поддержка приходит дальнейший алгорифм. Его суть состоит в применении теории вероятности. Алгорифм работает в два этапа:

  1. Определение вероятности в отдельных ячейках, рассматривая воздействие нескольких открытых ячеек
  2. Корректировка вероятностей, рассматривая взаимное воздействие групп с всеобщими ячейками друг на друга

Разглядим как работает данный способ на примере обстановки, когда открыты каждого две соседние ячейки со значениями 4 и 2. Вероятности нахождения мин от ячеек 4 и 2 по отдельности равны 4/7=0,57 и 2/7=0,28 соответственно.

Для вычисления вероятности нахождения мины в ячейке рядом с несколькими открытыми ячейками используем формулу расчета вероятности правда бы одного события:

Вероятность наступления события А, состоящего в происхождении правда бы одного из событий А1, А2,…, Аn, самостоятельных в общности, равна разности между единицей и произведением вероятностей противоположных событий. А=1- (1-A1)*(1-A2)*….*(1-An)

В смежных ячейках позже использования этой формулы итог равен 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 k! do{ repeat=false; for (Group group : groups){ // для всякой группы List<Double> 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 ArrayList<Point> getLastTurns() {
        int minesLeft = countMinesLeft(); // число оставшихся непомеченными мин
        ArrayList<Cell> unknownCells = getUnknownCells(); // список неведомых ячеек
        int notOpened = unknownCells.size();              // число неведомых ячеек
        Integer[] combinations = new Sequence6().getSequensed(minesLeft, notOpened); // массив разных комбинаций из заданного числа мин в заданном числе ячеек
        ArrayList<String> list = new ArrayList<String>(); // список допустимых комбинаций
        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.size()];
        list.toArray(comb);  // преобразовываем список в массив, и дальше трудимся с массивом
        int[] possibilities2 = new int[notOpened]; // массив по числу незнакомых ячеек, содержащий число вариантов, где может располагаться мина в заданной ячейке
        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<Integer> 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[minIndices.get(0)] / comb.length;
        System.out.println("LastTurns("   minesLeft   ","   notOpened   ") проверил "   comb.length  
                " подходящих комбинаций из "   combinations.length   " допустимых и обнаружил "   minIndices.size()   " ячеек"  
                " с минимальной вероятностью "   (int) minPossibility   " %");

        ArrayList<Point> result = new ArrayList<Point>(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%.

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB