Newsgroup: it.istruzione.scuola
Titolo: OT : Complessita', scacchi e tris

Allora… siccome non ho la scienza infusa e siccome preferisco evitare
di andare a "orecchio" come qualcuno sembra fare ho dato una occhiata
alla documentazione riguardante tre problemi :
1-	valutazione di complessita'
2-	strategie vincenti nel gioco del tris
3-	valutazione di complessita' nel gioco degli scacchi
Allora circa il punto 3- c'e' una documentazione piuttosto consistente
all'indirizzo 
http://www.xs4all.nl/~verhelst/chess/publications.html
chi fosse interessato alla questione puo' trovare sul sito un buon
punto di partenza.
Per quanto riguarda il punto 1- (se mai ce ne fosse bisogno) riporto
uno stralcio tratto da "CENNI DI COMPLESSITA' COMPUTAZIONALE" di Dalla
Libera, il testo completo e' riportato su
http://helios.unive.it/~franz/complexity.html
 
Cito testualmente dall'estratto :
"Una misura della bontà di un algoritmo é data dalla sua velocità di
esecuzione: questa dipende però moltissimo dal calcolatore utilizzato
e dalla tecnologia hardware; si preferisce quindi considerare una
misura astratta: il numero di operazioni elementari richieste. Questo
numero varia in generale a seconda delle dimensioni della particolare
istanza del problema: vedere se esiste un particolare elemento
all'interno di un elenco di 100 elementi richiede presumibilmente meno
operazioni che non in un elenco di 10000 elementi. Per dimensione del
problema si intende quindi la lunghezza dell'input su cui l'algoritmo
effettua le sue computazioni: ad esempio il numero di elementi o il
numero di bytes, ecc. 
Il tempo di esecuzione T di un programma dipende, quindi, dai seguenti
fattori: 
1.	i dati in input;
2.	la qualità del codice oggetto generato dal compilatore;
3.	la velocità della particolare macchina usata per eseguire il
programma ;
4.	la complessità "computazionale" dell'algoritmo su cui si basa
il programma.
 Il primo fattore ci dice che T deve essere definito come una funzione
dell'input; spesso T dipende non da quel particolare input ma dalla
sua "dimensione". Si usa perciò la notazione T(n) per indicare il
tempo di esecuzione di un programma su input di dimensione n. 
Si può pensare a T(n) come al numero di istruzioni eseguite su un
ideale computer. In molti casi però T è realmente funzione di un
particolare input e non solo della dimensione. In questi casi (e
saranno i più frequenti) definiamo T(n) come il caso peggiore tra
tutti i T(n), cioè, il massimo, su tutti gli input di dimensione n,
tra i tempi di esecuzione su quell'input. Si potrà considererare,
comunque, anche il caso medio. 
Esistono due metodi per "misurare" il tempo di esecuzione di un
programma. 
Il primo è quello di far girare effettivamente il programma su di una
data macchina e prendere nota della sua efficienza (o misurando il
tempo impiegato o contando il numero di operazioni eseguite). Per
poter utilizzare risultati di questo tipo è necessario eseguire il
test su diversi "campioni". Ma anche così è difficile farsi un'idea
generale sulle prestazioni del programma. I punti 2 e 3 ci dicono
infatti che T dipende anche dal computer (Hardware e Software)
utilizzato per compilare ed eseguire. Da ciò deriva il fatto che non
si può esprimere T(n) in unità di tempo standard come secondi. 
Il secondo metodo, invece, cerca di determinare la relazione
matematica che esiste tra il tempo richiesto e la dimensione n del
problema, conteggiando le unità di tempo di esecuzione attribuendo: 
-	alle istruzioni di assegnazione una unità di tempo 
- alle istruzioni iterative un tempo uguale alla somma delle unità per
ogni singola iterazione 
- alle istruzioni di selezione il massimo numero di unità delle sue
alternative."
Dal testo riportato si evince senza ombra di dubbio che la valutazione
di complessita' di un problema (o meglio di una classe di problemi) e
quindi dello specifico algoritmo studiato per risolverlo non e' in
alcun modo legato al tempo effettivo impiegato in esecuzione (anche se
ci da una stima dello stesso), e tanto meno dipende da una specifica
istanza del problema, non a caso si usa esprimere al valutazione di
complessita' in funzione di n e non per uno specifico n (vedere il
resto del materiale all'indirizzo citato per i dettagli.
Per quanto riguarda il punto 2- il gioco del Tris Susanna ha sostenuto
sul Ng che :
"Insisto; se stiamo parlando dello stesso gioco del tris, ti posso
garantire che con una strategia relativamente semplice si pareggia
sempre."
Allora, su 
http://www.conmet.it/sharkey/TRISWEB.HTM
 troviamo una
interessante dissertazione sul gioco del Tris (per la cronaca..si' ho
usato Google come motore di ricerca e anch'io sono convinto che sia il
migliore), in poche parole cio' che si dice sul sito in questione e'
che il gioco del Tris rientra fra i giochi di Tipo Finito e viene
regolato percio' dal Teorema sulle Strategie Vincenti per giochi di
Tipo Finito. Cio' significa che esiste una strategia vincente, per uno
dei due giocatori. Quindi effettivamente nel gioco del Tris e'
possibile sempre o vincere (se l'avversario non segue un criterio di
scelta ottimo delle mosse) oppure pareggiare sempre (se invece anche
l'avversario gioca seguendo gli stessi criteri) a prescindere dalla
mossa fatta. Quindi effettivamente Susanna aveva ragione. Tra l'altro
anche gli scacchi soddisfano le condizioni di gioco di Tipo Finito e
soddisfano il Teorema sulle Strategie Vincenti, quindi in teoria aveva
ragione chi sosteneva (non ricordo chi l'ha detto) che di suo gli
scacchi presentano sempre una strategia vincente… il problema
naturalmente e' individuarla infatti mentre nel gioco del Tris i nodi
dell'albero decisionale da visitare sono solo 9! (circa 360.000) nel
caso degli scacchi dopo le prime dieci mosse abbiamo la bellezza di
165.918.829.100.544.000.000.000.000 possibili mosse… e percio' la
ricerca esaustiva diventa per un essere umano come per un calcolatore
reale impossibile…
Augusto Pucci ( 
http://www.prospektiva.it/webmaster/
 )
Webmaster di Prospektiva On-line
http://www.prospektiva.it
Webmaster di 
CO.DI.CI
. Siena
http://codici.supereva.it

 3- valutazione di complessita' nel gioco degli scacchi
<omissis>
Bene.
Dato che il 'post' e` essoterico, merita.
La rettifica ti fa onore.
Chiusa qui.
susanna

 soddisfano il Teorema sulle Strategie Vincenti,
Interessante.
In proposito sono decisamente ignorante per cui mi scuso per la domanda
forse banale, ma sei certo che gli scacchi soddisfino le condizioni di gioco
di Tipo Finito?
In effetti ignoro quali siano queste condizioni ma mi sembra plausibile che
sia contemplata la caratteristica di avere un numero finito di mosse per
terminare il gioco.
Nel caso degli scacchi esiste qualche teorema che preveda appunto questa
caratteristica?
Saluti,
        Corrado

 caratteristica?
Non so il teorema ma certamente il numero di partite è finito (da
qualche pate ho segnato il numero) a causa della regola delle 50 mosse.
-- 
"I libri di storia devono essere plurali" (TG3, singolare intervista
durante un manifestazione studentesca)
http://digilander.iol.it/mmanca