Reti neurali - Risoluzione gioco numerico

[pinklady]

Ciao a tutti,
avrei bisogno di un consiglio. Devo svolgere una tesina sulle reti neurali e pensavo di addestrare la rete a risolvere il famoso gioco del 15, per chi non lo sapesse un quadrato 4x4 con i numeri da 1 a 15 e l'ultima casella vuota. Partendo da qualsiasi configurazione random la rete dovrebbe essere in grado di ordinare le caselle in meno mosse possibile, oppure se è in configurazione non risolvibile dirmelo come risposta.
Penso sia fattibile, no?

[g.schgor]

Molto interessante, ma sulla fattibilità ho qualche dubbio.
Il gioco richiede numerose mosse successive, quindi si tratta
di stabilire una strategia "vincente" per decidere ciascuna mossa.
Esiste un modello a cui riferirsi?

[dimaios]

E' un problema estremamente complesso da risolvere con una rete neurale in quanto il numero di possibilità nel searching path è enorme ( vedi per esempio questo ).

L'algoritmo classico per la sua soluzione è l' "A* search algorithm" che nulla ha a che fare con un neural network.

Un problema evidente con il quale dovresti scontrarti è il numero esiguo di campioni per il training rispetto al totale per cui l'interpolazione della rete neurale sarebbe inefficace.

Anche con le SVM la vedo molto dura perché non vedo facilmente un modo semplice per ricondurre il problema ad un classificatore.

[pinklady]

Mm quindi secondo voi mi metterei in qualcosa di troppo complicato? Ho trovato qualcosa di scritto con Java, ma ovviamente c'è da considerare che la metà delle combinazioni non è risolvibile, per un numero di scambi pari e io dovrei far dire alla rete semplicemente che non può farlo... Accidenti mi piaceva l'idea

[Guerra]

Mm quindi secondo voi mi metterei in qualcosa di troppo complicato?

"Agli ingegneri piace risolvere i problemi. Se non ci sono problemi sottomano, gli ingegneri li creeranno"
Scott Adams

[dimaios]

Una rete che gioca a tria si riesce a definire ed addestrare. Non è un progetto così ambizioso ma didatticamente interessante.

[pinklady]

Si hai ragione Guerra, è proprio nella mia firma! ;)
dimaios non ho capito che cos'è tria...

[PietroBaima]

Sì, anche io volevo proporti il problema del tris.

Se vuoi renderti conto di quanto è difficile il problema del gioco del 15 risolto con una rete neurale, prova a risolvere neuralmente il gioco del tris

Quando vidi la prima volta la rete neurale che risolveva il tic-tac-toe, il tris, appunto, rimasi stupito di quanta complessità possa avere un cervello di gallina (non è una battuta).

Quando avrai risolto il tris potrai passare al nim, in versione classica o Marienbad, per fare un po' di pratica con questo tipo di problemi.

Se risolvi il gioco del 15 ti prego di farmelo sapere.

Ciao,
Pietro.

[PietroBaima]

"Agli ingegneri piace risolvere i problemi. Se non ci sono problemi sottomano, gli ingegneri li creeranno"
Scott Adams

"Anche una rete neurale naturale ha bisogno di addrestramento"
Pietro Baima

[g.schgor]

Se ti interessano gjochi alternativi,
ti segnalo questi articoli:
NIM
Esapedone