Calculating probabilities

[kedaman]

You all know the game minesweeper i guess so i don't have to explain the rules?
I have 4 mines in this area:

----
-1--
----
-1--
----
----

And made a tester and found the approximative chance of hiting a mine at each square:

172‰ 173‰ 173‰ 236‰
173‰   0‰ 173‰ 239‰
 44‰  44‰  44‰ 237‰
173‰   0‰ 173‰ 237‰
173‰ 173‰ 174‰ 238‰
236‰ 237‰ 237‰ 237‰

If you add them up you get 4, the amount of mines, also there are 4 areas with different chances of hitting a mine:

AAAD
ABAD
CCCD
ABAD
AAAD
DDDD

where each areas chance is
A:172‰
B:0‰
C:44‰
D:237‰

How do you do this mathematically?

[kedaman]

I knew this would be tough but not that tough!!!

[Sam Finch]

I don't think anyone knows what the question is, That reminds me. Ked, what's the question?

[paulw]

How did you calculate them in the first place? Iteration - simply express mathematically and use symmetry to reduce the workload.

Cheers,

P.

PS Don't iterate through 1/0 - your loop might only tend to infinity but you'll wait for ever...

Only joshin'

P.

[kedaman]

If that last line wasn't clear enough, then hmm, i have be more specific..

I want to calculate the probability of hitting a mine for each single tile in the minefield.

Well, and if you don't know the rules:
- The field has a known amount of hidden mines, the tiles can be revealed by clicking on them, if you hit a mine you will die.. i mean have to restart the game. If you don't it shows how a number
- That number indicates how many mines is surrounding that tile(that is all adjacent 8 tiles(so the number is between 0 and 8(and if it's 0 then it automatically clicks all adjacent tiles to reveal the surrounding areas)))
- By revealing all unmined tiles you win.

This field was made pretty simple so that you can estimate the probabilities empirically, like i did with my tester, but in the real game, the field is much larger. This is why i can't have a tester, it actually took me 5 minutes to get the probabilities that exact (and paul, it would have looped forever if hadn't stopped it ).

[kedaman]

Here's a simple example:

---
-2-
---
---
with 3 mines

And here's some examples how they can be located

* *   |      |
 2    | *2   |  2
      |   *  | **
*     |  *   |   *

There's always 1 mine at the bottom row since the other 2 has to be surrounding the revealed tile. Therefore each tile in that row will have a 1/3 probability of hitting a mine. The two others around the number have a wider area to be spread out on, even per mine: 2/8 (amount of mines/area) this makes it safer to click a tile around the number instead of the bottom row.

[T-Bone]

Kedaman,

I tried doing a similar thing by writting a Chess Quiz where one had to place 8 Queens on a Standard Chess board without any one of them being able to take each other off.

What I ended up doing was creating a 2 dimentional array of Bytes. I first filled the array with Information that I did know, for instance I knew where all the queens were (pardon any obscureties in that last remark!) and so I gave them a value of 1. then I went through the array and if a Queen (Value 1) cast a shadow path of 2's (Value=2) then if it was to place a value of 2 where there already was a 1 then it would know that a Queens could take off another.

In your case I would set up the following:

Public Type tSquare
SqrVal as Byte 'What the Square is set to (ie. 0 to 8)
SqrPxH as Integer 'Probability of Square having Bomb
End Type

Then declare a 2-dimensional array (x & y coordinates of the grid) and for each move you will need to re-calculate the probabilities.

This will end up being a complex piece of code because you will have to keep track of the bomb's too. (Maybe add in another entity within the Type statement as to whether it is a bomb).

Really big Hint: When coding this break up each section into chunks, and place these chunks into separate Functions. This will make it slower but will simplify coding and remove a lot of complex loops.

[kedaman]

I'm not looking for technical details, but for a mathematical solution. Everytime i start thinking about this problem i don't get anywhere

[T-Bone]

Kedaman,

Q: Do you want me to do it for you?

[kedaman]

A: Sure, if you can

[jm3ksc]

172‰ 173‰ 173‰ 236‰
173‰ 0‰ 173‰ 239‰
44‰ 44‰ 44‰ 237‰
173‰ 0‰ 173‰ 237‰
173‰ 173‰ 174‰ 238‰
236‰ 237‰ 237‰ 237‰


How can this be correct, speaking in terms of probabity? If you have over a hundred percent chance of hitting a bomb in the square, doesn't that mean that you would hit a bomb in the square? That would show that there are 19 bombs in the square. Am I understanding the question correctly?

[simonm]

Kedaman,

In the example you illustrated in the first post, The greatest probability any quare could have (to begin with) is a 50% chance.

Obviously, this could go up as more squares were uncovered and more was know about the layout but you can only assign probabilities on what you know, surely?

[kedaman]

jm3ksc


‰ means promille, and is worth 1/1000

Simonm

The greatest probability is 23.7% according to my empirically generated tests, there is a set probability for each tile for every situation, which can be calculated analytically, i'm sure of that.

as you uncover, the situation change, and we have a different probability scheme and it's always dependent on what is known.

[jm3ksc]

Thanks...

Now, another question...

Why would any block around the 1 be anything other than 1/22?


Wouldnt the two possiblities be:

1/22 | 1/22 | 1/22 | 2/22
1/22 | ****| 1/22 | 2/22
0/22 | 0/22 | 0/22 | 2/22
1/22 | ****| 1/22 | 2/22
1/22 | 1/22 | 1/22 | 2/22
2/22 | 2/22 | 2/22 | 2/22

if the mine isn't between the 1's

0/22 | 0/22 | 0/22 | 3/22
0/22 | **** | 0/22 | 3/22
1/22 | 1/22 | 1/22 | 3/22
0/22 | **** | 0/22 | 3/22
0/22 | 0/22 | 0/22 | 3/22
3/22 | 3/22 | 3/22 | 3/22

if the mine is between the 1's


Would this be correct?
1/44 | 1/44 | 1/44 | 5/44
1/44 | **** | 1/44 | 5/44
1/44 | 1/44 | 1/44 | 5/44
1/44 | **** | 1/44 | 5/44
1/44 | 1/44 | 1/44 | 5/44
5/44 | 5/44 | 5/44 | 5/44

[kedaman]

where did you get 1/24 from?

[simonm]

jm3ksc,

When none of the sqaures has been uncovered, each sqaure would have a 1/6 chance of a mine being underneath it.

But, does uncovering a number increase or decrease the likelyhood of a surrounding sqaure yielding a mine?

[jm3ksc]

Sorry, meant 1/22 because there are 22 possiblities left, and there is a chance of 1 being under those... but I see what you mean, that you have to take just that area now and treat it as its own population... Cool.

[kedaman]

it's simple if you can split up them to totally independent areas like my second example, but when they interfer, i don't know how to proceed

[simonm]

I think it's too complex for me.

Once the two squares are uncovered (in your first example), each suggest that the surrounding sqaures have a 1/8 chance of containing a mine.

Disregarding that knowlege for a moment, all the remaining sqaures would have a 2/11 chance (4/22).

Since the sqaures surrounding the 1's have less chance than the rest of having a mine, this must push up the probability of the rest of the sqaures. The problem is, by what amount?

I wouldn't know where to proceed from there.

[kedaman]

Hmm, I'm posting something for you to think about and analyze, i've been getting the same result 1/8 for both A and C over and over again while correcting small bugs and finally found that one that tipped over some on C but it's definitely not enough. I'm hopeless

Fixed mines:
2 Mines at D 
TotalLeft: 24-2Mines at D-2Revealed=20

Case1: Area C has a mine
	A=0/10
	B=0/2
	C=1/3
	D=3/9
Case2: Area A has 2 mines
	A=2/10
	B=0/2
	C=0/3
	D=2/9
Case3: Invalid
	A=?/10
	B=0/2
	C=?/3
	D=?/9


Chances of Case 1:

	(3/20)*(7/19)+(7/20)*(3/19)	=0,110526315789474
	(CLeft/TotalLeft)*(Dleft/Totaleft)+(DLeft/TotalLeft)*(Cleft/Totaleft)


Chances of Case 2:

	(10/20)*(5/19)	=0,131578947368421
	(ALeft/TotalLeft)*(AOthersideleft/Totaleft)


Chances of Case 3:

	1-((3/20)*(7/19)+(7/20)*(3/19)+(10/20)*(7/19))	=0,757894736842105
	1-((Case1)+(Case2))

Chance of not being Case 3
	0,110526315789474+0,131578947368421
	0,242105263157895

EXLUSION OF CASE 3

Chances of Case1:
	0,110526315789474/0,242105263157895 =0,456521739130436
Chances of Case2:
	0,131578947368421/0,242105263157895 =0,543478260869564

Chances Of A:
	0,543478260869564*2/10	=0,108695652173913
Chances of B
	0
Chances of C
	0,456521739130436*1/3	=0,152173913043479
Chances of D
	0,456521739130436*3/9+0,543478260869564*2/9	=0,272946859903382

[jm3ksc]

23/208 23/208 23/208 29/117
23/208 0/0 23/208 29/117
23/104 23/104 23/104 29/117
23/208 0/0 23/208 29/117
23/208 23/208 23/208 29/117
29/117 29/117 29/117 29/117


Here are your probabilities...

And this is how I came up with them mathmatically.

If touching 2:

Probability = ((23/16)/13)*2

If touching 1:
Probability = ((23/16)/13)*1


Im not really great at explaining this... its just bouncing in my head... let me know what you think.

The 23 is derived by the following:

23 = (10*2) + (1*3)

If one of the 10 squares that are not adjacent to both the 1's will cause 2 mines. If one of the 3 squares that are between both mines are chosen, then it will cause only 1 mine in the area.

Thus, the 23

The 16 is derived from all the possible positions on the chart in the area by the following

16 = (10*1) + (2*3) Overlapping squares cause the number not to be 13, but 16.

The 13 is pretty easy, just the number of squares in that area.

And the 1 or 2 is caused by the sum of the numbers in the square(s) it is touching.

If not:

Probability = ((3/13)*3+(10/13)*2)/9

The outside area looks at it a different way.
It sees that if one of the 3 of the 13 in the area that are touching contains a mine, there will be 3 mines left in its area. If a mine is contained in one of the other 10 squares, that means there are 2 mines in that area and two mines in its area.

The division by 9 just takes that area and divides by the squares in that area.

Ill try to come up with a better formula... just wanted to show what I had.

[kedaman]

what i hate about probabilities is that you have a ****load of numbers and have to explain every single bit or you will get lost.

your probability scheme didn't fullfill one critera:
The sum of them has to be 4, not 4,77403846153846

Hmm, i have difficulties to follow your reasoning, and i can't see what youre trying to accomplish.
When calculating probabilities, you need to know two things, the total amount of alternatives left and the amount of qualifying alternatives: 1 of 3 is 1/3, 3 of 5 is 3/5. Combinations are separated by * operator and alternatives are separated by +. You can't exclude that you're able to put the first mine in the D field, since you could place the second in C giving a bias for C.

thanks anyway for trying out something

[jm3ksc]

(23/208)*10 = 1.105769231
(23/104) * 3 = 0.663461538
(29/117) * 9 = 2.230769231

Add those up and you get 4....

But, in answer to the second part...

What I am doing is finding the probability of the area in question and then taking the "weight" of probability per square in the area.

The probability of the area C+A is 23/16, but yet there are only 13 squares...

The 16 is number of squares around 1 mine + number of squares around the other mine.

The division by 13 determines the weight per square... if the sum of the uncovered square it is touching is 1. If the sum is greater, the multiplier affect would go up.

I don't know if this clears up what I was thinking or not... let me know.

[kedaman]

Doesn't make any sense and still i don't see what you did to area D

[jm3ksc]

The probability of a mine being in area c (for D's point of veiw) is 3/13 chances
This will only place 1 mine in area C+A leaving 3 mines in Area D

The probability of a mine being in area A is 10/13.
This will place 2 mines in A's area leaving leaving 2 mines in Area D

So the probability of a mine being in all of area D is

((3/13)*3+(10/13)*2)

Meaning that there is a 3/13 chance that the mine is in A and that leaves a weight of 3 mines that would be left in Area D

+ (Because we have found the probability of one situation and now finding the probability of another situation)

a 10/13 sqaures that the mine could be in for the area A+C, leaving 2 mines to be dispursed throughout D's area.

The 9 takes all that probabilty and divides it by the number of squares in D's area....

Does this clear up what I'm thinking?