Fastest Minesweeper ever! What are the chances?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Sableagle
Ormurinn's Alt
Posts: 1642
Joined: Sat Jun 13, 2015 4:26 pm UTC
Location: The wrong side of the mirror
Contact:

Fastest Minesweeper ever! What are the chances?

Postby Sableagle » Fri Sep 16, 2016 7:34 pm UTC

FastestMinesweeperEver.png
FastestMinesweeperEver.png (4.08 KiB) Viewed 4237 times


I'm a little rusty but nCr = n!/(n-r)!r! isn't it?

That's:
64!/(64-10)!10! = 1.515 * 1011 for Beginner;
256!/(256-40)!40! = 1.049 * 1047 for Intermediate;
496!/(496-99)!99! = 2.100 * 10106 for Expert
... and ridiculously huge for a custom grid that covers the whole screen.

I'm curious.

How would you calculate the odds of getting a one-click win as shown above?
Oh, Willie McBride, it was all done in vain.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3274
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Fastest Minesweeper ever! What are the chances?

Postby Soupspoon » Fri Sep 16, 2016 7:42 pm UTC

I think you have to take into account that the first square you reveal is never a mine (whether or not that means it is a neighbour-square that only reveals a number or a non-neighbour from which a flood-reveal propogates). But whether that's because it shifts any first-click boom somewhere else before you get to see it or that it waits to see where you clicked before placing any mines, I don't know. You'd have to ask Monty Hall about that, perhaps.. ;)

(But it might mean that it is 63!/(63-10)!10! = ... for Beginner, etc, if the rest of that is right...)

ThemePark
Posts: 450
Joined: Fri Jun 27, 2008 5:42 pm UTC
Location: Århus, Denmark

Re: Fastest Minesweeper ever! What are the chances?

Postby ThemePark » Fri Sep 16, 2016 8:48 pm UTC

For that particular setup, there's 376 empty cells and you could click anyone of them to get that result. So for that, it's 376/499 or 75,35 %.

But it's only possible to win in one click on those setups where all empty cells are connected in one big shape. So you "only" have to concern yourself with those, and for each of them the odds would be (board size-bombs-cells with numbers on them)/board size.

The bombs don't have to be lumped into one shape though, they can be divided. But short of iterating all ways of placing the empty cells all together, I don't see how it's possible to calculate the odds for the entire game of one particular board size.

Oh, and Soupspoon, it is very possible to hit a bomb in the first click.
I have traveled from 1979 to be a member of the unofficial board Council of Elders. Phear M3

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3274
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Fastest Minesweeper ever! What are the chances?

Postby Soupspoon » Fri Sep 16, 2016 9:21 pm UTC

ThemePark wrote:Oh, and Soupspoon, it is very possible to hit a bomb in the first click.

Might depend on the version of (Windows) Minesweeper, but I am sure that it quite famously hasn't been possible. Even setting to Custom parameters with whatever settings gives you most mines per grid area for maximum challenge, for ultimate testing, I've never had a first-click1-BOOM! happen and, given the number of games played at this setting (and almost inevitably lost, but only from the second reveal onwards), when I was a definite Minesweepe Junkie, I think that I'm statistically confident in that assertion.

(For Advanced difficulty, my speed-run opening move tends to be two rapid and random clicks in different halves of the board. If lucky, that floods over many non-mine spaces (never yet all of them, sometimes very very few are left to discover, though, even if still ambiguous) and I can then start using logic, or guesswork for the obvious insolubly ambiguous (behind a "wall") to get them out of the way. If unlucky, the second click detonates (if unlucky and stupid, first click reveals told me it would be so, but in my rush to get the advantage I let myself fall on my sword). Never a first click failure.)

1 First revealing click, that is. Flagging/Questionmarking, revealing elsewhere (safely!) then de-marking and clicking-for-real the original tile still possibly/likely gives a boom on the originally marked tile. Unless the true-first-reveal shows that your first choice is definitely safe, naturally.
Last edited by Soupspoon on Fri Sep 16, 2016 9:35 pm UTC, edited 4 times in total.

User avatar
Eebster the Great
Posts: 2978
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby Eebster the Great » Fri Sep 16, 2016 9:26 pm UTC

The position of all the mines is set before your first click. If your first click is over a mine, that mine will be moved to the top left corner instead. If there is already a mine there, it will go one square to the right, and so on.

In early releases of Minesweeper on DOS-based Windows kernels, Beginner boards were 8x8 but one-click games were not normally possible. This is because boards were not generated from the entire space of legal boards but from a couple of small cycles which only generated 48,624 distinct boards under normal conditions. However, boards could be changed using the method mentioned above. In extremely rare cases, it is possible to change a board into a one-click board on which your first click is a solution, leading to the One Click Bug. There were also other ways to force nonstandard boards by opening two games simultaneously, but that's not really relevant here.

For releases on OSes with NT-based kernels and third-party clones, a much more sophisticated PRNG is used and a far larger of number of boards is possible. It is unknown however if every legal board is possible or if all possible boards are equally probable. In particular, clicking on a mine still moves that mine to the top left corner, ultimately making boards with a mine or multiple mines at the far left of the top row more likely than other boards. This should increase the probability of one-click games somewhat, and the page linked above gives two examples of one-click Beginner (9x9) games on XP, one "natural" game in which no mine was moved to the corner, and another "bugged" game in which a mine was moved to the corner, causing the timer bug.

The exact board you showed below is only one single board, so if the program uses a properly distributed RNG, the probability of it occurring discounting symmetry or anything else is simply the reciprocal of the number of boards. In this case, it is Expert, 16x30=480 squares with 99 mines, so the number of possible boards is simply n = 480 choose 99 = 480!/(99!(480-99)!) = 560220999337421345429058985775821108059290502723897901281458809527214479570631168198385673295159633481600 ≈ 5.6 × 10104. Since this board cannot be generated by moving a mine but must arise naturally, the probability that it arises is 1/n ≈ 1.8 × 10-105.

However, actually winning this board in one click depends where you click. For example, if you click in the bottom left corner, you will simply get a 3, moving the mine to the top left, and giving you a decent shot of simply losing on your next click. Clicking on any mine or on any number will not win immediately. Thus only 360 of the 480 spaces result in a one-click win, meaning if you play a randomly generated board and click a random space, your probability of winning with this particular board is 3/(4n) ≈ 1.4 × 10-105.


A more interesting question though is how many one-click win boards there are. Discounting first-click mines, this should be computable, though I'm not exactly sure how to go about it. Counting first-click mines makes it even more complicated.


EDIT: The board you posted is 16x31, which is super weird. Expert boards are usually 16x30 with 99 mines for modern purposes, or 24x30 with 200 (or 225) mines for super-expert. Anyway, for the 16x31 board, instead of 480 choose 99 boards, there are 496 choose 99 boards, or 2.1 × 10106, as above. Therefore the probability of getting that exact board before clicking is (480C99)-1 = 4.8 × 10-107, and to win on the first click with that exact board is 376/496 = 47/62 ≈ 0.76 times as much.
Last edited by Eebster the Great on Fri Sep 16, 2016 10:22 pm UTC, edited 3 times in total.

Tub
Posts: 378
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby Tub » Fri Sep 16, 2016 9:49 pm UTC

ThemePark wrote:Oh, and Soupspoon, it is very possible to hit a bomb in the first click.

I've never seen it happen on the old windows-based implementations, even on custom games where the field is like 99% bombs. It seemed like the program created a random game the moment you clicked the first field, and discarded any games with a bomb under your cursor. You could notice, because as you increased the bomb count, there was a progressively longer delay between the first click and the uncovering of the first tile.

But then again, there's no authoritative implementation of minesweeper, so YMMV.

496!/(496-99)!99! = 2.100 * 10106 for Expert

That math seems sound for the exact game you pictured. There are of course other 1-click-solvable games, but counting them seems difficult, so I'm not going to try.

Allow me one side note: that chance is around 1 to 2^237, which means that any random number generator with less than 237 bits of state is unlikely to ever produce a sequence resulting in your game. The common non-cryptographic RNGs of the previous millennium all had a state of only one word (at most 32 bits back then), so for any minesweeper before win2k, it's very likely that your game cannot be generated at all.

User avatar
Eebster the Great
Posts: 2978
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby Eebster the Great » Fri Sep 16, 2016 10:25 pm UTC

Tub wrote:Allow me one side note: that chance is around 1 to 2^237, which means that any random number generator with less than 237 bits of state is unlikely to ever produce a sequence resulting in your game. The common non-cryptographic RNGs of the previous millennium all had a state of only one word (at most 32 bits back then), so for any minesweeper before win2k, it's very likely that your game cannot be generated at all.

Yeah old versions used a 16 bit seed and generated fewer than 65,000 boards. Newer versions probably use 32 or 64 bit seeds, but I doubt any would use a full 256 bits, and even if they did, I doubt they would map onto all the possible boards, and even if they did, I very much doubt they would do so uniformly. But since nobody seems to know what the RNG is, statistically we have to treat all possibilities as equally likely anyway.

User avatar
Soupspoon
You have done something you shouldn't. Or are about to.
Posts: 3274
Joined: Thu Jan 28, 2016 7:00 pm UTC
Location: 53-1

Re: Fastest Minesweeper ever! What are the chances?

Postby Soupspoon » Fri Sep 16, 2016 11:42 pm UTC

Entropically, though, a cluster (whether rectangular in a corner, a 'full border' that you clicked within the empty centre of or a far wavier shape) is numerically more unique.. *cough* ...than all the possible slapdash 'noisy' distributions that defeat oneclickwinability by the 'surface' of neighbourcells occupying and thus covering far more gaps behind which unrevealed (first-order) solutions may yet lurk.

(From the top of my head. The worst case scenario may well be (unbeknownst to the player) all 2x2 clusters positioned with two un-mined cells-worth of columns/rows between them all; all over the shop there's two-neighbour pairs abutting 2-neighbour pairs, 1-neighbours clustered as 2x2s at the near meeting of four corners can be open up their 1-neighbour compatriots, but the 2-neighbours don't reveal which of three positions the hindmost bomb might be in, if there's a possibility that cross-gap 2s might be referencing the same 'hindbomb', at the point in the reveal where you can't work out/guess the likelihood from the undiscovered count. Between that (unlikely high regularity) pattern and the least neighbourful combination (an entire edge lined by bombs, by whatever necessary number deep; the most ideal one-click solution) there's a whole host of godawful combinations with sufficient neighbourfulness to block even 'perfect' play from a guaranteed solution, superficially identical with countless1 kin given the initial or even continuing reveal.)

But maybe that's the way to count them. Assuming bombs, B, on an XxY grid has both X and Y as factors (for simplicity at this stage, ideally) then start with four layouts (flush and level top-lining, bottom-lining, left-lining and right-lining solutions, with both short-side layouts actually featuring least neighbour-cells), then morph to more jagged-edged variations by dislocating individual mines around the various exposed sides, pairs of mines both together and independently, and forwards with greater and greater numbers departing more combinations of origin. Include (unless too dense to leave workable space in the centre) all four-edges bordering (flatly) patterns, and even tendrils and 'minor floaters' into the interior, so long as they don't cause opposing neighbour-cells to meet and isolate separate zero-neighbour washes from each other.

Once you have done that, you (should?) have enumerated all one-click solubles. From the factorially-inclined totality of combinations, you have your proportion/likelihood thus calculated.

But this 'simple' initial count is not so trivial. Just perhaps more trivial than my other ideas.



1 Practically, that is. Not mathematically.

hujackus
Posts: 79
Joined: Sat Aug 22, 2009 4:30 am UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby hujackus » Tue Sep 20, 2016 12:52 am UTC

I've played well over 40,000 expert games over the last 4 years with a success rate hovering between 23% and 24% (win7 version). This thread has sniped me away from what I was planning on doing today, but unfortunately my time online has run out. I'm interested in finding out more about how the RNG is used in generating a pattern of mines. I'll be back.

lorb
Posts: 404
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Fastest Minesweeper ever! What are the chances?

Postby lorb » Tue Sep 20, 2016 7:58 pm UTC

hujackus wrote:40,000 expert games over the last 4 years


so about 30 games every day? for four years. how does it never get old?
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

hujackus
Posts: 79
Joined: Sat Aug 22, 2009 4:30 am UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby hujackus » Wed Sep 21, 2016 5:14 pm UTC

lorb wrote:so about 30 games every day? for four years. how does it never get old?

I checked my files again, and it's closer to 48 thousand games since mid 2013. I don't even play everyday so that equates to more 50-100 games in a single day. If I have nothing to do, or if I'm stressed out, I can mindlessly play for a few hours straight. Sometimes when I set a new time record, I don't find out about it until a few games or days later. My best time is 99 seconds, but I only have a hand full of sub 110 times.

User avatar
Flumble
Yes Man
Posts: 1996
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby Flumble » Wed Sep 21, 2016 6:07 pm UTC

hujackus wrote:I've played well over 40,000 expert games over the last 4 years with a success rate hovering between 23% and 24% (win7 version).

Have you tried Tatham's minesweeper? It has a checkbox for solubility, so you don't have to guess the last 1-3 mines. :D (unfortunately, it doesn't listen to ctrl or shift, but at least it has the uncover-if-the-right-number-of-mines-are-marked)

hujackus
Posts: 79
Joined: Sat Aug 22, 2009 4:30 am UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby hujackus » Wed Sep 21, 2016 6:39 pm UTC

Flumble wrote:
hujackus wrote:I've played well over 40,000 expert games over the last 4 years with a success rate hovering between 23% and 24% (win7 version).

Have you tried Tatham's minesweeper? It has a checkbox for solubility, so you don't have to guess the last 1-3 mines. :D (unfortunately, it doesn't listen to ctrl or shift, but at least it has the uncover-if-the-right-number-of-mines-are-marked)

I just tried it right now. It looks like a pretty good javascript version of the game, but having an undo button and a solve instantly button sitting at the top takes all the joy out of winning a game. Maybe if the solve button used a computer algorithm to actually solve the board over a period of a few seconds, it might be valuable to me. I do like the 'ensure solubility' checkbox you mentioned. If I re-write Tatham's minesweeper I'd probably keep that, add statistics and remove all traces of the the undo feature.

User avatar
ThirdParty
Posts: 311
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: Fastest Minesweeper ever! What are the chances?

Postby ThirdParty » Mon Sep 26, 2016 4:57 am UTC

Eebster the Great wrote:A more interesting question though is how many one-click win boards there are. Discounting first-click mines, this should be computable, though I'm not exactly sure how to go about it.
Hmm. Let's assume a 16x30 board (480 total tiles) with 99 mines. (So, 381 non-mines.)

Here are two facts about every one-click-win board:
  • The board has a contiguous block of at least 76 "zeroes"--i.e. tiles with no adjacent mines. (Because we have to reveal 381 tiles at once; the first zero clicked reveals at most 8 tiles, and subsequent zeroes activated reveal at most 5 new tiles each.)
  • Every one of the 381 non-mine tile must be adjacent to a zero. From this it can be inferred that for any given non-mile tile, at least one of the following conditions is true:
    1. The tiles west, northwest, and north of it are all non-mines.
    2. The tiles north, northeast, and east of it are all non-mines.
    3. The tiles east, southeast, and south of it are all non-mines.
    4. The tiles south, southwest, and west of it are all non-mines.
I've run out of time to think about it tonight, but maybe these facts could be used to put an upper bound on the probability of a random board being winnable in one click?

EmelinaVollmering
Posts: 11
Joined: Tue Oct 18, 2016 10:24 am UTC

Re: Fastest Minesweeper ever! What are the chances?

Postby EmelinaVollmering » Tue Oct 18, 2016 11:47 am UTC

It all depends on the algorithm that is created by microsoft in this case. Second, you can't draw the probability, if you don't know multiple factors. In this case, you know how many mines are there and how many are left hidden. Let say, the algorithm favors all the hidden points equally.

If the distribution of mines are equal in all the regions, we will probabilities over whole probability.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests