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

/**
     * Создает список групп ячеек, связанных одним значением открытого поля, а также разбивает их на более мелкие, удаляет повторяющиеся.
     */
    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);
    }

/**
     * Метод вносит корректировку в значения вероятностей нахождения мин в ячейках, учитывая взаимное влияние вероятностей соседних ячеек друг на друга
     */
    private void correctPosibilities(){
        Map<Cell,Double>cells= 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<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);
        }
    }

/**
     * Самостоятельный алгоритм расчета путем банального перебора. Можно использовать только если количество неизвестных ячеек не больше 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;
    }