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
cshould have one mine, 44 fields in groupashould 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
FieldProxyclass - 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:
- go to a random game on my Minesweeper Flags Stats page
- go to a random situation within that game
- click on the map
- click on the analyze link at the bottom
- then click on a random field on the map.
A popup element will show the detailed probabilities for that field.
Questions
In 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 approach
- 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)
