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.MotivationIn 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.DescriptionConsider this 8x7 Minesweeper board with a total of 6 mines: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)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 combinationsNow, 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           abbbbbbaAs 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 aCalculating the detailed probabilities for a Probability GroupLet's focus on this solution for now: 4c = 1, 44a = 3, 3b = 0, 3d = 2, 158928 combinationsWe 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 reflectionThere'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 analyzeDetailedResults: interface for accessing the resultsDetailedResultsImpl: Implementation of the above interfaceFieldProxy: Container for the detailed probabilities for a single fieldNeighborFind: Interface to perform checking for neighbors and determining the current known mines around a fieldProbabilityKnowledge: The public interface of the FieldProxy classProxyProvider: Interface used while creating the results to access the data of other fieldsDependenciesAnalyzeResult, Combinatorics, FieldGroup, GroupValues, RuntimeTimeoutException, Solution from the other parts of my Minesweeper Analyze projectCodeThe code is using Java 6, and can be found in my Minesweeper Analyze github repositoryFirst of all, modified version of GroupValuespublic 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 / TestAvailable on Github: https://github.com/Zomis/Minesweeper-Analyze/blob/master/src/test/java/net/zomis/minesweeper/analyze/DetailAnalyzeTest.javaTo see results of analyze in action, follow these steps:go to a random game on my Minesweeper Flags Stats pagego to a random situation within that gameclick on the mapclick on the analyze link at the bottomthen click on a random field on the map.A popup element will show the detailed probabilities for that field.QuestionsIn order of importance:Does another implementation of this exist? Are there any existing libraries out there?Any general comments welcome about this code and/or this approachCan 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)
Advanced and Detailed Minesweeper Probabilities
java;algorithm;combinatorics;minesweeper
@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!!