Programmare una IA

Quote:

---

Originally Posted by Axet

Ma dai? :D
Il punto è che stimare qualcosa che in fin dei conti è imprevedibile è dura, questo dico. Poi magari ci sono degli strumenti statistici che ti consentono di fare una stima più accurata, però come già detto ignoro se esistono/come funzionano :nod:

---

Ma infatti dipende da cosa devi stimare, di solito una qualsiasi azienda che produce software, non crea dal nulla, ma ha una storia dietro, cioe' , non vado a chiedere a un azienda che fa' siti web, di farmi un IA per un robot che deve mungere una mucca.....................
Invece l azienda se gli chiedo un sito web, dalle mie richieste sa quanto ci mettera', dall analisi del problema, ci sono delle tabelle ben definite di quante "linee" di codice servono per fare X cosa, che si usano appunto in ingegneria software per poter dare una stima del costo al cliente, non e' che a uno vado la e gli dico "10.000 euro per tutto" , no devo argomentare perche' gli chiedo 10.000, che magari poi sono 10.240......................

Quote:

---

Originally Posted by marlborojack

Primo e terzo approccio richiedono strumenti matematici delicati, per cui ti consiglierei il 2°, ma è divertente come una settimana di vacanza premio nelle miniere in siberia, imho

---

Se hai fatto ricerca operativa, dovresti usare il sistema dei cammini pesati. Ora non ricordo la teoria e tutto il sistema di calcoli sotto, ma c'e una marea di cose da studiare(o ripassare) per poter poi implementare correttamente (se sei fortunato prendi un codice funzionante ad esempio quello di un navigatore o gestore di trasporti..... alla bill gates insomma).
Una volta che hai il software per la gestione dei cammini, l unico problema (forse il piu difficile per far qualcosa di veramente sensato) è attribuire un peso alle "pedine" e alle mosse. Cosa che puoi fare solo dopo esserti letto 20000 manuali sugli scacchi.

Se vuoi un consiglio, prima fai un bel tris/battaglia navale(si lo so la battaglia navale non è influenzata dalle mosse dell'avversario) e poi puoi passare a forza quattro/dama/scacchi

si chiamano markov decision process ai quali sono collegati gli algoritmi di apprendimento per rinforzo... ma ripeto ne conosco solo la teoria

Si vabbeh informatici contro ingegneri FTW. Io sono un ingegnere e sto studiando per un PhD in computer science, cosa devo cercare di strozzarmi con le mie stesse mani ???? :O :O :O.

mahahah.

Quote:

---

Originally Posted by NoeX

dipende dal tipo di IA, vuoi fare una IA per gioco di scacchi ?
Allora devi considerare un generatore di mosse, i punti dei pezzi, i valori delle caselle e un algoritmo beta-pruning

---

NoeX ti ha risposto.

Inizia da come si modella un gioco Min-Max che e' la base e poi vai avanti da li. La difficolta' sara' sul peso che metterai per valutare le mosse.
Gli scacchi hanno un livello di branching pari, piu' o meno, a 40, quindi ti vengono dei gran alberoni :dumbnod:, per quello noex parla di beta-pruning.

Quote:

---

Originally Posted by black

Se hai fatto ricerca operativa, dovresti usare il sistema dei cammini pesati. Ora non ricordo la teoria e tutto il sistema di calcoli sotto, ma c'e una marea di cose da studiare(o ripassare) per poter poi implementare correttamente (se sei fortunato prendi un codice funzionante ad esempio quello di un navigatore o gestore di trasporti..... alla bill gates insomma).
Una volta che hai il software per la gestione dei cammini, l unico problema (forse il piu difficile per far qualcosa di veramente sensato) è attribuire un peso alle "pedine" e alle mosse. Cosa che puoi fare solo dopo esserti letto 20000 manuali sugli scacchi.
Se vuoi un consiglio, prima fai un bel tris/battaglia navale(si lo so la battaglia navale non è influenzata dalle mosse dell'avversario) e poi puoi passare a forza quattro/dama/scacchi

---

Non sono convinto che un PL su rete sia quello che ci vuole, teoricamente il grafo può cambiare ad ogni mossa e dovresti risolverlo per ogni pedina, dopodichè stabilire un ordinamento sulle soluzioni per decidere una mossa. Ti tirerebbero le pietre prima di finire il calcolo

Quote:

---

Originally Posted by Alkabar

Si vabbeh informatici contro ingegneri FTW. Io sono un ingegnere e sto studiando per un PhD in computer science, cosa devo cercare di strozzarmi con le mie stesse mani ???? :O :O :O.
mahahah.

---

You will always be the child of two worlds. The question is, what will you choose?

ho deciso di fare il taglialegna grazie e arrivederci :angel:

Quote:

---

Originally Posted by marlborojack

Non sono convinto che un PL su rete sia quello che ci vuole, teoricamente il grafo può cambiare ad ogni mossa e dovresti risolverlo per ogni pedina, dopodichè stabilire un ordinamento sulle soluzioni per decidere una mossa. Ti tirerebbero le pietre prima di finire il calcolo
You will always be the child of two worlds. The question is, what will you choose?

---

non ho preso in esame il caso, ma considerando che il numero delle combinazioni possibili è piuttosto limitato (confrontato con un qualsiasi problema di "navigazione" ad esempio) direi che un calcolatore non dovrebbe avere grossi problemi a calcolare tutte le mosse possibili (cmq limitate).

Poi magari ho preso sotto gamba la complessità del problema, ma credo che il problema piu grosso resti comunque valutare il peso della mossa, piu che valutare tutte le mosse possibili (intendo dire che una mossa ha un valore in un dato momento, in un altro ha un "valore" diverso)

La prima cosa che mi verrebbe in mente è di memorizzare tutte le combinazioni possibili in un db, e poi in base alle mosse prese, al valore delle pedine, e al risultato finale, salvare il valore delle mosse in automatico.
Una volta fatto ciò, e lanciata la simulazione di due IA una contro l'altra, con un numero limitato di partite giocate (1M credo basti) in teoria basterebbe che il pc selezionasse dal database la combinazione migliore possibile in base alla media del valore registrato nel 1M partite giocate.

Certo si parla di db con le mosse piuttosto grossi e di numero di calcoli impressionanti.
Però cosi il pc "apprenderebbe" dalle mosse precendenti, e potrebbe anche fare "valutazioni" sulle mosse future. Una sorta di giocatore di scacchi senziente

Quote:

---

Originally Posted by black

non ho preso in esame il caso, ma considerando che il numero delle combinazioni possibili è piuttosto limitato (confrontato con un qualsiasi problema di "navigazione" ad esempio) direi che un calcolatore non dovrebbe avere grossi problemi a calcolare tutte le mosse possibili (cmq limitate).
Poi magari ho preso sotto gamba la complessità del problema, ma credo che il problema piu grosso resti comunque valutare il peso della mossa, piu che valutare tutte le mosse possibili (intendo dire che una mossa ha un valore in un dato momento, in un altro ha un "valore" diverso)
La prima cosa che mi verrebbe in mente è di memorizzare tutte le combinazioni possibili in un db, e poi in base alle mosse prese, al valore delle pedine, e al risultato finale, salvare il valore delle mosse in automatico.
Una volta fatto ciò, e lanciata la simulazione di due IA una contro l'altra, con un numero limitato di partite giocate (1M credo basti) in teoria basterebbe che il pc selezionasse dal database la combinazione migliore possibile in base alla media del valore registrato nel 1M partite giocate.
Certo si parla di db con le mosse piuttosto grossi e di numero di calcoli impressionanti.
Però cosi il pc "apprenderebbe" dalle mosse precendenti, e potrebbe anche fare "valutazioni" sulle mosse future. Una sorta di giocatore di scacchi senziente

---

Non capisco bene il confronto con il problema di navigazione, che viene facilmente risolto con una PNG, o una APNG o le altre mille varianti, magari ti riferisci all'obstacle avoidance di cui non sono esperto, ma le guide principalmente per adesso si fanno a waypoint e si sfruttano piattaforme inerziali per l'automazione del dead reckoning.

BTW, teoricamente, il database che prevedi tu, per ogni possibile configurazione dei pezzi sulla scacchiera e per ogni possibile mossa di ogni pezzo, contiene una riga con un peso, per cui sì, è MOLTO grosso, della serie che minimo per farlo funzionare ti serve davvero un x86 con un po' di memoria onboard. In più, associando un peso ad ogni mossa, devi controllare la convergenza del risultato, che purtroppo è la vittoria, che non dipende solo dalle tue mosse ma anche da quelle dell'aversario, per cui paradossalmente puoi dare un peso alto ad una mossa sbagliata solo perchè il tuo avversario ha anch'egli sbagliato mossa. Insomma il numero di regole è sì upper bounded, ma non è detto che i pesi convergano realmente ad una soluzione. Onestamente, non so bene come farei io perchè non ho il tempo di studiare il problema, ma cercherei un approccio differente, magari di tipo minmax vincolato in maniera da risolvere il tutto con LMI

Quote:

---

Originally Posted by black

non ho preso in esame il caso, ma considerando che il numero delle combinazioni possibili è piuttosto limitato (confrontato con un qualsiasi problema di "navigazione" ad esempio) direi che un calcolatore non dovrebbe avere grossi problemi a calcolare tutte le mosse possibili (cmq limitate).
Poi magari ho preso sotto gamba la complessità del problema, ma credo che il problema piu grosso resti comunque valutare il peso della mossa, piu che valutare tutte le mosse possibili (intendo dire che una mossa ha un valore in un dato momento, in un altro ha un "valore" diverso)
La prima cosa che mi verrebbe in mente è di memorizzare tutte le combinazioni possibili in un db, e poi in base alle mosse prese, al valore delle pedine, e al risultato finale, salvare il valore delle mosse in automatico.
Una volta fatto ciò, e lanciata la simulazione di due IA una contro l'altra, con un numero limitato di partite giocate (1M credo basti) in teoria basterebbe che il pc selezionasse dal database la combinazione migliore possibile in base alla media del valore registrato nel 1M partite giocate.
Certo si parla di db con le mosse piuttosto grossi e di numero di calcoli impressionanti.
Però cosi il pc "apprenderebbe" dalle mosse precendenti, e potrebbe anche fare "valutazioni" sulle mosse future. Una sorta di giocatore di scacchi senziente

---

Il branching factor ad ogni mossa di un ipotetica partita a scacchi è enormemente superiore rispetto a quello di un qualsiasi problema di navigazione eh.
Senza contare poi la difficoltà nell'individuazione dell'euristica, che per quanto concerne un programma di navigazione è una boiata, per gli scacchi è qualcosa di incredibilmente complicato.

memorizzare ogni possibile combinazione di una scacchiera è tipo impossibile :nod:

Quote:

---

Originally Posted by Axet

Il branching factor ad ogni mossa di un ipotetica partita a scacchi è enormemente superiore rispetto a quello di un qualsiasi problema di navigazione eh.
Senza contare poi la difficoltà nell'individuazione dell'euristica, che per quanto concerne un programma di navigazione è una boiata, per gli scacchi è qualcosa di incredibilmente complicato.

---

infatti io ho detto che avevo probabilemente sottovalutato il problema.

per il discorso della valutazione delle mosse in base a quelle dell'avversario, in definitiva non esiste una mossa "sbagliata" secondo la mia idea, ma solo una con valore "inferiore". certo la mia idea di IA non è di una IA destinata a vincere sempre, ma in teoria a "imparare" dai propri errori. (in fondo una ia non è una macchina per vincere, ma una macchina che apprende).

Sul discorso invece delle capacità di calcolo e peso del progetto, non sapevo ci fossero dei limiti. (non ho letto proprio tutto il 3d completamente, mi scuso)
Io davo per assunto che fossero quanto meno due macchine x86 (o una) a lavorare sul tutto (db/codice/etc).

Il problema grosso secondo me non sta nell'hardware, ma nello scrivere un codice piu sensato possibile, che non cada in deadlock e che possa dare risultati in tempi "certi"

wikipedia dice :
Si stima che il numero di posizioni legalmente ammesse sia compreso fra 10^43 e 10^50 e "l'albero di complessità del gioco" è approssimativamente di 10^123, mentre ad ogni mossa le possibilità variano da 0 (in caso di stallo o di scacco matto) a 218.

quindi cosi a naso teoricamente è possibile memorizzare tutto, probabilmente i tempi di risposta non saranno eccelsi se si accentra tutto in una macchina, ma stiamo parlando di una IA, e sfido chiunque a dire che il suo pc possa diventare piu intelligente di una persona (ora guardo deep blue che caratteristiche aveva, cmq non era sicuramente senziente...)

La forza di Deep Blue deriva principalmente dalla sua straordinaria potenza computazionale. Infatti è costituito da un "computer a parallelismo massiccio a 30 nodi basato su RS/6000" supportato da 480 processori specifici VLSI progettati per il gioco degli scacchi. L'algoritmo per il gioco degli scacchi è scritto in C e gira sotto un sistema operativo AIX. L'algoritmo è capace di calcolare 100 milioni di posizioni al secondo

Direi che aveva un bell hw coi contro caxxi per i tempi (96-97)

Quote:

---

Originally Posted by black

per il discorso della valutazione delle mosse in base a quelle dell'avversario, in definitiva non esiste una mossa "sbagliata" secondo la mia idea, ma solo una con valore "inferiore". certo la mia idea di IA non è di una IA destinata a vincere sempre, ma in teoria a "imparare" dai propri errori. (in fondo una ia non è una macchina per vincere, ma una macchina che apprende).

---

La mossa sbagliata la puoi vedere come la diminuzione del valore di una regola, nel tuo esempio. Ci sono due problemi in questo approccio, uno banale di tipo matematico: chi ti dice che i pesi si assestino ad un valore, ovvero, come pesi la dinamica dell'errore, o ancora in altri termini, come fai a decidere se ha imparato o no? Ci vorrebbe una dimostrazione di convergenza, e, ahimè, non ci sono pasti gratis, se conosci l'omonimo teorema. Il secondo è di natura computazionale. Al limite massimo, un'IA del genere avrà un numero di regole pari a tutte le possibili combinazioni di pedine sulla scacchiera moltiplicato cartesianamente a tutte le possibili mosse di ogni singola pedina. Il numero è talmente esorbitante anche solo a pensarci, che confrontato con la complessità di un qualsiasi algoritmo di aggiornamento delle regole probabilmente impiegherebbe un lasso di tempo non molto ragionevole.

Potresti controbattere dicendo di limitare il numero di regole, ma in tal caso ti avverto che dimensionare il numero di regole, equivale a dimensionare il numero di neuroni di una rete neurale necessari a svolgere il compito: anche lì, vale il no free launches theorem. Insomma, a parte le minchiate come Deep Blue, che principalmente servono come trovare pubblicitarie, sono i mezzi logici ad essere inadeguati per un'IA che apprende nel senso comune del termine, tutt'al più per adesso, siamo in grado di spiegargli a priori le mosse dei pezzi e fargli usare qualche regoletta in certe situazioni. Piuttosto deludente, anzichenò

EDIT: 10^123 >>>> di uno yottabyte (S.I. 10^24). Tu su che cazzo memorizzi i dati? ne vorrei uno

Quote:

---

Originally Posted by black

infatti io ho detto che avevo probabilemente sottovalutato il problema.

per il discorso della valutazione delle mosse in base a quelle dell'avversario, in definitiva non esiste una mossa "sbagliata" secondo la mia idea, ma solo una con valore "inferiore". certo la mia idea di IA non è di una IA destinata a vincere sempre, ma in teoria a "imparare" dai propri errori. (in fondo una ia non è una macchina per vincere, ma una macchina che apprende).

---

Certo ma già il fatto di assegnare un peso a una certa mossa è un qualcosa di esageratamente difficile visto che cmq si tratta di un contesto dinamico.
L'efficacia di una mossa è relativa a quello che l'avversario ha fatto all'istante t-1, il che basta per rendere l'idea di quanto è fottutamente difficile trovare un'euristica adatta.

Inoltre non è vero che una AI è una macchina che apprende, la base della conoscenza può anche essere statica.

Quote:

---

wikipedia dice :
Si stima che il numero di posizioni legalmente ammesse sia compreso fra 10^43 e 10^50 e "l'albero di complessità del gioco" è approssimativamente di 10^123, mentre ad ogni mossa le possibilità variano da 0 (in caso di stallo o di scacco matto) a 218.

quindi cosi a naso teoricamente è possibile memorizzare tutto, probabilmente i tempi di risposta non saranno eccelsi se si accentra tutto in una macchina, ma stiamo parlando di una IA, e sfido chiunque a dire che il suo pc possa diventare piu intelligente di una persona (ora guardo deep blue che caratteristiche aveva, cmq non era sicuramente senziente...)

La forza di Deep Blue deriva principalmente dalla sua straordinaria potenza computazionale. Infatti è costituito da un "computer a parallelismo massiccio a 30 nodi basato su RS/6000" supportato da 480 processori specifici VLSI progettati per il gioco degli scacchi. L'algoritmo per il gioco degli scacchi è scritto in C e gira sotto un sistema operativo AIX. L'algoritmo è capace di calcolare 100 milioni di posizioni al secondo

Direi che aveva un bell hw coi contro caxxi per i tempi (96-97)

---

Si ma possibile è possibile, solo che l'essere possibile e l'essere attuabile ci passa l'universo :D

Tu pensa proprio allo stesso deep blue, un macchina strutturata in ogni sua componente hardware e software appositamente per il gioco degli scacchi.
Nonostante riuscisse a calcolare 100 milioni di posizioni al secondo, contro kasparov ha preso le pizze in faccia e quando ha vinto è stato perchè tra un match e l'altro i tecnici IBM ottimizzavano il programma per far si che non cadesse nelle "trappole" tese dall'avversario umano.

Quote:

---

Originally Posted by marlborojack

Non capisco bene il confronto con il problema di navigazione, che viene facilmente risolto con una PNG, o una APNG o le altre mille varianti, magari ti riferisci all'obstacle avoidance di cui non sono esperto, ma le guide principalmente per adesso si fanno a waypoint e si sfruttano piattaforme inerziali per l'automazione del dead reckoning.
BTW, teoricamente, il database che prevedi tu, per ogni possibile configurazione dei pezzi sulla scacchiera e per ogni possibile mossa di ogni pezzo, contiene una riga con un peso, per cui sì, è MOLTO grosso, della serie che minimo per farlo funzionare ti serve davvero un x86 con un po' di memoria onboard. In più, associando un peso ad ogni mossa, devi controllare la convergenza del risultato, che purtroppo è la vittoria, che non dipende solo dalle tue mosse ma anche da quelle dell'aversario, per cui paradossalmente puoi dare un peso alto ad una mossa sbagliata solo perchè il tuo avversario ha anch'egli sbagliato mossa. Insomma il numero di regole è sì upper bounded, ma non è detto che i pesi convergano realmente ad una soluzione. Onestamente, non so bene come farei io perchè non ho il tempo di studiare il problema, ma cercherei un approccio differente, magari di tipo minmax vincolato in maniera da risolvere il tutto con LMI

---

Quote:

---

Originally Posted by Axet

Il branching factor ad ogni mossa di un ipotetica partita a scacchi è enormemente superiore rispetto a quello di un qualsiasi problema di navigazione eh.
Senza contare poi la difficoltà nell'individuazione dell'euristica, che per quanto concerne un programma di navigazione è una boiata, per gli scacchi è qualcosa di incredibilmente complicato.

---

il database non si fa perche' a ogni mossa corrispondono nel nuovo turno altre 40 mosse in media. Normalmente una partita di scacchi va avanti per 100aia di mosse.

Mettiamo siano 100 mosse in totale, sempre:

40^100 e' il numero di record che hai da infilare nel database.... :wolfeek::wolfeek:

Comunque gli scacchi stanno per diventare un gioco completamente risolvibile.

"stanno per diventare" come ho già scritto dipende da quando riusciremo a calcolare tutte le mosse in tempo utile e ad adottare una strategia per evitare ripetizioni (altrimenti le mosse sono chiaramente infinite), allora si, anche negli scacchi vincerà chi muove per primo.

Quote:

---

Originally Posted by Hador

"stanno per diventare" come ho già scritto dipende da quando riusciremo a calcolare tutte le mosse in tempo utile e ad adottare una strategia per evitare ripetizioni (altrimenti le mosse sono chiaramente infinite), allora si, anche negli scacchi vincerà chi muove per primo.

---

Piu' semplice hador: c'e' gia' un computer quantistico in grado di calcolare tutte le mosse in tempo reale.... Quando vanno in produzione industriale, tra una ventina di anni, gli scacchi si giocheranno tra umani e basta.

continuo ad esser scettico sui computer quantistici, al di la della tecnica (se ne parla da 30 anni cmq) voglio vedere come cazzo ci programmi sopra :nod:

Quote:

---

Originally Posted by marlborojack

EDIT: 10^123 >>>> di uno yottabyte (S.I. 10^24). Tu su che cazzo memorizzi i dati? ne vorrei uno

---

non ho detto che sia fattibile oggi, ma solo che sia teoricamente fattibile. certo che le mie "idee" sono molto terra terra, non ho valutato un sacco di cose. e cmq ci sono cose che in questo momento mi sfuggono (o ignoro completamente).

imho cmq questa è una via per risolvere il gioco degli scacchi.

Per il discorso che una IA non deve per forza imparare, e della conoscenza statica, è una questione di punti di vista. Secondo me una IA che non impare, e aumenta le sue conoscenze non è una IA. Cioè se voglio tentare di paragonarla a quella umana deve : apprendere, modificare le informazioni apprese, eliminare quelle considerate inutili (bel problema) e saper scegliere la soluzione ottima per il contesto (non la migliore).

Il concetto di AI è a dir poco labile.
Ci sono miliardi di interpretazioni.. un po' come i roboticisti e quelli del ramo AI che si scannano sul concetto di agente insomma