Brute force deep analysis - DavidNHill/Minesweeper GitHub Wiki

Brute force deep analysis is the process of playing out every possible move in every possible order to determine the path which gives the best chance of winning.

The input required is the complete list of candidate solutions generated by the Brute force process. Due to performance concerns this process only runs if there is less than 4,000 candidate solutions remaining. It is therefore only of value in the end game.

The java class which performs this function can be found here

Processing overview

Using the candidate solutions calculate which tiles are alive.

For a living tile there are a maximum 9 possible values the tile can be, zero through 8. Each of these values represents a new Node one step closer to completing the game; Node(Tile=0), Node(Tile=1),... Node(Tile=8) and they have a corresponding probability P(Tile=0), P(Tile=1), ... P(Tile=8). Many of the probabilities will be zero, but at least 2 will be non-zero (or they wouldn't be living).

If we define P(Node, Tile) = probability of winning the game from position Node if tile Tile is clicked

Then P(Node) the probability of winning the game from position Node (with best play) is

P(Node) = Maximum [ P(Node, Tile) for each living tile Tile available at position Node]

Additionally, for a Node we can determine what the odds of winning the game is if we click a Tile:

P(Node, Tile) = Sum[ P(Tile=v) * P(Node(Tile=v)) ] for v = 0 to 8.

Combining these two equations we get the recursive relationship:

P(Node, Tile) = Sum[ P(Tile=v) * Maximum [ P(Node(Tile=v), Tile1) for each living tile Tile1 available at position Node(Tile=v)] ] for v = 0 to 8.

The recursion ends when either

The number of candidate solutions remaining is 1, in which case P(Node) = 1
The number of living nodes is zero, in which case P(Node) = 1 / (number of candidate solutions)

Efficiency optimisations

Walking the tree

Building the tree is an expensive operation but once done no further processing is required. You can now walk down the tree playing the best move and branching depending on what value is revealed.

Sorting the living locations

When the living locations have been identified they can be sorted by the probability there is not a mine there. In practice this is the same as sorting by the number of candidate solutions which has a mine at that location. By prioritising the order you look at the living positions you make the pruning more efficient.

Pruning the tree

For each Node, if a branch of the tree can no longer be better then the current best branch then processing down it can be stopped.

Consider a node with at least two living locations. The first living location has to be explored and it returns a 77% chance to win. When we explore the next living location it has 3 possible values; a mine 10%, a '3' 70% and a '4' 20%. We explore the '3' branch and discover a 80% to win from here. If we assume that the '4' branch will win 100% of the time then the best win% we could have down this path is (0.7 * 0.8) + (0.2 * 1) = 0.76 = 76%. So even before we have processed the '4' branch we can see that we can never do better than the 77% chance we have already got. We can safely stop processing this branch knowing we haven't missed the best solution.

Pruning makes a massive difference to the processing speed.

Caching the nodes

Caching the nodes seems to offer an improvement. If you have calculated P(NODE) = x then if you arrive at the same NODE again, but by a different sequence of moves, you don't have to recalculate that branch.

Autoplay safe moves

If a living tile is 100% safe (No mine at this location for all candidate solutions) then don't bother checking any other branches. Since you can't die from playing here it can't affect your chances of winning the game. This helps reduce the number of living tiles considered going forward.

Pseudo code for recursive procedure

(probably needs work)

`process(Node parent, Living tile, Decimal cutoff) {

    result = 0;  // 

    useCutoff = cutoff;

    Node[] children = parent.getChildren(tile);  // get the possible nodes when playing tile

    int notMines = parent.getSolutionSize() - parentAlive.mines;

    for (Node child: parentAlive.children) {

        if (child == null) {
            continue;  // continue the loop but ignore this entry
        }

        // this is the maximum prob that this move can yield, i.e. if everything else left in the loop is 100%
        Decimal maxProb = result + ( notMines / parent.getSolutionSize() ) 

        // if the max probability is less than the current cutoff then no point doing the analysis
        if (maxProb <= useCutoff) {
            parentAlive.pruned = true;
            return result;
        }

        Decimal best = 0;
        if (child.getSolutionSize() == 1) {
            best = BigDecimal.ONE;   // if only one solution left then we have solved it
        } else if (child.getLivingLocations().isEmpty()) {
            best = 1 / child.getSolutionSize() // no further information ==> all solution indistinguishable
        } else {
            for (Living alive: child.getLivingLocations()) {

                Decimal prob = process(child, alive, best);  // the recursive bit 

                if (best < prob){
                    best = prob;
                    child.bestLiving = alive;
                }
                // if there are no mines then this is a 100% certain move, so skip any further analysis
                if (alive.mines == 0) {
                    break;
                }
            }
        }
        
        Decimal work = best * child.getSolutionSize() /  parent.getSolutionSize()

        // store the best probability available at this node
        child.probability = best;

        result = result.add(work);	
        notMines = notMines - child.getSolutionSize();  // reduce the number of not mines

    }

    parentAlive.probability = result;

     return result;

}