Quasi-empirical estimation of expected board completion rate

Want to calculate something or share your results?
User avatar
Tjips
Posts: 72
Joined: Sat Apr 18, 2009 1:15 am
Location: South Africa

Quasi-empirical estimation of expected board completion rate

Post by Tjips » Thu May 31, 2012 12:10 pm

An interesting question came up in the guestbook recently:
Arjádre wrote: Does anyone know of experiments to calculate the optimal percentage of wins on expert, intermediate, and expert (assuming perfect gameplay)? I'd like to compare to the results I'm getting with my solver.

I'm pretty sure I've read someplace that a win percentage of around 25-30% is possible on expert. I just have no idea where that article is!

Thanks!
This got me thinking on the subject, and I think I've basically figured out how we can make a pretty decent quasi-empirical prediction of what the completion rate of a player solving perfectly should be. To start of it's important to note that the problem consists of two parts, contingent on a few ground rules I set at the outset.

Let's consider a player who begins a game by guessing randomly, and that the revealed numbers aren't taken into account in calculating the probability of hitting a mine/opening on the next click, then the probabilities associated with the three possible outcomes of the nth click are:

Code: Select all

P_failure(n) = p/(A-n),
P_success(n) = N(0)/(A-n), and
P_null(n) = (A-n - p - N(0))/(A-n),
where P_failure is the chance of hitting a mine, P_success(n) is the chance of hitting an opening (i.e., a zero), P_null is the chance of hitting a number in [1,8], p is the number of mines on the board, A is the area of the board, and N(0) is the number of 0's on the board. Notice that the three probabilities add to 1.

Considering an ensemble of games now (all with identical parameters, i.e. identical p, A, and N(0)), it is easy to see that the proportion of successes to failures is simply equal to the ratio p/N(0). Oh, and a success here is defined as hitting an opening, as hitting an opening would allow deductive solving to commence. Most players start this way in my experience, so it should be accurate enough...

Ok, that's the first of the two parts of the calculation of expected completion rates (I know this is scatter-brained, but I didn't sleep and my house almost burned down, so just deal :P ). The second part is simply taking account of the number of forced guesses the player is going to see on avg. during a game. Then you simply take the two figures and multiply them.

Now, I call this quasi-empirical as the two important numbers in this calculation are at this point only attainable via simulation, namely the number of forced guesses, and the number of 0's on a board (which will of course loosely be a function of 3bv). Fortunately the former has already been touched upon by qqwref in this thread.

An example ballpark would look like this:
For exp qqwref's thread gives around 0.8 50-50 guesses per board, meaning that once we've actually hit an opening our chance of finishing the board is around 57%. Now, lets consider an avg 3bv of about 171 (we're only ballparking, relax). This means that about 210 squares aren't 3bv or mines, or in other words part of openings or opening rims. Lets further assume some totally arbitrary ratio of number of squares on the rim to the number of 0's, something like 9 0's out of every 10 opening squares. This means that we have 189 0's on our fictitious board. Thus the chance of safely hitting an opening is about 52%. Multiply these two numbers (properly, of course), and we get an expected completion rate of 29,6%, or basically 30%.

Ok, granted, half the numbers where pulled out very blatantly from dark places, but the approach, I think is sound. I am of course not a statistics boffin, seeing as I actually failed the subject once, so I might be wrong on any number of points :P. Anyhow, that's how I approached the problem...

P.S., I'll try and find time somewhere to get a distribution for number of zero's vs 3bv... Should be a nice narrow 2D normalish distribution...
The number of minesweeper boards:
Exp: 140055249834355336357264746443955277014822625680974475320364702381803619892657792049596418323789908370400 (1.4e104)
Int: 13115156192346373485000211099954895788134532256 (1.3e46) &
Beg: 18934455246 (1.9e10)
:D

Quate
Posts: 11
Joined: Thu Mar 29, 2012 11:22 pm
Location: California

Re: Quasi-empirical estimation of expected board completion rate

Post by Quate » Thu May 31, 2012 10:23 pm

I'm curious as to what would happen if, instead of disregarding any initial null numbers (1-8), one would make the best possible random guess. Obviously, a 1/8 chance is a much more favorable one to the density of an expert board if one were to find a one by clicking randomly. I'm sure this wouldn't help too much, but would definitely improve one's board completion rate a little bit.
Best Times: 1.25-17.99-71.03 = 90.27!
NF Times: 1.25-24.27-114.26 = 139.78

Best 3BV/s: 4.604-3.051-2.349 = 10.004!
NF 3BV/s: 3.232-2.424-1.392 = 7.048

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

Re: Quasi-empirical estimation of expected board completion rate

Post by Tjips » Fri Jun 01, 2012 9:23 am

Well you are absolutely right that guessing by taking the revealed numbers into account is a good idea, even if you determine that guessing around it is bad. The question is simply what your goals are while guessing, and the proper course of action is dictated by that. Let's take your example of a revealed 1. The probability of hitting a mine around it is 1 in 8, as you stated, but that's not the only outcome of importance. In the discussion I gave the important goal throughout the random clicking part of the solve as hitting an opening (thus a zero). In the case of the 1 the chances of hitting a zero around it are at most 5 in 8. In the above example I ballparked the ratio of 0's to surface area as 189/480 which comes out to over 3 in 8 (3.15). The 5 in 8 is also very optimistic and almost certain to be lower on any actual board (certainly comparable to 3 in 8 if not lower). Furthermore, the ratio p/N(0) for exp is about 0.52, which means that once the probable number of zero's around the 1 drops below 2.08 it becomes better to guess elsewhere (ito finding 0's). (Corollary: Until it reaches 2.08 it probably is better to guess around the one :D ). BUT, you also brought up guessing around the 1 in the context of density, which changes things quite a bit. In density the number of zero's are usually very low, so your chances of hitting an opening go down significantly (remember, it goes like p/N(0)), and the goal of you play is never really hitting and opening. The goal in density is simply to stay alive, and in some cases (like beg-49) you don't even stand much of a chance of finding a part of the board to apply logic to. Thus the best strategy is to make all deductive moves possible and take the lowest risk possible. Which differs from the opening of a speed exp game as taking the lowest risk is replaced by "just click like mad coz there're enough boards to spare which have nice, juicy openings for you to go Bolt on...".

So, in the broadest sense, that should of course be taken into account, but in the context of speed-solving of boards on which the latter strategy are appropriate and solving rate not the goal, it's not really of much importance imo :D

P.S., I know this was again nice and scatterbrain, but I don't care :P
The number of minesweeper boards:
Exp: 140055249834355336357264746443955277014822625680974475320364702381803619892657792049596418323789908370400 (1.4e104)
Int: 13115156192346373485000211099954895788134532256 (1.3e46) &
Beg: 18934455246 (1.9e10)
:D

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Wed Oct 17, 2012 10:29 pm

I'm considering writing (once my nascent strategy page settles down a bit) a test suite to evaluate guessing strategies. It would have perfect play but would let you define a set of prioritized strategies for the guessing parts (e.g. guess in corner for first move, then guess squares with a percentage better than 50%, then guess randomly along an edge, etc.). It would then compete strategies that people submit by running thousands of trials against each and seeing which came out on top.

I think it would be very possible that a human could still have a better percentage than an algorithm -- there may be strategies like "guess in the narrowest part of the blob of uncleared squares" that would be very difficult to capture in an algorithm. Also, the optimal algorithm might be very difficult to apply to human play (e.g. if it involves counting the remaining unflagged mines, this is very difficult for us NFers). But this test suite could generate a lower bound on solving and probably at least suggest good approaches for humans.

It would also be rather amusing, I think, to develop a minesweeper version for humans that does all the perfect play, and leaves only the guessing part for you to mouse-click...

User avatar
Tommy
Posts: 223
Joined: Mon Dec 01, 2008 9:22 pm
Location: Vienna

Re: Quasi-empirical estimation of expected board completion rate

Post by Tommy » Thu Oct 18, 2012 6:34 am

computronium wrote:(e.g. if it involves counting the remaining unflagged mines, this is very difficult for us NFers).
Same for flaggers. We don't flag everything, far from it, making this equally unfeasible.
computronium wrote:It would also be rather amusing, I think, to develop a minesweeper version for humans that does all the perfect play, and leaves only the guessing part for you to mouse-click...
That would actually be awesome! If you want to improve in that specific area, this would give you only guesses, and remove lots of frustration, making evaluating guess situations less emotional and more rational.
Don't anthropomorphize computers - they don't like it.

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Wed Oct 31, 2012 5:12 am

Tommy wrote:Same for flaggers. We don't flag everything, far from it, making this equally unfeasible.
Good point. It's been a long time since I flagged a mine :)
Tommy wrote:That would actually be awesome! If you want to improve in that specific area, this would give you only guesses, and remove lots of frustration, making evaluating guess situations less emotional and more rational.
I have plans now to actually build this, just to satisfy my curiosity. I have a feeling it will be rather not fun to play at all, actually; it leaves only the least fun (IMO) part of the game up to the human. I might try to make it more interesting by shading the uncleared squares that are adjacent to cleared squares, according to their likelihood of being a mine (based on their immediate neighbors only, not the overall remaining mine count or anything).

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

Re: Quasi-empirical estimation of expected board completion rate

Post by qqwref » Wed Oct 31, 2012 4:51 pm

Instead of having it play "normally" (i.e. guess wrong and you blast) it might be more fun to have a higher-density game where you just get an error for each mine you hit, and a success for each time you guess right and/or complete a pattern. So then the game would serve up random guess patterns (generate a game, open an opening, solve as much as possible, hand off to player) and you would be scored on your error-to-success ratio. A perfect ratio would be impossible but trying to optimize it over a large number of games would be quite interesting and could be very good practice.
NF player. Best scores 1-10-39.

EWQMinesweeper
Posts: 410
Joined: Sun Nov 30, 2008 11:50 pm

Re: Quasi-empirical estimation of expected board completion rate

Post by EWQMinesweeper » Mon Nov 12, 2012 4:24 pm

Tjips wrote:we get an expected completion rate of 29,6%, or basically 30%.
finished 27 out of 100 games today. lost 2 games because of careless mistakes and 5-10 times i had no motivation to think about where to guess.
„Das perlt jetzt aber richtig über, ma sagn. Mach ma' noch'n Bier! Wie heißt das? Biddä! Bidddää! Biddddäää! Reiner Weltladen!“

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Tue Nov 13, 2012 10:42 am

EWQMinesweeper wrote:finished 27 out of 100 games today. lost 2 games because of careless mistakes and 5-10 times i had no motivation to think about where to guess.

Certainly interesting. But I am not convinced that one sample compared against someone else's guestimate proves the point. When I write the guessing strategy evaluator (Real Soon Now [tm]) that does perfect play until forced to guess, we'll be able to compare completion success rate of the just guessing randomly strategy against other strategies. Any bets on the results? I'm betting we can improve on just guessing by 5-10% at least.

EWQMinesweeper
Posts: 410
Joined: Sun Nov 30, 2008 11:50 pm

Re: Quasi-empirical estimation of expected board completion rate

Post by EWQMinesweeper » Tue Nov 13, 2012 5:24 pm

have you watched the games? i doubt that any guessing strategy would have won more than 35 games. just have a look at the replays and let me know where you would have clicked elsewhere and why.
„Das perlt jetzt aber richtig über, ma sagn. Mach ma' noch'n Bier! Wie heißt das? Biddä! Bidddää! Biddddäää! Reiner Weltladen!“

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Wed Nov 14, 2012 1:37 am

EWQMinesweeper wrote:have you watched the games? i doubt that any guessing strategy would have won more than 35 games. just have a look at the replays and let me know where you would have clicked elsewhere and why.

I haven't -- I'm running on a Linux box, and sorin's recorder/player seems to be built around Windows. Do you know if these files are readable by any *nix programs? I'm hoping to eventually build in the ability to parse them in the suite of Minesweeper stuff I have planned -- which includes Yet Another player -- but it may be a ways off (I'm still plugging away on the minesweeper patterns web page nightly based on everyone's input and will be unveiling the revamped version soon).

I'm hoping to make the guessing strategy evaluator a shared effort, so even if I couldn't currently improve on your just-guess approach, that doesn't mean no one could. Can I ask, what approach DO you take? Do you start in the same place? When you get stuck, do you guess near to areas you've already cleared, or randomly in other uncleared areas? Along the edges/corners, or in the middle?

EWQMinesweeper
Posts: 410
Joined: Sun Nov 30, 2008 11:50 pm

Re: Quasi-empirical estimation of expected board completion rate

Post by EWQMinesweeper » Wed Nov 14, 2012 5:59 pm

can't help you with whether they are readable by *nix stuff. maybe people like tkolar or qqwref have some ideas.

my guessing strategy is mostly intuitive. i can't really say why i click a certain square, other than 'this seems like it might work out nicely'.
„Das perlt jetzt aber richtig über, ma sagn. Mach ma' noch'n Bier! Wie heißt das? Biddä! Bidddää! Biddddäää! Reiner Weltladen!“

aradesh
Posts: 90
Joined: Sat Aug 29, 2009 3:37 pm

Re: Quasi-empirical estimation of expected board completion rate

Post by aradesh » Wed Nov 14, 2012 11:12 pm

computronium wrote:
EWQMinesweeper wrote:have you watched the games? i doubt that any guessing strategy would have won more than 35 games. just have a look at the replays and let me know where you would have clicked elsewhere and why.

I haven't -- I'm running on a Linux box, and sorin's recorder/player seems to be built around Windows. Do you know if these files are readable by any *nix programs? I'm hoping to eventually build in the ability to parse them in the suite of Minesweeper stuff I have planned -- which includes Yet Another player -- but it may be a ways off (I'm still plugging away on the minesweeper patterns web page nightly based on everyone's input and will be unveiling the revamped version soon).

I'm hoping to make the guessing strategy evaluator a shared effort, so even if I couldn't currently improve on your just-guess approach, that doesn't mean no one could. Can I ask, what approach DO you take? Do you start in the same place? When you get stuck, do you guess near to areas you've already cleared, or randomly in other uncleared areas? Along the edges/corners, or in the middle?
Re the joint effort: Sounds like something I would be willing to help with. I have a bunch of ideas I never get around to doing, and sounds as though we might have some overlap here, but working as a team things would hopefully move faster and with less breaks of boredom. :P I'm sure maybe some others would be interested also.

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

Re: Quasi-empirical estimation of expected board completion rate

Post by Tjips » Thu Nov 15, 2012 1:01 pm

Nice to see this getting some discussion :D.

computronium is, of course, right in saying that EWQ's set of games isn't really submittable as proof for the accuracy of my little guess, but EWQ didn't really present it as such either. It's still fun to have his completion rate be close to what I predicted :P.

On a more PTFO note, I would like to address some things I notice about your planned study of how guesses pan out in minesweeper. The first thing I'd like to point out is that the knowledge out there about guesses is actually far more comprehensive than you seem to think. People like tkolar and EWQ have quite a reservoir of intuition and strategic awareness concerning which guesses are better to take and why. I'm not claiming to have the same level of intuition on this subject, but I can most definitely keep up when they start explaining these things :D. Disclaimer: The main reason I am so in the dark on guessing strategies is that I shy away from globally unforced guesses. Many players adopt a strategy which doesn't place such a high premium on guess minimization, meaning that they're more willing to guess in situations where playing around the effective guess would simply cost too much time.

First, I think I should lay down some nomenclature. When a player acts upon a cell (i.e., either places a flag on it, or opens it) without having deduced the mine-state of that cell, we call it a guess. Not all guesses are created equal, however. Some guesses are forced upon the player on a global scale. By global I mean that there's no way to deduce the state of the square (guessed on), even when considering the information contained on the entire board. By 'the entire board' we could mean two very different things, of course. We could consider the entire board as it is when the player encounters the guess, or the entire board after all possible deductive routes have been followed (i.e., only guesses remain). In the first case we could call the guess an instantaneous global forced guess, and in the latter an absolute global forced guess. As demonstrated in a discussion between tkolar (I think, it might have been Joni...) and the developers of minesweeperlive.org the distinction between these two is very real. Now that we have those down we can move on to the next kind of guess. As you no doubt guessed (I made a punny :P), the next kind of guess is a local forced guess, meaning that it is a guess when taking only some part of the board into account. This 'part of the board' can be defined in various ways, but the most relevant way (I think) is the natural way of defining it from a constraint viewpoint. As you may know, each uncovered number on a board can be thought of as yielding a constraint of the form x1+x2+x3+x4+x5+x6+x7+x8 = n, where the x's are the number of mines contained in each of the 8 squares around the number (0 or 1), and n is the total number of mines in those 8 squares (i.e., the uncovered number). These constraints become useful when we have many of them, enabling us to make deductions beyond the trivial deductions (i.e., beyond "The number of closed cells around this 4 is equal to 4, thus they're all mines" or "I've found all 3 the mines around this 3, thus the other cells are safe"). Where they become useful to us here, is where we have a set of cells whose constraints form a closed unit. Put more explicitly, it's a set of constraints (derived from cells) which contains all the constraints involving the (unresolved) cells mentioned in the constraints in the set. Thus, a guess can be defined as local if the set of constraints it is contained in is a subset of the entire set of available constraints. This, of course, makes them instantaneous by definition, hence the lack of specification.

Ok, so now that we have that down... :D

The completion rate prediction I made above makes a few (apparently) key implicit assumptions. Firstly, it assumes that the only guesses of significance are 50-50 guesses. Secondly, it assumes that all these guesses are absolute global forced guesses, as well as independent. All three the assumptions can be justified relatively well from our experience of the game, and yield a (anecdotal) reasonable prediction. Your proposed study, however, attempts something completely different. It wants to look at how the things not covered by these assumptions could be dealt with most effectively, by applying all sorts of guessing strategies and seeing which ones yield the best ensemble average completion rate. This is, of course, way more difficult (and subtle) an endeavor. The strategies (and thus algorithms) will have to deal with very slippery concepts, such as the usefulness of information, and the projected gain in information when using a piece of information, weighed up against the cost in efficiency (if you wish to find efficient guess strategies, with respect to clicks), etc..

Lastly, I'd like to point out that your statement that a human player will always do better than an algorithm is blatantly false. Human players apply algorithms. If human players beat your algorithm, then there's a better algorithm. You just need to put in the effort of formalizing it....

Ok, this post was kinda scatterbrain (again). My gf pulled me away from my PC yesterday when I was about half-way through typing this post, so it might not be as coherent as it should have been... :P
The number of minesweeper boards:
Exp: 140055249834355336357264746443955277014822625680974475320364702381803619892657792049596418323789908370400 (1.4e104)
Int: 13115156192346373485000211099954895788134532256 (1.3e46) &
Beg: 18934455246 (1.9e10)
:D

aradesh
Posts: 90
Joined: Sat Aug 29, 2009 3:37 pm

Re: Quasi-empirical estimation of expected board completion rate

Post by aradesh » Thu Nov 15, 2012 2:55 pm

I just had a thought of something that we could do. We could try to solve entirely the question of "what is the best strategy for completion?" for very small boards. e.g. 5x5 boards with 5 mines (or 5x5 with 20 mines for something interesting). Where it could solve entirely from any position (either by creating a database or examining bruteforce from a given scenario) the question "what is the probability of completing the board from this position, and what do I need to do to achieve that probability here?". If we solved this problem for very small boards, it would be quite interesting to watch it solve random boards, and seeing what it chooses to do at each point.

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

Re: Quasi-empirical estimation of expected board completion rate

Post by qqwref » Thu Nov 15, 2012 8:46 pm

I'm going to guess that a rough version of one of EWQ's strategies - choose a pattern that uses fewer mines, when possible - will usually be the best.

However, speaking of probabilities, it's interesting to consider that when you hit a situation you can't figure out, it's very likely that all squares on the border have a probability greater than that of squares you haven't gotten anywhere near yet. That is, if you get stuck, it's probably better to make a random guess away from any clues (and I'd say at the border is better, so it's more likely to be an opening) than to try to solve the situation, unless you are sure there is a forced guess pattern that can't be solved from the "other side". Let's call this the "other side" strategy, unless you guys have a better name.

For instance, consider this pattern:

Code: Select all

+----
|ab1 
|cd21
|12*1
| 111
Here, a, b, c, and d are unknown squares. Assuming you don't know how many mines are here, there are four possible ways to fill this in (one with 1 mine, two with 2, one with 3). EWQ's strategy tells you that the one with one mine is the most probable, so you should open a, b, or c - and in practice it would probably be b or c, just going by how human players solve boards. The "other side" strategy tells you that a touches no clues, so it is still about as likely as any square to hold a mine, so it's less likely to hold a mine than any of the other letter squares, which means you should open that one first. Note that both strategies have the rough consensus that picking d is a bad idea, without actually computing any probabilities.
NF player. Best scores 1-10-39.

User avatar
Tommy
Posts: 223
Joined: Mon Dec 01, 2008 9:22 pm
Location: Vienna

Re: Quasi-empirical estimation of expected board completion rate

Post by Tommy » Fri Nov 16, 2012 3:51 am

I decided to formalize the things we are talking about here. For now, all I have is definitions, and by far not as many as I would like, but it is definitely a start, and so I'll share them here. As a matter of fact, my definitions haven't even started to get interesting IMO, but they should provide an insight as to where this is going. And of course, feedback is awesome, and Tjips was curious on IRC already ;)
solvability_definitions-20121116.pdf
(91.56 KiB) Downloaded 2760 times
Don't anthropomorphize computers - they don't like it.

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

Re: Quasi-empirical estimation of expected board completion rate

Post by Tjips » Fri Nov 16, 2012 12:26 pm

@qqwref: While you are correct that there are cases in which guessing in the totally unknown region has a greater likelihood of not putting you on a mine on the next click, a guess like this doesn't come with the same kind of guarantee of useful information as most at-the-clues guesses have. This means that you'll need to click multiple times before you can start deducing again (in most cases). On exp, with a density of 0.20625 mines/square, you'll have a less than 50% chance of your set of guesses getting you safely to a deducible position by click 3 (it goes down to about 40%). This means that if you'll have to click an average of more than 2 times to get to useful info in this region, you're not gonna have a good time (another punny :P). Disclaimer: If you get to a deducible position on avg. in 2 clicks or less, then your strategy is better than guessing a 50-50, of course :D. Also, This kind of reasoning assumes each new click in that region is on a clueless square (I'm on fire :twisted: ). One could work out the odds for the scenario where only the first guess is totally blind too though, I just don't have the time. Point being, I'm not shooting your strategy down :D.

Your point does still hold some water though. You just need a slightly different approach. A guess strategy that's worked well for me in the past is to guess in the unknown region (i.e., where the probability is still basically 0.21 for a mine), but to guess right behind the squares with clues next to them. This way I get the perks of a low probability of hitting a mine, and of new information guaranteed...

So, to summarize: Guess by opening a square with no clues next to it, but with squares with clues next to them next to it. Choose the square which satisfies this and maximizes the likelihood of the attained info being useful.

That's my proposed guessing strategy :D.
The number of minesweeper boards:
Exp: 140055249834355336357264746443955277014822625680974475320364702381803619892657792049596418323789908370400 (1.4e104)
Int: 13115156192346373485000211099954895788134532256 (1.3e46) &
Beg: 18934455246 (1.9e10)
:D

EWQMinesweeper
Posts: 410
Joined: Sun Nov 30, 2008 11:50 pm

Re: Quasi-empirical estimation of expected board completion rate

Post by EWQMinesweeper » Fri Nov 16, 2012 11:32 pm

so much text and so little time. as times change so do priorieties. in 2009 or 2010 i would have been all in for such discussions. but i simply lack the time to contribute much input on this topic. however, i'm quite interested in the outcome. would you mind summarizing some stuff for me, whenever you found out something that might positively affect completition ratios on expert and in density mode?

also, here are two guessing strategies that have come to my mind recently. i don't know whether they are any good.

1. click the square that is further from the edge (edge of the board or a wall of unsolved squares) to gain information on more squares.

2. similar to what i think qq suggested. use the fact that a mine or two or more have to be among certain squares and click a square that is non-adjacent to any solved squares but adjacent to squares that we already have information on. this has actually worked out quite well for me in density mode as far as i can tell. maybe a part of it is also intuition.
„Das perlt jetzt aber richtig über, ma sagn. Mach ma' noch'n Bier! Wie heißt das? Biddä! Bidddää! Biddddäää! Reiner Weltladen!“

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

Re: Quasi-empirical estimation of expected board completion rate

Post by qqwref » Sun Nov 18, 2012 2:27 am

These are probably obvious, but it's good to have these written down in general, if people want to work on formalizing guessing strategies:

1) If two squares are just as likely to be safe, guess the one which is more likely to provide useful information (e.g. making a pattern solvable) when opened.

2) If you find a pattern that must be guessed, guess it as soon as possible. It doesn't affect game completion percentage but avoids wasting time. However, if you find a lone unknown square surrounded by mines, guess it last, because the board will be automatically completed if it has a mine.

3) Guess patterns with known number of mines (e.g. 50-50s) that do not share squares or clues are statistically independent of each other. However, patterns with an unknown number of mines may not be independent.

4) Opening a square is not the only possible guess; you can also guess that a square is a mine. Of course, you'd want to do this on squares with high mine probability, not low.
NF player. Best scores 1-10-39.

misio
Posts: 5
Joined: Mon Dec 03, 2012 3:24 am

Re: Quasi-empirical estimation of expected board completion rate

Post by misio » Mon Dec 03, 2012 10:00 pm

Basically, my experiments say that for expert, 16x30, 99 mines, no automatic opening,
it cannot be less than 30.45%. The algorithm is pretty stupid, least probability,
so the actual result will be slightly higher.

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Tue Dec 04, 2012 11:06 am

Tjips wrote:Lastly, I'd like to point out that your statement that a human player will always do better than an algorithm is blatantly false. Human players apply algorithms. If human players beat your algorithm, then there's a better algorithm. You just need to put in the effort of formalizing it....
Well, I guess I did partially contrast human thinking with algorithms, implying a difference -- but I also kind said what you're saying, about it requiring effort to capture human the human approach in an algorithm, but not suggesting it was impossible. And a human outplaying a computer in something implies the existence of an algorithm, but I'd say it stretches the definition of algorithm to say that a human is always applying one.

In reference to your other points -- I'm aware that there's been a lot of knowledge gathered on guessing strategy -- in fact I'm hoping to capture some of that. I'm about to post a follow-up about the approach I'm taking -- it will leave such things as local vs global guessing as an implementation detail of the various competing approaches.

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Tue Dec 04, 2012 12:29 pm

Okay, promised follow-up. I've got the framework built for the other effort I've been having a go at -- the patterns website -- and the rest is just busy work of building pattern examples. That's the least fun part so I've decided to just do a bit here and there while I work on more interesting things. Meaning, I've started in on the guessing strategy evaluator. Here are the details of my approach:

1. It will be open source, so anyone can feel free to expand on it or use the results.

2. It's in Java (yeah, it's my weapon of choice but is fairly ubiquitous), but you won't have to know Java to participate (see below). I'll be using Tommy and Tjips' suggested terminology where I can.

3. The test framework will compare some number of strategies by running an extensive series of trials (where "extensive" is loosely defined as "enough to confidently determine whether one strategy is better than another") and the results will be posted on my website.

4. It will allow trials to be run for different board sizes and mine densities, though the initial focus will be on the ubiquitous Windows board sizes (and, using the same first-click-reprieve algorithm).

5. A "strategy" is just a bit of code that's given a unfinished board and responds with a guess (the equivalent of a left mouse click by a human). The test framework will then clear that cell, and mark every mine and clear everything possible as a result of that probe, and then call the strategy again, giving it the updated board. The clearing and flagging I'm guaranteeing to be complete as possible, so your strategy will only ever be presented with boards which require a guess. (I realize that optimal clearing and flagging will be a challenge -- not only based on the famous "minesweeper is NP complete" paper, but also thanks to other pathological cases involving the number of available mines. I know there are some good solvers out there but I don't know to what level this has been fully addressed.)

6. I can see no reason for a strategy to flag a cell as a mine -- certain mines will be flagged by the framework as a result of successful probe, and if a strategy wants to guess that some cell is a mine, it can track that internally and return probes of the surrounding cells when asked for a guess.

7. Strategies will be able to query the current board for various useful data computed by the test framework, such as the set of all cells next to cleared cells, the set of all cells on an edge, the odds of an uncleared cell being a mine based on the number of unflagged mines, etc. which it can use to formulate a guess. I expect that the number of available such data will be expanded as strategies get developed. but any such data is available for any strategy to use.

8. I will keep a running leaderboard on my site. I can't make any claim to it being "official" but I will do my best to take it seriously and be fair and equitable. You are of course welcome to take the source code and do your own experiments, but I'm hoping for a group effort and no real ownership behind any of the strategies (or code, or data).

9. I haven't fully worked out how new strategies will be submitted. If you can code in Java, you will of course be able to add them to the github source repo and I will rerun the test suite. If you can't code in Java - or can't much code at all - I'm sure if you describe your strategy in this forum with sufficient clarity, I or someone else will be able to code it up and throw it into the thunderdome with the others.

10. I'm thinking strategies will typically be coded as an ordered collection of "sub-strategies" that will get tried in order until one of them returns a cell to probe. You would want to order the sub-strategies so that the ones with a higher chance of finding a clear square, or with a higher "usefulness", are tried first. If a sub-strategy can't be applied in a situation, the next one would then be applied. I will provide a framework to let strategies be built this way, and would expect that sub-strategies could be shared in an effort to find the optimal combination. By default the last sub-strategy in any high-level strategy will be "probe any of the uncleared cells at random", which will get used if none of the other sub-strategies come up with a guess. In fact, there will be a baseline strategy that consists of *only* this sub-strategy, as a basis for comparison.

Anyway, I'm eager to see how good we can get a solving algorithm, even if EWQMinesweeper's skepticism has reigned in my optimism a bit :). I'm wondering now if maybe the best guessing strategy we can come up with will only generate a 1-2% improvement. We'll see. December is generally a bad month to start in on a project like this but I have some basic classes built and hopefully I will have something to show in a week or so...

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Sat Dec 15, 2012 8:44 am

Sorry for the late follow-up. I've made decent progress on this, but am still only about halfway there, thanks to a few intense weeks at work that have depleted my daily programming mojo. I've knocked out all the least fun bits, so it's mostly the fun parts left. Still, probably a week or so off,

computronium
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia
Contact:

Re: Quasi-empirical estimation of expected board completion rate

Post by computronium » Wed Jan 30, 2013 10:09 am

Still plugging away here (if anyone cares). If I were to spin the excuse rolodex it might come up "holidays" or "busy at work", but the more truthful answer would be that I got away from it for a bit and had a hard time getting back. Back making progress, but I underestimated the task a bit, so I'm not going to predict a completion date more accurate than "soonish"...

Post Reply