|
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.
|
|
|
|
|
|
EPT
