Advanced and Detailed Minesweeper Probabilities

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:

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 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 gr

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, FieldProxy> bufferedValues = new HashMap, FieldProxy>();

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 solution, double combinations, int mines) {
    if (Thread.interrupted()) {
        throw new RuntimeTimeoutException();
    }

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

    // Get the first assignment
    Entry, Integer> fieldGroupAssignment = remaining.entrySet().iterator().next();
    FieldGroup 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 solution, double combinations, int mines) {
2. GroupValues 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  Solution createSolution(GroupValues values) {
    return new Solution(values).nCrPerform();
}

calls

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

and then

private Solution nCrPerform() {
    double result = 1;
    for (Entry, 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 alte

StackExchange Code Review Q#62383, answer score: 16