Re: [Enigma-devel] level submission: minesweeper

[Andreas Lochmann]

Hi,

Ronald Lamprecht schrieb:
> > thank you, this level is really interesting!
> > I particularly like that it's not exactly Minesweeper, but
> > twisted by a typically Enigmian obstacle: You can "open"
> > only those tiles which are adjacent to another "open"
> > tile (or the border).
> >
> > But there's one fundamental problem: It's not always
> > solvable. Minesweeper in itself is not always solvable,
> > and the above peculiarity worsens this ... I thought about
> > this since yesterday, but can't come up with a good
> > idea yet ...
> >
> > Well, maybe some kind of "inverse Minesweeper":
> > You see all tiles and their numbers (numbers also on the
> > mine-fields), have to touch those without mines, after
> > which these numbers disappear. Provided that the border
> > is mine-free and that the set of mine-free tiles is connected,
> > we can proove solvability. But that's not Minesweeper
> > anymore.
>
> I do like the approach of marking the bomb free fields by moving the 
> marble over them. That is a fast input much better than clicking :-)
>
> The problem of unsolvable bomb distributions can be fixed by a simple 
> algorithm. All bomb free fields must be connected to the outside area 
> by direct path. For all bomb free fields of the border mark all 
> reachable fields by a recursive depth run. Marking all visited fields 
> allows to limit the recursive depth run to those border fields that 
> are not yet marked.
>
> This would reduce the problem to bomb distributions that are not 
> "solvable" due to the intrinsic ambiguity.
Not exactly, as you can't reach the diagonal tiles
without stepping on the directly adjacent ones.

> A simple solution would be to set enigma.ConserveLevel to TRUE and 
> provide a panelty that keeps players from misusing it. E.g. an it-weight
> on each resurrection would be fair. That would be o.k. for solving one 
> or two last ambiguities by trial. But it should keep players from 
> using it on a regular basis.
Yes, sounds sensible. Though there still remains
some small probability for unsolvability. I have no
idea how small this is ... though we can estimate it:
One of the typical unsolvable patterns is

***
+?+
+?+
***

where "M" stands for Mine, "+" for free fields or mines,
and "?" for the tiles to be evaluated, one free and one
with a mine. Given 30 mines on the 14 x 11-playground,
the probability for a field to be a mine is 19.5%. We need
seven mines and one free field for the upper pattern,
times two for the two possible configurations of "?" makes
1.73*10^-5. The pattern can happen in 12 x 8 = 96
positions, thus giving a chance of 0.17 % per game.
Same calculation for the pattern appearing in a corner:
 0.195^3 * 0.805 * 2 * 4 = 4.78 %
on a vertical edge:
 0.195^5 * 0.805 * 2 * 2 * 8 = 0.73 %
and on a horizontal edge:
 0.195^4 * 0.805 * 2 * 12 * 2 = 5.59 %
Adds up to 11.3 %.
Assume the same for the horizontal version of the same
pattern, and we get a probability of 21.3 % for an unsolvable
minesweeper from this type of patterns (sounds a lot - did
I make a mistake?)

When introducing ConserveLevel = true as above, we need
three such patterns to render the level unsolvable, which
makes up for approximately 0.97 %, which is too much.
(10^-5 is acceptable in my view, 10^-6 better: Imagine
10.000 players, each player plays the level 10 times.)

When we make sure that there are no mines on the
border tiles, we get a definitely better result:
The probability for a mine in the 12 x 9 center field raises
to 27.8 %, but there can only be 10 x 6 positions for the
pattern, thus
 0.278^7 * 0.722 * 2 * 60 = 1.11 %.
With the horizontal pattern yields 2.21 %, on three trials:
1.08*10^-5. Would be okay. But there are more patterns,
and the higher mine density might strengthen them.

> Of course you are welcome to write an algorithm that rejects ambiguos 
> bomb distributions. This would allow you to give the user a solvable 
> start of a few opened fields, too. But the algorithm might be more 
> complex.
>
> Either way, thanks for your contribution,

Best greets,
Andreas