Mastermind

Den här artikeln behandlar spelet Mastermind. För Wallanderfilmen, se Wallander – Mastermind.

Mastermind

Mastermind eller master mind är ett logikbaserat brädspel för två spelare som uppfanns 1970 av israelen Mordecai Meirowitz. Färgkoden består i originalutgåvan av fyra färgsvampar (enfärgad pigg som placeras i hål på spelplanen) med sex olika färger att välja mellan, vilket ger $6\cdot 6\cdot 6\cdot 6=1296$ möjliga färgkoder. Det finns även en svårare version där färgkoden består av fem färgsvampar med åtta olika färger att välja mellan. Detta i sin tur ger spelet $8\cdot 8\cdot 8\cdot 8\cdot 8=32768$ möjliga färgkoder.

Mastermind har många likheter med ett tidigare engelskt spel ”Bulls and Cows”, som spelas med papper och penna.

Spelets gång

1. Första spelaren (kodskaparen) väljer en hemlig färgkod med fyra färgsvampar, där samma färg får användas flera gånger.
2. Andra spelaren (kodbrytaren) gör ett första (av upp till tolv) försök att gissa rätt färg.
3. Första spelaren återkopplar varje gissning genom att först placera en svart (ibland röd) svarspigg för varje färgsvamp med rätt färg på rätt plats, och därefter en vit svarspigg för varje färgsvamp med rätt färg men på fel plats. Det finns 14 olika kombinationer av vägledande svar, eftersom svarssekvensen 31/SSSV inte är möjlig och 40/SSSS innebär rätt färgkod funnen.
4. Andra spelaren gör därefter ett nytt försök med målet att lyckas klura ut den hemliga färgkoden på så få försök som möjligt.

Regelvarianter

En alternativ regel är att tillåta samma färg max en gång i färgkoden, alltså $6\cdot 5\cdot 4\cdot 3=360$ möjliga koder, vilket gör spelet mycket lättare. Detta är ett alternativ med till exempel ”Mini Mastermind” med endast sex försöksrader, eller vid spel med små barn.

En annan variant är att spela med åtta möjliga färger, där svarspiggarna har samma storlek som färgsvamparna, och därför kan användas i färgkoden. Kombinerat med alternativregeln om samma färg max en gång ger det $8\cdot 7\cdot 6\cdot 5=1680$ möjliga färgkoder.

Mastermind har liksom flera andra sällskapsspel även implementerats i olika versioner för spel på dator eller mobiltelefon, även med datorn (AI) som motspelare.

Lösningar

Vad som anses vara bästa lösning beror på situation. Som sällskapsspel, med begränsad betänketid och utan tillgång till dator, sätter antalet försöksrader en praktisk gräns. Att hitta en lösning på minimalt antal försök i genomsnitt gillas i matematiska sammanhang. Om dator finns uppskattas lösningar som använder små systemresurser eller som kan programmeras enkelt.

Femstegslösningar

År 1977 visade Donald Ervin Knuth att kodbrytaren kan hitta färgkoden på max fem försök genom en algoritm med försök som stegvis utesluter så många olika felaktiga varianter som möjligt, förutsatt att startförsöket är 1122, dvs. två färgsvampar av den första färgen och därefter två av den andra färgen. Efterföljande tre försök i ett vanligt typfall är 1344, 3526 och 1462. Knuth visade också att andra startvarianter inte kan garantera en lösning inom fem försök. Startförsöket 1122 kombinerat med efterföljande svarssekvens, minskar antalet möjliga färgkoder maximalt. I värsta fallen finns 256 av inledande 1296 färgkoder kvar, vilket ändå bara är 20 %.

Efterföljande matematiker har hittat olika algoritmer som minskar det genomsnittliga antalet försök som behövs för att lösa färgkoden. År 1993 gjorde Kenji Koyama och Tony W. Lai en uttömmande djup-först sökning som visade att den optimala metoden når ett genomsnitt på $5625/1296=4,3403$ försök, med ett värsta fall på sex. De visade också samma år att med en mindre förändring som ger ett minimalt ökat genomsnitt till 4,341 hittas alltid en lösning inom fem försök.

Andra lösningar

Det ”statiska” problemet, formulerat 1983 av Vasicek Chvátal, med att hitta minsta antalet gissningar som kodbrytaren måste göra på en gång i början av spelet utan att vänta på första och enda återkopplingen, och sedan när du har fått återkopplingen, bestämma koden helt i nästa ”försök”, kan lösas med sex initiala gissningar enligt Greenwell 1999–2000. En speciell kombination som gör det möjligt för kodbrytaren att känna till koden efter sex gissningar (och så den sjunde för att avslöja sin kunskap om lösningen) är 1221, 2354, 3311, 4524, 5656, 6643. Det är inte känt, men osannolikt, huruvida detta antal kan minskas till fem försök eftersom uttömmande kontroll kräver $6^{5\cdot 4}=6^{20}\approx 3,7\cdot 10^{15}$ beräkningar.

Åren 1999–2000 gör Swaszek analyser av praktiska strategier som inte kräver komplicerad journalföring eller användning av dator. Att göra en slumpmässig gissning från uppsättningen av återstående kandidatkodssekvenser ger en förvånansvärt kort genomsnittlig spellängd på 4,638, samtidigt som man tolkar varje gissning som ett nummer och använder nästa högre antal i överensstämmelse med känd information, ger ett spel med medellängd 4,758.

Referenser

• Denna artikel är helt eller delvis översatt från motsvarande artikel på engelska Wikipedia.

Externa länkar

• Spela Mastermind på internet
• Efficient solutions for Mastermind using genetic algorithms