Öppna huvudmenyn
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ärghattar med sex olika färger att välja emellan, vilket ger 6*6*6*6 = 1296 möjliga färgkoder. Olika versioner av spelet har 6-12 rader för gissningar.

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

Spelets gångRedigera

1. Första spelaren (kodskaparen) väljer en hemlig färgkod med fyra eller sex färgsvampar/hattar, 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/nål för varje färgsvamp med rätt färg på rätt plats/position, och därefter en vit svarspigg för varje färgsvamp med rätt färg men på fel plats/position. 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 så snabbt som möjligt.

RegelvarianterRedigera

En alternativ regel är att tillåta samma färg max en gång i färgkoden, alltså 6*5*4*3 = 360 möjliga koder, vilket gör spelet mycket lättare. Detta är ett bra 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*7*6*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ösningarRedigera

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.[1] Om dator finns uppskattas lösningar som använder små systemresurser eller som kan programmeras enkelt.

FemstegslösningarRedigera

Å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.[2] 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%.[3]

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 och ett minimalt ökat genomsnitt till 4,341, hittas alltid en lösning inom fem försök.[4]

Andra lösningarRedigera

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"[5], 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, om detta antal kan minskas till fem försök eftersom uttömmande kontroll kräver 6^(5×4)=6^(20)= ca 3,7×10^(15) beräkningar).[6]

Å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.[7]

ReferenserRedigera

Externa länkarRedigera