Newsgroup: it.scienza.informatica
Titolo: Strategie al calcolatore

Salve a tutti, vorrei programmare alcuni giochi al computer:
Tris, Cinque in fila, Battaglia navale ... etc.
Ho un problema che pero' deriva dal fatto che non ho idea di quale
strategia programmare per il computer. Ammetto di essere un pessimo
giocatore, tuttavia mi viene difficile pensare ad una strategia che
il computer possa seguire per battere l'avversario e riuscire a mettere
ad esempio cinque crocette in fila orrizontalmente, verticalmente o in 
diagonale, oppure trovare un metodo di indagine non casuale che consenta
al computer di indagare in modo ottimale la scacchiera della battaglia 
navale.
Sapete se esistono libri a riguardo ?
Un grazie anticipato
Maurizio

 Maurizio
 

 navale.
Io per Tris ad esempio avevo pensato in origine a questa banale strategia:
- ti tieni un vettore di mosse
- valuti ogni mossa, assegnandogli un punteggio (es: 10 per una che ti fa
vincere, 0 per una che fa vincere l'avversario)
- scelgo la mossa col valore più alto
- per renderlo più divertente, scelgo un numero casualmente, assegnando ad
ogni valore una probabilità pari al suo punteggio diviso la somma dei
punteggi di tutte le mosse
Dopodichè mi hanno consigliato un metodo migliore per gestire una
profondità, come negli scacchi (io faccio questa, lui fa quella ed io
vinco): usare una albero di mosse, e seguire il percorso che porta alla
foglia col punteggio più alto. A te l'implementazione ;-)
-- 
Andrea Bergia - studente              Linux Registred User #281550
"The one thing we're all waiting for, is peace on Earth and an end to war,
it's a miracle we need, the miracle, the miracle, 
Peace on earth and end to war today,
That time will come one day you'll see when we can all be friends"

@ Salve a tutti, vorrei programmare alcuni giochi al computer:
@ <snip> non ho idea di quale
@ strategia programmare <snip>
@ esistono libri a riguardo ?<snip>
In generale, dovresti cercare un libro ad hoc per ogni gioco che vuoi
implementare.
Matematicamente si tratta di risolvere, nella maggior parte dei casi,
problemi np-completi, quindi la 'strategia' consiste nel 'tagliare',
ad ogni passo, le mosse considerate 'sbagliate'.
Nel caso il numero totale di mosse possibili sia sufficientemente
basso da poterlo affrontare col calcolatore, allora puoi usare il
metodo di forza bruta, scegliendo ogni volta la mossa che ha come
conseguenza la maggiore percentuale di vittorie su tutte le mosse
successive possibili, o il minor numero di vittorie avversarie. Ma
anche questo e' discutibile, l'avversario potrebbe incanalarti 1n un
percorso obbligato, vedi il gioco del tris.
-- 
Real email address hasn't .nntp

 ha scritto nel messaggio
news:5203294c.03011...@posting.google.com...

Bisogna usare gli algoritmi "minimax" che risolvono i giochi a somma zero
(dove il vantaggio di uno corrisponde allo svantaggio di un altro).
L'argomento è abbastanza ampio, in due parole, ecco come funziona...
Sono algoritmi che usano un sistema chiamato Backtracking, ovvero ad ogni
mossa il programma chiama una funzione es "mossa".
la funzione mossa attribuisce un punteggio ad una posizione finale (es, tris
o scacco matto) e lo ritorna.
Se non si è giunti in una posizione finale mossa ricerca tutte le mosse
possibili
per ogni mossa possibile, la gioca (in memoria, cioè senza aggiornare la
memoria video...) quindi chiama mossa di nuovo (la funzione mossa deve
quindi riconoscere e rispondere sia che il turno di gioco sia a uno o
all'altro giocatore).
alla fine dell'iterazione se è il turno del primo giocatore viene scelta la
mossa con il punteggio più alto se è l'altro turno invece sceglie quella con
punteggio pià basso tra quelle possibili.
Importante per questi algoritmi è quindi la funzione del punteggio, ad
esempio nel tris potrebbe essere
f(t1,t2,t3)=t1+100*t2+10000*t3
t1 è il numero di X o di O piazzate, t2 è il numero di due X o di due O
allineate, t3 si verifica in presenza di un tris, nota che quando viene
raggiunto il punteggio schizza in alto e quindi inequivocabilmente diventa
la mossa da giocare X se ha segno più, infatti t(x)=Xx-Ox.
Infatti il segno X da il risultato +, la O da il segno -, ecco perché mossa
in un caso sceglie la mossa che massimizza il risultato (quando gioca per X)
oppure quella che minimizza (se gioca per O).
La funzione mossa serve solo a tirare le fila di tutto questo calcolo.
Dopo si possono fare tante ottimizzazioni (chiamate "potature" dell'albero
delle varianti), comunque la base è quella...
Lo so che in due righe non è molto chiaro, però se cerchi su internet trovi
qualcosa...
ciao.

 ciao.
Grazie a tutti per le risposte, ho un testo di logica sulla teoria dei
giochi "B. D'Amore - Teoria dei Giochi" e il N.Wirth, dove si parla di
Backtracking (che pure studiai per l'esame di TAMC molti anni fa). 
Mi mettero' a studiare.
Ciao
maurizio.

 Backtracking (che pure studiai per l'esame di TAMC molti anni fa).
Ma sei sicuro a TAMC???
Io l'ho studiato a Sistemi I
--
TheProf

...

Si feci solo due esami di informatica (a parte analisi numerica) a
matematica:
1) - Cibernetica e Teoria dell'Informazione
2) - Teoria e Applicazione delle Macchine Calcolatrici (TAMC)
Poiche' gli esami a disposizione x i matematici (diversi anni fa)
potevano
essere al piu' essere 3, nell'esame di TAMC dovevi praticamente fare 
tutto, dalle basi dati ai sistemi operativi alla teoria degli automi
.... alla teoria dei linguaggi e compilatori, .... strutture
informative dinamiche etc.
Era pero' l'esame piu' importante da dare per chi intendeva seguire la
strada
applicativa (a parte analisi numerica).
Ciao
maurizio.

 ha scritto nel messaggio
news:6qDX9.35202$YG2.9...@twister1.libero.it...

[CUT]
Ti avverto che non è così semplice ,ci sono diversi studi.
Ma vuoi trovare un vero studio sulla toria dei giochi e su come far
comportare l'algoritmi in risposta a percezioni ,nel tuo caso nei giochi in
risposta adavversari.
Ti consiglio un libro di "inteliggenza artificiale" in particolare -
Inteliggenza Artificiale autore Russel .
E' presente anche l'algoritmo di minimax ,CAP 5(giochi),che ha accennato
giustamente Maurizio , ma stai attento è sempre un algoritmo di ricerca in
profondità potresti avere T(n) esponenziale potresti avere tempi di risposta
di un criceto :-) se non fai le opportune potature.
Cmq in questo libro è tutto spiegato, anche di +
ciao
Sotomajor

 wrote in message
5203294c.03011...@posting.google.com...

Se intendi effettuare la programmazione in assembler esiste un buon libro
chiamato "Quasi Intelligenza Artificiale". Ci sono alcuni esempi di
algoritmo per il gioco del tris ed altri giochi di logica.
Federico Santandrea

Ragazzi,
è veramente triste vedervi discuture con tanto accanimento su queste
sciocchezzuole trite e ritrite.
Mi aspettavo di meglio da questo newsgroup...
Vincenzo
http://www.vincenzoiannopollo.too.it

 Mi aspettavo di meglio da questo newsgroup...
Non mi sembra che tu sia nelle condizioni di criticare gli altri:
facendo una ricerca con google (gruppi) per vincenzoiannopollo
http://groups.google.it/groups?hl=it&lr=&ie=UTF-8&oe=UTF-8&scoring=d&q=vincenzoiannopollo
si vede che praticamente il tuo unico contributo alle discussioni
e' stato inviare messaggi con contenuti fasulli per pubblicizzare
il tuo sito (che fra parentesi qualunque dodicenne e' capace di
surclassare sia per forma che per contenuti...).
Se si considera che sei pure laureato in fisica....
Addio,
g.