Mixing
![Is there an intuitive reason why the natural logarithm shows up in the Prime Number Theorem? [duplicate]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Expected area “sweeped†on an infinite Minesweeper board
Clash Royale CLAN TAG#URR8PPP
up vote
8
down vote
favorite
Given an average density (x/y) of x mines in y squares, is it possible to calculate the expected number of squares you can "sweep" (i.e. identify whether there is a mine or not) on an infinitely sized minesweeper game, before you have to guess- i.e. no more squares can be deduced.
probability recreational-mathematics
asked Jul 30 at 4:02
Oddly asymmetric
505
 |Â
show 4 more comments
up vote
8
down vote
favorite
Given an average density (x/y) of x mines in y squares, is it possible to calculate the expected number of squares you can "sweep" (i.e. identify whether there is a mine or not) on an infinitely sized minesweeper game, before you have to guess- i.e. no more squares can be deduced.
probability recreational-mathematics
asked Jul 30 at 4:02
Oddly asymmetric
505
But i don’t really understand how the minesweeper game works: sometimes when you press on one square, some squares in its vicinity with no mines would also be automatically pressed.
– Szeto
Jul 30 at 5:01
1
One interesting part of your question is at what density the expected area swept diverges, and the asymptotic form of the divergence.
– joriki
Jul 30 at 6:02
To fully clarify the question (in case there are different implementations of the game): Every square contains a mine independently of all other squares with probability $p=frac xy$, except the first square we click on, which is guaranteed not to contain a mine -- correct?
– joriki
Jul 30 at 6:05
1
@SangchulLee: That's what I meant above. There is a threshold at which the expected area you can sweep diverges. This could be the site percolation threshold for the square lattice, or it could be a higher threshold.
– joriki
Jul 30 at 12:01
1
@Oddlyasymmetric: I don't understand the problem you raise in your last comment. Before you see any numbers, how does a mine on some square imply that other squares can't have one? Of course once you see numbers, there are such implications, but that doesn't keep us from generating the original board (which determines those very numbers) with independent choices.
– joriki
Jul 30 at 12:02
 |Â
show 4 more comments
up vote
8
down vote
favorite
up vote
8
down vote
favorite
Given an average density (x/y) of x mines in y squares, is it possible to calculate the expected number of squares you can "sweep" (i.e. identify whether there is a mine or not) on an infinitely sized minesweeper game, before you have to guess- i.e. no more squares can be deduced.
probability recreational-mathematics
asked Jul 30 at 4:02
Oddly asymmetric
505
Given an average density (x/y) of x mines in y squares, is it possible to calculate the expected number of squares you can "sweep" (i.e. identify whether there is a mine or not) on an infinitely sized minesweeper game, before you have to guess- i.e. no more squares can be deduced.
probability recreational-mathematics
asked Jul 30 at 4:02
Oddly asymmetric
505
edited Jul 30 at 11:53
asked Jul 30 at 4:02
Oddly asymmetric
505
asked Jul 30 at 4:02
Oddly asymmetric
505
asked Jul 30 at 4:02
Oddly asymmetric
505
505
But i don’t really understand how the minesweeper game works: sometimes when you press on one square, some squares in its vicinity with no mines would also be automatically pressed.
– Szeto
Jul 30 at 5:01
1
One interesting part of your question is at what density the expected area swept diverges, and the asymptotic form of the divergence.
– joriki
Jul 30 at 6:02
To fully clarify the question (in case there are different implementations of the game): Every square contains a mine independently of all other squares with probability $p=frac xy$, except the first square we click on, which is guaranteed not to contain a mine -- correct?
– joriki
Jul 30 at 6:05
1
@SangchulLee: That's what I meant above. There is a threshold at which the expected area you can sweep diverges. This could be the site percolation threshold for the square lattice, or it could be a higher threshold.
– joriki
Jul 30 at 12:01
1
@Oddlyasymmetric: I don't understand the problem you raise in your last comment. Before you see any numbers, how does a mine on some square imply that other squares can't have one? Of course once you see numbers, there are such implications, but that doesn't keep us from generating the original board (which determines those very numbers) with independent choices.
– joriki
Jul 30 at 12:02
 |Â
show 4 more comments
But i don’t really understand how the minesweeper game works: sometimes when you press on one square, some squares in its vicinity with no mines would also be automatically pressed.
– Szeto
Jul 30 at 5:01
1
One interesting part of your question is at what density the expected area swept diverges, and the asymptotic form of the divergence.
– joriki
Jul 30 at 6:02
To fully clarify the question (in case there are different implementations of the game): Every square contains a mine independently of all other squares with probability $p=frac xy$, except the first square we click on, which is guaranteed not to contain a mine -- correct?
– joriki
Jul 30 at 6:05
1
@SangchulLee: That's what I meant above. There is a threshold at which the expected area you can sweep diverges. This could be the site percolation threshold for the square lattice, or it could be a higher threshold.
– joriki
Jul 30 at 12:01
1
@Oddlyasymmetric: I don't understand the problem you raise in your last comment. Before you see any numbers, how does a mine on some square imply that other squares can't have one? Of course once you see numbers, there are such implications, but that doesn't keep us from generating the original board (which determines those very numbers) with independent choices.
– joriki
Jul 30 at 12:02
But i don’t really understand how the minesweeper game works: sometimes when you press on one square, some squares in its vicinity with no mines would also be automatically pressed.
– Szeto
Jul 30 at 5:01
But i don’t really understand how the minesweeper game works: sometimes when you press on one square, some squares in its vicinity with no mines would also be automatically pressed.
– Szeto
Jul 30 at 5:01
1
1
One interesting part of your question is at what density the expected area swept diverges, and the asymptotic form of the divergence.
– joriki
Jul 30 at 6:02
One interesting part of your question is at what density the expected area swept diverges, and the asymptotic form of the divergence.
– joriki
Jul 30 at 6:02
To fully clarify the question (in case there are different implementations of the game): Every square contains a mine independently of all other squares with probability $p=frac xy$, except the first square we click on, which is guaranteed not to contain a mine -- correct?
– joriki
Jul 30 at 6:05
To fully clarify the question (in case there are different implementations of the game): Every square contains a mine independently of all other squares with probability $p=frac xy$, except the first square we click on, which is guaranteed not to contain a mine -- correct?
– joriki
Jul 30 at 6:05
1
1
@SangchulLee: That's what I meant above. There is a threshold at which the expected area you can sweep diverges. This could be the site percolation threshold for the square lattice, or it could be a higher threshold.
– joriki
Jul 30 at 12:01
@SangchulLee: That's what I meant above. There is a threshold at which the expected area you can sweep diverges. This could be the site percolation threshold for the square lattice, or it could be a higher threshold.
– joriki
Jul 30 at 12:01
1
1
@Oddlyasymmetric: I don't understand the problem you raise in your last comment. Before you see any numbers, how does a mine on some square imply that other squares can't have one? Of course once you see numbers, there are such implications, but that doesn't keep us from generating the original board (which determines those very numbers) with independent choices.
– joriki
Jul 30 at 12:02
@Oddlyasymmetric: I don't understand the problem you raise in your last comment. Before you see any numbers, how does a mine on some square imply that other squares can't have one? Of course once you see numbers, there are such implications, but that doesn't keep us from generating the original board (which determines those very numbers) with independent choices.
– joriki
Jul 30 at 12:02
 |Â
show 4 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
This is not an answer, but I thought it would be interesting to do a simulation on a finite board.
So I made a bare-bones Minesweeper solver and ran a 1000 games for various mine densities on a 50x50 board and got the following:
The X axis shows the mine density (i.e. the probability that a square is a mine) and the Y axis shows the percentage of mines swept.
As can be seen, the steepness of the curve is quite large. At a density of 0.13 it is at 90% and at 0.22 it is under 10%.
To check how good (or bad) my algorithm was, I manually played 10 games of Minesweeper at expert level (where mine density is less than 0.21) and got the result of 53%. This is almost twice as good as my algorithm which got 27%. But the steepness of the curve means my primitive algorithm got 57% at the slightly lower density of 0.18.
So, even with a better Minesweeper solver I expect the basic curve shape will be the same, just shifted a bit to the right.
answered 6 hours ago
Jens
3,0162726
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
This is not an answer, but I thought it would be interesting to do a simulation on a finite board.
So I made a bare-bones Minesweeper solver and ran a 1000 games for various mine densities on a 50x50 board and got the following:
The X axis shows the mine density (i.e. the probability that a square is a mine) and the Y axis shows the percentage of mines swept.
As can be seen, the steepness of the curve is quite large. At a density of 0.13 it is at 90% and at 0.22 it is under 10%.
To check how good (or bad) my algorithm was, I manually played 10 games of Minesweeper at expert level (where mine density is less than 0.21) and got the result of 53%. This is almost twice as good as my algorithm which got 27%. But the steepness of the curve means my primitive algorithm got 57% at the slightly lower density of 0.18.
So, even with a better Minesweeper solver I expect the basic curve shape will be the same, just shifted a bit to the right.
answered 6 hours ago
Jens
3,0162726
add a comment |Â
up vote
0
down vote
This is not an answer, but I thought it would be interesting to do a simulation on a finite board.
So I made a bare-bones Minesweeper solver and ran a 1000 games for various mine densities on a 50x50 board and got the following:
The X axis shows the mine density (i.e. the probability that a square is a mine) and the Y axis shows the percentage of mines swept.
As can be seen, the steepness of the curve is quite large. At a density of 0.13 it is at 90% and at 0.22 it is under 10%.
To check how good (or bad) my algorithm was, I manually played 10 games of Minesweeper at expert level (where mine density is less than 0.21) and got the result of 53%. This is almost twice as good as my algorithm which got 27%. But the steepness of the curve means my primitive algorithm got 57% at the slightly lower density of 0.18.
So, even with a better Minesweeper solver I expect the basic curve shape will be the same, just shifted a bit to the right.
answered 6 hours ago
Jens
3,0162726
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This is not an answer, but I thought it would be interesting to do a simulation on a finite board.
So I made a bare-bones Minesweeper solver and ran a 1000 games for various mine densities on a 50x50 board and got the following:
The X axis shows the mine density (i.e. the probability that a square is a mine) and the Y axis shows the percentage of mines swept.
As can be seen, the steepness of the curve is quite large. At a density of 0.13 it is at 90% and at 0.22 it is under 10%.
To check how good (or bad) my algorithm was, I manually played 10 games of Minesweeper at expert level (where mine density is less than 0.21) and got the result of 53%. This is almost twice as good as my algorithm which got 27%. But the steepness of the curve means my primitive algorithm got 57% at the slightly lower density of 0.18.
So, even with a better Minesweeper solver I expect the basic curve shape will be the same, just shifted a bit to the right.
answered 6 hours ago
Jens
3,0162726
This is not an answer, but I thought it would be interesting to do a simulation on a finite board.
So I made a bare-bones Minesweeper solver and ran a 1000 games for various mine densities on a 50x50 board and got the following:
The X axis shows the mine density (i.e. the probability that a square is a mine) and the Y axis shows the percentage of mines swept.
As can be seen, the steepness of the curve is quite large. At a density of 0.13 it is at 90% and at 0.22 it is under 10%.
To check how good (or bad) my algorithm was, I manually played 10 games of Minesweeper at expert level (where mine density is less than 0.21) and got the result of 53%. This is almost twice as good as my algorithm which got 27%. But the steepness of the curve means my primitive algorithm got 57% at the slightly lower density of 0.18.
So, even with a better Minesweeper solver I expect the basic curve shape will be the same, just shifted a bit to the right.
answered 6 hours ago
Jens
3,0162726
answered 6 hours ago
Jens
3,0162726
answered 6 hours ago
Jens
3,0162726
answered 6 hours ago
Jens
3,0162726
3,0162726
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2866649%2fexpected-area-sweeped-on-an-infinite-minesweeper-board%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
But i don’t really understand how the minesweeper game works: sometimes when you press on one square, some squares in its vicinity with no mines would also be automatically pressed.
– Szeto
Jul 30 at 5:01
1
One interesting part of your question is at what density the expected area swept diverges, and the asymptotic form of the divergence.
– joriki
Jul 30 at 6:02
To fully clarify the question (in case there are different implementations of the game): Every square contains a mine independently of all other squares with probability $p=frac xy$, except the first square we click on, which is guaranteed not to contain a mine -- correct?
– joriki
Jul 30 at 6:05
1
@SangchulLee: That's what I meant above. There is a threshold at which the expected area you can sweep diverges. This could be the site percolation threshold for the square lattice, or it could be a higher threshold.
– joriki
Jul 30 at 12:01
1
@Oddlyasymmetric: I don't understand the problem you raise in your last comment. Before you see any numbers, how does a mine on some square imply that other squares can't have one? Of course once you see numbers, there are such implications, but that doesn't keep us from generating the original board (which determines those very numbers) with independent choices.
– joriki
Jul 30 at 12:02