Продвинутые и подробные вероятности мин.

В предыдущем вопросе я показал свой код для расчета вероятности шахты для каждого и каждое поле на борту Minesweeper. Но это не останавливается на достигнутом. В этом же проекте Minesweeper Analyze существует также алгоритм вычисления вероятности каждого и каждого числа для каждого поля.

Мотивация

В многопользовательской версии Minesweeper, называемой Minesweeper Flags , вы должны быть осторожны, чтобы не показывать слишком много информации вашему противнику. Часто это отличает хорошего игрока от игрока bad неопытного . Если есть 80% -ный шанс стать мином, но 20% -ный шанс открыть открытое поле (которое потенциально может открыть 10 очевидных мин вашему противнику), вы рискнете? Вычисление Ожидаемое значение (это совершенно другая тема само по себе) говорит нам, что это, вероятно, плохая идея.

Описание

Рассмотрим эту плату 8x7 Minesweeper с общим количеством 6 мин:

8x7 Плата с маневром с 1-3 последовательностью в середине

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

  • 3 поля подключаются только к 1 (b)
  • 4 поля, соединенные как с 1, так и с 3 (c)
  • 3 поля, только связанные с 3 (d)
  • 44 полей, не связанных ни с одним (a)

Та же карта, организованная в группы полей

При выполнении анализа вероятности разминирования на этой плате мы обнаруживаем, что есть две группы решений:

  • 4c = 1, 44a = 3, 3b = 0, 3d = 2, 158928 комбинаций (4 поля в группе c должны иметь одну шахту, 44 поля в группе a должен иметь 3 мин и т. д.)
  • 4c = 0, 44a = 2, 3b = 1, 3d = 3, 2838 комбинаций

Теперь, какова вероятность числа «2» непосредственно над «1»? Назовем поле над 1 как x. Можно было бы вычислить, что добавив FieldRule к существующей плате для соседей x (2a + 3d + 1b = 2) , и правило для этого поля, которое не является миной (x = 0). Но если бы мы сделали это для каждого поля на доске, это заняло бы довольно много времени. Не говоря уже о том, что мы должны делать это для каждого номера (0-8).

Итак, мы можем сгруппировать поля в группы групп вероятности , с помощью которых группы полей они соседствуют с:

Field Groups     Probability Groups
  aaaaaaaa           abbbbbba
  aaaaaaaa           bcdefghb
  aabccdaa           bijklmnb
  aab13daa           bop13qrb
  aabccdaa           bijklmnb
  aaaaaaaa           bcdefghb
  aaaaaaaa           abbbbbba

В соответствии с приведенной выше диаграммой группа вероятности k принадлежит нашему полю x, она соседствует с группами полей 3*a, 2*b, 1*c. Эта информация может быть сохранена в структуре GroupValues, которая была введена в предыдущем вопросе, по существу, это Map<FieldGroup, Integer>. Чтобы улучшить скорость поиска, это значение hashCode сохраняется после его вычисления в первый раз для лучшей производительности.

Мы видим, что на карте групп вероятностей на самом деле два кода k, поэтому мы получаем некоторую производительность, группируя их вместе , поскольку они будут иметь одинаковые подробные вероятности . Есть также 22 b на карте , поэтому мы получаем большую производительность, чтобы получить их долю вероятности. Обратите внимание, что все поля в группе вероятности b являются соседними 5 FieldGroupa

Вычисление подробных вероятностей для группы вероятностей

Давайте сосредоточимся на этом решении на данный момент: 4c = 1, 44a = 3, 3b = 0, 3d = 2, 158928 комбинаций

Мы знаем, что поле x (в группе вероятности k) имеет следующие соседи: 3 * a, 2 * b, 1 * c.

Сначала мы имеем дело с 1c (потому что это то, что выбрал отладчик Eclipse). Либо у этого конкретного соседа есть мина, либо нет. Допустим, у него нет шахты. Тогда есть 2 комбинации, так как есть два поля c вдали от поля x, и у одного из них должен быть мой.

Во-вторых, 3a. В группе a всего 44 поля, и в этом решении должно быть 3 мин. Это поле находится рядом с 3 из этих полей. Предположим, что 1 из этих соседей - моя, тогда есть (согласно гипергеометрическое распределение ) \ $ \ binom {3} {1} * \ binom {44 - 3} {3 - 1} = 2460 \ $.

Тогда соседи 2b. Мы знаем из нашего решения, хотя в b нет мин, так что это легко: одна комбинация.

Мы не являемся соседом ни с кем, поэтому есть 3 комбинации для них (3 поля, 2 мин).

Итак, для не мины в c, одна моя в a и никакие мины в b, есть всего одна мина, и \ $ 2 * 2460 * 1 * 3 = 14760 \ $. Поскольку в поле x в настоящее время не найдено ни одного найденного поля, мы добавляем 14760 к комбинациям для нашего поля x как 1

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

В конце мы получим этот double[] для числа вероятностей для нашего поля x: [0.4004549781783564, 0.2998343285980985, 0.05172285894440117, 0.0023552538852416455, 1.854530618300508E-5, 0.0, 0.0, 0.0, 0.0]

То есть 40% риск быть открытым полем, 29,9% шанс для 1, 5,1% для 2 и т. д.

Отражение скорости

Существует одна итерация по группам вероятности, одна для решений и одна для соседних FieldGroups, а затем одна рекурсивная петля для конкретного назначения. Так что это что-то вроде \ $ O (вероятностные группы * решений * K ^ {соседниеGroups}) \ $ Кроме того, есть также некоторый расчет реальных комбинаций, используя биномиальный коэффициент и гипергеометрическое распределение .

Это вызывает огромные проблемы с производительностью при наличии множества решений, многих групп полей и /или многих групп вероятности, например, в «Супер доска смерти» , в результате чего такие доски остаются практически нерешенными, так как для их решения потребуется слишком много времени. К счастью, хотя такие ситуации редко бывают . Когда бот использует этот алгоритм для воспроизведения бота, он упрощает анализ, необходимый при приеме мин. И в других случаях, когда этот алгоритм используется, он в основном используется для анализа игр, где игроки несколько умны, поэтому игра редко становится слишком сложной. И кроме того ... этот алгоритм быстрее всех других алгоритмов /подходов, о которых я знаю.

Типичные значения:

  • Группы полей обычно составляют от 10 до 50, в некоторых редких случаях до 100.
  • Группы решений имеют тенденцию быть от 2 до 50, в некоторых играх, где два плохих игрока играют друг с другом, он может легко подняться до 1500 (и за его пределами).
  • Вероятностные группы обычно составляют около 50, в некоторых случаях до 100.

Этот алгоритм тайм-аутов, когда эти значения тожебольшой.

Поскольку игры воспроизводятся на доске 16x16 (в настоящий момент, по крайней мере, в будущем будет больше поддерживать), абсолютный максимум для групп полей и групп вероятностей - 256. Для групп решений нет известного максимума, как игры с большое количество групп решений занимает слишком много времени, чтобы анализировать даже при «простом» анализе (только вероятности мин).

Сводка классов (7 файлов)

  • DetailAnalyze: Entry-point, содержащий один статический метод для выполнения анализа
  • Подробные результаты: интерфейс для доступа к результатам
  • ПодробноРезультатыИмпл: Реализация вышеуказанного интерфейса
  • FieldProxy: контейнер для подробных вероятностей для одного поля
  • NeighborFind: интерфейс для проверки соседей и определения текущих известных мин вокруг поля
  • ProbabilityKnowledge: открытый интерфейс класса FieldProxy
  • ProxyProvider: интерфейс, используемый при создании результатов для доступа к данным других полей

Зависимости

AnalyzeResult, Combinatorics, FieldGroup, GroupValues, RuntimeTimeoutException, решение из других частей моего Проводник анализа проекта

Код

Код использует Java 6 и может быть найден в моем Minesweeper Анализ репозитория github

Прежде всего, измененная версия GroupValues

public class GroupValues<T> extends HashMap<FieldGroup<T>, Integer> {
    private static final long   serialVersionUID    = -107328884258597555L;
    private int bufferedHash = 0;

    public GroupValues(GroupValues<T> values) {
        super(values);
    }

    public GroupValues() {
        super();
    }

    @Override
    public int hashCode() {
        if (bufferedHash != 0) {
            return this.bufferedHash;
        }

        int result = super.hashCode();
        this.bufferedHash = result;
        return result;
    }

    public int calculateHash() {
        this.bufferedHash = 0;
        return this.hashCode();
    }

}

Затем остальная часть кода:

DetailAnalyze.java: (62 строки, 2139 байт)

/**
 * Creator of {@link DetailedResults} given an {@link AnalyzeResult} and a {@link NeighborFind} strategy
 * 
 * @author Simon Forsberg
 */
public class DetailAnalyze {
    public static <T> DetailedResults<T> solveDetailed(AnalyzeResult<T> analyze, NeighborFind<T> neighborStrategy) {
        // Initialize FieldProxies
        final Map<T, FieldProxy<T>> proxies = new HashMap<T, FieldProxy<T>>();
        for (FieldGroup<T> group : analyze.getGroups()) {
            for (T field : group) {
                FieldProxy<T> proxy = new FieldProxy<T>(group, field);
                proxies.put(field, proxy);
            }
        }

        // Setup proxy provider
        ProxyProvider<T> provider = new ProxyProvider<T>() {
            @Override
            public FieldProxy<T> getProxyFor(T field) {
                return proxies.get(field);
            }
        };

        // Setup neighbors for proxies
        for (FieldProxy<T> fieldProxy : proxies.values()) {
            fieldProxy.fixNeighbors(neighborStrategy, provider);
        }

        double totalCombinations = analyze.getTotal();
        Map<GroupValues<T>, FieldProxy<T>> bufferedValues = new HashMap<GroupValues<T>, FieldProxy<T>>();
        for (FieldProxy<T> proxy : proxies.values()) {
            // Check if it is possible to re-use a previous value
            FieldProxy<T> bufferedValue = bufferedValues.get(proxy.getNeighbors());
            if (bufferedValue != null && bufferedValue.getFieldGroup() == proxy.getFieldGroup()) {
                proxy.copyFromOther(bufferedValue, totalCombinations);
                continue;
            }

            // Setup the probabilities for this field proxy
            for (Solution<T> solution : analyze.getSolutionIteration()) {
                proxy.addSolution(solution);
            }
            proxy.finalCalculation(totalCombinations);
            bufferedValues.put(proxy.getNeighbors(), proxy);
        }

        int proxyCount = bufferedValues.size();

        return new DetailedResultsImpl<T>(analyze, proxies, proxyCount);
    }
}

DetailResults.java: (46 строк, 1162 байта)

/**
 * Interface for retreiving more detailed probabilities, for example 'What is the probability for a 4 on field x?'
 * 
 * @author Simon Forsberg
 *
 * @param <T> The field type
 */
public interface DetailedResults<T> {

    Collection<ProbabilityKnowledge<T>> getProxies();

    /**
     * Get the number of unique proxies that was required for the calculation. As some can be re-used, this will always be lesser than or equal to <code>getProxyMap().size()</code>
     * 
     * @return The number of unique proxies
     */
    int getProxyCount();

    /**
     * Get a specific proxy for a field
     * 
     * @param field
     * @return
     */
    ProbabilityKnowledge<T> getProxyFor(T field);

    /**
     * Get the underlying analyze that these detailed results was based on
     * 
     * @return {@link AnalyzeResult} object that is the source of this analyze
     */
    AnalyzeResult<T> getAnalyze();

    /**
     * @return The map of all probability datas
     */
    Map<T, ProbabilityKnowledge<T>> getProxyMap();

}

ПодробныерезультатыImpl.java: (46 строк, 1211 байт)

public class DetailedResultsImpl<T> implements DetailedResults<T> {

    private final AnalyzeResult<T> analyze;
    private final Map<T, ProbabilityKnowledge<T>> proxies;
    private final int proxyCount;

    public DetailedResultsImpl(AnalyzeResult<T> analyze, Map<T, FieldProxy<T>> proxies, int proxyCount) {
        this.analyze = analyze;
        this.proxies = Collections.unmodifiableMap(new HashMap<T, ProbabilityKnowledge<T>>(proxies));
        this.proxyCount = proxyCount;
    }

    @Override
    public Collection<ProbabilityKnowledge<T>> getProxies() {
        return Collections.unmodifiableCollection(proxies.values());
    }

    @Override
    public int getProxyCount() {
        return proxyCount;
    }

    @Override
    public ProbabilityKnowledge<T> getProxyFor(T field) {
        return proxies.get(field);
    }

    @Override
    public AnalyzeResult<T> getAnalyze() {
        return analyze;
    }

    @Override
    public Map<T, ProbabilityKnowledge<T>> getProxyMap() {
        return Collections.unmodifiableMap(proxies);
    }
}

FieldProxy.java: (182 строки, 5711 байт)

public class FieldProxy<T> implements ProbabilityKnowledge<T> {

    private static int minK(int N, int K, int n) {
        // If all fields in group are neighbors to this field then all mines must be neighbors to this field as well
        return (N == K) ? n : 0;
    }

    private double[] detailedCombinations;
    private double[] detailedProbabilities;
    private final T field;
    private int found;
    private final FieldGroup<T> group;
    private final GroupValues<T> neighbors;

    public FieldProxy(FieldGroup<T> group, T field) {
        this.field = field;
        this.neighbors = new GroupValues<T>();
        this.group = group;
        this.found = 0;
    }

    void addSolution(Solution<T> solution) {
        recursiveRemove(solution.copyWithoutNCRData(), 1, 0);
    }

    /**
     * This field has the same values as another field, copy the values.
     * 
     * @param copyFrom {@link FieldProxy} to copy from
     * @param analyzeTotal Total number of combinations
     */
    void copyFromOther(FieldProxy<T> copyFrom, double analyzeTotal) {
        for (int i = 0; i < this.detailedCombinations.length - this.found; i++) {
            if (copyFrom.detailedCombinations.length <= i + copyFrom.found) {
                break;
            }
            this.detailedCombinations[i + this.found] = copyFrom.detailedCombinations[i + copyFrom.found];
        }

        this.finalCalculation(analyzeTotal);
    }

    /**
     * Calculate final probabilities from the combinations information
     * 
     * @param analyzeTotal Total number of combinations
     */
    void finalCalculation(double analyzeTotal) {
        this.detailedProbabilities = new double[this.detailedCombinations.length];
        for (int i = 0; i < this.detailedProbabilities.length; i++) {
            this.detailedProbabilities[i] = this.detailedCombinations[i] / analyzeTotal;
        }
    }

    /**
     * Setup the neighbors for this field
     * 
     * @param neighborStrategy {@link NeighborFind} strategy
     * @param proxyProvider Interface to get the related proxies
     */
    void fixNeighbors(NeighborFind<T> neighborStrategy, ProxyProvider<T> proxyProvider) {
        Collection<T> realNeighbors = neighborStrategy.getNeighborsFor(field);
        this.detailedCombinations = new double[realNeighbors.size() + 1];
        for (T neighbor : realNeighbors) {
            if (neighborStrategy.isFoundAndisMine(neighbor)) {
                this.found++;
                continue; // A found mine is not, and should not be, in a fieldproxy
            }

            FieldProxy<T> proxy = proxyProvider.getProxyFor(neighbor);
            if (proxy == null) {
                continue;
            }

            FieldGroup<T> neighborGroup = proxy.group;
            if (neighborGroup != null) {
                // Ignore zero-probability neighborGroups
                if (neighborGroup.getProbability() == 0) {
                    continue;
                }

                // Increase the number of neighbors
                Integer currentNeighborAmount = neighbors.get(neighborGroup);
                if (currentNeighborAmount == null) {
                    neighbors.put(neighborGroup, 1);
                }
                else neighbors.put(neighborGroup, currentNeighborAmount + 1);
            }
        }
    }

    @Override
    public T getField() {
        return this.field;
    }

    @Override
    public FieldGroup<T> getFieldGroup() {
        return this.group;
    }

    @Override
    public int getFound() {
        return this.found;
    }

    @Override
    public double getMineProbability() {
        return this.group.getProbability();
    }

    @Override
    public GroupValues<T> getNeighbors() {
        return this.neighbors;
    }

    @Override
    public double[] getProbabilities() {
        return this.detailedProbabilities;
    }

    private void recursiveRemove(Solution<T> solution, double combinations, int mines) {
        if (Thread.interrupted()) {
            throw new RuntimeTimeoutException();
        }

        // Check if there are more field groups with values
        GroupValues<T> remaining = solution.getSetGroupValues();
        if (remaining.isEmpty()) {
            this.detailedCombinations[mines + this.found] += combinations;
            return;
        }

        // Get the first assignment
        Entry<FieldGroup<T>, Integer> fieldGroupAssignment = remaining.entrySet().iterator().next();
        FieldGroup<T> group = fieldGroupAssignment.getKey();
        remaining.remove(group);
        solution = Solution.createSolution(remaining);

        // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
        int N = group.size();
        int n = fieldGroupAssignment.getValue();
        Integer K = this.neighbors.get(group);
        if (this.group == group) {
            N--; // Always exclude self becuase you can't be neighbor to yourself
        }

        if (K == null) {
            // This field does not have any neighbors to that group.
            recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines);
            return;
        }

        // Calculate the values and then calculate for the next group
        int maxLoop = Math.min(K, n);
        for (int k = minK(N, K, n); k <= maxLoop; k++) {
            double thisCombinations = Combinatorics.NNKK(N, n, K, k);
            recursiveRemove(solution, combinations * thisCombinations, mines + k);
        }
    }

    @Override
    public String toString() {
        return "Proxy(" + this.field.toString() + ")"
                + "\n neighbors: " + this.neighbors.toString()
                + "\n group: " + this.group.toString()
                + "\n Mine prob " + this.group.getProbability() + " Numbers: " + Arrays.toString(this.detailedProbabilities);
    }
}

NeighborFind.java: (30 строк, 718 байт)

/**
 * Interface strategy for performing a {@link DetailAnalyze}
 * 
 * @author Simon Forsberg
 *
 * @param <T> The field type
 */
public interface NeighborFind<T> {
    /**
     * Retrieve the neighbors for a specific field.
     * 
     * @param field Field to retrieve the neighbors for
     * 
     * @return A {@link Collection} of the neighbors that the specified field has
     */
    Collection<T> getNeighborsFor(T field);

    /**
     * Determine if a field is a found mine or not
     * 
     * @param field Field to check
     * 
     * @return True if the field is a found mine, false otherwise
     */
    boolean isFoundAndisMine(T field);
}

ProbabilityKnowledge.java: (39 строк, 1031 байт)

public interface ProbabilityKnowledge<T> {

    /**
     * @return The field that this object has stored the probabilities for
     */
    T getField();

    /**
     * @return The {@link FieldGroup} for the field returned by {@link #getField()}
     */
    FieldGroup<T> getFieldGroup();

    /**
     * @return How many mines has already been found for this field
     */
    int getFound();

    /**
     * @return The mine probability for the {@link FieldGroup} returned by {@link #getFieldGroup()}
     */
    double getMineProbability();

    /**
     * @return {@link GroupValues} object for what neighbors the field returned by {@link #getField()} has
     */
    GroupValues<T> getNeighbors();

    /**
     * @return The array of the probabilities for what number this field has. The sum of this array + the value of {@link #getMineProbability()} will be 1.
     */
    double[] getProbabilities();

}

ProxyProvider.java: (7 строк, 132 байта)

public interface ProxyProvider<T> {

    FieldProxy<T> getProxyFor(T field);

}

Использование /Тест

Доступно в Github: https://github.com/Zomis/Minesweeper-Analyze/blob/master/src/test/java/net/zomis/minesweeper/analyze/DetailAnalyzeTest.java

Чтобы просмотреть результаты анализа в действии, выполните следующие действия:

Элемент popup покажет подробные вероятности для этого поля.

Вопросы

В порядке важности:

  1. Есть ли другая реализация этого? Есть ли там существующие библиотеки?
  2. Любые общие комментарии приветствуются об этом коде и /или таком подходе
  3. Можно ли сделать еще быстрее? (за исключением некоторых оптимизаций, я сомневаюсь в этом сам, но мне действительно понравилось бы, если бы оно могло быть значительно улучшено)
30 голосов | спросил Simon Forsberg 9 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 09 Sep 2014 15:02:14 +0400 2014, 15:02:14

3 ответа


11

@Pimgd были определенно на что-то большое в последней части ответа, но не на это достаточно. Простое изменение Solution<T> на GroupValues<T> не помогло.

Однако, что помогло , заключается в использовании List<Entry<FieldGroup<T>, Integer>> (как уродливое, как выглядит это объявление типа) , И итерации через Список без изменения чего-либо .

Оказывается, что только это изменение сделало код NINE (9) до TEN (10) раз быстрее .

Новый метод выглядит следующим образом:

private void recursiveRemove(List<Entry<FieldGroup<T>, Integer>> solution, double combinations, int mines, int listIndex) {
    if (Thread.interrupted()) {
        throw new RuntimeTimeoutException();
    }

    // Check if there are more field groups with values
    if (listIndex >= solution.size()) {
        // TODO: or if combinations equals zero ?
        this.detailedCombinations[mines + this.found] += combinations;
        return;
    }

    // Get the assignment
    Entry<FieldGroup<T>, Integer> fieldGroupAssignment = solution.get(listIndex);
    FieldGroup<T> group = fieldGroupAssignment.getKey();

    // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
    int N = group.size();
    int n = fieldGroupAssignment.getValue();
    Integer K = this.neighbors.get(group);
    if (this.group == group) {
        N--; // Always exclude self becuase you can't be neighbor to yourself
    }

    if (K == null) {
        // This field does not have any neighbors to that group.
        recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines, listIndex + 1);
        return;
    }

    // Calculate the values and then calculate for the next group
    int maxLoop = Math.min(K, n);
    for (int k = minK(N, K, n); k <= maxLoop; k++) {
        double thisCombinations = Combinatorics.NNKK(N, n, K, k);
        recursiveRemove(solution, combinations * thisCombinations, mines + k, listIndex + 1);
    }
}

И вызывается вот так:

recursiveRemove(new ArrayList<Entry<FieldGroup<T>, Integer>>(solution.copyWithoutNCRData().getSetGroupValues().entrySet()), 1, 0, 0);

Итерация вместо непрерывного копирования и модификации. Почему я раньше не думал об этом?

Это означает, что этот большой анализ на Супербор смерти теперь сделан примерно через 3,5 минуты вместо 35 минут!

ответил Simon Forsberg 13 SatEurope/Moscow2014-12-13T03:57:00+03:00Europe/Moscow12bEurope/MoscowSat, 13 Dec 2014 03:57:00 +0300 2014, 03:57:00
13

Фокусировка на оптимизации:

в GroupValues:

@Override
public int hashCode() {
    if (bufferedHash != 0) {
        return this.bufferedHash;
    }

    int result = super.hashCode();
    this.bufferedHash = result;
    return result;
}

к

@Override
public int hashCode() {
    if (bufferedHash == 0) {
        this.bufferedHash = super.hashCode();
    }

    return this.bufferedHash;
}

1 локальный магазин удален. Точка выхода может помочь как-то.


В DetailAnalyse:

Map<GroupValues<T>, FieldProxy<T>> bufferedValues = new HashMap<GroupValues<T>, FieldProxy<T>>();

bufferedValues может быть final.


В FieldProxy:

for (int i = 0; i < this.detailedCombinations.length - this.found; i++) {
    if (copyFrom.detailedCombinations.length <= i + copyFrom.found) {
        break;

упрощена

for (int i = 0; i < a - b; i++) {
    if (a2 <= i + b2) {
        break;

мы можем назначить iMax Math.min(a - b, a2 - b2)

Это сохраняет постоянную переоценку постоянных значений:

final int iMax = Math.min(this.detailedCombinations.length - this.found, copyFrom.detailedCombinations.length - copyFrom.found);
for (int i = 0; i < iMax; i++) {

Скорее всего, это быстрее (никто не знает с микрооптимизацией, когда вы просто смотрите на код, профилирование работает лучше в этих случаях).

Новый фрагмент:

final int iMax = Math.min(this.detailedCombinations.length - this.found, copyFrom.detailedCombinations.length - copyFrom.found);
for (int i = 0; i < iMax; i++) {
    this.detailedCombinations[i + this.found] = copyFrom.detailedCombinations[i + copyFrom.found];
}

Я рекомендую запускать тесты с вызовом System.arrayCopy, заменяющим цикл for for.

System.arrayCopy(copyFrom.detailedCombinations, copyFrom.found, this.detailedCombinations, this.found, Math.min(this.detailedCombinations.length - this.found, copyFrom.detailedCombinations.length - copyFrom.found));

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


Опять же, FieldProxy:

private void recursiveRemove(Solution<T> solution, double combinations, int mines) {
    if (Thread.interrupted()) {
        throw new RuntimeTimeoutException();
    }

    // Check if there are more field groups with values
    GroupValues<T> remaining = solution.getSetGroupValues();
    if (remaining.isEmpty()) {
        this.detailedCombinations[mines + this.found] += combinations;
        return;
    }

    // Get the first assignment
    Entry<FieldGroup<T>, Integer> fieldGroupAssignment = remaining.entrySet().iterator().next();
    FieldGroup<T> group = fieldGroupAssignment.getKey();
    remaining.remove(group);
    solution = Solution.createSolution(remaining);

    // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
    int N = group.size();
    int n = fieldGroupAssignment.getValue();
    Integer K = this.neighbors.get(group);
    if (this.group == group) {
        N--; // Always exclude self becuase you can't be neighbor to yourself
    }

    if (K == null) {
        // This field does not have any neighbors to that group.
        recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines);
        return;
    }

    // Calculate the values and then calculate for the next group
    int maxLoop = Math.min(K, n);
    for (int k = minK(N, K, n); k <= maxLoop; k++) {
        double thisCombinations = Combinatorics.NNKK(N, n, K, k);
        recursiveRemove(solution, combinations * thisCombinations, mines + k);
    }
}

CTRL + F solution:

1. private void recursiveRemove(Solution<T> solution, double combinations, int mines) {
2. GroupValues<T> remaining = solution.getSetGroupValues();
3. solution = Solution.createSolution(remaining);
4. recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines);
5. recursiveRemove(solution, combinations * thisCombinations, mines + k);

Solution используется только в заголовке функции, чтобы получить значения группы и передать ее обратно в функцию. Он также построен один раз ...

Изменяет ли это значения группы?

public static <T> Solution<T> createSolution(GroupValues<T> values) {
    return new Solution<T>(values).nCrPerform();
}

вызовы

private Solution(GroupValues<T> values) {
    this.setGroupValues = values;
}

, а затем

private Solution<T> nCrPerform() {
    double result = 1;
    for (Entry<FieldGroup<T>, Integer> ee : this.setGroupValues.entrySet()) {
        result = result * Combinatorics.nCr(ee.getKey().size(), ee.getValue());
    }
    this.nCrValue = result;
    return this;
}

, который вызывает

public static double nCr(int n, int r) {
    if (r > n || r < 0) {
        return 0;
    }
    if (r == 0 || r == n) {
        return 1;
    }

    double value = 1;

    for (int i = 0; i < r; i++) {
        value = value * (n - i) / (r - i);
    }

    return value;
}

И там цепь заканчивается.

Таким образом, он не изменяет значения группы.

Следующее изменение приведет к повышению производительности:

Замените старую версию функции

private void recursiveRemove(Solution<T> solution, double combinations, int mines) {
    if (Thread.interrupted()) {
        throw new RuntimeTimeoutException();
    }

    // Check if there are more field groups with values
    GroupValues<T> remaining = solution.getSetGroupValues();
    if (remaining.isEmpty()) {
        this.detailedCombinations[mines + this.found] += combinations;
        return;
    }

    // Get the first assignment
    Entry<FieldGroup<T>, Integer> fieldGroupAssignment = remaining.entrySet().iterator().next();
    FieldGroup<T> group = fieldGroupAssignment.getKey();
    remaining.remove(group);
    solution = Solution.createSolution(remaining);

    // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
    int N = group.size();
    int n = fieldGroupAssignment.getValue();
    Integer K = this.neighbors.get(group);
    if (this.group == group) {
        N--; // Always exclude self becuase you can't be neighbor to yourself
    }

    if (K == null) {
        // This field does not have any neighbors to that group.
        recursiveRemove(solution, combinations * Combinatorics.nCr(N, n), mines);
        return;
    }

    // Calculate the values and then calculate for the next group
    int maxLoop = Math.min(K, n);
    for (int k = minK(N, K, n); k <= maxLoop; k++) {
        double thisCombinations = Combinatorics.NNKK(N, n, K, k);
        recursiveRemove(solution, combinations * thisCombinations, mines + k);
    }
}

с новым

private void recursiveRemove(GroupValues<T> remaining, double combinations, int mines) {
    if (Thread.interrupted()) {
        throw new RuntimeTimeoutException();
    }

    // Check if there are more field groups with values
    if (remaining.isEmpty()) {
        this.detailedCombinations[mines + this.found] += combinations;
        return;
    }

    remaining = new GroupValues<T>(remaining);

    // Get the first assignment
    Entry<FieldGroup<T>, Integer> fieldGroupAssignment = remaining.entrySet().iterator().next();
    FieldGroup<T> group = fieldGroupAssignment.getKey();
    remaining.remove(group);

    // Setup values for the hypergeometric distribution calculation. See http://en.wikipedia.org/wiki/Hypergeometric_distribution
    int N = group.size();
    int n = fieldGroupAssignment.getValue();
    Integer K = this.neighbors.get(group);
    if (this.group == group) {
        N--; // Always exclude self becuase you can't be neighbor to yourself
    }

    if (K == null) {
        // This field does not have any neighbors to that group.
        recursiveRemove(remaining, combinations * Combinatorics.nCr(N, n), mines);
        return;
    }

    // Calculate the values and then calculate for the next group
    int maxLoop = Math.min(K, n);
    for (int k = minK(N, K, n); k <= maxLoop; k++) {
        double thisCombinations = Combinatorics.NNKK(N, n, K, k);
        recursiveRemove(remaining, combinations * thisCombinations, mines + k);
    }
}

Это должно дать хороший импульс производительности. Интересно, все ли время от времени?


Кроме того, из-за недавнего смущения я предлагаю вам переименовать Solution.getSetGroupValues() в Solution.getCopyOfGroupValues() или что-то подобное. Это вызвало ошибку при более раннем пересмотре моего ответа.

ответил Pimgd 1 MonEurope/Moscow2014-12-01T16:19:24+03:00Europe/Moscow12bEurope/MoscowMon, 01 Dec 2014 16:19:24 +0300 2014, 16:19:24
5

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

Итак, я предлагаю разработать какой-то метод Монтекарло. По вашему предыдущему вопросу я понимаю, что у вас есть полное представление о том, как перечислять все решения, каждый из которых имеет свою точную вероятность: вы просто произвольно распределяете мины на каждой полевой группе. Таким образом, вы можете написать алгоритм для получения случайного решения с равной вероятностью среди всех возможных решений.

Если это сделано, метод Монтекарло прост: произвольно выберем N решений и вычислим полученные значения для ваших случайных величин (т. е. количество мин в соседнем поле) и оцените вероятность с отношением: positive_cases /total_cases.

Хорошим моментом в этом является то, что вы можете одновременно оценивать все позиции с одинаковыми случайными выборками. Также вы можете решить, сколько времени потратить на вычисление: чем больше времени вы потратите, тем приблизительные результаты.

ответил Emanuele Paolini 9 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 09 Sep 2014 16:27:20 +0400 2014, 16:27:20

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132