Quasi-empirical estimation of expected board completion rate

Want to calculate something or share your results?
bcw
Posts: 1
Joined: Thu Sep 19, 2013 2:54 am

Re: Quasi-empirical estimation of expected board completion rate

Post by bcw »

So I tried writing a program to play against minesweeper. I'm only interested in the odds of winning; I recognize that most people here are interested in speed.
Can anyone fill me in on the status, history or references for the odds of winning question and programs and algorithms for winning?

>> EDIT:, now I've found this:https://www.cs.us.es/cursos/ia1-2007/tr ... oronto.pdf

I made a minesweeper game with the usual 9x9 with 10mines or 16x16 with 40 or 30x16 at 99mines and the rule that you can never lose on the first move (the mine is moved randomly if it should be hit on first move.)
First pick is a corner.

My play algorithm tries the following on each move, using the first success:
1. find easy no-mine spots (known mines=mine readouts)
2. Find spot pairs with 50% chance of a mines, make two copies of the screen, and set each copy (A or B) with the mine at one of the two location alternatives. The choice then forces other spots to be mines or not. Find all the other spots that are determined by the 50/50 selection. Branch on the three possibilities: a) position A or B cause there to be too many mines somewhere, meaning that one of the positions is impossible and the other is correct; or b) Both seem possible. On b) compare the two case results and look for spots that are open in both cases and return these as the play. This picks up things like 111 running in from an edge where the third 1 in cannot be a mine.
3. If b) occurs but there are no common open spots, search for the next 50%/50% pair and repeat 2.
4. If all 50%/50% spots fail to give a move, guess, selecting amongst the covered spots, initially requiring the chosen spots to be fully surrounded so the risk is mines/total spots in the sequence: a) corners b) edges c)rest of spots. If there are no fully surrounded spots: d) choose least likely to be a mine.
In b,c,and d the algorithm prefers squares adjacent to 50%/50% squares.

Using this algorithm I get 89.9% wins for the beginner game and 72.0% for the intermediate game. All of the losses happen on guesses. For the expert game I only win 20% of games.

The distribution of number of guesses (after the first move) for the intermediate game is in 1000 games is 0=283,1=311,2=192,3=101,4=54,5=31,6=7,7=8,8=6,>8=7 .
The distribution of guesses for lost games is 0=0,1=124,2=62,3=41,4=25,5=15,6=4,7=4,8=3,>8=3.
The intermediate win rate 72% is (95% of) what you would expect for the number of guesses= (216/256)^1.584=76.4% This may be due to ambiguous 50%/505 cases in the endgame.

For the expert game, winning at 20%, the distribution of guesses at T 3.43 guesses/game in 1000 games is 0=19,1=236,2=210,3=158,4=130,5=71,6=56,7=40,8=23,>8=57
The distribution of guesses for lost games is 0=0,1=207,2=174,3=126,4=107,5=56,6=43,7=30,8=15,>8=42.
I collected data showing about 5% of the losses are on guesses on 50%/50% cases. I've assumed that such guesses should be left to last as the odds are so poor.

I've experimented a bit with different guess approaches and find nothing beats the corners. That means that up to 3 guesses is the corners which account for half the losses.

Misio says above that he expects a completion rate of 30.45% for the expert game . What is the background for this statement?
Post Reply