|
I'm no good at math but I was curious to know the expected value of a mini game in the new Legend of Zelda: Skyward sword. It's sort of like mine sweeper and you get money for every safe square you pick. It has several modes, but the basic one is set up like this:
-the board for the game, "thrill digger", is a 5x4 grid, and you choose squares in the grid
-4 bombs are randomly placed in the grid, game ends when you hit a bomb
-you get rupees based on how many bombs are adjacent to that safe square you choose
-1 rupee for a square with no adjacent bombs (these help narrow where the bombs are though)
-5 rupees for a square with 1 or 2 adjacent bombs
-20 rupees for a square with 3 or 4 adjacent bombs
-the game costs 30 rupees to play
So what I've figured is that you have a 20% chance to lose right off the bat on your first pick. This means you need to average 37.5 rupees in your other games to break even. The most money you could make is, I think, 108? That's with the 4 bombs in a line, maximing the number of 20 rupee squares to 4.
My strategy so far has been to pick the corners because if its blue then I will narrow down bomb locations until I have to guess.
|
Interesting, at first glance it doesn't sound profitable.
|
I played this game about 50 times for hours and hours and I more or less came out even (making no obvious mistakes)
I only made about 200 profit because of a couple of games where I hit it big. Most of the time I break even though.
|
This looks like a fun problem, if no one answers it by the time I finish my take home exam I'll give it a crack
|
You have to include that if you get all the non-bomb squares, the guy who runs the minigame gives you something (I got a small blue feather, sells for 100 rupees). Idk if you win that every time or if its just a one time thing though.
|
United States10328 Posts
lol, my friend played this and made quite a profit? because there are random (3-4, I think) silver rupees worth 100.
unless you changed it for the purposes of the math problem (?) for your problem as it stands, I suspect the best solution is "by computer" (because as a combinatorics problem, it's quite ugly D: too many cases)
|
On December 24 2011 08:37 calgar wrote:
I'm no good at math but I was curious to know the expected value of a mini game in the new Legend of Zelda: Skyward sword. It's sort of like mine sweeper and you get money for every safe square you pick. It has several modes, but the basic one is set up like this:
-the board for the game, "thrill digger", is a 5x4 grid, and you choose squares in the grid
-4 bombs are randomly placed in the grid, game ends when you hit a bomb
-you get rupees based on how many bombs are adjacent to that safe square you choose
-1 rupee for a square with no adjacent bombs (these help narrow where the bombs are though)
-5 rupees for a square with 1 or 2 adjacent bombs
-20 rupees for a square with 3 or 4 adjacent bombs
-the game costs 30 rupees to play
So what I've figured is that you have a 20% chance to lose right off the bat on your first pick. This means you need to average 37.5 rupees in your other games to break even. The most money you could make is, I think, 108? That's with the 4 bombs in a line, maximing the number of 20 rupee squares to 4.
My strategy so far has been to pick the corners because if its blue then I will narrow down bomb locations until I have to guess.
Cool problem, but unfortunately I highly doubt there's a legit solution to finding an optimal strategy or even expected value without exhaustive computer search through all 4845 possible positions (which isn't very many at all, computer-wise, but clearly too many to attack by hand, even counting symmetry).
As a quick note, your 108 best case is wrong. You get 108 for the arrangement
ooxoo
ooxoo
ooxoo
ooxoo
where o is empty and x is a bomb, but
ooooo
oxoxo
oxoxo
ooooo
gives 110, and what I think is best is
ooooo
xxxxo
ooooo
ooooo
which gives 120. Worst case is obviously 0 if you hit a bomb straight off the bat, but worst case if you clear the board is 32:
xoooo
xoooo
xoooo
xoooo
Might edit more stuff in later -- cooking things for Christmas and browsing TL in my sporadic downtime.
|
side note how is the game getting it for xmas (saw brother with it, clearly my gift from him)
|
Questions:
Do bombs on the diagonals count as "adjacent"?
Do you get to know how many points your square gave, ala minesweeper? Or do you not know until after?
|
On December 24 2011 11:31 Iranon wrote:
Worst case is obviously 0 if you hit a bomb straight off the bat, but worst case if you clear the board is 32:
xoooo
xoooo
xoooo
xoooo
That board would yield 62 for a full clear, worst should be:
xxooo
xxooo
ooooo
ooooo
for 36.
|
On December 24 2011 11:47 Telegnosis wrote:Show nested quote +On December 24 2011 11:31 Iranon wrote:
Worst case is obviously 0 if you hit a bomb straight off the bat, but worst case if you clear the board is 32:
xoooo
xoooo
xoooo
xoooo
That board would yield 62 for a full clear, worst should be: xxooo xxooo ooooo ooooo for 36.
Oops - good catch. I had that 36 board in my post originally and edited it out sticking the wrong one in there.
|
On December 24 2011 10:50 bananaman533 wrote:
You have to include that if you get all the non-bomb squares, the guy who runs the minigame gives you something (I got a small blue feather, sells for 100 rupees). Idk if you win that every time or if its just a one time thing though. You can win the goddess plume and the blue bird feather also if you perfect clear, but that's a side note since I was more curious about the rupee value. If you consider the added bonus at the end then yeah it probably makes it more profitable.
There are actually 3 different difficulties, beginner, intermediate, and expert. The example problem I outlined is the beginner version. Medium and expert cost more rupees, have bigger grids, more bombs, but also negative rupees. Silver is from intermediate/expert and would be a '5' or '6' in minesweeper with 5 or 6 bad holes around it. I've played the beginner version mostly because it was cheaper, and after about 12 games I came out on top by 30 or so. I had a bad streak where I lost in 1 or 2 digs for 4 games but then I made 70, 80, and 100 also.
On December 24 2011 11:32 ohokurwrong wrote:
side note how is the game getting it for xmas (saw brother with it, clearly my gift from him) It's pretty awesome, I've put in about 10 hours and had a blast. I read in a Game Informer article that the game designers consider it the best zelda they've made because it is so complete and stretches the boundaries with motion controls, sound (30 full orchestra songs?!), and storytelling.
On December 24 2011 11:37 Adeny wrote:Questions:
Do bombs on the diagonals count as "adjacent"?
Do you get to know how many points your square gave, ala minesweeper? Or do you not know until after? As the king moves, they say. One square in any direction, horizontal, vertical, or diagonal counts. Since there are only 4 bombs in this version the most you can have is 20 rupees from having 3 or 4 bombs around the square in any variation.
You find out the value of the square after you dig it. It's like minesweeper, though, but the information provided isn't conclusive. Like, if you dig and you get a 5 rupee, you know that there is a dangerous square around it, but there could be 2, or just 1. Hope that helps.
edit: Good catch on 120 iranon. So 120 at best, and 32 at worst if you can full clear.
|
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
|
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..
|
On December 24 2011 12:26 calgar wrote:Show nested quote +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.
|
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
Nice, someone with programming knowledge. Depending on how you implemented things, you could simulate optimal decision-making by, when you're going to pick the next square,
- look at the previously chosen squares (now tagged as either 1, 5, or 20)
- check a database of all possible games and flag the ones which have those numbers in those locations, say there are N
- assign each of the 20 squares a probability of being a bomb by counting up how many of those N instances have a bomb there and dividing by N (ignore the squares you've chosen so far, of course)
- randomly choose one of the squares with the lowest probability as above
Of course, there's a bit more to it, namely it would be nice to replace the probability mentioned above with some sort of weighted average of the probability of it not being a bomb and the score it gives you, but that should be good enough to out-logic most human players.
Edit: as the above post points out, yeah, it would save you some time to recursively check all squares around a discovered 1, but you don't need to bother if you do the above (you'd eventually recurse through all those squares, as they'd get probability 0)
|
This is just minesweeper, no?
|
On December 24 2011 13:03 Primadog wrote:
This is just minesweeper, no?
It's minesweeper with a scoring system instead of just a fastest time to clear. So yeah, an implementation of an optimal minesweeper strategy would give you the best shot at clearing the board, and clearing the board gives you the best possible score, but sometimes in minesweeper there are logical dead ends where any of 2-3 squares could be a bomb and otherwise you're stuck -- here there's some extra mechanics going on which make some of those squares potentially better than others, since even if they're equally likely to be a bomb they might not be equally likely to score 1 or 5 or 20....
|
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.
|
o o o o o
o o x o x
x o x o o
o o o o o
1 5 5 5 5
5 20 x 20 x
x 20 x 20 5
5 5 5 5 1
132
In normal minesweeper, I pick the corner because the first pick is always safe, and if I get a 1, I have a 1 in 3 chance (assuming the geography doesn't hurt the odds.
Then
1 1 means the cell to the right is safe, and below that is safe, so you start with 4 squares.
1 x means there's (x-1) bombs on the right
Now
1 1 A
B
if A = B, then since they share the same squares except the 3 below, you can clear the 3 bottom adjacent squares to B
so you could have
1 1 A
A
C D E
C, D E are clickable, and moreover, C can be compared to the 1 two above it. If C=1, then you can clear all squares below and to the side of it.
If A or B is clear, then you've cleared at least 2 to 6 more squares.
If B>A, then there are B-A mines bottom adjacent to B
So if we change this strategy to the short side:
1 .5
1 .5 (B-A)/3
A B (B-A)/3
? ? (B-A)/3
which is decent information
If the corner is 2 or more, then you have better odds anywhere the 2 mines aren't.
|
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
