際際滷

際際滷Share a Scribd company logo

Behind the scenes of Sudoku - Application of genetic algorithms for the optimal fun.

Download as PPTX, PDF
T
Thomas Bridi

This work discusses about algorithms belonging to the branch of artificial intelligence for the generation of Sudoku puzzle. It will be demonstrated how the use of algorithms related to the constraint programming and genetic algorithms can improve the generation of puzzles in order to make the game more competitive and therefore more attractive to the public. In particular, it will be used an algorithm similar to the forward checking for the generation of a population of deterministic puzzles with a feasible solution and then will be used a genetic algorithm to evolve the population in order to optimize a function that rates the difficulty of their resolution. http://ceur-ws.org/Vol-860/paper2.pdf

1 of 13
Download to read offline
Behind the scenes of Sudoku - Application of genetic algorithms for the optimal fun.
Behind the scenes of Sudoku Application of genetic algorithms for the optimal fun Thomas Bridi Thomas.bridi@studio.unibo.it S
Sudoku: il gioco S Gioco di logica S Dominio e vincoli S Sudoku probabiliatici S Sudoku deterministici
Lobbiettivo S Generare Sudoku deterministici S Creare puzzle sempre pi湛 difficili
Inizialmente S Mappare il problema della generazione come un CSP S Creare un algoritmo ad-hoc per la propagazione dei domini S Risolutore che mima le tecniche di soluzione usate dalluomo per identificare un puzzle deterministico
Il problema S La difficolt del puzzle non 竪 garantita a causa del risolutore: la difficolt dipende dal numero di tecniche implementate ma pu嘆 capitare che un puzzle generato possa essere risolto usando solamente tecniche semplici S Lagoritmo riconosce solo un sottoinsieme di puzzle deterministici
Una possibile soluzione S Generare una popolazione di Sudoku e farli evolvere utilizzando unalgoritmo genetico per ottenere puzzle sempre pi湛 difficili
Lapproccio (1) S Viene creato un genotipo in base alle celle selezionate durante la creazione e al valore inserito Genotype:
Lapproccio (2) S Una funzione di fitness (da ottimizzare) basata su quante volte una tecnica (con un determinato peso di difficlt) viene utilizzata S Viene generata una popolazione iniziale di puzzle S Vengono applicate operazioni come mutazione, incrocio e selezione naturale
Lambiente S Ambiente molto selettivo S Tutti i membri della popolazione vengono incrociati con tutti gli altri pi湛 volte S Tutti i membri vengono mutati S Tutti i genitori muiono nella generazione successiva S La popolazione viene mantenuta costante dalla selezione naturale S Possibilit di estinzione
Performance e risultati (1) S Solo l8,24% delle griglie porta con successo a un puzzle deterministico prima del fallimento dellalgoritmo spiegato in precedenza S La percentuale di mutazioni che porta a griglie pi湛 difficili 竪 il 35,88% S Lalgoritmo richiede circa 3 ore per generare e mutare 10000 puzzle (20000 Sudoku differenti)
Performance e risultati (2) Andamento della difficolt media e massima su una popolazione costante di 100 puzzle mutati, incrociati e selezionati 1600 1400 1200 1000 800 Difficolt media 600 Difficolt massima 400 200 0 0 1 2 3 4 5 6 7
Behind the scenes of Sudoku - Application of genetic algorithms for the optimal fun.

More Related Content

Behind the scenes of Sudoku - Application of genetic algorithms for the optimal fun.

  • 2. Behind the scenes of Sudoku Application of genetic algorithms for the optimal fun Thomas Bridi Thomas.bridi@studio.unibo.it S
  • 3. Sudoku: il gioco S Gioco di logica S Dominio e vincoli S Sudoku probabiliatici S Sudoku deterministici
  • 4. Lobbiettivo S Generare Sudoku deterministici S Creare puzzle sempre pi湛 difficili
  • 5. Inizialmente S Mappare il problema della generazione come un CSP S Creare un algoritmo ad-hoc per la propagazione dei domini S Risolutore che mima le tecniche di soluzione usate dalluomo per identificare un puzzle deterministico
  • 6. Il problema S La difficolt del puzzle non 竪 garantita a causa del risolutore: la difficolt dipende dal numero di tecniche implementate ma pu嘆 capitare che un puzzle generato possa essere risolto usando solamente tecniche semplici S Lagoritmo riconosce solo un sottoinsieme di puzzle deterministici
  • 7. Una possibile soluzione S Generare una popolazione di Sudoku e farli evolvere utilizzando unalgoritmo genetico per ottenere puzzle sempre pi湛 difficili
  • 8. Lapproccio (1) S Viene creato un genotipo in base alle celle selezionate durante la creazione e al valore inserito Genotype:
  • 9. Lapproccio (2) S Una funzione di fitness (da ottimizzare) basata su quante volte una tecnica (con un determinato peso di difficlt) viene utilizzata S Viene generata una popolazione iniziale di puzzle S Vengono applicate operazioni come mutazione, incrocio e selezione naturale
  • 10. Lambiente S Ambiente molto selettivo S Tutti i membri della popolazione vengono incrociati con tutti gli altri pi湛 volte S Tutti i membri vengono mutati S Tutti i genitori muiono nella generazione successiva S La popolazione viene mantenuta costante dalla selezione naturale S Possibilit di estinzione
  • 11. Performance e risultati (1) S Solo l8,24% delle griglie porta con successo a un puzzle deterministico prima del fallimento dellalgoritmo spiegato in precedenza S La percentuale di mutazioni che porta a griglie pi湛 difficili 竪 il 35,88% S Lalgoritmo richiede circa 3 ore per generare e mutare 10000 puzzle (20000 Sudoku differenti)
  • 12. Performance e risultati (2) Andamento della difficolt media e massima su una popolazione costante di 100 puzzle mutati, incrociati e selezionati 1600 1400 1200 1000 800 Difficolt media 600 Difficolt massima 400 200 0 0 1 2 3 4 5 6 7