Kansverdeling bij MSN Mijnenveger

[MrBucket]

Ik ben bezig met een programma die een spelsituatie van MSN Mijnenveger kan doorrekenen om te bepalen welke vakjes de hoogste kans hebben om een mijn te bevatten. Alleen, nu zit ik met de volgende (kansrekenings)vraag: zijn situaties waar veel mijnen bij elkaar liggen minder waarschijnlijk dan situaties waar de mijnen meer gespreid zijn?

Even een korte introductie voor mensen die het spel Mijnenveger of Minesweeper niet kennen: het spel wordt gespeeld op een grid, waar een aantal mijnen in verborgen zijn. In het begin van het spel zijn alle vakken 'dicht', maar door een vak aan te klikken wordt het vak geopend en wordt getoond wat er in dat vak ligt. Dit kan een mijn zijn; echter, als het geen mijn is, dan zal er een getal in het vak
verschijnen dat aangeeft hoeveel mijnen er grenzen aan dat vak. Het doel van het spel is om, gebruikmakend van deze hints, alle mijnen te vinden.

Specifiek voor MSN Mijnenveger geldt dat het speelveld 16 bij 16 vakjes is, waarin 51 mijnen verborgen zijn.

Nu is het zo dat, gegeven een bepaalde spelsituatie, er vaak meerdere mogelijkheden zijn waar mijnen verborgen kunnen zijn. Stel dat dit de situatie is:

code:

    . . . #
    . . . #
    . . 2 #
    . . 1 #
    . . . #
    . . . #

        ('*' = Mijn, '.' = leeg, '#' = de rand van het speelveld)

Dan kunnen de mijnen op de volgende 6 manieren verdeeld zijn:

code:

  . . . #    . . . #    . . . #    . . . #    . . . #    . . . #
  . * * #    . * * #    . . * #    . . * #    . * . #    . * . #
  . . 2 #    . . 2 #    . * 2 #    . . 2 #    . * 2 #    . . 2 #
  . . 1 #    . . 1 #    . . 1 #    . * 1 #    . . 1 #    . * 1 #
  . * . #    . . * #    . . . #    . . . #    . . . #    . . . #
  . . . #    . . . #    . . . #    . . . #    . . . #    . . . #
    (a)        (b)        (c)        (d)        (e)        (f)

Zoals te zien is, worden bij mogelijkheden (a) en (b) drie mijnen gebruikt, terwijl bij ( c), (d), (e) en (f) er maar 2 worden gebruikt.

Omdat er bij Mijnenveger een vast aantal mijnen verborgen zijn (51), en de verhouding mijn/niet-mijn ongeveer 1:4 is, vroeg ik me af of dit de mogelijkheden (a) en (b) minder waarschijnlijk maakt, en zo ja, met welke factor?
Ik kwam bij dit idee volgens de redenering dat, omdat je bij (a) en (b) een mijn meer gebruikt, 1 mijn minder over hebt om over de rest van het speelveld te verdelen.

p.s. P&W leek me het beste forum om op te posten, omdat het imo toch wat dieper gaat dan een gemiddeld G&D topic.

[.oisyn]

Uhm, het idee van kansberekeningen is dat elke mogelijkheid even veel meetelt. En dus is de kans dat (a) voorkomt net zoveel is als de kans dat (b) voorkomt. De kans dat er dus een mijn linksboven de 2 ligt, is dus 4/6 = 2/3 (er zijn 6 mogelijkheden, en a, b, e en f voldoen eraan)

Dit past trouwens meer in W&L
PW -> WL

[ Voor 8% gewijzigd door .oisyn op 14-09-2003 13:45 ]

[Zoijar]

MrBucket schreef op 14 september 2003 @ 13:38:
vraag: zijn situaties waar veel mijnen bij elkaar liggen minder waarschijnlijk dan situaties waar de mijnen meer gespreid zijn?

Over het geheel gezien, macroscopisch, is de situatie dat alle mijnen "goed verspreid" liggen meer waarschijnlijk. Er zijn nl. meer configuraties waarbij de mijnen over het hele bord verspreid liggen, dan waarbij bv alle mijnen aan elkaar grenzen.

Maar op microscopisch niveau heb je daar weinig aan, en dat is waar jij in geinteresseerd bent. Het zijn lastige voorwaardelijke kansen; het hele bord heeft invloed. Wat je denk ik het best kan doen is een simulatie schrijven. Leg enkele duizenden keren random een bord mijnen neer, en tel dan hoe vaak bepaalde situaties voorkomen.

[Confusion]

MrBucket schreef op 14 September 2003 @ 13:38:
Alleen, nu zit ik met de volgende (kansrekenings)vraag: zijn situaties waar veel mijnen bij elkaar liggen minder waarschijnlijk dan situaties waar de mijnen meer gespreid zijn?

We verwaarlozen even 1 mijn, dat rekent makkelijker.
Je zou 50 mijnen in een blokje van 10 bij 5 kunnen indelen. Het speelveld is 16x16, dus kan een blok van 10x5 kan daar op 7x12 verschillende manieren opgelegd worden opgelegd worden (horizontaal: 1-10, 2-11, 3-12, 4-13, 5-14, 6-15, 7-16).

Je zou 50 mijnen in een blok van 10x4 kunnen indelen, plus een rij van 10x1. Het blok kan dan op 7*13 verschillende manieren neergelegd worden en de rij kan dan per plaatsing van het blok op 7*12 verschillende manieren neergelegd worden. In totaal dus 7²*25 manieren, minus de 7*12 manieren die bovenstaand blok van 10*5 zouden vormen. Zoals je ziet is deze configuratie al vele malen waarschijnlijker. Alleen zie je ook een complicatie: voor elke configuratie van losse onderdelen die je berekend, moet je alle positioneringen eraf trekken die een andere configuratie vormen. Een willekeurige configuratie uitrekenen is daardoor best lastig.

Je kan de mijnen niet allemaal vrij leggen, dus er zal een meest waarschijnlijk verdeling zijn, maar ik heb geen flauw idee waar die zou moeten zitten. Als je naar zoveel mogelijk losse mijnen gaat wordt het aantal mogelijke configuraties weer kleiner, dus het is niet 'zoveel mogelijk losse en tweetallen'.

In totaal is het aantal manieren om de mijnen neer tel leggen 16²! / (16² - 51)! = 256! / 205!. Met de Stirling benadering kom je op 2.8x10¹²⁰

[ Voor 15% gewijzigd door Confusion op 14-09-2003 15:15 ]

[jlrensen]

Dit soort situaties kun je het beste tot het laatst bewaren, als alleen deze situatie overblijft, dan weet je of je nog 2 of 3 bommen overhebt, en kun je naar aanleiding daarvan wat vakjes vrijklikken.

Als je het niet weet, dan kun je het aantal mogelijkheden tot een bom per vakje berekenen.
Neem de 6 genoemde situaties, en kijk in hoeveel van de situaties er een bom in een bepaald vakje zit.

code:

...#
.44#
.2T#
.2E#
.11#
...#

Je kan dus het beste een va de onderste vakjes aanklikken, in dit geval.

[Anoniem: 8386]

Om antwoord te geven op je vraag: ja er is een verschil in de waarschijnlijkheid van de verschillende configuraties met verschillende aantal mijnen. Echter de situatie met de minste mijnen hoeft niet altijd het waarschijnlijkst te zijn.

Over het algemeen zal je over een bepaald aantal (X) vakjes op het veld geen informatie hebben. Het aantal mijnen dat nog over is (Y) zal over deze vakjes zijn.
Nu wordt de waarschijnlijkheid van een bepaalde configuratie bepaald door het aantal mogelijke verschillende verdelingen van de over gebleven mijnen (Y) over de onbekende vakjes (X). Dit aantal is gelijk aan X boven Y (=X!/(Y!(X-Y)!)).
De verhoudingen van deze aantalen geeft de verhouding van de kansen.

[Confusion]

Omdat het misschien niet helemaal helder is: met mijn bovenstaande post bedoel ik dus te zeggen dat doordat het moeilijk is om uit te rekenen welke verdeling van mijnen over ééntallen, tweetallen, etc. het vaakst voorkomt, je ook niet kan zeggen of het waarschijnlijker is dat een configuratie zoals je die in je post schetst op twee of drie mijnen duidt. Indien bijvoorbeeld een configuratie met veel groepjes van drie mijnen veel waarschijnlijker is dan die met veel groepjes van twee mijnen, dan zal zoiets eerder op drie dan op twee mijnen duiden.

Ik denk dat je het het beste kan proberen te schatten door te simuleren.

[Anoniem: 8386]

Confusion schreef op 14 September 2003 @ 18:36:
Omdat het misschien niet helemaal helder is: met mijn bovenstaande post bedoel ik dus te zeggen dat doordat het moeilijk is om uit te rekenen welke verdeling van mijnen over ééntallen, tweetallen, etc. het vaakst voorkomt, je ook niet kan zeggen of het waarschijnlijker is dat een configuratie zoals je die in je post schetst op twee of drie mijnen duidt. Indien bijvoorbeeld een configuratie met veel groepjes van drie mijnen veel waarschijnlijker is dan die met veel groepjes van twee mijnen, dan zal zoiets eerder op drie dan op twee mijnen duiden.

Ik denk dat je het het beste kan proberen te schatten door te simuleren.

Je kan het gewoon uitrekenen. Zoals ik eerder heb aangegeven. In principe is elke configuratie van mijnen over het veld even waarschijnlijk. Het enige wat je dus hoeft te doen is uitrekenen hoeveel configuraties over een komen met de elke situatie en daarmee heb je gelijk de waarschijnlijkheid.

[Confusion]

Anoniem: 8386 schreef op 14 september 2003 @ 21:16:
Je kan het gewoon uitrekenen. Zoals ik eerder heb aangegeven. In principe is elke configuratie van mijnen over het veld even waarschijnlijk. Het enige wat je dus hoeft te doen is uitrekenen hoeveel configuraties over een komen met de elke situatie en daarmee heb je gelijk de waarschijnlijkheid.

Maar daarvoor moet je bijvoorbeeld wel weten of er voornamelijk losse mijnen danwel voornamelijk mijnen in tweetallen voorkomen. Dat is de eerste verdeling.

De tweede verdeling wordt gegeven door informatie tijdens het spel: aantal mijnen gevonden, aantal vakjes nog leeg, aantal vakjes met of zonder informatie. Dat geeft een tweede verdeling en het produkt van die twee geeft de kans dat een bepaalde configuratie het bijvoorbeeld waarschijnlijker maakt dat er twee mijnen in plaats van 1 verborgen zitten. Mijn punt is dat de eerste verdeling knap lastig uit te rekenen is.

Voorbeeld: bij plaatjes a tot f zou je denken dat de kans groter is dat er twee mijnen aan grenzen in plaats van drie, maar als de optimale verdeling van 51 mijnen vooral in drietallen blijkt te zijn, dan wordt drie mijnen weer waarschijnlijker als oplossing. Dat hangt dan vervolgens nog af van wat er al gevonden is.

[Anoniem: 17989]

Volgens mij moet je het als volgt aanpakken.

De beginconfiguratie is uniform random. Je hebt daar geen info over, dus heeft elk hokje een gelijke kans om een bom te bevatten.

Als je een kruisje zet, dan heb je iets meer info over de naastgelegen hokjes. Je kunt daar een kansmaat op loslaten.

In het midden van het veld heb je 8 omringende hokjes. Als er in je gekozen hokje een 1 staat, dan hebben alle hokjes erom heen een kans van 1/8 om de bom te bevatten.

Om te generaliseren moet je het gekozen hokje uitsplitsen naar alle mogelijke van de volgende situaties:

1: hoeveel nog niet gekozen hokjes staan er om heen? 1-7
2: hoeveel bommen staan er rondom het gekozen vakje? 0-8

Voor elke kan je een kansuitrekenen:

Bv, in het midden met 2 bommen om het gekozen vakje heen is de kans 2/8 dat een hokje om het gekozen hokje een bom bevat. Als er al een hokje omheen weg is, wordt de kans 2/7.

Van slag naar slag evalueer je alleen het nieuw gekozen hokje, en en update je de hokjes erom heen door de verwachtingswaarde uit te rekenen van alle hokjes die wat zeggen over dat specifieke hokje.


Stel je voor dat een hokje met een hogere kans om een bom te bevatten steeds roder wordt. Dan kies je dus altijd de lichtste hokjes.

Overigens is dat dan de beste gok, maar geen wingarantie.

[MrBucket]

Thanks voor alle reacties so far.

Hetgeen wat Trias heeft omschreven klinkt mij het aannemelijkst in de oren: ik had zelf ook al zo'n vaag vermoeden, maar ik kon het niet concreet maken voor mezelf...

Ehm, maar even voor de duidelijkheid: hoe meer mogelijke configuraties van het aantal overgebleven mijnen in het onbekende gebied, hoe aannemelijker de situatie?

En ik heb de formule om de verhouding van het aantal mogelijkheden tussen twee spelsituaties omgeschreven van:

code:

iC boven iA             iA! * (iC - iA)!
-----------    naar     ----------------
iC boven iB             iB! * (iC - iB)!

(Met iA en iB als de aantallen overgebleven mijnen in beide situaties, en iC als het aantal onbekende vakjes)

Maar ik krijg m niet eenvoudiger. Ik zou met name de factoren die zowel in de teller als in de noemer voorkomen tegen elkaar weg willen kunnen strepen. (Gewoon uitrekenen gaat niet op een computer aangezien de registers te klein zijn om de faculteiten te kunnen bevatten, en ik wil geen BigInteger-achtige library gaan gebruiken).

Zijn er mensen die nog wat nuttige rekenregels weten om dit soort dingen eenvoudiger te maken?

Cheers.

[Confusion]

Alle mijnen los neerleggen kan door links boven te beginnen en er telkens 1 gaatje tussen te laten aan alle kanten (inclusief schuin). Dan heb je in totaal iets meer dan 12x16 vakjes nodig om ze allemaal neer te leggen. Laten we doen alsof je 48 mijnen hebt, dan heb je exact 12x16 vakjes nodig.
Nu kan je de laatste steen op alle mogelijke plekken neer gaan leggen. Dat kan op 4x16 manieren. Dit kan je voor iedere steen herhalen, dus dit levert (4x16)⁴⁸ mogelijkheden op.
Nu verplaats je de laatste steen en vervolgens ga je met de één na laatste steen alle mogelijke overgeblekeven plekken af. Dit zijn er bijna (4x16). Dit herhalen voor alle stenen levert dus ongeveer (4x16)⁴⁷ configuraties op, maar omdat de laatste steen nog op (4x16) verschillende plekken kan liggen, zijn die wederom (4x16)⁴⁸ configuraties.
Vervolgens kan je de laatste en de één-na-laatste verleggen en met de eerstvolgende alle overgebleven manieren uitproberen. De twee te verleggen stenen zijn op 48!/(46!x2!) verschillende manieren te kiezen uit de 48 stenen en per gekozen stenen zijn dan vervolgens weer (4x16)⁴⁸ verschillende configuraties mogelijk.

Dit levert een rete irritante som op, die wel uit te werken is, maar niet klopt omdat bepaalde verdelingen minder efficient zijn dan degene die we oorspronkelijk gekozen hebben. We kunnen op deze manier wel een bovengrens vaststellen.

Leg je ze in tweetallen neer, dan kan je met ongeveer 9x16 vakjes toe. Ga je vervolgens het laatste tweetal verschuiven over de resterende (7x16) vakjes, dan kunnen ze daar op (7x16) verschillende manieren liggen, want dus ook weer voor alle stenen herhaald moet worden. Alleen heb je maar half zoveel stenenparen, waardoor het (7x16)²⁴ verschillende mogelijkheden wordt.
Verder loopt de behandeling ongeveer hetzelfde, met de uitzondering dat je paren van twee stenen ook nog kan kantelen. Dus allemaal horizontale combinaties van twee stenen en een verticale combinatie van twee stenen. En dan het hele zwikkie herhalen. De multipliciteit daarvan is ook weer een som over combinaties.

Ik durf echt niet te zeggen wat gunstiger uit zal vallen...

[joepP]

MrBucket schreef op 14 September 2003 @ 22:07:
Thanks voor alle reacties so far.

Hetgeen wat Trias heeft omschreven klinkt mij het aannemelijkst in de oren: ik had zelf ook al zo'n vaag vermoeden, maar ik kon het niet concreet maken voor mezelf...

Ehm, maar even voor de duidelijkheid: hoe meer mogelijke configuraties van het aantal overgebleven mijnen in het onbekende gebied, hoe aannemelijker de situatie?

En ik heb de formule om de verhouding van het aantal mogelijkheden tussen twee spelsituaties omgeschreven van:

code:

iC boven iA             iA! * (iC - iA)!
-----------    naar     ----------------
iC boven iB             iB! * (iC - iB)!

(Met iA en iB als de aantallen overgebleven mijnen in beide situaties, en iC als het aantal onbekende vakjes)

Maar ik krijg m niet eenvoudiger. Ik zou met name de factoren die zowel in de teller als in de noemer voorkomen tegen elkaar weg willen kunnen strepen. (Gewoon uitrekenen gaat niet op een computer aangezien de registers te klein zijn om de faculteiten te kunnen bevatten, en ik wil geen BigInteger-achtige library gaan gebruiken).

Zijn er mensen die nog wat nuttige rekenregels weten om dit soort dingen eenvoudiger te maken?

toon volledige bericht

Ja

Boven en onder komen een heleboel gelijke termen voor. Stel a=6 en b=4, dan weet je dat je in de teller 1*2*3*4*5*6 hebt, en in de noemer 1*2*3*4. Ergo, in de teller staat 5*6, en in de noemer 1.

Met dit idee kan je het volgende doen:

code:

if a > b then
  teller = [b+1, ..., a]
  noemer = [c-a+1, ..., c-b]
elseif a < b then
  noemer = [a+1, ..., b]
  teller = [c-b+1, ..., c-a]
end

En daarna de termen in de teller en noemer 1 voor 1 met elkaar vermenigvuldigen binnen een float, om overflows te voorkomen. In code:

code:

result = 1
for i = 0 to max(teller.last, noemer.last) do
  result = result * teller[i]/noemer[i]

Waarbij je uiteraard de waarde '1' neemt indien het element buiten de array valt.

[Anoniem: 8386]

MrBucket schreef op 14 September 2003 @ 22:07:
Maar ik krijg m niet eenvoudiger. Ik zou met name de factoren die zowel in de teller als in de noemer voorkomen tegen elkaar weg willen kunnen strepen. (Gewoon uitrekenen gaat niet op een computer aangezien de registers te klein zijn om de faculteiten te kunnen bevatten, en ik wil geen BigInteger-achtige library gaan gebruiken).

Zijn er mensen die nog wat nuttige rekenregels weten om dit soort dingen eenvoudiger te maken?

Er werd al eerder naar verwezen. De stirling benadering: n! ~ n^n*exp(-n)*sqrt(2pi*n).

Dit is een redelijk goede benadering voor grotere n. (al bij 4 of 5 wordt het best redelijk)

Verder kan je x boven y makelijker met de computer uitrekenen dan met de faculteiten.

x boven y = x*(x-1)*...*(x-y+1)/(1*2*...*y)

Dit is natuurlijk ook gelijk aan (x/y)*(x-1)/(y-1)*...*(x-y+1)/1

x/y is doorgaans ongeveer 5 zoals je zelf al aan gaf. Dat betekend dat dit iets minder snel uit de hand loopt. Hoewel 256 boven 51 nog steeds ruwweg iets van 5^50 is.

[Anoniem: 17989]

Have a look @

http://www.google.com/sea...q=Minesweeper+probability

waar bv

http://www.nothings.org/games/minesweeper/

te vinden is.

Mijn benadering wordt daar local probabilities genoemd.

Met hier de volledige oplossing:

http://www.cs.toronto.edu/~cvs/minesweeper/minesweeper.pdf

[ Voor 37% gewijzigd door Anoniem: 17989 op 15-09-2003 19:40 ]

[MrBucket]

@ joepP:

Ik zag het patroon ook verschijnen nadat ik het had uitgeprogrammeerd
(gewoon elk van de factoren van de teller in een lijst zetten, en de factoren van de noemer in een andere lijst, en dan factoren tegen elkaar wegstrepen). Helaas zag ik je post pas daarna, maar evengoed bedankt

@ olav:

Toch leuk om te zien dat ik niet de enige ben die zich hier mee bezig houdt Ik was idd van plan om iets met die local probabilities te gaan doen ja.

De methode in het pdf-je omschrijft trouwens een methode die in grote lijnen overeenkomt met die ik gebruik. Alleen waar hij de constraints expliciet opslaat in een lijst om ze met elkaar te kunnen verenigen, probeer ik voor een groep gerelateerde 'nummer-vakjes' alle geldige mijnconfiguraties te genereren, en dan gewoon te tellen hoe vaak er van al deze configuraties een mijn ligt (zoals oisyn in zijn post laat zien).

Alleen zit je dan met het gewicht van zo'n kans... zoals Trias aangaf zijn configuraties die minder mijnen gebruiken (over 't algemeen) aannemelijker, omdat je dan meer mijnen overhoudt die je in het onbekende gebied kunt plaatsen.
Dus dat weet ik nu ook - nu alleen nog in m'n programma stoppen

@ Confusion:
Zoals je zelf ook al aangaf, als je echt alle configuraties voor een speelveld wilt doorrekenen, hebben ze zelfs bij de NASA voorlopig nog niet genoeg rekenkracht... Daarom probeer ik ook niet om een uitspraak te doen in de trant van "voor een groep van x stenen is deze mijnconfiguratie het meest waarschijnlijk". Zelfs als het zou lukken om een soort van lookup-tabel te maken met dit soort data, dan zal deze al snel te groot worden om echt effectief te kunnen worden gebruikt.

Maar ik denk dat iedereen 't er wel mee eens is dat 't een interessant rekenprobleem is

[Anoniem: 8386]

MrBucket schreef op 15 September 2003 @ 21:41:
Alleen zit je dan met het gewicht van zo'n kans... zoals Trias aangaf zijn configuraties die minder mijnen gebruiken (over 't algemeen) aannemelijker, omdat je dan meer mijnen overhoudt die je in het onbekende gebied kunt plaatsen.
Dus dat weet ik nu ook - nu alleen nog in m'n programma stoppen

Wacht ff.
Het is dus niet perse zo dat als je meer mijn over houdt je meer mogelijkheden hebt om ze te verdelen. Als je even veel mijn over houdt als legevakjes, dan is er zelfs maar een mogelijkheid. Ideaal zijn situaties waarin er precies twee keer zoveel legehoekjes als mijn over blijven. Dit betekent dat in het begin er dus zeker een grote voorkeur is voor configuraties met weinig mijnen.

[merlin_33]

Confusion schreef op 14 September 2003 @ 15:00:
[...]

We verwaarlozen even 1 mijn, dat rekent makkelijker.
Je zou 50 mijnen in een blokje van 10 bij 5 kunnen indelen. Het speelveld is 16x16, dus kan een blok van 10x5 kan daar op 7x12 verschillende manieren opgelegd worden opgelegd worden (horizontaal: 1-10, 2-11, 3-12, 4-13, 5-14, 6-15, 7-16).

Dit klopt niet helemaal, het spel kan namelijk geen uitkomst hebben als mijnen op elkaar geklonterd zitten. Het spel werkt op zon manier dat een cijfer aangeeft hoeveel mijnen aan het hokje van het cijfer aangesloten zitten.
Maximaal kunnen er 8 mijnen aansluiten aan dit vakje.
In hoeken en aan de kanten kun je ook nog situaties uitsluiten.
In een hoek kun je maximaal 3 mijnen kwijt en aan een zijde 5.
In een blok van 10 bij 5 moeten er 10 plekken open blijven om aan te kunnen geven hoeveel mijnen aansluiten. In de meest massieve situatie zitten er dus 40 mijnen in een blok van 10x5.

Over het geheel gezien, macroscopisch, is de situatie dat alle mijnen "goed verspreid" liggen meer waarschijnlijk. Er zijn nl. meer configuraties waarbij de mijnen over het hele bord verspreid liggen, dan waarbij bv alle mijnen aan elkaar grenzen.

Maar op microscopisch niveau heb je daar weinig aan, en dat is waar jij in geinteresseerd bent. Het zijn lastige voorwaardelijke kansen; het hele bord heeft invloed. Wat je denk ik het best kan doen is een simulatie schrijven. Leg enkele duizenden keren random een bord mijnen neer, en tel dan hoe vaak bepaalde situaties voorkomen.

als we microscopisch kijken en uitgaan van het vakje dat aangeeft hoeveel mijnen aansluiten is de mogelijkheid dat er 8 mijnen aansluiten 1. Er zijn 8 mogelijkheden van 7 aansluitende mijnen etc. Als het cijfer helemaal in de hoek staat is er 1 mogelijkheid van 3 en 3 van 2 en 3 van 1 en 1 van 0. Als we elke mijn benoemen zijn er natuurlijk veel en veel meer mogelijkheden.Nu ben ik niet zon wiskundig genie dat ik dat even snel ga uitrekenen.Maar toch moeten we de onmogelijkheden eerst uitsluiten om de resterende kansen te bereken.

In ieder geval is de mogelijkheid van op elkaar gepakte mijnen vele malen kleiner.
De mogelijkheid van lege hokjes die aan elkaar aansluiten is groter dan dat hokjes met mijnen aan elkaar aansluiten.
Daarom zie je bij bijna elk spelletje dat bij een microscopische oplossing er macroscopisch grote gaten vallen. De mogelijkheid dat alle mijnen netjes verdeelt zijn is ook kleiner.

[Confusion]

merlin_33 schreef op 17 september 2003 @ 10:51:
Dit klopt niet helemaal, het spel kan namelijk geen uitkomst hebben als mijnen op elkaar geklonterd zitten. Het spel werkt op zon manier dat een cijfer aangeeft hoeveel mijnen aan het hokje van het cijfer aangesloten zitten.

Ik heb bij mijnenveger weleens een klont van vier mijnen in een hoek meegemaakt; de binnenste werd nergens door aangegeven. Volgens mij hoeft het dus niet zo te zijn dat elke mijn door een nummertje aangewezen wordt.

[merlin_33]

Confusion schreef op 17 September 2003 @ 11:33:
[...]

Ik heb bij mijnenveger weleens een klont van vier mijnen in een hoek meegemaakt; de binnenste werd nergens door aangegeven. Volgens mij hoeft het dus niet zo te zijn dat elke mijn door een nummertje aangewezen wordt.

Hmm

In dat geval wordt het moeilijk om tot een oplossing te komen. Stel dat een nummertje ergens tussen een klont mijnen staat en je hebt de rest van het speelveld opgelost. De oplossing wordt dan heel erg moeilijk.
Het lijkt me dat de ontwerper van het spel wel enige restricties heeft toegepast.
Het spel zou anders erg moeilijk worden.
Wanneer wij een groepje mijnen hebben blootgelegd vallen alle vakjes daaromheen die niet aan een mijn aangrenzen open tot vakjes die wel aan een mijn aangrenzen. Wat jij zegt is interessant misschien moeten we berekeningen toepassen op het aantal vakjes waar geen mijnen liggen.

Je kunt natuurlijk ook kijken hoe het spel geprogrammeert is, waarschijnlijk zijn er enkelle regels die over betrekking hebben op het random invullen van het speelveld. De programmeur kan deze gebruiken om het invullen van het speelveld bij te stellen als het te vaak gebeurd dat mijnen extreem samenklonteren.

[ Voor 15% gewijzigd door merlin_33 op 17-09-2003 12:00 ]

[Anoniem: 8386]

merlin_33 schreef op 17 September 2003 @ 11:52:
[...]


Hmm

In dat geval wordt het moeilijk om tot een oplossing te komen. Stel dat een nummertje ergens tussen een klont mijnen staat en je hebt de rest van het speelveld opgelost. De oplossing wordt dan heel erg moeilijk.
Het lijkt me dat de ontwerper van het spel wel enige restricties heeft toegepast.
Het spel zou anders erg moeilijk worden.
Wanneer wij een groepje mijnen hebben blootgelegd vallen alle vakjes daaromheen die niet aan een mijn aangrenzen open tot vakjes die wel aan een mijn aangrenzen. Wat jij zegt is interessant misschien moeten we berekeningen toepassen op het aantal vakjes waar geen mijnen liggen.

Je kunt natuurlijk ook kijken hoe het spel geprogrammeert is, waarschijnlijk zijn er enkelle regels die over betrekking hebben op het random invullen van het speelveld. De programmeur kan deze gebruiken om het invullen van het speelveld bij te stellen als het te vaak gebeurd dat mijnen extreem samenklonteren.

toon volledige bericht

Zo ver ik weet worden de mijnen gewoon random verdeeld met als consequentie dat spelletjes niet altijd oplosbaar zijn zonder gokken. (ik heb wel eens een versie gemaakt voor de TI-83, die de mijnen gewoon random verdeelde. En deze gedroeg zich niet veel anders dan de pc versie)

[merlin_33]

Anoniem: 8386 schreef op 17 September 2003 @ 20:52:
[...]


Zo ver ik weet worden de mijnen gewoon random verdeeld met als consequentie dat spelletjes niet altijd oplosbaar zijn zonder gokken. (ik heb wel eens een versie gemaakt voor de TI-83, die de mijnen gewoon random verdeelde. En deze gedroeg zich niet veel anders dan de pc versie)

Mijn ervaring is dat bij veel spelletjes random instellingen verfijnt kunnen worden om later ongewenste effecten van random verdelingen te kunnen bijstellen.
Ik zal er betreft mijnenveger wel naast zitten ik heb zelf nooit zon spel gemaakt.
Ik heb wel aan instellingen zitten klooien bij andere spellen maar die waren eerlijk gezegt complexer dan mijnenveger.

[Anoniem: 76427]

Confusion schreef op 17 September 2003 @ 11:33:
[...]

Ik heb bij mijnenveger weleens een klont van vier mijnen in een hoek meegemaakt; de binnenste werd nergens door aangegeven. Volgens mij hoeft het dus niet zo te zijn dat elke mijn door een nummertje aangewezen wordt.

Op deze site zijn zelfs klonten van 8 mijnen mogelijk.

[merlin_33]

Jånnis schreef op 17 September 2003 @ 23:53:
[...]


Op deze site zijn zelfs klonten van 8 mijnen mogelijk.

Mooi! maar dus geen mijn die niet wordt aangegeven door een cijfer.

Maar lijkt me een intressante site voor de topicstarter!

Bekijk de site eens naar N=Np probleem
oplossing is 1 miljoen dollar waard. http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
deze is dan ook handig http://www.cwi.nl/events/conferences/VC99/beukers.pdf

Ps confusion jou samengeklonterde hoek lijkt mij uiterst zeldzaam. Wanneer de hoek verder samengeklontert is met een opening, is de uitkomst logisch onoplosbaar

[ Voor 48% gewijzigd door merlin_33 op 18-09-2003 01:57 ]

[Confusion]

merlin_33 schreef op 18 September 2003 @ 00:25:
Wanneer de hoek verder samengeklontert is met een opening, is de uitkomst logisch onoplosbaar

Maar dat is wel vaker zo: volgens mij zijn er altijd situaties waarin je bijvoorbeeld 50/50 of 33/33/33 moet gokken. Ik zie geen reden waarom de puzzels logisch oplosbaar zouden moeten kunnen zijn. Dat kost veel te veel programmeerwerk.

[merlin_33]

Confusion schreef op 18 september 2003 @ 08:22:
[...]

Maar dat is wel vaker zo: volgens mij zijn er altijd situaties waarin je bijvoorbeeld 50/50 of 33/33/33 moet gokken. Ik zie geen reden waarom de puzzels logisch oplosbaar zouden moeten kunnen zijn. Dat kost veel te veel programmeerwerk.

Ik zeg ook niet dat het zo moet zijn.
Maar meestal bied je geen onoplosbare puzzels aan.
Ik heb het nog niet meegemaakt dat een mijn niet door een nummer werd aangegeven.
Kun je mischien vertellen of jij het spelletje voltooid hebt toen er in de hoek 4 mijnen zaten?

[Anoniem: 8386]

merlin_33 schreef op 18 September 2003 @ 15:53:
[...]


Ik zeg ook niet dat het zo moet zijn.
Maar meestal bied je geen onoplosbare puzzels aan.
Ik heb het nog niet meegemaakt dat een mijn niet door een nummer werd aangegeven.
Kun je mischien vertellen of jij het spelletje voltooid hebt toen er in de hoek 4 mijnen zaten?

Hier:

www.science.uva.nl/~mmeent/mine.bmp

Sreenshot van een zo'n geval. (na ruw weg 50 pogingen )

[Confusion]

merlin_33 schreef op 18 September 2003 @ 15:53:
Maar meestal bied je geen onoplosbare puzzels aan.

Meestal niet, maar in het geval van mijnenveger is het voor de programmeurs wel zo verstandig een gokfactor te accepteren .

Kun je mischien vertellen of jij het spelletje voltooid hebt toen er in de hoek 4 mijnen zaten?

Ik had de drie mijnen om het hoekpunt heen en had op het eind nog 1 mijn en 1 vakje over: dat hoekpunt. Als je de hoek overhoudt, zou het logisch oplosbaar kunnen zijn, maar ik kan me geen mijnenveger sessie herinneren waarbij ik niet op een zeker moment moest gokken. Uberhaupt is mijnenveger niet noodzakelijk oplosbaar, omdat je de beginvakjes al moet gokken.

[Anoniem: 8386]

Confusion schreef op 19 september 2003 @ 11:36:
Ik had de drie mijnen om het hoekpunt heen en had op het eind nog 1 mijn en 1 vakje over: dat hoekpunt. Als je de hoek overhoudt, zou het logisch oplosbaar kunnen zijn, maar ik kan me geen mijnenveger sessie herinneren waarbij ik niet op een zeker moment moest gokken. Uberhaupt is mijnenveger niet noodzakelijk oplosbaar, omdat je de beginvakjes al moet gokken.

Maar het eerste hokje dat je klikt is nooit een mijn. (probeer maar eens met 10x10 en 81 mijnen)

[merlin_33]

Confusion schreef op 19 September 2003 @ 11:36:
[...]

Meestal niet, maar in het geval van mijnenveger is het voor de programmeurs wel zo verstandig een gokfactor te accepteren .


[...]

Ik had de drie mijnen om het hoekpunt heen en had op het eind nog 1 mijn en 1 vakje over: dat hoekpunt. Als je de hoek overhoudt, zou het logisch oplosbaar kunnen zijn, maar ik kan me geen mijnenveger sessie herinneren waarbij ik niet op een zeker moment moest gokken. Uberhaupt is mijnenveger niet noodzakelijk oplosbaar, omdat je de beginvakjes al moet gokken.

Natuurlijk is er een gokfactor bij mijnen veger.
Maar ik noemde een aantal mogelijkheden die je bij de kansberekening uit kon sluiten nl het samenklonteren van mijnen die daardoor niet door een cijfer kunnen worden aangegeven. Je maakt het spel daarmee bijna onoplosbaar doordat je je dan in het wilde weg moet gaan gokken.
Jij gaf aan dat er 4 mijnen in een hoek zaten dus 1 helemaal in de hoek en 3 eromheen. klopt dit?

[Anoniem: 8386]

merlin_33 schreef op 19 September 2003 @ 14:23:
[...]


Natuurlijk is er een gokfactor bij mijnen veger.
Maar ik noemde een aantal mogelijkheden die je bij de kansberekening uit kon sluiten nl het samenklonteren van mijnen die daardoor niet door een cijfer kunnen worden aangegeven. Je maakt het spel daarmee bijna onoplosbaar doordat je je dan in het wilde weg moet gaan gokken.
Jij gaf aan dat er 4 mijnen in een hoek zaten dus 1 helemaal in de hoek en 3 eromheen. klopt dit?

Ik gaf net een situatie aan waarin dergelijke samenklontering voorkomt. (6 bij elkaar langs de kant.) Ik zie echter niet waarom dergelijke situatie zo moeilijk zou zijn. Als er maar een is op een speelveld dan vormt het namelijk geen probleem. er bestaan veel vervelendere situaties in minesweeper die nooit op te lossen zijn te gokken.

[Confusion]

Anoniem: 8386 schreef op 19 September 2003 @ 11:38:
Maar het eerste hokje dat je klikt is nooit een mijn. (probeer maar eens met 10x10 en 81 mijnen)

Dat is me nooit opgevallen

Maargoed, dan kreeg je weleens een vierkantje met allemaal 2'en ofzo. Dat schiet nog niet op

[merlin_33]

Anoniem: 8386 schreef op 19 september 2003 @ 15:03:
[...]


Ik gaf net een situatie aan waarin dergelijke samenklontering voorkomt. (6 bij elkaar langs de kant.) Ik zie echter niet waarom dergelijke situatie zo moeilijk zou zijn. Als er maar een is op een speelveld dan vormt het namelijk geen probleem. er bestaan veel vervelendere situaties in minesweeper die nooit op te lossen zijn te gokken.

Yup duidelijk
Deze is wel oplosbaar