Algoritmo del Ruzzle Solver

Con il successo di Ruzzle Solver, molti utenti mi hanno più volte richiesto di pubblicarne il codice sorgente, o semplicemente delle informazioni su come se ne potesse fare uno simile. Altri invece erano particolarmente interessati, visto che avrebbero dovuto fare un progetto simile per un esame universitario.

In questo post cercherò solamente di valutare brevemente alcuni metodi per poter realizzare un algoritmo di questo tipo. Sicuramente scriverò altri articoli che tratteranno di temi più specifici in futuro.

I test che vedrete in seguito sono stati eseguiti con algoritmi scritti in C, ed su un MacBook Pro con processore Intel Core i5 da 2.3 Ghz; altre implementazioni potranno quindi riportare risultati differenti, anche se mi aspetto che il rapporto tra di esse sia identico.

Continua a leggere

Intelligenza Artificiale: Markov Decision Process

In Intelligenza artificiale, in alcune situazioni, hai bisogno di una semplice sequenza di azioni per raggiungere in determinato obiettivo, partendo da uno stato noto; in tutti quegli ambienti dove invece le azioni non sono deterministiche (non deterministiche o stocastiche), questo non è più sufficiente: c’è bisogno di una policy, ovvero di una politica che ci dice qual’è l’azione giusta da fare in ogni stato.

Le Markov Decision Process sono una struttura matematica che ci aiuta a costruire queste policy in ambienti stocastici dove si conoscono le probabilità che si verifichino determinati risultati.

In questo post, io vi darò una brevissima introduzione e poi vi mostrerò le parti essenziali della mia implementazione, in python, dei più importanti algoritmi che vi possono aiutare per trovare le policy in ambienti stocastici. Potete trovare una più dettagliata descrizione delle Markov Decision Process nelle mie slide che ho preparato per un seminario nella mia università.

Continua a leggere