ALGORITMO PER MASTERMIND - Pagina 2

-fidel- · 06-07-2006, 09:32

Quote:

Originariamente inviato da Visir932

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

-fidel- · 06-07-2006, 10:27

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 (

) 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

Quote:

Originariamente inviato da -fidel-

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 (

) 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ú

-fidel- · 06-07-2006, 11:01

Quote:

Originariamente inviato da trallallero

Potrebbe anche tener traccia delle soluzioni scartate
per evitare inutili giri

anche questo é un gioco da ragazzi, 4 righe di codice

o poco piú

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.

-fidel- · 06-07-2006, 11:38

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

Quote:

Originariamente inviato da -fidel-

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

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

cionci · 06-07-2006, 12:55

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

Quote:

Originariamente inviato da cionci

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"

cionci · 06-07-2006, 13:22

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!

-fidel- · 06-07-2006, 14:15

Quote:

Originariamente inviato da cionci

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...

cionci · 06-07-2006, 14:19

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...

-fidel- · 06-07-2006, 14:22

Quote:

Originariamente inviato da Visir932

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.

-fidel- · 06-07-2006, 14:25

Quote:

Originariamente inviato da cionci

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.

-fidel- · 06-07-2006, 14:29

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).

cionci · 06-07-2006, 14:37

Quote:

Originariamente inviato da -fidel-

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

cionci · 06-07-2006, 14:38

Quote:

Originariamente inviato da -fidel-

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...

cionci · 06-07-2006, 14:43

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.

-fidel- · 06-07-2006, 14:44

Quote:

Originariamente inviato da cionci

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.

06-07-2006, 10:27	#22
-fidel- Senior Member Iscritto dal: Jan 2006 Messaggi: 2722	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 () 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. __________________ - Spesso gli errori sono solo i passi intermedi che portano al fallimento totale. - A volte penso che la prova piu' sicura che esiste da qualche parte una forma di vita intelligente e' il fatto che non ha mai tentato di mettersi in contatto con noi. -- Bill Watterson Ultima modifica di -fidel- : 06-07-2006 alle 10:36.

06-07-2006, 11:38	#25
-fidel- Senior Member Iscritto dal: Jan 2006 Messaggi: 2722	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...) __________________ - Spesso gli errori sono solo i passi intermedi che portano al fallimento totale. - A volte penso che la prova piu' sicura che esiste da qualche parte una forma di vita intelligente e' il fatto che non ha mai tentato di mettersi in contatto con noi. -- Bill Watterson

06-07-2006, 12:55	#27
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	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. Ultima modifica di cionci : 06-07-2006 alle 12:59.

06-07-2006, 14:29	#35
-fidel- Senior Member Iscritto dal: Jan 2006 Messaggi: 2722	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). __________________ - Spesso gli errori sono solo i passi intermedi che portano al fallimento totale. - A volte penso che la prova piu' sicura che esiste da qualche parte una forma di vita intelligente e' il fatto che non ha mai tentato di mettersi in contatto con noi. -- Bill Watterson

06-07-2006, 13:22	#29
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	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...

06-07-2006, 14:09	#30
Visir932 Junior Member Iscritto dal: Mar 2006 Messaggi: 27	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!

06-07-2006, 14:19	#32
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	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...

06-07-2006, 14:43	#38
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	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.

Strumenti
Mostra una versione stampabile Invia questa pagina per email