2 ms·

> Each of these 11 configurations should be equally likely to be the actual position. This is not true. For calculating the odds of a configuration you need to

> Each of these 11 configurations should be equally likely to be the actual position. This is not true. For calculating the odds of a configuration you need to take into account the non-border squares and the number of the remaining mines too. Example (3 remaining mines): 1111 *22* xxxx xxxx The * represents the marked mines, 'x' represents the unmarked squares. There are three border configurations: 1. mine, empty, empty, mine 2. empty, mine, empty, empty 3. empty, empty, mine, empty But actually the first one is actually is 4 global configurations, as the remaining one mine can be anywhere on the remaining squares. The second and third are 6 and 6 global configurations respectively as the remaining two mines can be anywhere on the remaining 4 squares (4 choose 2). The probabilities of a border squares to be empty are 3/4, 5/8, 5/8 and 3/4 respectively as opposed to 2/3, 2/3, 2/3 and 2/3 that your rule gives. The probability for a non-border square to be empty is 9/16, slightly more than 1/2. One can argue that when the number of the remaining unmarked squares is large compared to the border squares this gives little difference. But it's not true, this gives significant differences even when this is the case. [1] http://nothings.org/games/minesweeper/ http://nothings.org/games/minesweeper/ "Counting unencountered mines"

luckyt 9y ago
That's a fair objection. You can view my rule as a heuristic that's easy to compute and gives good guesses in most situations, rather than calculating the mathematically correct probability. My AI does actually account for this, but only in the endgame when there are a small number of squares left -- then it considers the global configuration instead of just local. This works out because the endgame is where this problem is the most significant, it's computationally expensive unless there's a small number of squares remaining.
- leni536 9y ago
  Then I suggest an improved heuristics for mid-game. You can actually calculate the number of global configurations for each border configuration, they are just (n choose k) type calculations. It's somewhat more sophisticated when there are multiple disjoint border regions. Alternatively for a mid-game heuristic you can approximate the initial uniform distribution of the fixed amount of mines on the playing field with another distribution: Each square having an independent probability of having a mine or not. This could potentially simplify the calculation but it wouldn't be accurate when there are not so many mines left.
  - Someone 9y ago
    ”It's somewhat more sophisticated when there are multiple disjoint border regions.” I don’t see why that would be the case. Can you explain?
Someone 9y ago
That assumes those three border configurations are equally likely. In this case, I think that is true, but in general, I don’t think it is true that all possible border configurations are equally likely. For example, if you add a fifth row of xxxx to your example, ignoring what we know of the third row, the expected number of mines in each row would be one. That would make the first configuration, with two mines, less likely than each of the other two. Similarly, if, in your example, there are only 2 remaining mines, the first option is less likely, if there are 5 missing mines, the first is more likely, and if there are 6 missing mines, the second and third cannot happen. Things get even more complicated if one assumes the mines aren’t placed uniformly, for example because the programmer wants to avoid areas of the field completely separated by mines.

luckyt 9y ago

That's a fair objection. You can view my rule as a heuristic that's easy to compute and gives good guesses in most situations, rather than calculating the mathematically correct probability. My AI does actually account for this, but only in the endgame when there are a small number of squares left -- then it considers the global configuration instead of just local. This works out because the endgame is where this problem is the most significant, it's computationally expensive unless there's a small number of squares remaining.

leni536 9y ago
Then I suggest an improved heuristics for mid-game. You can actually calculate the number of global configurations for each border configuration, they are just (n choose k) type calculations. It's somewhat more sophisticated when there are multiple disjoint border regions. Alternatively for a mid-game heuristic you can approximate the initial uniform distribution of the fixed amount of mines on the playing field with another distribution: Each square having an independent probability of having a mine or not. This could potentially simplify the calculation but it wouldn't be accurate when there are not so many mines left.
- Someone 9y ago
  ”It's somewhat more sophisticated when there are multiple disjoint border regions.” I don’t see why that would be the case. Can you explain?

Someone 9y ago

That assumes those three border configurations are equally likely. In this case, I think that is true, but in general, I don’t think it is true that all possible border configurations are equally likely. For example, if you add a fifth row of xxxx to your example, ignoring what we know of the third row, the expected number of mines in each row would be one. That would make the first configuration, with two mines, less likely than each of the other two. Similarly, if, in your example, there are only 2 remaining mines, the first option is less likely, if there are 5 missing mines, the first is more likely, and if there are 6 missing mines, the second and third cannot happen. Things get even more complicated if one assumes the mines aren’t placed uniformly, for example because the programmer wants to avoid areas of the field completely separated by mines.