Author Topic: Demina: a Minesweeper Solver/Helper (Read 74,825 times)

C++Speaker · « **on:** July 17, 2006, 10:20 AM »

This is my submission: a program that can help in solving Minesweeper game.

The zip files includes the program and a help file in htm:
Demine2006_Gianni.zip (1011.1 KB)

There are also some snapshots/screenshots of the program in acton:
Demina2006_Gianni_Snapshots.zip (813.6 KB)
SomeStepsAfterS.png (49.7 KB)

Enjoy it.

mouser · « **Reply #1 on:** July 17, 2006, 11:16 AM »

I have to say the concept and images do not do this tool justice -
it is quite amazing to see it in action.

it actually finds the normal windows minesweeper executable running, then takes screenshot of the window(!) then figures out the grid given the screenshot, then solves as much as it can, and then sends clicks back over to the minesweeper exe.

it actually made me laught out loud in suprise and pleasure as i was watching it work.. pretty damn amazing.

see the help file inside for a bit on the mathematics of how it works.

C++Speaker · « **Reply #2 on:** July 17, 2006, 01:11 PM »

Quote from: mouser on July 17, 2006, 11:16 AM

I have to say the concept and images do not do this tool justice -
it is quite amazing to see it in action.

Many Thanks for the kind words mouser.

Gianni

TPReal · « **Reply #3 on:** July 24, 2006, 05:37 PM »

Hi. I like the idea of this program, but it doesn't work on my computer! No matter what I set in the Prefer menu, when I try to capture, it says:
Using Direct Capturing Algo
Problems finding game or errors

The minesweeper on my computer is named winmine.exe, and it is Polish version of the program, so the caption of the window is 'Saper'. Is it what makes troubles?

By the way - when you make the Demine window large, you can see Panel2 caption on it... it isn't deliberate I guess

TPReal.

C++Speaker · « **Reply #4 on:** July 25, 2006, 07:21 AM »

Quote from: TPReal on July 24, 2006, 05:37 PM

Hi. I like the idea of this program, but it doesn't work on my computer! No matter what I set in the Prefer menu, when I try to capture, it says:
Using Direct Capturing Algo
Problems finding game or errors

The minesweeper on my computer is named winmine.exe, and it is Polish version of the program, so the caption of the window is 'Saper'. Is it what makes troubles?

Yes, as explained in the html help You have to add a line like the following:
Saper Saper
to the .gam file in the .exe directory
Also Saper must already be running.

Quote from: TPReal on July 24, 2006, 05:37 PM

By the way - when you make the Demine window large, you can see Panel2 caption on it... it isn't deliberate I guess

Gotcha ! :-)

TPReal · « **Reply #5 on:** July 25, 2006, 08:18 AM »

Yeah, now I can say i like the program

I'd add an option that allows the program to choose one of the fields with least probability of being mined, if nothing is obvious, so that all board can (might) be solved just by pressing Ctrl+Space. And then I'd add an option for auto pressing Ctrl+Space

as fast as possible...

Also, after making a move, the capture engine could just check those fields that might have changed, if that would make the process faster.

My idea would be also to check probabilities of not only those tiles that are adjacent to open tiles. Let's imagine situation where you have just made the first move, and the number 5 was revealed. Then, the rest of the board has much less probability of not being mined, that these 8 tiles adjacent to this 5. In fact, on Expert mode (16x30, 99 mines) when the only revealed number is 2, then the probability on adjacent tiles is 25%, whereas on the rest of the tiles we have 97/(16*30-9)=21%, so your program advises a bad move! I'm not for covering the whole area with numbers, but I think writing the probability of the unstable tales would be good.

Nice work.
TPReal.

C++Speaker · « **Reply #6 on:** July 25, 2006, 09:07 AM »

Quote from: TPReal on July 25, 2006, 08:18 AM

Yeah, now I can say i like the program

Thanks

Quote from: TPReal on July 25, 2006, 08:18 AM

I'd add an option that allows the program to choose one of the fields with least probability of being mined, if nothing is obvious, so that all board can (might) be solved just by pressing Ctrl+Space. And then I'd add an option for auto pressing Ctrl+Space as fast as possible...

Well this is a possibility, but it has been coded to be an helper not a 'solve Saper as fast as possible' tool, for example it also remember all possible configurations it has found and some other information. I like to use it when I'm not able to move forward and then try to understand the moves it suggests.
However I can share the source code, so everyone can even add the features she likes most.

Quote from: TPReal on July 25, 2006, 08:18 AM

Also, after making a move, the capture engine could just check those fields that might have changed, if that would make the process faster.

The capture phase is already quite fast, but obviously it can be improved. This can be an improvement.

Quote from: TPReal on July 25, 2006, 08:18 AM

Let's imagine situation where you have just made the first move, and the number 5 was revealed. Then, the rest of the board has much less probability of not being mined ...

Good point !

Really !

Quote from: TPReal on July 25, 2006, 08:18 AM

Nice work.

Many thanks again.

Gianni

C++Speaker · « **Reply #7 on:** July 26, 2006, 07:49 AM »

Here is the source code and an html file explaining some techniques used by the program (the techniques.html file in the techniques directory).

enjoy it !

Gianni

P.S. The program evolved over some attempts and some different (sometimes also wrong) techniques so if the code doesn't seem to cut corners and go straight to the point ... well it's possible.

As always bugs, suggestions, ideas and so on are welcome !

C++Speaker · « **Reply #8 on:** August 03, 2006, 07:33 AM »

Hi,
Just before going on holydays

I want to post a version of the program with a little improvement, some bug-fixes and some new ideas.
The improved part is the final phase.
DemineBDS2006_improved.zip contains some configs: the previous version gives out probs requiring a random click from the user, while this new version can sort things out correctly.

The improvement come from a suggestion made by TPReal

The help.html file with the prog. details all changes and a new version of the Techniques.html file describes the final-phase tecnique just added

and another trick previously not explained.

Gianni

As usual enjoy it !

... and good luck to everybody !!!

C++Speaker · « **Reply #9 on:** August 24, 2006, 07:20 AM »

Hallo,
while waiting for contest winners (by the way best wishes to everybody) I want to post an update to my program Demine.

There are some bug-fixes, some improvements, but the most important new feature is the ability to parse and solve a special Minesweeper clone I have coded; I called it DemineExercizer.
With DemineExercizer it is possible to play a configuration again and again (in a sense it can be considered the dynamic counterpart to .min files) and also to create configurations to exercise Demine by hand. With this helper it is possible to debug and improve Demine much more easily.

I have already used it to improve Demine.

as usual enjoy them.

Gianni

P.S. Suggestions, ideas and so on are welcome.

Good luck to everybody

C++Speaker · « **Reply #10 on:** September 13, 2006, 08:15 AM »

Just got an idea:

Wouldn't it be nice to have tiles with Cody ?

So numbers count how many Cody there are around.
If someone graphic-oriented could provide such tiles: 16 tiles (16x16 pixels) .bmp format
same sequence as MineSweeper tiles then
I could add them to the Draw As menu of Demina & Demine Exercizer;
Also if proper sounds are found I can add them to DemineExercizer.

Ciao.

C++Speaker · « **Reply #11 on:** September 28, 2006, 12:28 PM »

Well,

this is the current version of Demine

!
It includes 2 new techniques ( explained in the techniques.html file included

).

I think now the program has everything I can think about so
if there will not be feedback, ideas, bugs and so on ...
this will be the last version for a while ...

There is also a new version of DemineExercizer.

As always have fun !

Gianni Luciani

mouser · « **Reply #12 on:** September 28, 2006, 01:13 PM »

thanks gianni!

mm267709 · « **Reply #13 on:** November 12, 2006, 06:34 AM »

Hi Gianni,

can you measure the odds of your solving algorithm?

After pausing one year I improved my solver and fixed some bugs. It does now 36.4% of expert games.
You can try it out: http://www.wsdh.org/?minesweeper

Mathias

P.S: I think I found and error within this board (having 10 bombs). The sum of all bomb probabilites should be 10 - but isn't:

mouser · « **Reply #14 on:** November 12, 2006, 07:20 AM »

two minesweeper solvers!!!

now i know for sure that this world is just a dream world inside the matrix.

mouser · « **Reply #15 on:** November 12, 2006, 07:26 AM »

mathias, your minesaver solver screensaver looks so fun - but i couldn't get it to work on my machine.
it starts the minesweeper (always in simple mode), and never plays it and just gives blank screen.

mm267709 · « **Reply #16 on:** November 12, 2006, 02:54 PM »

Quote from: mouser on November 12, 2006, 07:26 AM

but i couldn't get it to work on my machine.
it starts the minesweeper (always in simple mode), and never plays it and just gives blank screen.

This is a difficult issue, as controlling the MineSweeper application is quite complex. I tested it on several systems - all working fine.
Does the MineSweeper Solver run (if not what OS do you use)?

I will try to make a version logging the errors which occur. Maybe that will give me a hint what is wrong.

Thx for trying anyway.

mouser · « **Reply #17 on:** November 12, 2006, 05:26 PM »

im using winxp pro sp2, english.
the solver part of the screensaver does not appear to be running but i havent tried any standalone solver, just the screensaver.

C++Speaker · « **Reply #18 on:** November 14, 2006, 07:52 AM »

Quote from: mm267709 on November 12, 2006, 06:34 AM

Hi Gianni,

Hi Mathias

Quote from: mm267709 on November 12, 2006, 06:34 AM

can you measure the odds of your solving algorithm?

No, I haven't added such a feature.

Quote from: mm267709 on November 12, 2006, 06:34 AM

After pausing one year I improved my solver and fixed some bugs. It does now 36.4% of expert games.
You can try it out: http://www.wsdh.org/?minesweeper

I downloaded the program, but when I try to let it solve a configuration it runs an instance
of minesweeper (here in Italy is called Campo fiorito (flowers instead of mines)) and then it
shows an error saying 'Could not find application winmine.exe'.
My OS is Win2k with service pack 4 if I remember well.
I will try it at home with Win XP.

Quote from: mm267709 on November 12, 2006, 06:34 AM

P.S: I think I found and error within this board (having 10 bombs). The sum of all bomb probabilites should be 10 - but isn't:

I don't understand it for now, but I guess I will understand when I will see Your program in action.
Also did You find the html file on which I detail some techniques used to solve the game ?
Do You use some different ones ?

Gianni

C++Speaker · « **Reply #19 on:** November 14, 2006, 07:59 AM »

Quote from: mouser on November 12, 2006, 07:20 AM

two minesweeper solvers!!!

now i know for sure that this world is just a dream world inside the matrix.

I sometimes have this same suspect, too !

Well, when I decided to partecipate to the contest I was thinking to have something really original, but it seems like somebody other had the same idea, that's really incredible !

Gianni

C++Speaker · « **Reply #20 on:** November 14, 2006, 08:02 AM »

Quote from: mm267709 on November 12, 2006, 06:34 AM

...

After pausing one year I improved my solver and fixed some bugs. It does now 36.4% of expert games.
You can try it out: http://www.wsdh.org/?minesweeper

Mathias

Well, if Your program is The world's best MineSweeper solver,
can i claim mine to be the world's coolest ?

Gianni

mm267709 · « **Reply #21 on:** November 15, 2006, 02:32 AM »

Hi Gianni,

Quote

here in Italy is called Campo fiorito (flowers instead of mines)

after reading your manual carefully, I found all the information. I have to localize my application as I didn't know that their are different versions (testing with Windows Vista would be interesting too).

Quote

Also did You find the html file on which I detail some techniques used to solve the game ?
Do You use some different ones ?

I developed the algorithm mainly on my own (it is quite similar), doing a bit more about the theoretical stuff. I think I am the only one calculating the correct probabilites for a mine (thus solving more than 36% of expert games). But this could still be improved.

I wanted to publish the algorithm but this went out of my focus.

Maybe I will get this done in some time.

I will post a working version for the italian version of MineSweeper. It is good to get some feedback.

C++Speaker · « **Reply #22 on:** November 15, 2006, 04:14 PM »

Quote

testing with Windows Vista would be interesting too.

I agree.

Quote

I developed the algorithm mainly on my own (it is quite similar), doing a bit more about the theoretical stuff. I think I am the only one calculating the correct probabilites for a mine

It's possible: I hate probabilities

However I think the current version is quite good at it.
I'd like to see how You assign probs for some examples,
may be I can try to improve my calculation.

Quote

It is good to get some feedback.

True.

C++Speaker · « **Reply #23 on:** November 15, 2006, 04:17 PM »

Quote

I will post a working version for the italian version of MineSweeper.

If You want I can send You some different Italian versions to test You program with.
You can however get board's bitmaps from my project, too.

aCkRiTe · « **Reply #24 on:** May 18, 2007, 04:13 AM »

Here is a Automatic Minesweeper solver that was written over in the AutoHotKey forum. Its pretty impressive for a single file!

Automatic Minesweeper - http://www.informatik.uni-bremen.de/~bhao/autosweeper.ahk

Topic at AutoHotKey - http://www.autohotkey.com/forum/viewtopic.php?t=11662&highlight=minesweeper