Master Mind

[Noixe]

Salve,

penso conosciate tutti questo gioco, vi chiedo quindi qualcosa sulle regole:

Innanzi tutto so che:

1) La sequenza e' formata da 4 elementi
2) I 4 elementi sono scelti da un gruppo di 6
3) Ci possono essere doppioni
4) I tentativi a disposizione devono essere 8 (e' vero che 8 tentativi sono
sufficienti a vincere sempre? Secondo quale regola?)


Ora, quando si indovinano posizioni e colori?

Ad es. supponiamo che i 6 elementi siano:

A: Arancione
B: Blu
F: Fucsia
G: Giallo
R: Rosso
V: Verde

E che la sequenza da indovinare sia GBRB:

Se io come primo tentativo scrivo: BARB

Ho indovinato: 2 posizione e 2 colori?
In pratica i doppioni non vanno contati 2 volte per quanto riguarda i
colori?

Grazie
--
Noixe

[Ivan Sofa n.1]

Post by Noixe
Se io come primo tentativo scrivo: BARB
Ho indovinato: 2 posizione e 2 colori?

2-1

due al posto giusto e uno al posto sbagliato

ivan

[Noixe]

Post by Ivan Sofa n.1

Post by Noixe
Se io come primo tentativo scrivo: BARB
Ho indovinato: 2 posizione e 2 colori?

2-1
due al posto giusto e uno al posto sbagliato

No aspetta, con "RB" ho indovinato sia 2 posizioni che 2 colori. Poi volevo
sapere se la "B" iniziale va conteggiata come colore.

Ciao

[Luigi Pasato]

Post by Noixe

Post by Ivan Sofa n.1

Post by Noixe
Se io come primo tentativo scrivo: BARB
Ho indovinato: 2 posizione e 2 colori?

2-1
due al posto giusto e uno al posto sbagliato

No aspetta, con "RB" ho indovinato sia 2 posizioni che 2 colori. Poi volevo
sapere se la "B" iniziale va conteggiata come colore.
Ciao

No, hai indovinato 2-1 come dice Ivan.
Quando indovini la posizione è scontato che hai indovinato anche il colore
(non è possibile indovinare la posizione ma non il colore... ;) ), per cui
devi solo segnalare la posizione corretta (e quindi anche il colore) con
il segnalino nero. Quando indovini un colore ma la non la posizione, metti
un segnalino bianco.

Ciao

Luigi [IHG87]

[Paolo Fasce]

Post by Luigi Pasato
non è possibile indovinare la posizione ma non il colore... ;)

Mbe', se si ammette la possibilita' di lasciare dei buchi vuoti...

[Noixe]

Post by Luigi Pasato
No, hai indovinato 2-1 come dice Ivan.
Quando indovini la posizione è scontato che hai indovinato anche il colore
(non è possibile indovinare la posizione ma non il colore... ;) ), per cui
devi solo segnalare la posizione corretta (e quindi anche il colore) con
il segnalino nero. Quando indovini un colore ma la non la posizione, metti
un segnalino bianco.

Umh, quindi se ad es. la sequenza esatta fosse: ABAC
Il tentativo BABA significa che: Ho indovinato 0 posizioni esatte e 3 oppure
4 colori giusti (ma posizione sbagliata)?

Perche' io penso:

3 se si fa un controllo "1 a 1"
4 se semplicemente preso un elemento del tentativo ne esiste almeno uno del
suo stesso colore nella sequenza esatta.

Grazie

[Luigi Pasato]

Post by Noixe
Umh, quindi se ad es. la sequenza esatta fosse: ABAC
Il tentativo BABA significa che: Ho indovinato 0 posizioni esatte e 3 oppure
4 colori giusti (ma posizione sbagliata)?
3 se si fa un controllo "1 a 1"
4 se semplicemente preso un elemento del tentativo ne esiste almeno uno del
suo stesso colore nella sequenza esatta.
Grazie

Riprendendo il tuo esempio, bisogna poter differenziare, per esempio, le
sequenze iniziali ABAC e ABAB, dato che con il tentativo BABA verrebbero
assegnate 0 posizioni esatte e 4 colori giusti per entrambe le sequenze.

Infatti il modo corretto è:
3 colori giusti (per ABAC) e 4 colori giusti (per ABAB).

Ciao

Luigi [IHG87]

[Ivan Sofa n.1]

Post by Noixe

Post by Luigi Pasato
No, hai indovinato 2-1 come dice Ivan.
Quando indovini la posizione è scontato che hai indovinato anche il colore
(non è possibile indovinare la posizione ma non il colore... ;) ), per cui
devi solo segnalare la posizione corretta (e quindi anche il colore) con
il segnalino nero. Quando indovini un colore ma la non la posizione, metti
un segnalino bianco.

Umh, quindi se ad es. la sequenza esatta fosse: ABAC
Il tentativo BABA significa che: Ho indovinato 0 posizioni esatte e 3 oppure
4 colori giusti (ma posizione sbagliata)?

hai fatto 0-3.

Post by Noixe
3 se si fa un controllo "1 a 1"

praticamente sì.

Post by Noixe
4 se semplicemente preso un elemento del tentativo ne esiste almeno uno del
suo stesso colore nella sequenza esatta.

no, così non è corretto e se fosse così sarebbe davvero un macello risolvere
il mastermind.

ivan

[Ivan Sofa n.1]

Post by Noixe

Post by Ivan Sofa n.1

Post by Noixe
Se io come primo tentativo scrivo: BARB
Ho indovinato: 2 posizione e 2 colori?

2-1
due al posto giusto e uno al posto sbagliato

No aspetta, con "RB" ho indovinato sia 2 posizioni che 2 colori. Poi volevo
sapere se la "B" iniziale va conteggiata come colore.

come fai ad indovinare una posizione senza indovinarne il colore? e che sei
un mago? O_o

fidati: 2-1.

ivan

[Paolo Coletti]

Post by Noixe
4) I tentativi a disposizione devono essere 8 (e' vero che 8 tentativi sono
sufficienti a vincere sempre? Secondo quale regola?)

non ho mai sentito questa regola.
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

Post by Noixe
Se io come primo tentativo scrivo: BARB
Ho indovinato: 2 posizione e 2 colori?
In pratica i doppioni non vanno contati 2 volte per quanto riguarda i
colori?

se dopo tutti i post precedenti ci fossero ancora dubbi, l'agoritmo
e':

1) confronta posizione per posizione e segna (con il nero) quanti sono
uguali per colore. Toglili.
2) prendi il primo di una delle due sequenze. Se ce n'e' uno dello
stesso colore nell'altra sequenza, segna (con il bianco) e togli
entrambi. Avanti cosi' con gli altri tre della medesima sequenza.

Secondo me non si possono lasciare spazi vuoti, come dice Paolo.
Potrebbe essere piu' facile (sicuramente per i principianti).

ciao,
Paolo

[Paolo Fasce]

Il Wed, 11 Aug 2004 09:56:32 +0200, Paolo Coletti

Post by Paolo Coletti
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

A naso, sono arciconvinto del contrario.

[Ivan Sofa n.1]

Post by Paolo Fasce
Il Wed, 11 Aug 2004 09:56:32 +0200, Paolo Coletti

Post by Paolo Coletti
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

A naso, sono arciconvinto del contrario.

effettivamente ci dovrebbe essere un algoritmo minimo. Ma qualcuno l'avrà
mai sviluppato?

ivan

[MaBi]

Post by Paolo Coletti

Post by Noixe
4) I tentativi a disposizione devono essere 8 (e' vero che 8 tentativi sono
sufficienti a vincere sempre? Secondo quale regola?)

non ho mai sentito questa regola.
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

No, la complessita' computazionale del MasterMind e' praticamente
nulla, visto che le combinazioni possibili sono solo 6^4=1296.
(era un classico ai bei vecchi tempi dello ZX-80, VIC-20, ecc. :)

Esiste un algoritmo ottimale che permette di trovare la soluzione
in un massimo di 6 tentativi. Il numero 8 a cui si riferisce Noixe
probabilmente viene dal fatto che 8 e' il numero massimo di tentativi
necessari seguendo il banale algoritmo di fare nuovi tentativi a caso
purche' consistenti con le risposte avute finora. Direi quindi che
limitare ad 8 i tentativi e' sensato.

Cercando con Google si trovano migliaia di riferimenti in rete,
ne metto uno a caso:
http://www.tnelson.demon.co.uk/mastermind/

[Ivan Sofa n.1]

Post by MaBi

Post by Paolo Coletti

Post by Noixe
4) I tentativi a disposizione devono essere 8 (e' vero che 8 tentativi sono
sufficienti a vincere sempre? Secondo quale regola?)

non ho mai sentito questa regola.
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

No, la complessita' computazionale del MasterMind e' praticamente
nulla, visto che le combinazioni possibili sono solo 6^4=1296.
(era un classico ai bei vecchi tempi dello ZX-80, VIC-20, ecc. :)
Esiste un algoritmo ottimale che permette di trovare la soluzione
in un massimo di 6 tentativi.

ecco, come non detto nel post precedente :-))))

Il numero 8 a cui si riferisce Noixe

Post by MaBi
probabilmente viene dal fatto che 8 e' il numero massimo di tentativi
necessari seguendo il banale algoritmo di fare nuovi tentativi a caso
purche' consistenti con le risposte avute finora. Direi quindi che
limitare ad 8 i tentativi e' sensato.
Cercando con Google si trovano migliaia di riferimenti in rete,
http://www.tnelson.demon.co.uk/mastermind/

[Noixe]

Post by Paolo Coletti
non ho mai sentito questa regola.
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

Non credo... cosi al volo mi viene in mente come algoritmo anche una
semplice sequenza di 4 cicli for annidati ognuno che va da 1 a 6... prima o
poi la sequenza esce... ma forse non intendi algoritmi di questo tipo?

Post by Paolo Coletti
se dopo tutti i post precedenti ci fossero ancora dubbi, l'agoritmo
1) confronta posizione per posizione e segna (con il nero) quanti sono
uguali per colore. Toglili.
2) prendi il primo di una delle due sequenze. Se ce n'e' uno dello
stesso colore nell'altra sequenza, segna (con il bianco) e togli
entrambi. Avanti cosi' con gli altri tre della medesima sequenza.

Ma pensa, e' proprio l'algoritmo che ho usato per il programmino ;P
Anche se spesso mentre in mente e' chiaro, nella programmazione spuntano
errori vari :(
Ma penso di aver risolto.

Anzi, se volete ve lo invio piu che altro per sapere se il programma si
comporta bene nel segnalare cosa si e' indovinato.

Ciao

[Ivan Sofa n.1]

Post by Noixe

Post by Paolo Coletti
non ho mai sentito questa regola.
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

Non credo... cosi al volo mi viene in mente come algoritmo anche una
semplice sequenza di 4 cicli for annidati ognuno che va da 1 a 6... prima o
poi la sequenza esce... ma forse non intendi algoritmi di questo tipo?

vabbè così non hai nemmeno bisogno di sapere se ci sei andato vicino.....
:-)

ivan

[angiolillo]

Post by Paolo Coletti
Secondo me non si possono lasciare spazi vuoti, come dice Paolo.
Potrebbe essere piu' facile (sicuramente per i principianti).

Con le regole base no, non si possono lasciare vuoti. C'è una variante
in cui si può, e in pratica lo spazio vuoto è considerato un settimo
colore: ovviamente, indovinare diventa più difficile.

Ci sono poi altre varianti ancora... Se non ricordo male 8 colori con
codici da 5, oppure pilini di cui vanno indivinati posizione, colore e
forma (ce n'è di tondi, quadrati, triangolari, a croce...).

Nelle versioni carta e matita ce n'è con numeri da 0 a 9 non
ripetibili, o con parole di 4 lettere di senso compiuto (una nascosta,
e anche i tentativi di indovinare vanno con parole di 4 lettere di
senso compiuto). Qualcosa avevo messo in un libro LDC "Giocare con
carta e matita", la cui edizione in italiano è però attualmente fuori
stampa, e forse anche in un supplemento della rivista "E Giochi" che
ne costituiva un'edizione ridotta.

Ciao a tutti!

Andrea

[Paolo Coletti]

On Wed, 11 Aug 2004 09:56:32 +0200, Paolo Coletti

Post by Paolo Coletti
Ad occhio penso che la complessita' computazionale del problema sia
tale che impedisce lo sviluppo di un algoritmo certo che funzioni in
un numero di mosse.

ehmmm, forse aver usato la parola ALGORITMO ha fatto scattare nella
mente degli informatici la possibilita' immediata di poter utilizzare
un computer per giocare.

Scusate, ero rimasto ancora con carta e matitina...

Io intendevo la dimostrazione di una strategia ottima (che faccia
sempre tentativi che minimizzano il numero medio di mosse future).

Pero' do il mio piccolo contributo dicendo che le mosse, se si applica
questa strategia http://www.tnelson.demon.co.uk/mastermind/table.html
sono al massimo 5 (anche se la strategia non e' ottima).

ciao,
Paolo