Newsgroup: it.scienza.informatica
Titolo: Algoritmi per implementare giochi

Salve a Tutti sarei grato a chi volesse chiarirmi cosa c'e' dietro un
gioco contro un computer , che tipo di algoritmi decisionali vanno
implementati per fare una partita a scacchi o un "semplice" tetris
chiaramente data l'enormita' della  domanda (credo) non mi aspetto una
risposta sul N.G. mi piacerebbe sapere come si chiama il settore
dell'informatica che tratta queste problematiche e quali sono i testi
che partono da un livello elementare che trattino l'argomento. Credo
che i pezzi sulla scacchiera siano trattate come come condizionial
contornopermassimizzare o minimizzare una funzione ma quale sia questa
funzione e come si faccia a determinarla non ho la piu' pallida idea,
centra forse la ricerca operativa ?
Grazie per l'attenzione!
Saluti Felix 

La parte dell'informatica che riguarda aspetti ludici tipo "che algoritmo
per vincere a risiko o a scacchi" è l'intelligenza artificiale.
Gli algoritmi base che vengono usati per decidere tra un insieme di
possibili mosse sono gli alberi minimax (se cerchi su google sicuramente
trovi molto a riguardo). In pratica il tutto consiste nel riuscire a dare un
euristica che restituisce il punteggio di ogni mossa (ad esempio, mangiare
un pezzo sono tot punti, prendere possesso di una certa casella tot, e così
via). A questo punto, partendo dalla radice di un albero, ogni figlio di
questo nodo è una delle possibili mosse. Lo scopo del primo livello è quello
di massimizzare il punteggio (quindi in teoria scegli la mossa con più
punti). Il problema è che al livello dopo, cioé quando tocca all'avversario,
verrà applicata una funzione che minimizza il punteggio (cioé l'avversario
rema contro). Quindi non è detto che scegliere la mossa che al primo livello
ha punteggio max sia vantaggioso, poiché potrebbe essere che al livello
successivo l'avversario scelga una mossa che trova un punteggio molto basso
(insomma, qualcosa tipo ti mangio la regina ma poi tu mi fai scacco matto).
Insomma, per farla breve (tipo slide):
Sono alternati livelli di min e livelli di max, dove max sarebbe quando
gioca il computer (che cerca di vincere la partita), min l'avversario
Nel livello di max si sceglie il max dei valori restituiti dal livello di
min
Nel livello di min si sceglie il min dei valori restituiti dal livello di
max
C'è il problema dell'orizzonte degli eventi, ovvero puoi vedere cosa succede
fino ad una certa profondità
Euristiche per tagliare rami di computazione
Problema nel trovare una buona euristica per il calcolo dei punteggi
Non sono esperto di queste cose quindi spero di non aver detto idiozie...

 euristica che restituisce il punteggio di ogni mossa (...)
In realta' l'euristica deve dare una valutazione della bonta' della
*posizione*, e non della mossa: quest'ultima e' una transizione
(accettabile secondo le regole) tra due posizioni. 
In teoria, avendo un'euristica perfetta, basterebbe scendere di un
livello: la mossa che porta alla euristica piu' elevata sarebbe la
migliore. Di fatto pero' una tale sarebbe possibile solo avendo risolto
totalmente il problema (spesso NP-hard), cosi' che non solo l'euristica
non sara' mai perfetta ma in neppure monotona: e' per questo che occorre
scendere in profondita' valutando le risposte dell'altro.
In pratica si procede unendo conoscenza generale a priori (la nostra
euristica) e analisi specifica (algoritmi minmax con tagli alfa-beta,
ricerca della quiescienza...). E' sempre poi necessario un compromesso tra
le due componenti, perche' a parita' di risorse non e' detto che una
euristica piu' precisa ma computazionalmente piu' complessa porti a
risultati migliori: se il gioco ha diramazione limitata puo' esser meglio
scendere a profondita' maggiore con euristiche banali. In genere pero'
l'esplosione combinatoria e' esponenziale mentre l'euristica e'
polinomiale, dunque si punta piu' su questa.
Per fare un esempio, nel confronto uomo-macchina in genere il primo ha
euristiche piu' potenti (spesso "intuitive", ovvero difficilmente
formalizzabili) mentre la seconda punta piu' sull'analisi combinatoria
(chiamala, se vuoi, "forza bruta").
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it