View Full Version : ALGORITMO PER MASTERMIND
Visir932
05-07-2006, 13:11
Ciao Ragazzi,
ho un piccolo problema.
Devo sostenere un esame di informatica che consiste nel programmare una classe in Java che implementi tramite alcuni metodi un giocatore di Mastermind.
In pratica devo implementare questi 5 metodi:
void tell(int sequenceLength, int numberColors);
int specifyColor(int i);
Sequence guess();
Answer guessResult(Sequence guess);
void tellAnswer(Answer answer);
Inoltre ho già delle classi:quella Sequence,quella Answer,e un GameManager.
Una combinazione `e modellata dalla classe Sequence che ha un costruttore
che riceve come argomento la lunghezza della sequenza (ovvero n). Inoltre,
questa classe ha due metodi getColor( int ) e setColor( int, int ).
Una risposta `e modellata dalla classe Answer che ha un costruttore che riceve
come argomenti il numero di strike e il numero di ball. Inoltre, questa classe ha
due metodi getStrikes( ) e getBalls( ) che restituiscono, rispettivamente,
il numero di strike e il numero di ball della risposta.
Inizialmente,il GameManager comunica ai due giocatori la lunghezza n delle
combinazioni e il numero m di colori disponibili e chiede ad ogni giocatore di
specificare, per 0 " i " n−1, il valore del colore che si trova nell’(i+1)-esima
posizione della sua combinazione segreta. Successivamente, il gestore a turno
chiede ad un giocatore di effettuare un tentativo, chiede all’avversario di specificare
la risposta a tale tentativo e, infine, comunica al giocatore che ha fatto il
tentativo tale risposta. Il gestore termina il gioco se il numero di strike della risposta
`e uguale alla lunghezza della combinazione, per cui il giocatore che ha fatto
l’ultimo tentativo ha vinto
Della mia classe da implementare ho superato i primi due metodi ma al terzo mi sono bloccato.Come posso sviluppare un algoritmo che mi consenta di fare un tentativo?
Grazie a tutti per le risposte! ;)
Io Spammo!
05-07-2006, 14:23
Ringrazzi a vuoto, non hai fatto la domanda giusta e nessuno ti risponderà.
Devi chiedere qual'è la funzione che arrotonda un numero, o qualche cazzata del genere se vuoi una risposta.
Visir932
05-07-2006, 14:28
Voglio solo sapere un algoritmo funzionante che simuli un giocatore di mastermind!
Così va meglio?
Xalexalex
05-07-2006, 14:50
Ringrazzi a vuoto, non hai fatto la domanda giusta e nessuno ti risponderà.
Devi chiedere qual'è la funzione che arrotonda un numero, o qualche cazzata del genere se vuoi una risposta.
E' bello vedere che ci sono persone cordiali e disponibili su questo forum, che ti aiutano in modo costruttivo quando hai bisogno :)
P.S.: Ringrazi, non ringrazzi.
PP.S.: Sorry ma il Java non lo conosco...
Io Spammo!
05-07-2006, 15:10
No hai capito un cazzo.
Ho detto che è inutile che chiedi qualcosa, non dico di complicato, ma di appena normale, che non siano le 4 cazzate che si imparano nei primi 2 giorni di programmazione, perchè non ti risponderà nessuno.
Io ero stato iscritto in passato, e in 6 mesi, ho aperto almeno una decina di tread, senza mai ottenere una risposta da un cane.
Il moderatore, non c'è mai e non si scala nemmeno a leggere i topic, potrei insultarlo per intere pagine nella sua stessa sezione, e meno che qualcuno lo avverta, non se ne accorgerebbe neanche.
Ci sono solo centinai di niubbi che non sanno una forca di informatica, o in alternativa gente esperta che si fà solo i cazzi suoi o quelli dei loro amici, e che non si scaleranno mai a darti una mano, a meno che non chiedi qualcosa di terribilmente banale, perchè gli dai l'occasione di fare i bulli, e allora lì, prontamente, rispondono.
Hai capito ora, non ti sto sfottendo, ti sto solo dicendo come funziona qui per farti risparmiare tutto il tempo che ho perso io.
in bocca al lupo per l'esame, ed evita di girare per questo forum di merda che butti via solo tempo ed elettricità.
questo è il mio ultimo post.
Un caloroso "FOTTETEVI", a tutti quelli che hanno letto uno dei miei centinaia di tread, che sapevano aiutarmi, e che se ne sono sbattuti.
Un semplice "addio" per gli altri.
trallallero
05-07-2006, 15:23
No hai capito un cazzo.
Ho detto che è inutile che chiedi qualcosa, non dico di complicato, ma di appena normale, che non siano le 4 cazzate che si imparano nei primi 2 giorni di programmazione, perchè non ti risponderà nessuno.
Io ero stato iscritto in passato, e in 6 mesi, ho aperto almeno una decina di tread, senza mai ottenere una risposta da un cane.
Il moderatore, non c'è mai e non si scala nemmeno a leggere i topic, potrei insultarlo per intere pagine nella sua stessa sezione, e meno che qualcuno lo avverta, non se ne accorgerebbe neanche.
Ci sono solo centinai di niubbi che non sanno una forca di informatica, o in alternativa gente esperta che si fà solo i cazzi suoi o quelli dei loro amici, e che non si scaleranno mai a darti una mano, a meno che non chiedi qualcosa di terribilmente banale, perchè gli dai l'occasione di fare i bulli, e allora lì, prontamente, rispondono.
Hai capito ora, non ti sto sfottendo, ti sto solo dicendo come funziona qui per farti risparmiare tutto il tempo che ho perso io.
in bocca al lupo per l'esame, ed evita di girare per questo forum di merda che butti via solo tempo ed elettricità.
questo è il mio ultimo post.
Un caloroso "FOTTETEVI", a tutti quelli che hanno letto uno dei miei centinaia di tread, che sapevano aiutarmi, e che se ne sono sbattuti.
Un semplice "addio" per gli altri.
addio
per Visir932: se vuoi cercare qui:
http://sourceforge.net/search/?type_of_search=soft&words=mastermind
in bocca al lupo
Non è semplice... Ci sarebbe un po' da studiarci.... Prima di tutto di quale esame si tratta ? E' un esame di sola programmazione o anche di algoritmi ?
Comunque si trovano tanti algoritmi ed aiuti sulla rete...
http://www.geocities.com/shu97eb/solving.html
http://www.google.it/search?q=mastermind+algorithm&start=0&ie=utf-8&hl=it&oe=utf-8&client=firefox-a&rls=org.mozilla:it:official
Visir932
05-07-2006, 19:52
E' un esame di laboratorio di programmazione (in Java).Comunque ora do uno sguardo ai link che mi avete generosamente postato.
Vi posto comunque il pdf del progetto in caso qualcuno abbia voglia di leggerlo:
MASTERMIND (http://www.p2pforum.it/forum/attachment.php?attachmentid=9625&d=1151749654)
Grazie.
Una domanda: ti è possibile implementare il metodo guess() con un algoritmo genetico? Altrimenti non ne esci facilmente.
Visir932
05-07-2006, 20:37
Una domanda: ti è possibile implementare il metodo guess() con un algoritmo genetico? Altrimenti non ne esci facilmente.
Scusa l'ignoranza ma non capisco cosa mi vuoi dire.Cosa significa "genetico"?
Una domanda: ti è possibile implementare il metodo guess() con un algoritmo genetico? Altrimenti non ne esci facilmente.
Giusto...
Qui c'è come calcolare la funzione di fitness, anche se è in C# (di fatto è banale):
http://www.c-sharpcorner.com/Code/2002/July/MastermindAI.asp
Lì comunque fa uso di una libreria in C# che non dovrebbe essere troppo difficile da tradurre in Java...
Ringrazzi a vuoto, non hai fatto la domanda giusta e nessuno ti risponderà.
Devi chiedere qual'è la funzione che arrotonda un numero, o qualche cazzata del genere se vuoi una risposta. io sono il primo per le cazziate ai niubbi che non gli frega una mazza di programmazione e che chiedono "consigli su un buon libro di programmazione" (bleargh :Puke: ), ma sono anche un perfezionista: il cazziatone si, ma quando serve. qui non serve.
No hai capito un cazzo. no, tu :Prrr:
a proposito, si scrive "ringrazi" con una sola Z
Visir932
05-07-2006, 20:56
Comunque è chiaro che i metodi che posso usare sono solo quei 5 che ho scritto all'inizio,vero?Inoltre non mi serve niente di grafico quindi..tanto di guadagnato!
Ps.Grazie per la vostra disponibilità!
Quelli sono solo i metodi pubblici (in pratica l'interfaccia)... Altre classi non pubbliche o metodi privati credo che tu li possa tranuillamente usare...
Visir932
05-07-2006, 21:12
Quelli sono solo i metodi pubblici (in pratica l'interfaccia)... Altre classi non pubbliche o metodi privati credo che tu li possa tranuillamente usare...
Guarda, le uniche specifiche del progetto sono quelle contenute nel pdf che ho postato.Parlando con il professore mi ha fatto capire che l'importante è che funzioni a dovere.
Il moderatore, non c'è mai e non si scala nemmeno a leggere i topic, potrei insultarlo per intere pagine nella sua stessa sezione, e meno che qualcuno lo avverta, non se ne accorgerebbe neanche.
segnalato :D
scherzo :p
segnalato :D
scherzo :p
Nota la scrittina sotto al nick ;)
Nota la scrittina sotto al nick ;) ma lol :asd:
cmq era un penoso complessato
Scusa l'ignoranza ma non capisco cosa mi vuoi dire.Cosa significa "genetico"?
Un algoritmo genetico è un modello di algoritmo, chiamato così perchè ispirato alle regole evoluzionistiche naturali (riproduzione - mutazione - inversione genetica), utilizzato per risolvere problemi di ottimizzazione combinatoria.
Bene, il problema del mastermind è un problema di ottimizzazione combinatoria, oltre ad un buon inizio per chi si affaccia all'intelligenza artificiale.
Ti chiedevo se potevi implementare il metodo con un algoritmo genetico sottintendendo se lo avevi studiato. Altrimenti il prof immediatamente ti dirà che hai copiato da qualche parte :)
Comunque mi è venuta un'idea. Tutti gli algoritmi di ottimizzazione combinatoria che conosco che possono risolvere il tuo problema hannno lo scopo di minimizzare il numero di mosse che servono ad arrivare alla soluzione.
Se questo (come presumo) a te non interessa, ma il tuo scopo è semplicemente quello di arrivare ad una soluzione, ti propongo un semplice algoritmo che mi è venuto in mente proprio ora :) E' abbastanza "bovino" ma semplicissimo da implementare come metodo "Sequence guess()". Funziona così:
1) La prima volta, il metodo genera una soluzione ammissibile scegliendo casualmente n colori diversi dagli m colori disponibili. Ovviamente scelto un colore, devi evitare di sceglierlo nuovamente dal pool di m elementi, a meno che non sia prevista la possibilità di scegliere più di una volta lo stesso colore. Memorizzi tale soluzione in una variabile che chiamiamo soluzione_corrente.
2) Richiedi al GameManager di valutare la soluzione corrente. Se è corretta, hai vinto (:D) ed esci, altrimenti salvi in due variabili intere (le chiamiamo strikes e balls) la risposta del game manager.
3) Prendi soluzione_corrente ed applichi a questa una mutazione in modo casuale. In parole povere, puoi avere due tipi di mutazione:
3.1) scambio di posizione tra due elementi della soluzione
3.2) sostituzione di un elemento con un altro dal pool di m elementi
per chiarire meglio, immagina di avere un pool di 6 elementi, e la soluzione di 4 elementi.
Pool m: 123456
Soluzione n: 1354
La mutazione 3.1 può essere del tipo:
Mutazione: 4351 (ho scambiato il primo elemento con il quarto)
mentre la 3.2 può essere:
Mutazione: 1364 (ho tolto il 5 per metterci un elemento del pool (tra i due rimasti) che non era presente prima in soluzione).
Generare una delle due mutazioni (quale delle due la scegli casualmente ad ogni iterazione dell'algoritmo) è davvero un gioco da ragazzi, 4 righe di codice...
4) Memorizzi la soluzione "mutata" nella variabile nuova_soluzione. Mi raccomando a non modificare il contenuto di soluzione_corrente per ora...
5) Proponi al GameManager la nuova soluzione. Se hai indovinato, esci. Altrimenti confronta la risposta (strikes e balls) con i valori memorizzati prima nelle variabili strikes e balls. Hai 3 casi:
5.1) Gli strikes della nuova soluzione sono maggiori del valore memorizzato
in strikes. In questo caso, metti il valore di nuova_soluzione
in soluzione_corrente ed aggiorni le variabili strikes e
balls
5.2) Gli strikes della nuova soluzione sono minori del valore memorizzato in
in strikes. In questo caso, ti tieni soluzione_corrente.
5.3) Gli strikes della nuova soluzione sono uguali al valore memorizzato in
strikes. In questo caso, consideri il numero di balls. Per farla
breve (come puoi immaginare) se i balls sono maggiori aggiorni la
soluzione, se minori ti tieni soluzione_corrente, se uguali sei libero
di tenerti soluzione_corrente o aggiornare tale valore con
nuova_soluzione.
6) Ritorni al punto 3.
Il metodo non è proprio ottimo, ma è semplicissimo da implementare e funziona. Soprattutto, è sì "bovino" se paragonato ad un algoritmo genetico o ad un min-max, però non è del tutto casuale, dal momento che considera sempre la bontà di una nuova soluzione generata casualmente rispetto a quella vecchia. Tra l'altro, con i valori proposti nella traccia (m=6 ed n=4) raggiungi una soluzione neanche troppo lentamente ;)
Spero di esserti stato d'aiuto. Ciao :)
EDIT: Io ho supposto che, dato il pool di colori, la soluzione sia composta di colori diversi. Se invece la traccia del problema ti permette di avere una soluzione con un colore preso più volte (ad esempio, con il pool 123456, una soluzione può essere tranquillamente del tipo 1155), c'è un vantaggio ed uno svatnaggio, perchè la generazione della prima soluzione (passo 1) è più semplice (non hai vincoli), mentre nella mutazione (passo 3) devi controllare se la nuova soluzione (mutata) non sia uguale alla vecchia soluzione (soluzione_corrente), nel qual caso la rigeneri fino ad avere una soluzione diversa prima di proseguire al passo 4.
trallallero
06-07-2006, 10:45
Comunque mi è venuta un'idea. Tutti gli algoritmi di ottimizzazione combinatoria che conosco che possono risolvere il tuo problema hannno lo scopo di minimizzare il numero di mosse che servono ad arrivare alla soluzione.
Se questo (come presumo) a te non interessa, ma il tuo scopo è semplicemente quello di arrivare ad una soluzione, ti propongo un semplice algoritmo che mi è venuto in mente proprio ora :) E' abbastanza "bovino" ma semplicissimo da implementare come metodo "Sequence guess()". Funziona così:
1) La prima volta, il metodo genera una soluzione ammissibile scegliendo casualmente n colori diversi dagli m colori disponibili. Ovviamente scelto un colore, devi evitare di sceglierlo nuovamente dal pool di m elementi, a meno che non sia prevista la possibilità di scegliere più di una volta lo stesso colore. Memorizzi tale soluzione in una variabile che chiamiamo soluzione_corrente.
2) Richiedi al GameManager di valutare la soluzione corrente. Se è corretta, hai vinto (:D) ed esci, altrimenti salvi in due variabili intere (le chiamiamo strikes e balls) la risposta del game manager.
3) Prendi soluzione_corrente ed applichi a questa una mutazione in modo casuale. In parole povere, puoi avere due tipi di mutazione:
3.1) scambio di posizione tra due elementi della soluzione
3.2) sostituzione di un elemento con un altro dal pool di m elementi
per chiarire meglio, immagina di avere un pool di 6 elementi, e la soluzione di 4 elementi.
Pool m: 123456
Soluzione n: 1354
La mutazione 3.1 può essere del tipo:
Mutazione: 4351 (ho scambiato il primo elemento con il quarto)
mentre la 3.2 può essere:
Mutazione: 1364 (ho tolto il 5 per metterci un elemento del pool (tra i due rimasti) che non era presente prima in soluzione).
Generare una delle due mutazioni (quale delle due la scegli casualmente ad ogni iterazione dell'algoritmo) è davvero un gioco da ragazzi, 4 righe di codice...
4) Memorizzi la soluzione "mutata" nella variabile nuova_soluzione. Mi raccomando a non modificare il contenuto di soluzione_corrente per ora...
5) Proponi al GameManager la nuova soluzione. Se hai indovinato, esci. Altrimenti confronta la risposta (strikes e balls) con i valori memorizzati prima nelle variabili strikes e balls. Hai 3 casi:
5.1) Gli strikes della nuova soluzione sono maggiori del valore memorizzato
in strikes. In questo caso, metti il valore di nuova_soluzione
in soluzione_corrente ed aggiorni le variabili strikes e
balls
5.2) Gli strikes della nuova soluzione sono minori del valore memorizzato in
in strikes. In questo caso, ti tieni soluzione_corrente.
5.3) Gli strikes della nuova soluzione sono uguali al valore memorizzato in
strikes. In questo caso, consideri il numero di balls. Per farla
breve (come puoi immaginare) se i balls sono maggiori aggiorni la
soluzione, se minori ti tieni soluzione_corrente, se uguali sei libero
di tenerti soluzione_corrente o aggiornare tale valore con
nuova_soluzione.
6) Ritorni al punto 3.
Il metodo non è proprio ottimo, ma è semplicissimo da implementare e funziona. Soprattutto, è sì "bovino" se paragonato ad un algoritmo genetico o ad un min-max, però non è del tutto casuale, dal momento che considera sempre la bontà di una nuova soluzione generata casualmente rispetto a quella vecchia. Tra l'altro, con i valori proposti nella traccia (m=6 ed n=4) raggiungi una soluzione neanche troppo lentamente ;)
Spero di esserti stato d'aiuto. Ciao :)
EDIT: Io ho supposto che, dato il pool di colori, la soluzione sia composta di colori diversi. Se invece la traccia del problema ti permette di avere una soluzione con un colore preso più volte (ad esempio, con il pool 123456, una soluzione può essere tranquillamente del tipo 1155), c'è un vantaggio ed uno svatnaggio, perchè la generazione della prima soluzione (passo 1) è più semplice (non hai vincoli), mentre nella mutazione (passo 3) devi controllare se la nuova soluzione (mutata) non sia uguale alla vecchia soluzione (soluzione_corrente), nel qual caso la rigeneri fino ad avere una soluzione diversa prima di proseguire al passo 4.
mi sembra buono, semplice per un programma semplice.
Potrebbe anche tener traccia delle soluzioni scartate
per evitare inutili giri ;)
anche questo é un gioco da ragazzi, 4 righe di codice :)
o poco piú :D
Potrebbe anche tener traccia delle soluzioni scartate
per evitare inutili giri ;)
anche questo é un gioco da ragazzi, 4 righe di codice :)
o poco piú :D
Infatti, poi in java è molto semplice, basta usare un "vettore dinamico". Si definisce un vettore di n elementi in cui memorizzare le soluzioni scartate, poi quando il vettore non basta più lo si "allarga": basta reinstanziarlo (o "ridefinirlo" per usare una parola non consona all'OOP ma familiare per chi programma in C) con la nuova dimensione (in Java il vecchio contenuto non viene perso), ed aggiungere quindi ulteriori soluzioni scartate.
Aggiungo un concetto per rendere più "intelligente" l'algoritmo da me postato prima, oltre al suggerimento di trallallero.
Al passo 3 (quello della mutazione), ho detto che hai due modi per scegliere una nuova soluzione. Bene, pensandoci, lo scambio tra due elementi della soluzione corrente è opportuna quando hai almeno 2 balls (due elementi del colore esatto ma in posizione non corretta, o più). In questo caso è opportuno uno scambio. Immagina, con n=4 e m=6, di avere 1 strike e 3 balls. Non avrebbe senso sostituire un elemento di n con uno tra i 2 elementi rimasti di m, dal momento che strikes+balls=n. Anche se avessi 1 strike e 2 balls conviene scambiare invece che sostituire. se invece hai meno di 2 balls (1 o nessun balls) allora è necessario sostituire un elemento con un altro tra quelli rimanenti in m (non avrebbe senso scambiare...)
trallallero
06-07-2006, 11:51
Aggiungo un concetto per rendere più "intelligente" l'algoritmo da me postato prima, oltre al suggerimento di trallallero.
Al passo 3 (quello della mutazione), ho detto che hai due modi per scegliere una nuova soluzione. Bene, pensandoci, lo scambio tra due elementi della soluzione corrente è opportuna quando hai almeno 2 balls (due elementi del colore esatto ma in posizione non corretta, o più). In questo caso è opportuno uno scambio. Immagina, con n=4 e m=6, di avere 1 strike e 3 balls. Non avrebbe senso sostituire un elemento di n con uno tra i 2 elementi rimasti di m, dal momento che strikes+balls=n. Anche se avessi 1 strike e 2 balls conviene scambiare invece che sostituire. se invece hai meno di 2 balls (1 o nessun balls) allora è necessario sostituire un elemento con un altro tra quelli rimanenti in m (non avrebbe senso scambiare...)
uhm ... brillante osservazione :D
Io invece continuo sulla strada del memorizzare:
nel momento in cui scopri che quel colore non c'é (il massimo sarebbe avere un risultato n=0
con 4 colori diversi :eek ) ti conviene eliminarlo dalle possibilitá.
Forse questo é un pó piú difficile da determinare, devi avere molti elementi certi,
ma se ci riesci riduci di parecchie le possibiltá successive ;)
Io invece proverei così...l'algoritmo si svolge in due fasi: la ricerca dei colori e la ricerca dell'ordine...
La prima fase è la ricerca dei colori e non si tiene conto della correttezza della posizione, ma solo del numero di colori corretti nella soluzione e funziona in questo modo:
0 - N è il numero di elementi della soluzione, I = -1, S è la soluzione finale che contiene i colori sicuramente corretti
1 - ++I, genero una soluzione composta da N/2 elementi del colore I e N-N/2 elementi del colore I+1, verifico la soluzione, salvo la risposta, se la soluzione non ha almeno un colore giusto eseguo nuovamente questo punto, altrimenti vado al 2.
2 - genero la soluzione inserendo tutti elementi del colore I. Verifico la soluzione. Inserisco il numero di colori corretti in S (ad es. ho 2 colori corretti inserisco 2 elementi di colore I nella soluzione). Se ho già tutti i colori che compongono la soluzione esco e vado alla fase successiva. Se il numero di colori corretti è = a quello della soluzione precedente torno al punto 1, altrimenti vado al 3.
3 - genero la soluzione inserendo tutti elementi del colore I. Verifico la soluzione. Inserisco il numero di colori corretti in S. Se ho già tutti i colori che compongono la soluzione esco e vado alla fase successiva, altrimenti torno al punto 1.
Questa fase è completata ed ora in S ho N elementi che compongono la souzione, ma sono nelle posizioni scorrette, quindi ora bisogna trovare il giusto ordinamento:
Genero una soluzione per ogni combinazione degli elementi di S. Ovviamente bisogna enumerare le combinazioni in modo da generarle sequenzialmente.
trallallero
06-07-2006, 13:04
Io invece proverei così...l'algoritmo si svolge in due fasi: la ricerca dei colori e la ricerca dell'ordine...
La prima fase è la ricerca dei colori e non si tiene conto della correttezza della posizione, ma solo del numero di colori corretti nella soluzione e funziona in questo modo:
0 - N è il numero di elementi della soluzione, I = -1, S è la soluzione finale che contiene i colori sicuramente corretti
1 - ++I, genero una soluzione composta da N/2 elementi del colore I e N-N/2 elementi del colore I+1, verifico la soluzione, salvo la risposta, se la soluzione non ha almeno un colore giusto eseguo nuovamente questo punto, altrimenti vado al 2.
2 - genero la soluzione inserendo tutti elementi del colore I. Verifico la soluzione. Inserisco il numero di colori corretti in S (ad es. ho 2 colori corretti inserisco 2 elementi di colore I nella soluzione). Se ho già tutti i colori che compongono la soluzione esco e vado alla fase successiva. Se il numero di colori corretti è = a quello della soluzione precedente torno al punto 1, altrimenti vado al 3.
3 - genero la soluzione inserendo tutti elementi del colore I. Verifico la soluzione. Inserisco il numero di colori corretti in S. Se ho già tutti i colori che compongono la soluzione esco e vado alla fase successiva, altrimenti torno al punto 1.
Questa fase è completata ed ora in S ho N elementi che compongono la souzione, ma sono nelle posizioni scorrette, quindi ora bisogna trovare il giusto ordinamento:
Genero una soluzione per ogni combinazione degli elementi di S. Ovviamente bisogna enumerare le combinazioni in modo da generarle sequenzialmente.
potrebbe essere piú "permormante" su piú tentativi ma hai un minimo di tentativi assicurato cosí. O sbaglio ?
Almeno uno per fase.
E diciamo che elimini il fattore "culo" :D
Ah, ovviamente l'algoritmo si deve resettare se viene raggiunta la soluzione...
Diciamo che tiene anche conto della possibilità che ci siano più colori uguali nella stessa soluzione e comunque permette di raggiungere abbastanza velocemente il numero di elementi che compongo la soluzione...
Facendo un esempio con M=6 e N=4, se c'è una pedina per ognuno degli ultimi 4 colori:
1° tentativo (passo 1) trova zero colori
2° tentativo (passo 1) ne trova 2
3° tentativo (passo 2) ne trova 1, aggiungo il colore 3 a S
4° tentativo (passo 3) ne trova 1, aggiungo il colore 4 a S
5° tentativo (passo 1) ne trova 2
6° tentativo (passo 2) ne trova 1, aggiungo il colore 5 a S
7° tentativo (passo 3) ne trova 1, aggiungo il colore 6 a S
Quindi al massimo in 7 tentativi si trova la lista dei colori...
A questo punto bisogna fare tutte le combinazioni di 3-4-5-6...
Per carità, non sono poche, ma speriamo nella fortuna ;)
Mi sembra comunque abbastanza semplice da implementare... Per questo ho pensato ad un algoritmo di questo tipo...
Visir932
06-07-2006, 14:09
Ragazzi prima di tutto un grazie di cuore per l'aiuto che mi state dando.
Sto cercando di capire un pò quello che mi avete scritto e immaginare come possa chiaramente scriverlo in Java con le mie scarse conoscenze.Dovrei starci un pò sopra per vedere se effettivamente ce la faccio a tradurre tutto nel compilatore.
Comunque per quanto riguarda i colori,e rispondo a Fidel,possono essere anche tutti uguali in una sequenza quindi si possono ripetere senza problemi.
Quello che non sto riuscendo dall'inizio a spiegarmi è come posso interagire con il GameManager.Ad esempio quando Fidel dice:
"2) Richiedi al GameManager di valutare la soluzione corrente. Se è corretta, hai vinto () ed esci, altrimenti salvi in due variabili intere (le chiamiamo strikes e balls) la risposta del game manager. "....non capisco come io possa ordinare questo passaggio!
Inoltre devo capire come combinare i passaggi da voi descritti con i metodi che mi hanno detto di implementare.
So che vi starò sembrando uno stupido però sino ad ora ho solo letto un libro di 5 capitoli che spiega le prime nozioni di java e per quanto riguarda la pratica sono a 0,ho solo implementato qualche singolo metodo che svolge funzioni matematiche semplicissime!
Comunque spero di farcela perchè ne sarei davvero orgoglioso,inoltre il progetto mi appassiona molto ..se poi penso che l'alternativa sarebbe preparare qualche esame di Matematica...
Spero di farcela con il vostro aiuto! :mano:
Questa fase è completata ed ora in S ho N elementi che compongono la souzione, ma sono nelle posizioni scorrette, quindi ora bisogna trovare il giusto ordinamento:
Genero una soluzione per ogni combinazione degli elementi di S. Ovviamente bisogna enumerare le combinazioni in modo da generarle sequenzialmente.
Direi che nella parte che ho messo in grassetto si riscontra un problema non di poco conto. Una volta che hai i colori corretti (e trovare i colori corretti ha già un suo costo in numero di operazioni/iterazioni), ti trovi in una situazione in cui, data una soluzione con n elementi, hai n! possibili combinazioni da provare. al crescere di n il numero di combinazioni possibili diventa computazionalmente inaccetabile. Infatti, già con n=8 hai 40.320 combinazioni possibili. Con n=10 si sale a 3.628.800 combinazioni, e così via. Una complessita ad occhio di o(n^2). Questa complessità va inoltre sommata alla complessità del trovare i valori corretti...
Semplicemente tu dovrai gestirti l'algoritmo man mano che ti arrivano le chiamate di guess e tellAnswer...
In pratica nel costruttore generi il primo Sequence....quindi ogni passo dell'algoritmo sarà effettuato in tellAnswer...che di fatto genera la prossima Sequence che dovrai ritornare da guess... In tellAnswer ti passano la risposta al tentativo precedente...
Quindi non devi fare altro che salvarti lo stato dell'algoritmo nei dati privati per poter compiere il tentativo successivo in tellAnswer...
Ad esempio quando Fidel dice:
"2) Richiedi al GameManager di valutare la soluzione corrente. Se è corretta, hai vinto () ed esci, altrimenti salvi in due variabili intere (le chiamiamo strikes e balls) la risposta del game manager. "....non capisco come io possa ordinare questo passaggio!
Inoltre devo capire come combinare i passaggi da voi descritti con i metodi che mi hanno detto di implementare.
Nel metodo guess() ci piazzi la parte dell'algoritmo che genera una soluzione (fondalmente il passo 3, i primi due passi vengono eseguiti solo la prima volta per generare la prima soluzione).
La richiesta della correttezza della soluzione la fai al GameManager tramite la classe guessResult(Sequence guess) che non a caso ritorna un Answer.
EDIT: puoi "fondere" il passo 1, 2 e 3 in questo modo:
se non esiste una soluzione corrente (la variabile è vuota), la generi la prima volta, altrimenti ne generi una a partire dalla soluzione corrente. subito dopo chiedi se la soluzione è corretta.
Più in particolare, facendo la richiesta sul valore di nuova_soluzione, se soluzione_corrente è vuota generi la soluzione iniziale (passo 1) memorizzando il valore in nuova_soluzione, altrimenti generi nuova_soluzione a partire da soluzione_corrente. Ovviamente il Passo 1 è un caso particolare (va fatto una sola volta), l'importante è che dopo la prima iterazione tu abbia una soluzione in soluzione_corrente.
Semplicemente tu dovrai gestirti l'algoritmo man mano che ti arrivano le chiamate di guess e tellAnswer...
In pratica nel costruttore generi il primo Sequence....quindi ogni passo dell'algoritmo sarà effettuato in tellAnswer...che di fatto genera la prossima Sequence che dovrai ritornare da guess... In tellAnswer ti passano la risposta al tentativo precedente...
Quindi non devi fare altro che salvarti lo stato dell'algoritmo nei dati privati per poter compiere il tentativo successivo in tellAnswer...
Mmhh mi pare che tellAnswer sia solo un metodo per stampare a video il risultato, non a caso è una metodo void.
Secondo me deve, come dici tu, mettere nel costruttore i primi due passi dell'algoritmo da me postato prima, poi nel metodo guess() il passo 3, il quale metodo guess() richiame il metodo guessResult(...) per conoscere se il tentaivo è andato a buon fine.
Dimenticavo:
per la storia di come puoi chiedere al GameManager la bontà della soluzione, sicuramente la classe GameManeger espone un metodo che, data una sequenza, ti ritorna un tipo Answer. Una volta avuto un oggetto Answer di ritorno, puoi interrogarlo tramite i metodi getStrikes() e getBalls() (presenti infatti nella classe Answer).
Direi che nella parte che ho messo in grassetto si riscontra un problema non di poco conto. Una volta che hai i colori corretti (e trovare i colori corretti ha già un suo costo in numero di operazioni/iterazioni), ti trovi in una situazione in cui, data una soluzione con n elementi, hai n! possibili combinazioni da provare. al crescere di n il numero di combinazioni possibili diventa computazionalmente inaccetabile. Infatti, già con n=8 hai 40.320 combinazioni possibili. Con n=10 si sale a 3.628.800 combinazioni, e così via. Una complessita ad occhio di o(n^2). Questa complessità va inoltre sommata alla complessità del trovare i valori corretti...
Lo so che la complessità è molto alta...ma mi sembra l'algoritmo più semplice da scrivere...
La complessità per trovare il numero dei colori corretti (dovrebbe essere O(n)) è trascurabile rispetto al generare le combinazioni...
Tra l'altro non credo che la complessità della tua soluzione sia minore...almeno ad occhio... Di fatto potresti comunque dover provare tutte le possibili combinazioni prima di raggiungere la soluzione...quindi (M + N - 1)! / (M - 1)!...che sono ben più alte delle N! permutazioni ;)
Dimenticavo:
per la storia di come puoi chiedere al GameManager la bontà della soluzione, sicuramente la classe GameManeger espone un metodo che, data una sequenza, ti ritorna un tipo Answer. Una volta avuto un oggetto Answer di ritorno, puoi interrogarlo tramite i metodi getStrikes() e getBalls() (presenti infatti nella classe Answer).
No...è proprio tellAnswer che passa la risposta alla classe Player... Lui non ha un riferimento al GameManager...
void tell(int sequenceLength, int numberColors); <- comunica N e M al giocatore
int specifyColor(int i); <- chiede al giocatore un elemento della sua sequenza segreta
Sequence guess(); <- ritorna il tentativo corrente
Answer guessResult(Sequence guess); <- ritorna la risposta ad un tentativo dell'avversario sulla nostra sequenza segreta
void tellAnswer(Answer answer); <- comunica la risposta dell'altro giocatore al tentativo corrente
Il primo metodo viene invocato all’inizio della partita per comunicare al giocatore
la lunghezza delle combinazioni e il numero di colori, specificati dai due
argomenti. Il secondo metodo restituisce il colore che si trova, all’interno della
combinazione segreta del giocatore, nella posizione ricevuta come argomento. Il
terzo metodo effettua un tentativo e pertanto ritorna un oggetto di tipo Sequence,
che specifica la combinazione tentata dal giocatore. Il quarto metodo serve a specificare
il risultato del tentativo fatto dall’avversario: pertanto il valore dell’argomento
sar`a tale tentativo e il valore di ritorno sar`a un oggetto di tipo Answer
che specifica il numero di strike e il numero di ball realizzato con esso. Il quinto
e ultimo metodo comunica al giocatore, attraverso la risposta ricevuta come
argomento, il risultato del tentativo appena eseguito.
No...è proprio tellAnswer che passa la risposta alla classe Player... Lui non ha un riferimento al GameManager...
Ah ok :) Per fare una valutazione più precisa, dovrei avere almeno l'interfaccia della classe GameManager in effetti.
EDIT: leggendo il tuo post #38 ora il meccanismo della classe mi è più chiaro.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.