Analyzing Minesweeper Probabilities

Calculating probabilities in Minesweeper might sound like an easy task, but I've seen so many probability calculators that's either incorrect, horribly slow, or with ugly code (or all of them) so I have to share my code for this.

This code is used within my Minesweeper Flags online game by the AIs AI_Hard, AI_Extreme3 and AI_Nightmare.

This code is written in Java 6, but don't let that scare you away. It would not be too difficult to update to more modern Java versions.

So, how does it work?

Let's say this board has 6 mines. A simple approach would be to recursively place all 6 mines and count the number of combinations where each field has a mine. Although that would work for a small board like this, for a bigger board with the same pattern and 51 mines, that's not optimal.

So, what if you just place the mines around the 1 and the 3 and use combinatorics for the rest of the board where we don't have any clues? That would help with the bigger board with the same pattern, but what if you have plenty of clues distributed around the board like this, that's where things are starting to get too complex and too slow for most algorithms.

###My approach

I will explain my approach by guiding you through a manual calculation of the 4x4 example board above.

Board representation. This board can be represented like:

abcd
e13f
ghij
klmn

Rules. So we have a 1 and a 3 and we know there are 6 mines in total on the board. This can be represented as:

a+b+c+e+g+h+i = 1
b+c+h+i+d+f+j = 3
a+b+c+d+e+f+g+h+i+j+k+l+m+n = 6

This is what I call rules (the FieldRule class in my code)

Field Groups. By grouping fields into which rules they are in, it can be refactored into:

(a+e+g) + (b+c+h+i) = 1
(b+c+h+i) + (d+f+j) = 3
(a+e+g) + (b+c+h+i) + (d+f+j) + (k+l+m+n) = 6

These groups I call Field Groups (The FieldGroup class in the code)

The RootAnalyzeImpl class stores a collection of rules, and when it is getting solved it begins by splitting

GroupValues

GroupValues doesn't seem to serve much of a purpose beyond what you get from Map; it adds no functionality beyond an unused field. In practice, all I think it is achieving is obscuring what is actually going on.

FieldGroup

That you are extending ArrayList, rather than composing with it, is a code smell. I find myself looking at informAboutSolution. There's a calculation there that doesn't make any sense if the list is empty. Furthermore, because you are publicly a list, anybody can come along and remove all of your entries, or insert more entries, or do all manner of silliness that would screw up your calculation.

I think you should tease out the running tally aspect of what's going on here. At a minimum....

void informAboutSolution(int rValue, Solution solution, double total) {
    // codestyle: always use braces
    if (rValue == 0) {
        return;
    }
    double probabilityChange = solution.nCr() / total * rValue / fields.size();

    this.runningTally.update(probabilityChange);
}

This really needs better variable names - what are you really doing here? You are computing the probability that any cell in this group has a bomb, given a solution which allocates some number of bombs to the group.

class RunningTally {
    private double probability = 0;
    private int solutionsKnown = 0;

    public double getProbability() {
        return this.probability;
    }

    public int getSolutionsKnown() {
        return this.solutionsKnown;
    }

    public void update(double change) {
        probability += change;
        solutionsKnown++;
    }
}

void informAboutSolution(int bombsAllocated, Solution solution, double total) {
    // codestyle: always use braces
    if (bombsAllocated == 0) {
        return;
    }
    int cellsAvailable = fields.size();
    double probabilityBombed = bombsAllocated / cellsAvailable;
    double solutionPercentage = solution.nCr() / total;
    double probabilityChange = solutionPercentage * probabilityBombed;
    runningTally.update(probabilityChange);
}

Allocating objects and doing work together is a code smell -- not necessarily wrong, but definitely suspicious. If you are concerned enough with string concatenation to think that a StringBuilder is a good idea, it probably makes sense to allow multiple objects to share the same StringBuilder.

void writeTo(StringBuilder str) {
    final String START_OBJECT = "(";
    final String END_OBJECT = ")";
    final String SEPARATOR = " + ";

    str.append(START_OBJECT);

    if (fields.size() > 8) {
        str.append(fields.size());
        str.append(" FIELDS");
    } else {
        final int cursor = str.length();
        for (T field : fields) {
            // This is really a two state FSM...
            if (str.length() > cursor) {
                str.append(SEPARATOR);
            }

            str.append(field);
        }
    }
    str.append(END_OBJECT);
}

GameAnalyze

Don't care for the name much - class names are usually nouns, so maybe GameAnalyzer or GameAnalysis.

void solve() {
    if (Thread.interrupted())
        throw new RuntimeTimeoutException();

    if (!this.simplifyRules()) {
        return;
    }

    this.removeEmptyRules();
    this.solveRules();

    if (this.rules.isEmpty()) {
        callback.solved(Solution.createSolution(this.knownValues));
    }
}

Major props for checking for interruption. Because it's not obvious that solve() is recursive, it looks as though the interrupt check is in the wrong place. It might make more sense to put that check within solveRules.
I don't like cancelling the solve by throwing a runtime exception, and don't understand why you would choose to implement a unique RuntimeException for it at that. If you feel like you cannot throw a checked exception here, perhaps you should have a state object that various bits use to decide if they should continue processing.
It's not at all clear to me that Solution.createSolution is in the right place -- it seems more flexible to pass the known values to a callback that knows how to apply the solution.

One aspect of the recursive approach that I really don't like is you are missing the opportunity to solve positions in parallel. At a minimum, I would want to consider using a different core to create Solutions than to decompose the problem. Without profiling, it's difficult to say if this would make a difference, but your current approach doesn't support that refactoring. For example, consider a listener that takes knownValues; you could have one version that publishes solutions in line, and an alternative that puts the knownValues into a queue, where another thread will pick them up to convert them.

Solution

Solution is trying to be two different things at once - it's the calculator, and the solution. Those two bits should be teased apart, which will make everything that is going on in there much clearer.

The use of Random in `Solutio

StackExchange Code Review Q#54737, answer score: 32