pattern catalogue

Want to calculate something or share your results?
Post Reply
aradesh
Posts: 87
Joined: Sat Aug 29, 2009 3:37 pm

pattern catalogue

Post by aradesh »

I've been thinking about the idea of writing a computer program to somehow generate all patterns of a certain complexity or deepness.

The most simple kinds of patterns which I call level-1 patterns are the most simple form of logic you can make in minesweeper. Those patterns involving only 1 number. (examples: http://pastebin.com/PJv2xqbS)

For deeper patterns (examples: http://pastebin.com/tiuGkeU2) I have two ideas:

Idea 1) A level n pattern would be a pattern which you can solve by making a guess (by saying a square is a mine or safe) and then following the consequences of this guess using level-(n-1) patterns to draw contradictions. For example the top pattern in my "deeper patterns" list can be solved using this method as a level-2 pattern.

Idea 2) A level-n pattern is a pattern which involves n numbers, and which isn't the union of two lower level patterns. (everything other than my 1st deeper pattern falls into level-3 patterns in this case)

I quite like the second idea, because this is something a computer could search and get a finite list of possibilities. The first idea has problems in that there won't be a finite number of possible patterns of each deepness, but perhaps only a finite number of "concepts". I'd imagine that the class of all level-n patterns in both ideas would produce the class of "all solvable patterns" eventually...

Anyone got any ideas of other ways to categorize "deepness" or can think of any nice patterns to add to my list of "deep patterns"?
misio
Posts: 5
Joined: Mon Dec 03, 2012 3:24 am

Re: pattern catalogue

Post by misio »

aradesh,

I've got a database of perfect play; up to 10 cells. 10 cells means unknowns plus meaningful opens,
so, for example, if you've got 8 closed cells surrounded by a wall of mines with two holes in it -- here's your ten.

It's 25M gzipped file. Let me know.

misio
qqwref
Posts: 125
Joined: Thu Sep 23, 2010 4:17 pm

Re: pattern catalogue

Post by qqwref »

See if you can get that uploaded somewhere (an upload site) - I think several people here would be interested in taking a look.
NF player. Best scores 1-10-39.
misio
Posts: 5
Joined: Mon Dec 03, 2012 3:24 am

Re: pattern catalogue

Post by misio »

qqwref,

what do you plan to do with the data? So far nobody screamed "yay! want it!" but you :)

misio
User avatar
Tjips
Posts: 74
Joined: Sat Apr 18, 2009 1:15 am
Location: South Africa

Re: pattern catalogue

Post by Tjips »

Well, this forum is a bit more relaxed than others out there :D.

I can guarantee you that there are a few people watching this thread develop with intrigued looks on their faces. I didn't feel the need to reply here up to this point as the interaction is going swimmingly :). I'm not gonna say I'm screaming "Yay!", mostly because I'm less excited by databases of patterns, but I'm definitely curious to see what you've made/found.

Also, no-one knows what you mean when you say 'database of perfect play'... Might help if you perhaps gave an example, like a screenshot of a few of the patterns, or maybe even just a useful description...

Anyhow, I'll be watching ;)
The number of minesweeper boards:
Exp: 140055249834355336357264746443955277014822625680974475320364702381803619892657792049596418323789908370400 (1.4e104)
Int: 13115156192346373485000211099954895788134532256 (1.3e46) &
Beg: 18934455246 (1.9e10)
:D
qqwref
Posts: 125
Joined: Thu Sep 23, 2010 4:17 pm

Re: pattern catalogue

Post by qqwref »

Yeah, it's pretty much what you'd expect, just wanna take a look and see if you found any really interesting patterns :)
NF player. Best scores 1-10-39.
misio
Posts: 5
Joined: Mon Dec 03, 2012 3:24 am

Re: pattern catalogue

Post by misio »

OK, got it :) Totally forgot y'all speed junkies here :)

What I meant as a perfect play is a play which gives the best chance of solving the board. Not necessarily
the fastest way. For example, with one mine undecided,

Code: Select all

???X
X3XX
guessing in the corner (0,0) or on the rightmost cell (0,2) gives you a two thirds chance, middle (0,1) -- one third.

A little more dramatic example, three mines left.

Code: Select all

????XX
?????3
??X??2
??X42X
13X
For a human it's obvious what to do, but bear with me here :)

Simple guessing might give you a very bad result, 4.5% chance if you accidentally click on (2,4) corner.

Another strategy is to click where there's no mine, duh :) Clicking, say, at (0,0) gives you 45.4% chance. Pretty
good, but not perfect.

Perfect, obviously, is to take risk immediately by breaking through at (3,0) or (3,1). 50% chance of explosion
immediately, but if you guessed right, you're safe and clear :)

And an example from database, two mines left.

Code: Select all

???X
???X
???X
2XXX
The only correct choice is to play in the opposite corner, (0,2). If you click there, and only if you click there,
you are safe if you don't explode on the spot, 6/7 chance. Anything else is not good enough, for example (0,0)
might run into

Code: Select all

01?X
12?X
??6X
2XXX
, oops.

With 3 mines left best is another corner, (2,2) for 52% chance. 4 -- two options, (1,2) and (2,2) for 31%.
5 -- corner does not work anymore, playing on the side (1,2) gives 23% chance. With 6 mines 1/7 chance,
either side (1,2) or breakthrough (2,1). Not (2,0)! 7 mines -- same 1/7, options are (2, 2), (2, 0), (1, 2), (2, 1).

Enjoy :)
User avatar
Tjips
Posts: 74
Joined: Sat Apr 18, 2009 1:15 am
Location: South Africa

Re: pattern catalogue

Post by Tjips »

Ok, this looks quite interesting... And like quite a bit of work...

Let me sum up what I understand: In each position you consider every possible unknown square and evaluate what the chances are of completing the board if you start by guessing at that square. If this is what you've done then I commend your ambition...

You're right, most of us are 'speed junkies' :D. This doesn't mean we haven't thought about this kind of stuff though. It only means that what we think about we tend to apply in the context of efficiency and speed during actual play. I must admit that I hadn't really noticed this tendency in my musings before your post. I will defend my approach, though, by stating that I'm someone very much geared to application when it comes to research. I like understanding things that I can somehow play with in real life, which makes efficiency a much more enticing subject in the case of minesweeper.

This, of course, leads me to immediately start asking questions applicable to actual play :D. Is it a general trend in your database that "breaking through" is the better strategy? Also, what happens in symmetric situations like an untouched exp board? I imagine the best options would congregate at either the corners, edges, or rest of the board, but do they always congregate in the same population (i.e., always edges) or is there a relation between the density of mines on the board and the population the best solutions congregate in (e.g., low density = edges best; high density = corners best)? What happens on a board that is a rectangle and not a square? Does one direction stand out from the other? Also, something I'm very curious about, is how does the curve of survival odds vs. density look? I've always wondered whether it changed gradually or if there is some point at which the curve kinks.

Granted, I do have thoughts on some of those questions, and know some of their answers, but it would still be intriguing to see what your database reflects.

I am also extremely curious on how you actually managed to generate your database. Would be interesting to see how far one could push the idea... Also, how did you deal with completely isolated regions? Let's say you had two such regions, did you take into account their continued interdependence, i.e., the fact that they constitute a single guess?

Anyhow, that's all I have for now :D. Look forward to seeing the thing itself...

P.S. How are you storing your database? Perhaps you could consider generating a .mbf file for each situation and a simple accompanying .csv file listing the probabilities for each square. If I were to delve into your database an easily input method of storage would be great :D.
The number of minesweeper boards:
Exp: 140055249834355336357264746443955277014822625680974475320364702381803619892657792049596418323789908370400 (1.4e104)
Int: 13115156192346373485000211099954895788134532256 (1.3e46) &
Beg: 18934455246 (1.9e10)
:D
misio
Posts: 5
Joined: Mon Dec 03, 2012 3:24 am

Re: pattern catalogue

Post by misio »

Tjips,

Thanks for kind words :-)

As of your questions. "Breaking through" is definitely not always the best strategy; and database wouldn't say much about it. It does not contain enough of "pool + front" patterns :-(

As of starting position, my experiments say that your best option in case you can explode immediately or are not guaranteed an opening is corner, for completion rate of above 30%. If you are guaranteed an opening -- then (3,3) spot, assuming corner is (0,0). Completion rate is above 50% on large board. I still need to incorporate database into solver :-)

The database, unfortunately, grows exponentially with number of cells :-( Optimization should make 13-cell database feasible, like eliminating patterns impossible In practical play, independent separated regions etc. And yes, if regions are separate they are not necessarily independent, one has to consider all points :-)

The database is stored as a set of adjacency graphs. So I can only generate a/set of example planar patterns. Let me do some optimization first :-)

Good luck to us,

misio
Post Reply