Mijnenveger spelen op netwerken

Het originele spel Mijnenveger speel je op een rooster (een grid) waarbij sommige vakjes een mijn bevatten. Het doel van het spel is om op alle vakjes te stappen waar geen mijn ligt, zonder op een vakje te stappen waar wel een mijn ligt. Je ‘stapt’ op een vakje door erop te klikken. Als dit vakje een mijn verschuilt, dan verlies je het spel (en misschien ook je voet). In de eerste versie van het spel had de cursor zelfs de vorm van een voet, die veranderde in een bloederige stomp wanneer je op een mijn stapte. In de versie die uiteindelijk uitgebracht werd, zit deze bloederige cursor niet meer. Je snapt misschien wel waarom.

Als het vakje waarop je klikt geen mijn bevat, dan verandert het vakje in een getal. Dit getal telt het aantal mijnen in aanliggende vakjes. Als er geen mijnen in aanliggende vakjes liggen, dan worden de aanliggende vakjes automatisch aangeklikt. Je wint het spel wanneer je op alle vakjes stapt die geen mijn bevatten. Wanneer dit gebeurt, krijgt de smiley bovenaan het scherm een mooie zonnebril op.

Als deze beschrijving nog geen nostalgie aanwakkert, kun je misschien het originele spel spelen voordat je verder leest. Er bestaan al veel varianten op dit spel. Bijvoorbeeld varianten met driehoekige of zeshoekige vakjes. Er bestaat zelfs een driedimensionale versie.

Als je dit spel iets abstracter bekijkt, dan zie je dat al deze versies met elkaar gemeen hebben dat het ‘mijnenveld’ een verzameling vakjes is (vierkant, driehoekig of welke vorm dan ook). Ook bevat het spel een manier om te bepalen welke vakjes aan elkaar grenzen. Het mijnenveld is dus als het ware een netwerk van vakjes, waarbij een verbinding tussen twee vakjes betekent dat de twee vakjes aan elkaar grenzen. Met deze abstractere kijk op het spel is het makkelijk om met nieuwe varianten van het spel te komen. In plaats van vakjes op een rooster, kun je bijvoorbeeld ook de twaalf provincies van Nederland nemen, waarbij twee provincies verbonden zijn als ze een landsgrens delen. Maar je kunt zelfs nog verder gaan: de vakjes hoeven eigenlijk niet eens vormpjes voor te stellen. Je kunt bijvoorbeeld ook een netwerk maken op basis van het afgelopen WK voetbal, waar je twee landen met elkaar verbindt als ze een wedstrijd tegen elkaar gespeeld hebben. Als je mijnenveger op dit netwerk speelt, zou je dan eerst op de kampioen ‘stappen’ of begin je juist bij de teams die al in de poulefase sneuvelden?

Netsweeper

Door het rooster op deze manier in te ruilen voor een netwerk, kom je uit op een variant van het spel dat ik ‘Netsweeper’ noem (naar het Engelse Minesweeper). Omdat een netwerk natuurlijk veel spannender is dan een saai rechthoekig rooster, geeft dit extra variatie aan het spel. De beste tactiek hangt bijvoorbeeld ook af van het specifieke netwerk waar je op speelt. Netsweeper kan je onderaan deze pagina spelen om te zien hoe het werkt.

De netwerken die ik in het spel geprogrammeerd heb, zijn deels netwerken die in mijn onderzoek vaak voorkomen, deels ‘standaard’ netwerken uit de wiskunde en nog een paar andere netwerken die ik leuk vond om toe te voegen, zoals een netwerk van vierletterwoorden en het netwerk van het afgelopen WK voetbal. In de rest van deze blog geef ik meer uitleg bij deze netwerken en hoe eigenschappen van deze netwerken het spel beïnvloeden.

Basisregels

We beginnen met het samenvatten van de twee ‘basisregels’ van mijnenveger en Netsweeper. Allereerst: als je op een vakje stapt en het laat zien dat er maar een enkele mijn omheen ligt terwijl alle omliggende vakjes op één na al bekend zijn, dan weet je dat er dus een mijn op dat ene vakje ligt. Hetzelfde geldt voor twee of meer mijnen: wanneer het aantal ‘onbekende’ vakjes gelijk is aan het aantal mijnen dat je zoekt, dan weet je waar ze liggen. Wanneer je weet dat een vakje een mijn bevat, kun je het markeren met een vlaggetje zodat je het niet vergeet. Dit doe je door dit vakje met je rechtermuisknop aan te klikken (op de computer) of door gebruik te maken van de schakelaar rechtsboven.

De tweede regel is eigenlijk het omgekeerde van de eerste: als je een mijn vindt (bijvoorbeeld met de vorige regel) en je ziet dat een van de aanliggende vakjes gemarkeerd is met een ‘1’, dan weet je dat geen van de vakjes die grenzen aan dit vakje een mijn heeft. Dan kan je hier dus veilig op stappen. Wederom geldt deze regel ook voor grotere aantallen mijnen: als het cijfer in het geel gelijk is aan het aantal mijnen dat je in omliggende vakjes vindt, dan moeten de overige onbekende vakjes veilig zijn.

Met deze twee regels kom je al een heel eind. Maar ze zijn niet altijd toepasbaar.

Hubs vermijden

In de originele vorm van het spel grenst ieder vakje aan ongeveer evenveel andere vakjes (met uitzondering van vakjes op de rand van het rooster). Wanneer we dit rooster vervangen door een netwerk, kan het zijn dat er vakjes zijn die veel meer verbindingen hebben dan gemiddeld. In netwerkterminologie heet zo’n vakje met veel buren een hub. Neem bijvoorbeeld het WK-netwerk: als een team bij de poulefase al uit het toernooi viel, heeft het maar drie wedstrijden gespeeld, terwijl een team dat de finale bereikt zeven wedstrijden speelt. Wanneer een vakje veel buren heeft, bevatten deze aangrenzende vakjes waarschijnlijk een aantal mijnen en ook veel niet-mijnen. Dit maakt de kans klein dat je een van de vorige twee regels toe kan passen. Zodoende is het vaak handig om deze hubs voor het einde te bewaren. Als veel van de omliggende vakjes al bekend zijn, is de kans groter dat je een van de basisregels kan toepassen.

Verdeel en heers

Een nadeel van het spelen van mijnenveger op een netwerk in plaats van een rooster, is dat het soms onoverzichtelijk is. Als twee vakjes aan elkaar grenzen terwijl ze op verschillende uiteinden van het scherm staan, resulteert dit in een lijn die dwars door het netwerk loopt. Als je in dit spel klikt op een vakje dat geen mijnen in omliggende vakjes heeft, worden de omliggende vakjes ook automatisch bekend gemaakt. Vervolgens voegen de verbindingen van dit ene vakje naar de omliggende vakjes eigenlijk geen informatie toe, aangezien je weet dat aan allebei de uiteinden geen mijn ligt.

Wanneer je in het spel op zo’n vakje met geen mijnen in de buurt klikt, wordt dit vakje samen met haar verbindingen verwijderd. Dit maakt het netwerk weer wat overzichtelijker. Als je geluk hebt, kun je op deze manier zelfs het netwerk opbreken in kleinere netwerken. Naast dat dit wat fijner voor de ogen is, maakt dit de rest van het spel ook makkelijker, aangezien je het ene mijnenveld opsplitst in meerdere kleinere mijnenvelden.

Symmetrie en gokken

Als het netwerk waar je op speelt erg symmetrisch is, dan heeft dit ook invloed op het spel. Een voorbeeld hiervan is het Petersen netwerk, te zien in het plaatje hieronder. Dit netwerk is compleet symmetrisch: we kunnen ieder vakje verplaatsen naar de plek van een ander vakje en de overige vakjes vervolgens verschuiven zodat het plaatje er weer exact hetzelfde uitziet. Om deze reden doet het er aan het begin niet toe op welk vakje je het eerst stapt.

Het Petersen-netwerk.

Stel dat je nu op een vakje stapt en deze een ‘1’ laat zien, terwijl er drie mijnen in totaal zijn. Als je hierna op een van de drie buren van het eerste vakje klikt, stap je op een mijn met kans 1/3. In de overige zes vakjes liggen de overige twee mijnen, dus als je op een van deze vakjes stapt is de kans wederom 1/3. Deze symmetrie zorgt er dus voor dat je niet beter kunt dan willekeurig gokken.

Een ander voorbeeld van een netwerk met veel symmetrie is de dodecaëder (ook wel bekend als het regelmatige twaalfvlak). Als je twaalf regelmatige vijfhoeken uitknipt en deze op elkaar plakt tot een soort voetbal (zie onderstaand plaatje), dan is deze voetbal een soort netwerk: de vakjes zijn de hoekpunten van de voetbal en twee vakjes zijn met elkaar verbonden als er een lijn van de een naar de ander gaat.

Willekeurige netwerken

In deze blog heb ik een aantal netwerken genoemd waar je Netsweeper op kan spelen. Allereerst hebben we het netwerk van het afgelopen WK voetbal, het Petersen-netwerk en de dodecaëder. Met deze netwerken ben je waarschijnlijk al even zoet, maar ik heb ook nog een aantal willekeurig gegenereerde netwerken toegevoegd. Omdat deze iedere keer opnieuw willekeurig gegenereerd worden wanneer je het spel herstart, veeg je iedere keer weer een ander mijnenveld.

Het eerste willekeurige netwerk heet het ER-netwerk (ER staat voor Erdős–Rényi, maar de naam is niet zo belangrijk). Het bestaat simpelweg uit twintig vakjes, waarbij twee vakjes aan elkaar grenzen met kans 1/6. Als het ware wordt voor iedere twee vakjes een dobbelsteen gegooid en worden de twee vakjes met elkaar verbonden als er zes is gegooid. Zodoende kan het gebeuren dat er vakjes zonder verbindingen zijn, maar dit gebeurt niet al te vaak.

In het bovenstaande netwerk ligt het aantal buren van een vakje doorgaans tussen de een en de zes. Er zijn dus geen heel duidelijke hubs aanwezig. Een willekeurig netwerk dat meer hubs heeft is het PA-netwerk (PA staat voor Preferential Attachment, maar de naam is wederom niet erg belangrijk). In dit netwerk begin je met twee vakjes die met elkaar verbonden zijn en voeg je herhaaldelijk nieuwe vakjes toe, die je ieder verbindt met twee bestaande vakjes. De manier waarop de vakjes om mee te verbinden gekozen worden is willekeurig, maar wel dusdanig dat vakjes die al veel verbindingen hebben meer waarschijnlijk gekozen worden. Zodoende krijg je dus bepaalde vakjes met beduidend meer verbindingen dan de rest. Deze hubs maken het mijnenvegen wat moeilijker op dit netwerk.

Het vierletterwoordennetwerk

Het laatste netwerk is het vierletterwoordennetwerk. De punten van dit netwerk zijn woorden die in deze blog voorkomen en precies vier letters lang zijn. Je verbindt twee woorden met elkaar als ze precies één letter van elkaar verschillen. In het dagelijks leven gebruiken we heel veel vierletterwoorden (zoals ‘heel’ en ‘veel’) en er zijn er ook best veel die maar één letter van elkaar verschillen (wederom, zoals ‘heel’ en ‘veel’). Om het netwerk een beetje overzichtelijk te maken, laten we alleen maar de woorden zien die verbonden zijn aan het woord ‘mijn’. Dit kan via een directe verbinding zijn (zoals het woord ‘zijn’), of via een indirecte verbinding, zoals het woord ‘zien’.

Een woord komt dus alleen maar voor als er een pad van dat woord naar ‘mijn’ leidt. Het woord ‘uren’ staat bijvoorbeeld in de eerste zin van deze blog maar komt alleen maar voor in het vierletternetwerk als ik ook het woord ‘uien’ gebruik. En het woord ‘vier’ zou alleen maar in het vierletternetwerk voorkomen als ik ook nog eens het woord ‘uier’ zou gebruiken (oeps).

Van de 88 verschillende vierletterwoorden in deze blog, blijven er op deze manier nog maar 30 over. Het netwerk is hieronder te zien. Je ziet dat er een aantal kliekjes zijn, gevormd door lettercombinaties die veel vierletterwoorden delen (bijvoorbeeld -eel of -ijn) en dat deze onderling verbonden zijn door dunne slierten. Zodoende kun je dus redelijk makkelijk de verdeel-en-heers strategie toepassen op dit netwerk.

Dit geeft eindeloos veel mijnenvelden, ieder met zijn eigen karakteristieken die het spel en de beste veegstrategie beïnvloeden. Merk je deze verschillen tijdens het spelen? En merk je ook aan welke eigenschappen deze verschillen liggen?

Het spel Netsweeper is hierboven te spelen. Een eerdere versie van dit spel is in deze blog beschreven.