|
On December 24 2011 13:50 Primadog wrote:Rewording the OP as following: Assuming all puzzles are solvable, 'perfect' play, and ignoring value of user time, is playing "thrill digger" profitable? - aka, is expected value E of the game greater than the cost of the game?
- As calgar stated, to break even, E must exceed 37.5 (cost of the game 30 / 80% autolose rate)
- The number of maps possible is a simple combination problem (20 pick 4), so 20! / 4! / 16! = 4845 maps possible
- As Telegnosis stated, the minimum final score is 36:
xxooo
xxooo
ooooo
ooooo
Let's call this formation min. There're 3 other version of this map possible, one for each corner. So four cases of Score(min) = 36.
- The following formation scores 63 points:
xxooo
xoooo
ooooo
xoooo
Let's call this formation b. There're 3 other version of this map possible, one for each corner. So four cases of Score(b) = 63
We need to find whether E > 37.5 - The expected value of all cases of Score_b and all cases of Score_min is (4 x 36 + 4 x 63 ) / (4+4) = 49.5, which is more than 37.5.
- All other map formulations besides Score(min) and Score(b) score higher than 37.5.
- Therefore the expected value of the game must exceed 37.5.
Therefore, given the above assumptions, thriller digger is always profitable.
It was not given that all puzzles are "solvable", and the closest we can get to perfect play is picking the best squares. It's a probability problem, and as such you might not get to complete every puzzle without running in to a bomb.
|
There's no easy way to quantify user skill in solving problems, so assuming 'perfect play' is acceptable.
Assuming all problems are solvable, however, is less reasonable. However, I do not know whether there exists a formula for % of solvable and unsolvable minesweeper boards, so this was also a necessary assumption. Might be NP-complete.
We cannot/should not factor in user time tradeoff.
Without making these three assumptions, the question stated is essentially unsolvable.
|
On December 24 2011 14:02 Primadog wrote:
There's no easy way to quantify user skill in solving problems, so assuming 'perfect play' is acceptable.
Assuming all problems are solvable, however, is less reasonable. However, I do not know whether there exists a formula for % of solvable and unsolvable minesweeper boards, so this was also a necessary assumption.
We cannot/should not factor in user time tradeoff.
Without making these three assumptions, the question stated is essentially unsolvable.
It is absolutely not unsolveable, however it depends on your definition of 'perfect play'. It's a probability problem so assuming that the player is omnipotent is pointless, i.e. what's the chance of god picking the ace of hearts from a deck of cards? 1/1 of course.
So perfect play in this instance must mean that the player only picks the squares that give him the highest probability of success.
All problems are "solveable" in that it is possible to clean up the board before picking a bomb, but wether or not you'll be able to comes down to luck.
To find out if EV >= 37.5 we must find out if the average score one would get is >= 37.5 using an optimal strategy. If we can find this (which we can), we have solved the problem.
An approach was posted earlier that should give the optimal picking strategy (the databasing of all possible boards, etc). What is left to do is implement this or come up with a better approach.
|
On December 24 2011 14:13 Adeny wrote:Show nested quote +On December 24 2011 14:02 Primadog wrote:
There's no easy way to quantify user skill in solving problems, so assuming 'perfect play' is acceptable.
Assuming all problems are solvable, however, is less reasonable. However, I do not know whether there exists a formula for % of solvable and unsolvable minesweeper boards, so this was also a necessary assumption.
We cannot/should not factor in user time tradeoff.
Without making these three assumptions, the question stated is essentially unsolvable. It is absolutely not unsolveable, however it depends on your definition of 'perfect play'. It's a probability problem so assuming that the player is omnipotent is pointless, i.e. what's the chance of god picking the ace of hearts from a deck of cards? 1/1 of course. So perfect play in this instance must mean that the player only picks the squares that give him the highest probability of success. All problems are "solveable" in that it is possible to clean up the board before picking a bomb, but wether or not you'll be able to comes down to luck. To find out if EV >= 37.5 we must find out if the average score one would get is >= 37.5 using an optimal strategy. If we can find this (which we can), we have solved the problem. An approach was posted earlier that should give the optimal picking strategy (the databasing of all possible boards, etc). What is left to do is implement this or come up with a better approach.
You're right and I don't disagree.
Even with perfect play, some minesweeper maps are unsolvable. There're many google-able discussions about this http://math.stackexchange.com/questions/42494/odds-of-winning-at-minesweeper-with-perfect-play
However, nobody has figured out a exact formula for how many percentage of unsolvable permutation exists for a board of given size and number of bombs. Without knowing how many unsolvable maps are there, the solution to the OP is also unsolvable. This is why I put forward a solution assuming that all maps are solvable, otherwise the question is unanswerable.
PS Perfect play aka optimal picking strategy does not exist, or else you just solved NP-complete (or so I was told).
|
20C4 is a relatively small number, though, so it's certainly not theoretically or practically unsolvable.
4854. Very doable, if you can automate the strategy.
If someone could whip up an online 5x4x5 minesweeper, that would be helpful.
|
On December 24 2011 14:20 Primadog wrote:Show nested quote +On December 24 2011 14:13 Adeny wrote:On December 24 2011 14:02 Primadog wrote:
There's no easy way to quantify user skill in solving problems, so assuming 'perfect play' is acceptable.
Assuming all problems are solvable, however, is less reasonable. However, I do not know whether there exists a formula for % of solvable and unsolvable minesweeper boards, so this was also a necessary assumption.
We cannot/should not factor in user time tradeoff.
Without making these three assumptions, the question stated is essentially unsolvable. It is absolutely not unsolveable, however it depends on your definition of 'perfect play'. It's a probability problem so assuming that the player is omnipotent is pointless, i.e. what's the chance of god picking the ace of hearts from a deck of cards? 1/1 of course. So perfect play in this instance must mean that the player only picks the squares that give him the highest probability of success. All problems are "solveable" in that it is possible to clean up the board before picking a bomb, but wether or not you'll be able to comes down to luck. To find out if EV >= 37.5 we must find out if the average score one would get is >= 37.5 using an optimal strategy. If we can find this (which we can), we have solved the problem. An approach was posted earlier that should give the optimal picking strategy (the databasing of all possible boards, etc). What is left to do is implement this or come up with a better approach. Even with perfect play, some minesweeper maps are unsolvable. There're many google-able discussions about this http://math.stackexchange.com/questions/42494/odds-of-winning-at-minesweeper-with-perfect-playHowever, nobody has figured out a exact formula for how many percentage of unsolvable permutation exists for a board of given size and number of bombs.
Pretty interesting, and I didn't think about the fact that the mines might be generated after your first choice in OPs game too, could someone who has access test if it's possible to hit a bomb on your first pick?
Disregarding minesweeper, in the case of OPs problem specifically, we don't need to clear every board every time, we just need to get an average score of 37.5. So because of this we can ignore if puzzles are completely solveable or not. I'll try to implement a naive strategy (which might be enough if the margin of error is pretty big, i.e. maybe we don't need perfect play for all the corner cases) the next time I remember this thread, but for now I have to hit the sack.
|
On December 24 2011 14:36 Adeny wrote:Show nested quote +On December 24 2011 14:20 Primadog wrote:On December 24 2011 14:13 Adeny wrote:On December 24 2011 14:02 Primadog wrote:
There's no easy way to quantify user skill in solving problems, so assuming 'perfect play' is acceptable.
Assuming all problems are solvable, however, is less reasonable. However, I do not know whether there exists a formula for % of solvable and unsolvable minesweeper boards, so this was also a necessary assumption.
We cannot/should not factor in user time tradeoff.
Without making these three assumptions, the question stated is essentially unsolvable. It is absolutely not unsolveable, however it depends on your definition of 'perfect play'. It's a probability problem so assuming that the player is omnipotent is pointless, i.e. what's the chance of god picking the ace of hearts from a deck of cards? 1/1 of course. So perfect play in this instance must mean that the player only picks the squares that give him the highest probability of success. All problems are "solveable" in that it is possible to clean up the board before picking a bomb, but wether or not you'll be able to comes down to luck. To find out if EV >= 37.5 we must find out if the average score one would get is >= 37.5 using an optimal strategy. If we can find this (which we can), we have solved the problem. An approach was posted earlier that should give the optimal picking strategy (the databasing of all possible boards, etc). What is left to do is implement this or come up with a better approach. Even with perfect play, some minesweeper maps are unsolvable. There're many google-able discussions about this http://math.stackexchange.com/questions/42494/odds-of-winning-at-minesweeper-with-perfect-playHowever, nobody has figured out a exact formula for how many percentage of unsolvable permutation exists for a board of given size and number of bombs. Pretty interesting, and I didn't think about the fact that the mines might be generated after your first choice in OPs game too, could someone who has access test if it's possible to hit a bomb on your first pick? Disregarding minesweeper, in the case of OPs problem specifically, we don't need to clear every board every time, we just need to get an average score of 37.5. So because of this we can ignore if puzzles are completely solveable or not. I'll try to implement a naive strategy (which might be enough if the margin of error is pretty big, i.e. maybe we don't need perfect play for all the corner cases) the next time I remember this thread, but for now I have to hit the sack.
Ah, this strategy could work! Although I imagine it can only prove E > 37.5 but never E < 37.5
|
United States4053 Posts
I made a pretty crude version of this in mathematica, and I tried starting with the upper left corner. Excluding the times I exploded on click one, I scored in the 50s most of the time. Man, I'm lucky.
code:
+ Show Spoiler +BombList = Table[Table[0, {5}], {5}];
ButtonList = Table[Table["?", {5}], {5}];
While[Sum[k, {k, Flatten[BombList]}] < 4,
BombList[[RandomInteger[{1, 5}], RandomInteger[{1, 5}]]] = 1]
CheckBomb[x_, y_] :=
If[1 <= x <= 5 && 1 <= y <= 5, If[BombList[[x, y]] == 1, 1, 0], 0]
CheckScore[x_, y_] :=
If[CheckBomb[x, y] == 1, 0,
Switch[CheckBomb[x - 1, y] + CheckBomb[x, y - 1] +
CheckBomb[x + 1, y] + CheckBomb[x, y + 1], 0, 1, 1, 5, 2, 5, 3,
20, 4, 20]]
score = 0;
ThrillButton[x_, y_] :=
Button[Dynamic[ButtonList[[x, y]]],
If[ButtonList[[x, y]] == "?", score += CheckScore[x, y]];
If[CheckScore[x, y] == 0, ButtonList[[x, y]] = "!",
ButtonList[[x, y]] = CheckScore[x, y]]]
Dynamic[score]
Grid[Table[Table[ThrillButton[i, j], {i, 5}], {j, 5}]]
|
On December 24 2011 12:36 Adeny wrote:Show nested quote +On December 24 2011 12:26 calgar wrote:On December 24 2011 12:13 Adeny wrote:Running it 100,000 times and just picking blindly, I get an average score of 11. That doesn't feel like it's correct though, but I checked manually and I get the right scores for the right boards. What am I missing? C# code here (albeit very messy, it's 4am and christmas, I don't feel like thinking) http://pastie.org/3065188 Hm, is that just blind picking? edit - ah yeah, it is. Well if every square is randomly picked then that sounds like it makes sense. The trick here is that strategy would let you get much higher than that on average, though. Ie... if you run into a 20 rupee, then you automatically have a very good idea where 3 (or 4) of the bombs are, and can pick through the rest of the board. I have no idea how to program that though pfft.. Yup just completely at random. So let's talk strategy. First of, the corners are, on average, just as risky as the mid squares, but give far fewer points. If we pick a square and get 1 rupee, we know that all squares around it are safe. This works recursively until we run out of squares that give 1 rupee (that are connected at least). For squares that give 5 or 20 I think it's better to avoid all adjacent squares temporarily and pick at random again. If we run out of squares that are 1. not adjacent to a 1-rupee square, and 2. not a corner, we need to weigh the risk of picking corner vs. the risk of picking next to a square that gave 5 or 20 rupees. We need to take 2 things in cosideration: How many squares could be bombs around the square we are considering to pick, and how likely is it that the square we are picking is a bomb. I think that covers everything, need some time to work on the specifics. Edit: By corner I mean corner/edge. The corner is, on average, just as risky. But I think there might be some advantage to the corner anyways. It is more likely to be a 'safe' 1 rupee square, helping you reveal more adjacent territory safely and get more information. If it is a 20 rupee (very unlikely) then your EV shoots up drastically. Even with a 5 rupee you have narrowed down 1 or 2 mines to within a 4 square radius. Whereas before you had a 0.20 chance of losing randomly, with a 5 rupee in the corner the odds are now 0.125 with 2 mines or 0.1875 if only one is revealed.
I agree that avoiding adjacent squares temporarily is the safest way. Weighing the risk of picking a new square vs. next to where you think bombs might be is tricky though. Higher reward, higher risk.
After the corners are gone, do you think an edge with 5 surrounding is a better pick than in the middle with no other information?
And the bombs are generated before you pick so you can lose on your first try.
|
On December 25 2011 00:39 calgar wrote:Show nested quote +On December 24 2011 12:36 Adeny wrote:On December 24 2011 12:26 calgar wrote:On December 24 2011 12:13 Adeny wrote:Running it 100,000 times and just picking blindly, I get an average score of 11. That doesn't feel like it's correct though, but I checked manually and I get the right scores for the right boards. What am I missing? C# code here (albeit very messy, it's 4am and christmas, I don't feel like thinking) http://pastie.org/3065188 Hm, is that just blind picking? edit - ah yeah, it is. Well if every square is randomly picked then that sounds like it makes sense. The trick here is that strategy would let you get much higher than that on average, though. Ie... if you run into a 20 rupee, then you automatically have a very good idea where 3 (or 4) of the bombs are, and can pick through the rest of the board. I have no idea how to program that though pfft.. Yup just completely at random. So let's talk strategy. First of, the corners are, on average, just as risky as the mid squares, but give far fewer points. If we pick a square and get 1 rupee, we know that all squares around it are safe. This works recursively until we run out of squares that give 1 rupee (that are connected at least). For squares that give 5 or 20 I think it's better to avoid all adjacent squares temporarily and pick at random again. If we run out of squares that are 1. not adjacent to a 1-rupee square, and 2. not a corner, we need to weigh the risk of picking corner vs. the risk of picking next to a square that gave 5 or 20 rupees. We need to take 2 things in cosideration: How many squares could be bombs around the square we are considering to pick, and how likely is it that the square we are picking is a bomb. I think that covers everything, need some time to work on the specifics. Edit: By corner I mean corner/edge. The corner is, on average, just as risky. But I think there might be some advantage to the corner anyways. It is more likely to be a 'safe' 1 rupee square, helping you reveal more adjacent territory safely and get more information. If it is a 20 rupee (very unlikely) then your EV shoots up drastically. Even with a 5 rupee you have narrowed down 1 or 2 mines to within a 4 square radius. Whereas before you had a 0.20 chance of losing randomly, with a 5 rupee in the corner the odds are now 0.125 with 2 mines or 0.1875 if only one is revealed. I agree that avoiding adjacent squares temporarily is the safest way. Weighing the risk of picking a new square vs. next to where you think bombs might be is tricky though. Higher reward, higher risk. After the corners are gone, do you think an edge with 5 surrounding is a better pick than in the middle with no other information? And the bombs are generated before you pick so you can lose on your first try.
I'm not entierly convinced that corners are better, because if you get a 1-pointer in the corner, you only get to open 3 squares, if you get a 1-pointer in the middle, you get to open 8. It's then more likely that one of those 8 will be a one-pointer, leading to more points on average I would think. I don't know how I would begin calculating this though.
|
Fixed a silly coding error (5am coding \o/), that bumped the average up to 16. Then I added checking for ever square around 1-point squares, that puts the average score 28. I'll add more later, but I don't feel like coding the method of databasing all boards because christmas time is relaxing-time, and that would take a lot of coding.
Oh and for proving that it's not EV+, that can be done if we can prove which picking strategy is optimal, and if that strategy doesn't hold up then EV must be negative.
|
Added some more changes, now an average score of ~35 but this takes into account the times that you pick bombs on your first try, so it only has to be over 30 to be EV+. The simple strategy (far from optimal) I used is:
- Pick corners first
- If you open up a square that gives 1 score, open everything around it too
- Otherwise just pick at random
That's all it takes to beat this, code below (note: super messy, don't try this at home etc)
http://pastie.org/3073168
|
Looks like the answer is almost certainly yes based on your research, adeny.
|
|
|
|
|
|
EPT
