Mastermind (gioco da tavolo) - Mastermind (board game)

Mente

Un gioco completato di Mastermind
Progettato da	Mordecai Meirowitz
anni attivi	1970 ad oggi
Generi	Gioco da tavolo Gioco con carta e matita [root]
Giocatori	2
Tempo di preparazione	< 5 minuti
Tempo di esecuzione	10–30 minuti
possibilità casuale	Trascurabile
Fascia di età	8 e oltre

Mastermind o Master Mind è ungioco di rottura del codice per due giocatori. Il moderno gioco con i pioli è stato inventato nel 1970 da Mordecai Meirowitz , unpostmaster israeliano ed esperto di telecomunicazioni. Assomiglia a un precedente gioco di carta e matita chiamato Bulls and Cows che potrebbe risalire a un secolo fa.

Gioco e regole

Il gioco si gioca utilizzando:

• una scheda di decodifica , con uno scudo a un'estremità che copre una fila di quattro grandi fori e dodici (o dieci, o otto, o sei) file aggiuntive contenenti quattro grandi fori accanto a una serie di quattro piccoli fori;
• codice pioli di sei colori diversi (o più; vedi Variazioni sotto), con teste tonde, che verranno posizionate nei grandi fori della scacchiera; e
• pioli chiave , alcuni colorati di nero, altri bianchi, che sono a testa piatta e più piccoli dei pioli del codice; saranno inseriti nei piccoli fori sulla tavola.

I due giocatori decidono in anticipo quante partite giocheranno, che deve essere un numero pari . Un giocatore diventa il codemaker , l'altro il codebreaker . Il codemaker sceglie uno schema di quattro code pegging. Duplicati e spazi vuoti sono consentiti a seconda della scelta del giocatore, quindi il giocatore potrebbe anche scegliere quattro pedine del codice dello stesso colore o quattro spazi vuoti. Nel caso in cui gli spazi non vengano scelti per far parte del gioco, il decifratore non può utilizzare gli spazi vuoti per stabilire il codice finale. Il pattern scelto viene posizionato nei quattro fori coperti dallo scudo, visibili al codemaker ma non al codebreaker.

Il decifratore cerca di indovinare lo schema, sia nell'ordine che nel colore, entro otto-dodici turni. Ogni ipotesi viene effettuata posizionando una fila di pioli di codice sulla scheda di decodifica. Una volta posizionato, il codemaker fornisce un feedback posizionando da zero a quattro pioli chiave nei piccoli fori della riga con l'ipotesi. Un piolo chiave colorato o nero viene posizionato per ciascun codice piolo dall'ipotesi che è corretto sia nel colore che nella posizione. Un piolo chiave bianco indica l'esistenza di un piolo codice colore corretto posizionato nella posizione sbagliata.

Screenshot dell'implementazione del software (ColorCode) che illustra l'esempio.

Se ci sono colori duplicati nell'ipotesi, non tutti possono ricevere un piolo chiave a meno che non corrispondano allo stesso numero di colori duplicati nel codice nascosto. Ad esempio, se il codice nascosto è rosso-rosso-blu-blu e il giocatore indovina rosso-rosso-rosso-blu, il codemaker assegnerà due chiavi colorate per i due rossi corretti, niente per il terzo rosso perché non c'è un terzo rosso nel codice e un portachiavi colorato per il blu. Non viene fornita alcuna indicazione del fatto che il codice comprenda anche un secondo blu.

Una volta fornito il feedback, viene fatta un'altra ipotesi; supposizioni e feedback continuano ad alternarsi finché il decifratore di codici non indovina correttamente o tutte le righe delle schede di decodifica sono piene.

Tradizionalmente, i giocatori possono guadagnare punti solo giocando come codemaker. Il creatore del codice ottiene un punto per ogni ipotesi formulata dal decifratore. Un punto extra viene guadagnato dal codemaker se il codebreaker non è in grado di indovinare lo schema esatto entro il numero di turni specificato. (Un'alternativa è quella di segnare in base al numero di pioli chiave piazzati.) Il vincitore è colui che ha il maggior numero di punti dopo che è stato giocato il numero concordato di giochi.

Altre regole possono essere specificate.

Storia

Il gioco è basato su un vecchio gioco cartaceo chiamato Bulls and Cows . Un adattamento del computer di cui è stato eseguito nel 1960 su Cambridge University ‘s Titan sistema informatico, dove è stato chiamato 'MOO'. Questa versione è stata scritta da Frank King. C'era anche un'altra versione per il sistema di time sharing TSS/8, scritta da JS Felton e infine una versione per il sistema Multics al MIT da Jerrold Grochow.

Il moderno gioco con i pioli è stato inventato nel 1970 da Mordecai Meirowitz , un postmaster israeliano ed esperto di telecomunicazioni. Meirowitz ha presentato l'idea a molte importanti aziende di giocattoli ma, dopo averla mostrata alla Fiera Internazionale del Giocattolo di Norimberga , è stata ripresa da un'azienda di plastica, Invicta Plastics , con sede vicino a Leicester , nel Regno Unito . Invicta ha acquistato tutti i diritti del gioco e il fondatore, Edward Jones-Fenleigh, ha perfezionato ulteriormente il gioco. E 'stato rilasciato nel 1971-2.

Dal 1971, i diritti su Mastermind sono detenuti da Invicta Plastics. (Invicta ha sempre chiamato il gioco Master Mind ). Originariamente lo hanno prodotto da soli, anche se da allora hanno concesso in licenza la sua produzione a Hasbro in tutto il mondo, ad eccezione di Pressman Toys e Orda Industries che hanno i diritti di produzione rispettivamente negli Stati Uniti e in Israele.

A partire dal 1973, la scatola del gioco conteneva la fotografia di un uomo in giacca e cravatta seduto in primo piano, con una giovane donna asiatica in piedi dietro di lui. I due modelli amatoriali (Bill Woodward e Cecilia Fung) si sono riuniti nel giugno 2003 per posare per un'altra foto pubblicitaria.

Algoritmi e strategie

Prima di chiedere una migliore strategia del codebreaker bisogna definire qual è il significato di "migliore": Il numero minimo di mosse può essere analizzato nelle condizioni di caso peggiore e medio e nel senso di un valore minimax di uno zero- gioco della somma nella teoria dei giochi .

Le migliori strategie con quattro pioli e sei colori

Con quattro pioli e sei colori, ci sono 6 ⁴ = 1296 modelli diversi (consentendo colori duplicati).

Caso peggiore: algoritmo a cinque ipotesi

Nel 1977, Donald Knuth dimostrò che il decifratore può risolvere lo schema in cinque mosse o meno, utilizzando un algoritmo che riduce progressivamente il numero di possibili schemi. L'algoritmo funziona come segue:

1. Creare l'insieme S di 1296 possibili codici (1111, 1112 ... 6665, 6666)
2. Inizia con l'ipotesi iniziale 1122 (Knuth fornisce esempi che mostrano che questo algoritmo che utilizza altre prime ipotesi come 1123, 1234 non vince in cinque tentativi su ogni codice)
3. Gioca a indovinare per ottenere una risposta di pioli colorati e bianchi.
4. Se la risposta è quattro pioli colorati, la partita è vinta, l'algoritmo termina.
5. Altrimenti, rimuovi da S qualsiasi codice che non darebbe la stessa risposta se (la supposizione) fosse il codice.
6. Applicare la tecnica minimax per trovare un'ipotesi successiva come segue: per ogni possibile ipotesi, ovvero qualsiasi codice inutilizzato del 1296 e non solo quelli in S, calcolare quante possibilità in S verrebbero eliminate per ogni possibile punteggio peg colorato/bianco. Il punteggio di un'ipotesi è il numero minimo di possibilità che potrebbe eliminare da S. Un singolo passaggio per S per ogni codice inutilizzato del 1296 fornirà un conteggio dei risultati per ogni punteggio di peg colorato/bianco trovato; il punteggio piolo colorato/bianco con il numero di colpi più alto eliminerà il minor numero di possibilità; calcolare il punteggio di un'ipotesi utilizzando "minimo eliminato" = "conteggio di elementi in S" - (meno) "conteggio più alto". Dall'insieme di ipotesi con il punteggio massimo , selezionane una come ipotesi successiva, scegliendo un membro di S quando possibile. (Knuth segue la convenzione di scegliere l'ipotesi con il minor valore numerico, ad esempio 2345 è inferiore a 3456. Knuth fornisce anche un esempio che mostra che in alcuni casi nessun membro di S sarà tra le ipotesi con il punteggio più alto e quindi l'ipotesi non può vincere sul turno successivo, ma sarà necessario assicurarsi una vittoria in cinque.)
7. Ripetere dal passaggio 3.

Caso medio

I matematici successivi hanno trovato vari algoritmi che riducono il numero medio di giri necessari per risolvere il modello: nel 1993, Kenji Koyama e Tony W. Lai hanno eseguito una ricerca approfondita in profondità che mostra che il metodo ottimale per risolvere un codice casuale potrebbe raggiungere un media di 5625/1296 = 4,3403 turni da risolvere, con uno scenario peggiore di sei turni.

Valore minimo della teoria dei giochi

Il valore minimax nel senso della teoria dei giochi è 5600/1290 = 4,341. La strategia minimax del codemaker consiste in una selezione uniformemente distribuita di uno dei 1290 pattern con due o più colori.

Algoritmo genetico

Un nuovo algoritmo con un algoritmo genetico incorporato , in cui viene raccolto un ampio insieme di codici ammissibili attraverso le diverse generazioni. La qualità di ciascuno di questi codici è determinata sulla base di un confronto con una selezione di elementi dell'insieme ammissibile. Questo algoritmo si basa su un'euristica che assegna un punteggio a ciascuna combinazione idonea in base alla sua probabilità di essere effettivamente la combinazione nascosta. Poiché questa combinazione non è nota, il punteggio si basa sulle caratteristiche dell'insieme delle soluzioni ammissibili o sul campione di esse trovato dall'algoritmo evolutivo.

L'algoritmo funziona come segue:

1. Poni i = 1
2. Riproduci ipotesi iniziale fissa G ₁
3. Ottieni la risposta X ₁ e Y ₁
4. Ripeti mentre X _i ≠ P :
   1. Incrementa io
   2. Poni E _i = ∅ e h = 1
   3. Inizializza popolazione
   4. Ripeti mentre h ≤ maxgen e | E _io | ≤ maxsize :
      1. Genera nuova popolazione utilizzando crossover, mutazione, inversione e permutazione
      2. Calcola la forma fisica
      3. Aggiungi le combinazioni idonee a E _i
      4. Incrementa h
   5. Gioca a indovinare G _i che appartiene a E _i
   6. Ottieni risposta X _i e Y _i

Complessità e problema della soddisfacibilità

Nel novembre 2004, Michiel de Bondt ha dimostrato che risolvere un tabellone Mastermind è un problema NP-completo se giocato con n pioli per riga e due colori, mostrando come rappresentare un problema 3SAT uno su tre al suo interno. Ha anche mostrato lo stesso per Consistent Mastermind (giocando in modo che ogni ipotesi sia un candidato per il codice segreto che è coerente con i suggerimenti nelle ipotesi precedenti).

Il problema di soddisfacibilità di Mastermind è un problema decisionale che chiede: "Data una serie di ipotesi e il numero di pioli colorati e bianchi segnati per ogni ipotesi, esiste almeno uno schema segreto che genera quei punteggi esatti?" (In caso contrario, il codemaker deve aver valutato in modo errato almeno un'ipotesi.) Nel dicembre 2005, Jeff Stuckman e Guo-Qiang Zhang hanno mostrato in un articolo di arXiv che il problema di soddisfacibilità di Mastermind è NP-completo.

Variazioni

Variando il numero di colori e il numero di buche si ottiene uno spettro di giochi Mastermind con diversi livelli di difficoltà. Un'altra variante comune è quella di supportare un numero diverso di giocatori che assumono i ruoli di codemaker e codebreaker. Di seguito sono riportati alcuni esempi di giochi Mastermind prodotti da Invicta , Parker Brothers , Pressman , Hasbro e altri produttori di giochi:

Il livello di difficoltà di uno qualsiasi dei precedenti può essere aumentato trattando "vuoto" come un colore aggiuntivo o diminuito richiedendo solo che i colori del codice vengano indovinati, indipendentemente dalla posizione.

Sono state realizzate anche versioni del gioco per computer e Internet , a volte con variazioni nel numero e nel tipo di pezzi coinvolti e spesso con nomi diversi per evitare la violazione del marchio. Mastermind può essere giocato anche con carta e matita . Esiste una varietà numerica del Mastermind in cui viene indovinato un numero a 4 cifre.

Il gioco è stato compilato in Clubhouse Games: 51 Worldwide Classics per Switch con il nome "Hit & Blow".

Riferimenti

link esterno

• Mastermind: un approccio alla realtà aumentata, porting di un gioco legacy in un nuovo paradigma di interazione
• Articolo di Mathworld su Mastermind