brad's life - Minesweeper

brad's life - Minesweeper

[entries|archive|friends|userinfo]

Brad Fitzpatrick

[	website	\|	bradfitz.com	]
[	userinfo	\|	livejournal userinfo	]
[	archive	\|	journal archive	]

Minesweeper

[Jan. 31st, 2005|02:02 pm]

[

Tags

|

]

Yesterday I wrote a little program to play Minesweeper so I could graph what the likelihood of winning was given certain bomb densities.

Over 19,000 games:

(The X axis is bomb density, Y is winning percentage)

Currently the AI only flags bombs based on O(n) algorithms. I don't do any hypothetical-true-leads-to-inconsistent-state eliminations which get into exponential time, though I'll probably add that sometime.

Of course, sometimes it's just a 50/50 chance and no logic will help.

BOARD 511:

 1 2 X 2 1   1 1 1   1 1 2 1 1   1 * * 1       1 * 2 * 1 1 * * 2
 3 * . * 2   1 * 2 1 2 * 3 * 1 1 2 3 2 1   1 1 2 1 2 1 2 2 4 * 2
 * * * * 2   1 2 * 1 2 * 3 1 1 2 * 2 1 1 2 2 * 2 2 2 2 2 * 2 2 2
 3 4 3 3 3 2 1 1 1 1 1 1 1     2 * 3 2 * 3 * 4 * 2 * * 2 1 2 2 *
 * 2   1 * * 2       1 1 1     1 1 2 * 2 3 * 3 1 2 2 3 2 1 2 * 3
 * 3 1 1 4 * 4 1     1 * 1         2 2 3 3 3 2       1 * 1 2 * 2
 2 * 1   2 * * 1 1 1 2 1 2 1 1 1 1 2 * 3 * * 1   1 1 3 2 2 1 2 2
 2 2 2   1 3 3 2 1 * 1 1 2 * 1 1 * 3 3 * 3 2 1   2 * 4 * 1   1 *
 1 * 2 2 2 3 * 3 2 1 1 1 * 3 2 1 1 2 * 2 2 1 1   3 * * 2 2 1 3 2
 1 1 2 * * 3 * * 2 1 1 3 4 * 2     1 1 1 1 * 1 1 3 * 3 1 2 * 4 *
     1 2 2 2 3 * 2 1 * 2 * * 4 3 3 2 1   1 2 2 2 * 3 3 2 4 * 4 *
       1 1 1 1 2 2 2 1 2 2 3 * * * * 1     2 * 3 2 * 2 * * 2 2 1
       1 * 1 1 2 * 1       1 2 5 * 4 1     2 * 2 1 2 3 3 3 2 2 1
       2 2 2 1 * 2 1         1 3 * 3 1     2 2 2   1 * 1 1 * 3 *
 1 1 1 1 * 1 1 1 1       1 1 2 * 3 * 1     1 * 1   1 1 1 1 2 4 *
 1 * 1 1 1 1             1 * 2 1 2 1 1     1 1 1           1 * 2
DEAD!

Comments:

From:

olliejeff
2005-01-31 10:06 pm (UTC)

(Link)

It's good to see that the freedom you acquired from selling LiveJournal is being used constructively.

(Reply) (Thread)

From:

brad
2005-01-31 10:09 pm (UTC)

(Link)

Whatever, I do what I want!

(Reply) (Parent) (Thread)

From:

erik
2005-01-31 10:10 pm (UTC)

(Link)

Heh, I was going to say the very same thing. I'm not sure SixApart is giving him enough work to do. ;-)

(Reply) (Parent) (Thread)

From:

themabbi
2005-01-31 10:11 pm (UTC)

(Link)

Indeed.

Watch out Brad. The crazies are going to claim that the LJ outage was actually caused by you taking all the servers offline so they could crunch your minesweeper data instead ;)

(Reply) (Parent) (Thread)

From:

jwz
2005-01-31 10:10 pm (UTC)

(Link)

Is export of this research restricted under ITAR?

(Reply) (Thread)

From:

matte
2005-01-31 10:13 pm (UTC)

(Link)

I really need you sitting next to me at the blackjack table. ;)

(Reply) (Thread)

From:

maidden
2005-01-31 10:18 pm (UTC)

(Link)

I hate when it comes to that. Often I have the entire board figured out except for the one last bomb that could be either of the two places left to click. Then I lose. *sigh* Stupid game. Why can't I stop playing?

(Reply) (Thread)

From:

boggyb
2005-01-31 10:53 pm (UTC)

(Link)

And the strange part is that I've been toying with the idea of writing a minesweeper-solving-bot-type-thing recently. I think I have somewhere a VB version of minesweepers, which I will probably canibalise for this if I ever get round to it. Program in some simple rules (121, x3x, edge2x) and let it rip. Add in a random number generator for some added fun.

Hey, it'll give me something to do in lectures. Unless you beat me to it by GPL'ing your code or something, in which case I'll probably be lazy and use that!

(Reply) (Thread)

From:

xaosenkosmos
2005-01-31 10:55 pm (UTC)

Stupid question

(Link)

What's the graph of number-of-games vs percentage? A constant, or does it vary as well?

(Reply) (Thread)

From:

mahlon
2005-01-31 11:05 pm (UTC)

(Link)

Where can I download a distributed client so I can donate my cpu cycles to help find the mines?

huhUHuhhUH

(Reply) (Thread)

From:

chris
2005-01-31 11:05 pm (UTC)

(Link)

is this theoritcally solvable or actually solvable? you have to make that first click somewhere. I ask, because sometimes it might be on the 50/50 chance and you get it right.

(Reply) (Thread)

From:

brad
2005-01-31 11:08 pm (UTC)

(Link)

Actually solved.

It plays until it wins or dies. It only makes a random guess when it has nothing smart to do.

(Reply) (Parent) (Thread)

From:

jzig
2005-01-31 11:29 pm (UTC)

(Link)

If you want to speed up average solving time, have it so if there is a random choice for which no more information can be discoverable (ie, it's surrounded by known squares) make that choice as soon as possible, so if you're wrong you didn't waste time :)

I was going to write a minesweeper solver for class, but now I'm going to write a evolutionary cellular automata instead. Oh well.

(Reply) (Parent) (Thread)

From:

stalk_her
2005-01-31 11:22 pm (UTC)

(Link)

you take the fun out of mindsweeper! :(

(Reply) (Thread)

From:

adamthebastard
2005-02-01 12:21 am (UTC)

(Link)

I really hope we get to see more 'because I can' moments from you Brad. You do some really randomly cool stuff.

(Reply) (Thread)

From:

nothings
2005-02-01 12:49 am (UTC)

(Link)

some analysis of how to apply probability to minesweeper although it's probably more useful to do limited-lookahead-for-impossible-situations first.

(Reply) (Thread)

From:

granting
2005-02-01 01:12 am (UTC)

(Link)

So you sold LJ and now you're bored?

Not just bored... but that bored?

(Reply) (Thread)

From:

brad
2005-02-01 01:33 am (UTC)

(Link)

I wasn't bored at all... it was fun. And it was a Sunday.

You speak as if Six Apart has already unburdened me or something.... things aren't much different yet.

(Reply) (Parent) (Thread)

From:

granting
2005-02-01 01:40 am (UTC)

(Link)

I kid, I kid.

If you really want some programming to do on your off time I have an entire list of projects you could do... :-)

(Reply) (Parent) (Thread)

From:

mart
2005-02-01 10:06 am (UTC)

(Link)

It doesn't work like that. ;)

(Reply) (Parent) (Thread)

From:

dottey
2005-02-01 01:21 am (UTC)

(Link)

Were you watching "Numbers" (new show) on CBS this past week? The math-whiz on that show was working on this exact problem.

(Reply) (Thread)

From:

brad
2005-02-01 01:34 am (UTC)

(Link)

Yeah, I think that's what started it. The show was a little too painful though.

(Reply) (Parent) (Thread)

From:

bloonail
2005-02-01 02:29 am (UTC)

(Link)

I thought you were supposed to get a holiday on the seventh day?

(Reply) (Thread)

From:

brad
2005-02-01 02:35 am (UTC)

(Link)

That was! :-)

(Reply) (Parent) (Thread)

From:

nick
2005-02-01 02:55 am (UTC)

(Link)

Just wait till you are married dude. Dina still affords you this freedom because it's not too late to back out... but you'll be painting the baby's room on Sunday before long homey... just so you know.

(Reply) (Thread)

From:

nibot
2005-02-01 02:55 am (UTC)

(Link)

NB: http://www.cs.berkeley.edu/~daw/teaching/cs70-s05/Notes/lecture08.pdf and http://www.cs.berkeley.edu/~daw/teaching/cs70-s05/Notes/lecture09.pdf

(Reply) (Thread)

From:

nibot
2005-02-01 03:04 am (UTC)

(Link)

and http://www.cs.berkeley.edu/~daw/teaching/cs70-s05/Notes/lecture25.pdf

(Reply) (Thread)

From:

romaroma
2005-02-01 03:50 am (UTC)

(Link)

Wow! It's my favourite game! :-)

(Reply) (Thread)

From:

ahze
2005-02-02 06:55 am (UTC)

(Link)

http://www.nada.kth.se/~joh/minesweep3d/screenshots/minesweep3d.jpg

(Reply) (Thread)

From: (Anonymous)
2005-02-11 12:24 am (UTC)

(Link)

You are an evil genius.

(Reply) (Thread)

From:

tlhinganhom
2005-02-18 07:25 pm (UTC)

(Link)

The information contained within this post ranks among one of the best uses of programming skills, ever.

(Reply) (Thread)