Programmazione e giochi (e scacchi)

Cinema, Peperoncini, Navi Spaziali, Barbecue, Fisica Quantistica… TUTTO!
Post Reply
User avatar
Bubillus
oO
oO
Posts: 684
Joined: 13/08/2011 17:41
Blizzard BattleTag: Bubillus#2227

Programmazione e giochi (e scacchi)

Post by Bubillus » 02/03/2012 10:57

Premetto la mia profonda ignoranza in entambi i campi, ma mi è venuta in mente una riflessione mentre ieri mi dilettavo con un giochino del biliardo dove si può sfidare il computer. Ho pensato che una simulazione del biliardo deve contenere un po' di fisica per poter calcolare le traettorie delle varie palle, gli attriti, gli scontri tra di loro e con le sponde del tavolo etc etc e che, probabilmente, il miglior gioco del biliardo su computer è quello che meglio di tutti fa tale lavoro arrivando ad una simulazione quanto più perfetta della fisica reale. Però, così come il programma è in grado di calcolare la traettoria di una palla colpita dalla "stecca virtuale" dopo che ha ricevuto i dati in input da parte del giocatore umano che ha il mouse in mano, è altrettanto in grado di calcolare queste traettorie prima e quindi, in pratica, una sfida uomo contro computer dovrebbe essere sempre vinta dal computer a meno di non dare al giocatore umano la prima mossa e pensare ad una serie di colpi che lo porti alla vittoria finale senza mai passare la stecca al computer. Ma allora cosa rende divertente 'sto giochino? Il fatto che ogni tanto il PC sbaglia. Ma deve essere un errore programmato, previsto negli algoritmi. Per fare un esempio stupido: se dico al mio pc di calcolare 2+2 utilizzando la formula 2+2 + un valore compreso tra +0,1 e -0,1 inserisco un margine di errore che influisce sul calcolo finale e quindi metto nelle condizioni il pc di fornirmi una risposta sbagliata. Credo che il biliardo su pc debba funzionare più o meno allo stesso modo.
Però, e qui sta il bello, perché per gli scacchi invece la cosa non è così? Perché Kasparov nel 1996 riuscì a battere Deep Blue? Basterebbe poter utilizzare un computer estremamente veloce e potente per vincere ogni partita contro un giocatore umano (e quindi evidentemente Deep Blue all'epoca non lo era a sufficienza) oppure ci sarà sempre la possibilità per lo scacchista in carne ed ossa di vincere grazie, che ne so, alla strategia, alla fantasia, alla genialità? Cioè, in pratica, visto che non sono previsti elementi aleatori come dadi che rotolano, palline che girano, carte da pescare... è possibile essere certi di vincere una partita a scacchi matematicamente data una sufficiente potenza di calcolo?
"Secondo le leggi della fisica e dell'aerodinamica, la struttura alare del calabrone in relazione al suo peso non è adatta al volo. Ma lui non conosce queste leggi e vola"

User avatar
Mano[FA]
oO Team
oO Team
Posts: 2163
Joined: 24/10/2004 15:47
Location: UK

Re: Programmazione e giochi (e scacchi)

Post by Mano[FA] » 02/03/2012 11:26

per ora rispondo con questa, poi elaborero'

User avatar
CuginoIt
oO Team
oO Team
Posts: 2207
Joined: 08/12/2004 12:50
Blizzard BattleTag: CuginoIt#2830
Location: Copenhagen

Re: Programmazione e giochi (e scacchi)

Post by CuginoIt » 02/03/2012 13:46

In effetti mi sembra che dal 1996 ad oggi si siano fatti passi avanti tali nella velocita' dei computer (e quindi nelle possibili configuazioni future della scacchiera che il programma puo' valutare) che ormai si riesce, piu' o meno, a programmare qualcosa che batte anche il campione del mondo di scacchi (e basta un vecchio gioco ChessMaster per battere chiunque abbia un punteggio Halo "umano" e non da Maestro...). Io credo che, per gli scacchi, il limite nella programmazione possa essere assegnare un giusto "valore" alle configurazioni future che si prevedono. Cioe', date due situazioni diverse sulla scacchiera, come faccio a dire quale e' favorita e quale no?

EDIT: dal grafico di Mano risulta che dal 2005 c'e' un PC imbattuto negli scacchi, un mio amico pero' mi diceva che col GO e la scacchiera grande (19x19) le combinazioni sono talmente tante che ancora si e' ben lontani da battere i maestri. Da fisico che studia computazione quantistica posso aggiungere che questo sta nella capacita' dell'uomo ad avere una "visione d'insieme" e a valutare gli effetti che una mossa ha in posizioni distanti della scacchiera, mentre i computer, su una schacchiera cosi' grande, sono obbligati a procedere "localmente", valutando cioe' gli effetti solo vicino a dove e' stata compiuta la mossa, che nel go non e' sufficiente.

User avatar
Mano[FA]
oO Team
oO Team
Posts: 2163
Joined: 24/10/2004 15:47
Location: UK

Re: Programmazione e giochi (e scacchi)

Post by Mano[FA] » 02/03/2012 14:58

è altrettanto in grado di calcolare queste traettorie prima e quindi, in pratica, una sfida uomo contro computer dovrebbe essere sempre vinta dal computer
Quest'affermazione e' fuorviante. E' vero che il computer sa gia', a priori, il risultato del suo colpo, ma non ha la piu' pallida idea di come fare il colpo. Deve decidere direzione, forza ed effetto, entrambe variabili con, potenzialmente, infiniti valori e quindi non puo' provarle tutte (anche perche' per ogni combinazione deve simulare tutta la fisica, gli scontri i rimbalzi etc etc per sapere il risultato). Quindi ci deve essre un altro programma che fa "l'intelligenza". Che in qualche modo guarda la situazione e vede se puo' fare punto in qualche modo e poi lasciare la palla bianca in posizione difficile per l'avversario. Lo stesso per gli scacchi. Il computer sa benissimo cosa succede se gli dai la serie di mosse (dove sono i pezzi ad ogni mossa, quali pezzi sono catturati, se il re e' sotto scacco…) ma per far decidere al computer quali mosse fare serve un programma di intelligenza perche', per ora, non e' possibile calcolare tutte le possibili combinazioni che portano ad una vittoria.

Per io gioco del biliardino non so, magari e' un problema risolvibile, ma comunque non banale.

Per gli scacchi, dove storicamente un sacco di risorse sono state spese per raggiungere il traguardo, il computer non sa tutte le possibilita' e, da quel che ne so, la sua non e' solo "logica" ma ha accesso a un enorme database di partite giocate da maestri, tutte quelle dell'avversario e quindi puo' confrontare certe situazioni con alcune gia' avvenute.

User avatar
CuginoIt
oO Team
oO Team
Posts: 2207
Joined: 08/12/2004 12:50
Blizzard BattleTag: CuginoIt#2830
Location: Copenhagen

Re: Programmazione e giochi (e scacchi)

Post by CuginoIt » 02/03/2012 18:28

Riguardo il biliardo occorre distinguere due cose estremamente diverse:

1) Un programma che simula il gioco del biliardo, con regole della meccanica precise ma, allo stesso tempo, dove tutto è "meccanicamente" deterministico: in questo caso il computer, immettendo i dati iniziali, conosce il risultato finale in quanto è tutta una cosa deterministica quanto le regole della meccanica che sto buttando nel programma...

2) La realtà fisica (o un programma che tenga conto di un paio di effetti come una non perfetta "rettangolarità" del biliardo). In questo caso il risultato NON è deterministico semplicemente perchè la realtà non lo è. I biliardi sono, per eccellenza, l'esempio di un sistema caotico: basta che ci siano discostamenti minimi dalla forma rettangolare e differenze infinitesime nelle condizioni iniziali comportano differenze drastiche nei risultati. Quindi non è possibile approssimare il moto della palla nel biliardo non rettangolare se non in termini probabilistici.

Per ricondurmi all'esempio precedente anche per il GO su scacchiera grande gli algoritmi che vengono usati con più efficacia non sono algoritmi deterministici ma simulazioni probabilistiche di come andrà, all'incirca, a finire. (Per esempio quando sentite parlare di algoritmo alla Montecarlo, vuol dire che, in qualche modo, si simula un andamento probabile ma non si sta calcolando veramente tutto...).

User avatar
Bubillus
oO
oO
Posts: 684
Joined: 13/08/2011 17:41
Blizzard BattleTag: Bubillus#2227

Re: Programmazione e giochi (e scacchi)

Post by Bubillus » 02/03/2012 18:51

Mano[FA] wrote:Quest'affermazione e' fuorviante. E' vero che il computer sa gia', a priori, il risultato del suo colpo, ma non ha la piu' pallida idea di come fare il colpo. Deve decidere direzione, forza ed effetto, entrambe variabili con, potenzialmente, infiniti valori e quindi non puo' provarle tutte (anche perche' per ogni combinazione deve simulare tutta la fisica, gli scontri i rimbalzi etc etc per sapere il risultato). Quindi ci deve essre un altro programma che fa "l'intelligenza". Che in qualche modo guarda la situazione e vede se puo' fare punto in qualche modo e poi lasciare la palla bianca in posizione difficile per l'avversario. Lo stesso per gli scacchi. Il computer sa benissimo cosa succede se gli dai la serie di mosse (dove sono i pezzi ad ogni mossa, quali pezzi sono catturati, se il re e' sotto scacco…) ma per far decidere al computer quali mosse fare serve un programma di intelligenza perche', per ora, non e' possibile calcolare tutte le possibili combinazioni che portano ad una vittoria.
Uhm uhm non credo sia necessario che il computer (o meglio l'AI che sta dietro al programma) debba per forza calcolare tutte le possibili traettorie per poi sceglierne una vincente, sarebbe obiettivamente impossibile a meno di non prevedere, ai valori attuali di capacità di calcolo, di metterci ANNI per concludere una partita. No penso piuttosto però che possa funzionare con una variante del principio utilizzato dai navigatori GPS per calcolare il tragitto più breve tra un punto di partenza A ed il punto di arrivo B. Il buon vecchio algoritmo di Dijkstra che si studiava quando si trattava delle reti. Anzi probabilmente oramai ce ne sono anche di più efficenti. Data una distribuzione casuale sul tavolo virtuale possiamo immaginare come punto di partenza A la pallina che dobbiamo colpire, punto di arrivo B una delle buche e gli archi saranno tutte le linee di congiunzione tra gli elementi presenti. Le possibili variazioni saranno comunque limitate agli archi contigui a quelli che uniscono il centro geometrico degli elementi (ammetto che parlare di geometria trattando di bit su uno schermo è imbarazzante e criticabile ma non mi è venuto un termine migliore :D ).
Non a caso nei videogiochi esistono il livello easy, il livello normal ed il livello hard proprio perché secondo me varia la % di errore che "inquina" i risultati dell'algoritmo di calcolo dei percorsi facendo sbagliare di più o di meno l'avversario di silicio.

Trovo ragionevole l'osservazione che il pc che gioca a scacchi invece funzioni tramite l'analisi di un database sterminato che contiene tutte le possibili varianti ammesse nel gioco degli scacchi e si affidi alla mossa che, date le posizioni dei pezzi sulla scacchiera, le mosse già eseguite e chissà quali altre variabili, ha la % di successo più alta. Però se questo basta a non perdere più contro avversari umani dal 2005 a oggi è avvilente perché vuol dire che gli scacchisti non hanno una mente creativa ma una mente analitica e chi è più analitico di loro li batte. Oppure sarebbe lo stesso anche con una mente eccelsamente creativa che basi le sue decisioni sulla interpolazione di elementi non omogenei e su decisioni estemporanee perché il pc ottimizza il gioco sulla base delle mosse possibili indipendentemente dalla "originalità" di quelle dell'avversario. Un po' come giocare a PONG a livello massimo, puoi darci dentro come un dannato ma il PC ributterà sempre la pallina dalla tua parte.
"Secondo le leggi della fisica e dell'aerodinamica, la struttura alare del calabrone in relazione al suo peso non è adatta al volo. Ma lui non conosce queste leggi e vola"

User avatar
Bubillus
oO
oO
Posts: 684
Joined: 13/08/2011 17:41
Blizzard BattleTag: Bubillus#2227

Re: Programmazione e giochi (e scacchi)

Post by Bubillus » 09/03/2012 09:14

E questo come si spiega? Ieri mentre in pausa pranzo mi dilettavo con il giochino del biliardo (essendo a dieta ho un mucchio di tempo libero durante la pausa pranzo :( ) è successa una cosa anomala. La partita era del tipo (non so come si chiama) dove bisogna mandare in buca per ultima la palla 8, se la si manda prima di aver finito la propria serie di biglie (tutte colorate o colorate a metà) si perde. Beh ad un certo punto quando la partita era appena iniziata, il giocatore computer è impazzito, ha mirato la palla 8 e l'ha mandata in buca con un tiro diretto, preciso, senza sponde o rimbalzi. E ovviamente ha perso. Aveva praticamente tutte le altre sue biglie da poter colpire ma ha fatto quella scelta. Come si spiega? Cosa può essere andato storto nei suoi algoritmi?
Mi rendo conto che interpretare un risultato di un algoritmo compreso in un software è un esercizio di approssimazione, ma se parliamo di AI allora possiamo anche prevedere l'analisi comportamentale di un software :mrgreen: .
"Secondo le leggi della fisica e dell'aerodinamica, la struttura alare del calabrone in relazione al suo peso non è adatta al volo. Ma lui non conosce queste leggi e vola"

User avatar
mirino
Veteran
Veteran
Posts: 1314
Joined: 07/09/2005 09:50
Location: Turin

Re: Programmazione e giochi (e scacchi)

Post by mirino » 30/03/2012 13:24

Si è "suicidato" il PC, voleva terminare la partita e andare a pranzo anche lui :lolol:

Bug? O nella serie di risultati potenzialmente dannosi che avevano una pur minima probabilità di accadere, ha pescato quello dall'esito peggiore (per lui) ?

Hai festeggiato la vittoria?

Post Reply

Who is online

Users browsing this forum: No registered users and 28 guests