Programmare una IA

[Hardcore]

ho deciso di fare il taglialegna grazie e arrivederci

[black]

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

[marlborojack]

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

[Axet]

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.

[Hador]

memorizzare ogni possibile combinazione di una scacchiera è tipo impossibile

[black]

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)

[marlborojack]

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

[Axet]

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.

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

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.

[Alkabar]

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

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....

Comunque gli scacchi stanno per diventare un gioco completamente risolvibile.

[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.

[Alkabar]

"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.

[Hador]

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

[black]

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).

[Axet]

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