minesweeper contest

Performance Tuning
#1

hi,

to make it short: all of you are challenged to beat this solver:
http://www.radixversand.ch/diverses/minesweeper/HodSolve6e.java

it’s the winner of a small competition (me vs school class X vs school class Y). the winner was me.

here’s the application:
http://buche.informatik.rwth-aachen.de/MineSweeper/public/jar/minesweeper.jar

pretty easy to use. the main class is MineStarter. run it without parameters to get a list of possible ones. use “-g” to run it in gui-mode. double click it to…well. i never doubleclicked the jar^^

the rules:
a) open as much fields as possible. if you open more fields than the others, you win.
b) open the fields as fast as possible. if you open the same amount of fields as the others and are faster, you win.

some fields:
http://www.mitglied.lycos.de/tkdmatze/testfeld
http://www.mitglied.lycos.de/tkdmatze/testfeld30-30-170
http://www.mitglied.lycos.de/tkdmatze/testfeld30-30-200
http://www.isb.rwth-aachen.de/lehre/80-80
http://www.isb.rwth-aachen.de/lehre/79-79
http://www.isb.rwth-aachen.de/lehre/80-68 (12 bombs cannot be found without guessing)

just save & open them with the minesweeper-app.

#2

The links to the last three levels give 404 errors

Load Field button in GUI mode gives:
java.io.FileNotFoundException: minesweeper.conf (No such file or directory)
java.io.FileNotFoundException: (No such file or directory)
at java.io.FileInputStream.open(Native Method)
at java.io.FileInputStream.(FileInputStream.java:106)
at Sweeper.case.new(Unknown Source)
at Sweeper.class.try(Unknown Source)
at Sweeper.long.actionPerformed(Unknown Source)

Similar problem with Save Field button.

#3

i uploaded them:
www.radixversand.ch/diverses/minesweeper/fields

you have to chosse the location/name of a field before you can save it and specify the location/name of a field before you can load it…

#4

[quote=“HamsterofDeath,post:3,topic:25903”]
Then fix the UI. The buttons should not be enabled if the location/name isn’t specified. Though that may still be a poor UI choice. I was expecting a file chooser to appear after pressing the load/save buttons.

#5
  • there are search-buttons. use them.
  • it’s not my app.
#6

Ok, so… I’m a little unsure of the FULL rules. If I hit a bomb am I automatically disqualified, or do the correctly identified bombs up to that point count?

What is the scoring algorithm?

I have something I threw together over the weekend, but it does not do an exhaustive search for a solution, so I probably guess slightly more often than required. I used Java 5, that better be allowed :slight_smile:

#7

you could even use java6 if you wanted to.
there is no scoring algorithm implemented afaik.

the original scoring was like this:
time: 20% ( i have no idea how they exactly counted the scores here)
found bombs: 70% (all bombs = 70%, half bombs = 35% etc)
documentation: 5%
implementing the interface: 5%

and most likely some poor guy had do to it manually.

since i don’t know how to weigth the time and skipped the documentation (won anyway :)), i’d say we use these updated rules:

the rules:
a) open as much fields as possible. if you open more fields than the others, you win.
b) open the fields as fast as possible. if you open the same amount of fields as the others and are faster, you win.
c) if you hit a bomb, it’s the same as if you just stopped solving the field.

the reason for c) is that my algorithm stops here. it doesn’t take any risk. therefore, rule c) will allow some freaky strategies, which means more fun. i’ll start improving by solver as soon as you beat it in speed and/or found bombs

#8

I’m not near you in speed yet… but I have written the algorithm in a very general way so there is still room to optimize… though I think it will still be difficult for me to beat you on time. Generally you solve the levels more consistently and with lower risk than I do. However I just randomly generated a level that your solver consistently locks up on! I’m attaching it.

#9

the field has probably no unambigous solution at the point where my algorithm “hangs” (in fact it started to identify every possible solution which can take a while, depending on the number of open fields). it takes about 1 minute (1.8 ghz opteron) to check if 50 fields (forming an area) are solvable or not. 51 fields should take about 2 minutes, and 100 fields…forget it^^. there are some optimisations, but there’s no guarantee they work. they can help, but it depends on the situation.
i’m thinking hard to solve this problem. smoke already comes out.

#10

Ah… so you do an exhaustive search of all possible combinations along the known boundaries before making a guess?

My solution at the moment only looks for local solutions (maximum 8 unknowns), based on solving the bombs around a single spot and only considering immediate neighbours of unknowns related to that spot… if no such solution exists within that data set it makes a guess based on probability alone without trying to solve any larger domain.