Miinaharava läpi yhdessä sekunnissa

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Pääsin kerran miinaharavan helpoimman vaikeusasteen läpi yhdessä sekunnissa. Todettakoon heti alkuun, että kyse oli silkasta tuurista, sillä läpäiseminen vaati ainoastaan yhden klikkauksen. Tämä on mahdollista sillä tietokone automaattisesti merkkaa selvitetyiksi kokonaan numeroiden, kentän rajan tai tyhjien ruutujen ympäröimät miinankohdat. Jokainen voi testata kyseistä ilmiötä valitsemalla muokatun pelin ja syöttämällä maksimiluvut kokoa indikoiviin kenttiin ja minimiluvun miinan määrää indikoivaan kenttään. Eipä tarvitse kokeilla tuollaista superhelppoa peliä kuin muutaman kerran, niin saa yhdellä klikkauksella läpäistävissä olevan kentän.

Helpoimman vaikeusasteen kohdalla tilanne on kuitenkin aivan toinen. Rupesin pähkäilemään yhden klikkauksen läpäisyn todennäköisyyttä, ja lyhyen puntaroinnin jälkeen tulin siihen tulokseen, että todennäköisyys on aivan helvetin pieni. Faktat: helpon miinakentän koko on 9x9 ruutua ja miinoja on 10. Miinan automaattista merkkautumista rajoittavia tekijöitä: Miinoja ei saa olla lainkaan yhden ruudun päässä reunaa, ei vierekkäin kahden ruudun säteellä, eikä toiseen miinaan vinoittain sijoitettuna. Miinoista kumpikaan ei myöskään saa olla kentän rajan vieressä siinä tapauksessa, että toisen sijainti ensimmäisen suhteen on kolme ruutua eteenpäin tai kaksi ruutua eteenpäin ja yksi jommallekummalle sivulle tai kolme ruutua eteenpäin ja yksi sivulle. Sääntöjä lienee enemmänkin, mutta pelkästään tuollakin perusteella todennäköisyys lienee häviävän pieni.

Olisi mukava tietää todennäköisyyden tarkka arvo, mutta en tiedä tapaa jolla p:n saisi laskettua tällaisessa tapauksessa. Osaisikohan joku muu laskea?

Kommentit (11)

Vierailija
Empiristi
Olisi mukava tietää todennäköisyyden tarkka arvo, mutta en tiedä tapaa jolla p:n saisi laskettua tällaisessa tapauksessa. Osaisikohan joku muu laskea?



Noniin, kuka koodaa nopeimman ohjelman joka käy läpi 10^n tapausta ja tulostaa arvion todennäköisyydestä?

Neutroni
Seuraa 
Viestejä26898
Liittynyt16.3.2005

Tuossa taitaa olla 81 yli 10 eli noin 1,9E12 vaihtoehtoa. Kyllä nuo yössä tai parissa käy vaikka kaikki läpi. Isommille kentille brute force ei enää toimi.

Vierailija

En tajunnut mainita, että tismalleen vierekkäin miinat voivat olla jos muiden sääntöjen puitteissa pysytään, mutta eivät siis siten, että niiden välillä on yksi tai kaksi ruutua.

msdos464:lle: Tietokonetoimissaniko vai rasitus? Vastaa kyllä tai ei.

Vierailija
Empiristi
msdos464:lle: Tietokonetoimissaniko vai rasitus? Vastaa kyllä tai ei.



Siis hä?

Tulin jo alustavissa simulaatioissa siihen tulokseen, että todennäköisyys on todellakin häviävän pieni. Miina ei saa siis olla 1 ruudun päässä reunasta. Tämä tarkoittaa sitä, että jo 24 / 81 ruudusta on kiellettyjä. 10 miinalle se tekee todennäköisyydeksi (1 - (32 / 81))^10 eli noin 0,65%. Jokainen uusi miina kylläkin tekee kielletyksi aina lisää ruutuja.

[code:1ttgio2s]maar[0] => 0 = 0.00%
maar[1] => 0.00%
maar[2] => 0.01%
maar[3] => 0.05%
maar[4] => 0.24%
maar[5] => 1.00%
maar[6] => 3.35%
maar[7] => 8.71%
maar[8] => 17.96%
maar[9] => 29.41%
maar[10] => 39.27%[/code:1ttgio2s]

Tuossa on siis, että kuinka monta prosenttia yrityksistä keskeytyi kyseiseen "askeleeseen" lisätä uusi miina. maar[10] olisi teoriassa 32/81 eli noin 39,51%, eli hatusta vedetty satunnaislukugeneraattorini ei ollut täysin susi. Yrityksiä tehtiin 134217728 (0x8000000).

edit: tuo menee vähän nurin päin.. eli tuo numero hakasuluissa kertoo, että "montako miinaa oli tätä miinaa ennen laittamatta"

Tein vähän enemmän yrityksiä niin saa enempi desimaaleja.

[code:1ttgio2s]maar[0] => 0 = 0.000000 %
maar[1] => 2 = 0.000003 %
maar[2] => 4701 = 0.007005 %
maar[3] => 32913 = 0.049044 %
maar[4] => 161460 = 0.240594 %
maar[5] => 711640 = 1.060426 %
maar[6] => 2280670 = 3.398463 %
maar[7] => 5768326 = 8.595476 %
maar[8] => 11915954 = 17.756155 %
maar[9] => 19682400 = 29.329062 %
maar[10] => 26550798 = 39.563772 %
0 / 67108864 => 0.000000 %[/code:1ttgio2s]

edit2: oikeastaan todennäköisyys olisi kai 2 / 67108864 = noin 3e-8.

Vierailija

Tuolta poimittua. Siellä on ongelmasta jotain teoreettista pohdiskeluakin.

http://en.wikipedia.org/wiki/Minesweeper_(computer_game)

"Best times

The minesweeper community has compiled a world ranking of the fastest games submitted by players. In order to get on that list, records on beginner, intermediate and expert must add up to no more than 99 seconds. Since April 2000 the ranking has been hosted at Authoritative Minesweeper, although from 2004-2006 the ranking at Planet Minesweeper performed this function as well. [7]

The current world records are:
37 seconds on expert by Dion Tiu
10 seconds on intermediate tied with Dion Tiu, Roman Gammel, Manuel Heider, Kamil Muranski and Matt McGinley (and disputed scores of 9 and 10 by Jake Warner)
1 second on beginner, held by nobody - depending on the arrangement of mines, rare levels of "beginner" difficulty can be completed with a single click (1 click games are not accepted for ranking purposes)

Theoretically games can be solved with one click, but this is not the case as the Windows version of minesweeper uses a finite set of cycling boards, while clones accepted for rankings impose 3BV[8] limits."

Vierailija
msdos464
Siis hä?

Armeijajuttu, voit luultavasti unohtaa kysymyksen.

edit2: oikeastaan todennäköisyys olisi kai 2 / 67108864 = noin 3e-8.

Karua.

Wikipedia
Theoretically games can be solved with one click, but this is not the case as the Windows version of minesweeper uses a finite set of cycling boards

Siis väitetäänkö tuossa että Windowsin miinaharavalla on mahdotonta päästä helpon tason miinaharava yhdessä sekunnissa? Tuskin muistan väärin tuota 'ennätystäni', vaikka sen saamisesta onkin jonkin verran aikaa. Versio oli XP Pron Miinaharava. Lisäksi jossain pitäisi olla tallessa sellainen video, jossa saan tehtyä n. 40 randomia klikkausta Miinaharavan vaativalla vaikeusasteella ennen kuin peli kosahtaa miinaan.

Vierailija

Terve.

Olen harrastelija koodari ja ajattelin että kehitä "map hackin" miinaharavaan. Ei kestänyt kauaa todeta, että ekalla klikkausella ei voi hävitä.
Miinaharava toimii siten, että kun uusi peli luodaan, luodaan muistiin ruudukon kokoinen taulukko, jossa on kaikki miinat merkittynä. Joten, tein ohjelman, mikä lukee taulukon ja esittää sen minulle omassa ikkunassa. Kun sitten klikkaan miinan kohdalta, niin se ei osunutkaan miinaan. Huomasin, että se luo uuden taulukon jos ekalla meinaa osua miinaan.
Eip sillei vaikuta mihinkään, mutta kuitenkin, jotain huijausta pelissä tapahtuu. Olen itsekin selvittänyt pelin sekunnissa ( oletus vaikeuaste ). Random klikkailua niin nopeasti kuin voi.
( toki, tein ohjelman mikä luki miinat ja klikkas kaikkea muuta niin nopeasti kuin mahdollista )

Vierailija

Sanoppas vähän, että miten tuota maphackia pitää lähteä tekemään? Täytyykö käyttää WinAPIa, että tietää miinaharavan käyttämät muistiosoitteet? Itsellä ei ole näistä asioista mitään kokemusta.

ykskivi
Seuraa 
Viestejä1950
Liittynyt27.3.2006
msdos464
Sanoppas vähän, että miten tuota maphackia pitää lähteä tekemään? Täytyykö käyttää WinAPIa, että tietää miinaharavan käyttämät muistiosoitteet? Itsellä ei ole näistä asioista mitään kokemusta.



Kirjoittelin tuollaisen miinaharavan joskus vuonna 1995 pascalilla..
Miinapeli löytyi hakemalla ikkunaa, jonka nimi "miinaharava" tai "minesweeper". Ohjelmani kopioi ikkunan sisällön kuvana ja luki jokaisen ruudun kohdalta tietyn pikselin. Se sattui olemaan jokaisella eri numerolla eri värinen, joten yhden pikselin värin perusteella saattoi päätellä ruudussa olevan numeron.
Ikkunalle voi myös lähettää messagen, joka vastaa hiiren painamista määritellyssä kohdassa.
Itse algoritmi perustui puhtaasti joukkomatematiikkaan, eli se muodosti ruuduista joukkoja ja sitten muodosti näistä perusjoukoista uusia joukkoja laskemalla yhteen ja vähentämällä niitä toisistaan. (termi taisi olla peruskoulussa joukkojen summalle "unioni". vähennyslaskun termiä en kyllä enää muista..) Ei minulla mitään hajua ollut mistään NP teorioista!

To refuse a hearing to an opinion, because one is sure that it is false, is to assume that one's own certainty is the same thing as absolute certainty. All silencing of discussion is an assumption of infallibility. - John Stuart Mill -

Vierailija

Ei kyllä liity suoraan aiheeseen, mutta...

Voiko javalla tai c:llä tehdä ohjelmia, jotka klikkailee ruutua haluamistasi paikoista? Vai pitääkö aina jollain tavalla "murtautua" tietyn ohjelman koodiin, jotta sen näyttämää ikkunaa voi klikkailla automaattisesti?

Vierailija
ykskivi
Ohjelmani kopioi ikkunan sisällön kuvana ja luki jokaisen ruudun kohdalta tietyn pikselin. Se sattui olemaan jokaisella eri numerolla eri värinen, joten yhden pikselin värin perusteella saattoi päätellä ruudussa olevan numeron.



Itse en kyllä screenshotista löytänyt mitään eroa pikseleiden värissä. Muistaakseni magic wandin tresholdi oli oikeaoppisesti säädetty nollaan ja anti-aliasing pois.

Uusimmat

Suosituimmat