31
\$\begingroup\$

In an earlier question, I showed my code for calculating the mine probability for each and every field in a Minesweeper board. But it doesn't stop there. In that very same Minesweeper Analyze project, there is also an algorithm for calculating the probability of each and every number for each and every field.

Motivation

In the multiplayer version of Minesweeper called Minesweeper Flags, you have to be careful not to reveal too much information to your opponent. This is often what separates a good player from a bad inexperienced player. If there is a 80% chance of being a mine, but a 20% chance of revealing an open field (which could potentially reveal 10 obvious mines to your opponent), would you take the risk? Calculation of Expected Value (which is an entirely different topic in itself) tells us that it is probably a bad idea.

Description

Consider this 8x7 Minesweeper board with a total of 6 mines:

8x7 Minesweeper board with the 1-3 sequence in the middle

When grouping the fields into FieldGroups (see previous question for a definition of field group), we find that there is:

  • 3 fields only connect to the 1 (b)
  • 4 fields connected to both 1 and 3 (c)
  • 3 fields only connected to the 3 (d)
  • 44 fields connected to neither (a)

The same map organized into field groups

When performing a mine-probability analyze on this board, we find that there are two Solution groups:

  • 4c = 1, 44a = 3, 3b = 0, 3d = 2, 158928 combinations (4 fields in group c should have one mine, 44 fields in group a should have 3 mines, etc.)
  • 4c = 0, 44a = 2, 3b = 1, 3d = 3, 2838 combinations

Now, what is the probability for the number '2' directly above the '1'? Let's call the field above the 1 as x. It would be possible to calculate that by adding a FieldRule to the existing board for the neighbors of x (2a + 3d + 1b = 2), and a rule for that field not being a mine (x = 0). But if we were to do this for each and every field on the board, it would take quite a lot of time. Not to mention that we have to do it for each and every number (0-8).

So, we can group the fields into probability-groups by which field groups they are neighboring to:

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

As per the above 'diagram', the probability group k is where our field x belongs, it is neighboring the Field Groups 3*a, 2*b, 1*c. This information can be stored in the GroupValues structure that was introduced in the previous question, it is essentially a Map<FieldGroup, Integer>. To improve the lookup speed of it, it's hashCode value is stored once it is calculated for the first time, for better performance.

We can see that there are actually two k's on the probability groups map, so we gain some performance by grouping them together as they will have the same detailed probabilities. There are also 22 b's on the map so there's a lot of performance we gain there by having them share probabilities. Note that all fields in probability group b is neighboring 5 of FieldGroup a

Calculating the detailed probabilities for a Probability Group

Let's focus on this solution for now: 4c = 1, 44a = 3, 3b = 0, 3d = 2, 158928 combinations

We know that the x field (in probability group k) has these neighbors: 3*a, 2*b, 1*c.

First we deal with 1c (because that's what the Eclipse debugger chose). Either that specific neighbor has a mine, or it does not. Let's say that it does not have a mine. Then there are 2 combinations, as there are two c fields away from field x, and one of them must have a mine.

Secondly, 3a. The a group has 44 fields in total, and in this solution should have 3 mines. This field is neighbor to 3 of those fields. Let's say that 1 of those neighbors are a mine, then there's (according to hypergeometric distribution) \$\binom{3}{1}*\binom{44 - 3}{3 - 1} = 2460\$ combinations.

Then, the neighbors 2b. We know from our solution though that there are no mines in b, so that's an easy one: One combination.

We're not neighbor with any d's so there's 3 combinations for them (3 fields, 2 mines).

So, for no mines in c, one mine in a and no mines in b, there are a total of one mines, and \$2 * 2460 * 1 * 3 = 14760\$ combinations. As there is currently no found mine around the x field we add 14760 to the combinations for our field x to be a 1.

This is done for all possible variations of how many mines is in each group. Once all the neighbor-groups and solutions has been processed, it is divided by the total number of combinations for the entire map to get the actual probabilities.

In the end, we get this double[] for the number probabilities for our field x: [0.4004549781783564, 0.2998343285980985, 0.05172285894440117, 0.0023552538852416455, 1.854530618300508E-5, 0.0, 0.0, 0.0, 0.0]

That is, 40% risk of being open field, 29.9% chance for a 1, 5.1% for a 2, etc...

Speed reflection

There's one iteration over probability groups, one for solutions, and one for the neighboring FieldGroups, and then one recursive loop for a specific assignment. So it's something like \$O(probabilityGroups * solutions * K^{neighboringGroups})\$ Additionally, there's also some calculation of the actual combinations involved, using the binomial coefficient and hypergeometric distribution.

This causes huge performance issues when having many solutions, many field groups, and/or many probability groups - such as in The Super board of death, causing such boards to be left practically unsolved as it would take too much time to solve them. Luckily though, such situations rarely happen. When a bot is using this algorithm to play the bot simplifies the analyze required when taking mines. And in other occasions where this algorithm is used, it is mostly used to analyze games where the players are somewhat smart so the game rarely becomes too complex. And besides... this algorithm is faster than all other algorithms/approaches I know of.

Typical values:

  • Field Groups tend to be between 10 - 50, in some rare cases up to 100.
  • Solution Groups tend to be between 2 - 50, in some games where two bad players are playing each other, it can easily go up to 1500 (and beyond).
  • Probability Groups tend to be around 50, in some cases up to 100.

This algorithm timeouts when these values get too big.

As games are played on a 16x16 board (at the moment at least, might support bigger in the future), the absolute maximum for Field Groups and Probability Groups is 256. For Solution Groups, there is no known maximum as games with a large amount of solution groups take too long to analyze even with 'simple' analyze (mine probabilities only).

Class Summary (7 files)

  • DetailAnalyze: Entry-point, containing one static method to perform the analyze
  • DetailedResults: interface for accessing the results
  • DetailedResultsImpl: Implementation of the above interface
  • FieldProxy: Container for the detailed probabilities for a single field
  • NeighborFind: Interface to perform checking for neighbors and determining the current known mines around a field
  • ProbabilityKnowledge: The public interface of the FieldProxy class
  • ProxyProvider: Interface used while creating the results to access the data of other fields

Dependencies

AnalyzeResult, Combinatorics, FieldGroup, GroupValues, RuntimeTimeoutException, Solution from the other parts of my Minesweeper Analyze project

Code

The code is using Java 6, and can be found in my Minesweeper Analyze github repository

First of all, modified version of 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();
    }

}

Then, the rest of the code:

DetailAnalyze.java: (62 lines, 2139 bytes)

/**
 * 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);
    }
}

DetailedResults.java: (46 lines, 1162 bytes)

/**
 * 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();

}

DetailedResultsImpl.java: (46 lines, 1211 bytes)

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 lines, 5711 bytes)

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 lines, 718 bytes)

/**
 * 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 lines, 1031 bytes)

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 lines, 132 bytes)

public interface ProxyProvider<T> {

    FieldProxy<T> getProxyFor(T field);

}

Usage / Test

Available on Github: https://github.com/Zomis/Minesweeper-Analyze/blob/master/src/test/java/net/zomis/minesweeper/analyze/DetailAnalyzeTest.java

To see results of analyze in action, follow these steps:

A popup element will show the detailed probabilities for that field.

Questions

In order of importance:

  1. Does another implementation of this exist? Are there any existing libraries out there?
  2. Any general comments welcome about this code and/or this approach
  3. Can it be made even faster? (except for some optimizations, I doubt it myself, but I would really love it if it could be improved significantly)
\$\endgroup\$
14
\$\begingroup\$

Focusing on optimizations:

in GroupValues:

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

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

to

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

    return this.bufferedHash;
}

1 local store removed. Single exit point may help somehow.


In DetailAnalyse:

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

bufferedValues may be final.


In FieldProxy:

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

simplified

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

we can assign iMax to be Math.min(a - b, a2 - b2)

This saves constant re-evaluation of constant values:

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

It's most likely faster (one never knows with micro optimizations when one just looks at the code, profiling works better in these cases).

New snippet:

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];
}

I recommend running tests with a System.arrayCopy call replacing the whole for loop.

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

Maybe it's faster because it does a whole block in one go. Maybe it's slower because a whole native call for copying a few items is adding a lot of overhead. Do the profiling and find out.


Again, 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);

The Solution is only used in the function header, to get the group values, and to pass it back in the function. It's also constructed once...

Does this alter the group values?

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

calls

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

and then

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;
}

which calls

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;
}

And there the chain ends.

So it does not alter the group values.

The following change will thus give a performance boost:

Replace the old version of the function

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);
    }
}

with the new

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);
    }
}

This should give a nice boost in performance. I wonder whether it still times out?


Additionally, due to a recent confusing, I suggest you rename Solution.getSetGroupValues() to Solution.getCopyOfGroupValues() or something of the like. It's what caused the bug in an earlier revision of my answer.

\$\endgroup\$
  • \$\begingroup\$ In general native calls are usually faster than non-native calls since they don't run through the JIT. Maybe enough runs get the hotspot optimizations to kick in, but usually native code is faster than the java-bytecode, simply because of the translation inaccuracies... \$\endgroup\$ – Vogel612 Dec 1 '14 at 13:46
11
\$\begingroup\$

@Pimgd were definitely on to something big in the last part of the answer, but not on to it enough. Simply changing Solution<T> to GroupValues<T> did not help much.

However, what certainly did help, is to use a List<Entry<FieldGroup<T>, Integer>> (as ugly as that type declaration looks). And to iterate through the List without modifying anything.

It turns out that this change alone made the code NINE (9) to TEN (10) times faster.

The new method is like this:

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);
    }
}

And called like this:

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

Iterating instead of continuously copying and modifying. Why on earth did I not think of this before?

This means that doing this big analyze on The super board of death is now done in about 3.5 minutes instead of 35 minutes!!

\$\endgroup\$
6
\$\begingroup\$

For your use case (an AI for playing minesweeper) it could be more appropriate to have an approximate fast algorithm instead of an exact but slow one.

So I will suggest to develop some sort of Montecarlo method. By your previous question I understand that you have a complete understanding on how to enumerate all solutions each with its exact probability: you just distribute the mines randomly on every FieldGroup. So you are in the position to write an algorithm to extract a random solution with equal probability among all possible solutions.

If this is done, Montecarlo method is straightforward: extract N solutions at random and compute the resulting values for your random variables (i.e. the number of mines in the neighbour of a field) and estimate the probability with the ratio: positive_cases / total_cases.

The good point about this, is that you can evaluate all positions at the same time with the same random samples. Also you can decide how much time to spend on the computation: the more time you spend the better are the approximated results.

\$\endgroup\$
  • \$\begingroup\$ I appreciate your suggestion, when a timeout is likely to happen (because of big amount of solutions/field groups/probability groups), that approach can be taken. But in 9999 cases of 10000, this approach is efficient enough. \$\endgroup\$ – Simon Forsberg Sep 9 '14 at 14:09
  • \$\begingroup\$ As I now have managed to improve the speed by nine times, it is even less likely that I would use a Monte Carlo method. \$\endgroup\$ – Simon Forsberg Dec 15 '14 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.