Intelligenza artificiale: soluzione del gioco del 15

Nel post precedente abbiamo visto come creare il gioco del 15, oggi ci spingeremo ben oltre.
Il gioco del 15 è costituito da 16 pulsanti, dove il sedicesimo rappresenta lo spazio vuoto dove spostare le altre tessere, di base si può scrivere la configurazione della vittoria così:

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

che possiamo scriverla anche così:

1,2,3,4,
5,6,7,8,
9,10,11,12,
13,14,15,16

che possiamo scriverla anche così:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

La sequenza di numeri che si presenta quando il gioco comincia è mescolata, il problema che mettendo le tessere a caso, non tutte le combinazioni possono essere risolte. Senza entrare troppo nel dettaglio,sappiate che per essere risolvibile un gioco del quindici, il numero di inversioni deve essere pari o dispari a seconda di alcune condizioni.
Per inversione si intende che nella sequenza scritta tutta in un unica riga, in numero piccolo viene dopo un numero grande; la casella vuota, il 16 nel nostro caso, non conta.
Ad esempio questa combinazione:

12	1	10	2
7	11	4	14
5		9	15
8	13	6	3

si scrive così:

12,1,10,2,7,11,4,14,5,16,9,15,8,13,6,3

e in questa combinazione ci sono 49 inversioni, perchè:

• il 12 ha 11 inversioni dopo di sè
• il 10 ha 8 inversioni dopo di sè
• il 7 ha 4 inversioni dopo di sè
• il 11 ha 6 inversioni dopo di sè
• il 4 ha 1 inversioni dopo di sè
• il 14 ha 6 inversioni dopo di sè
• il 5 ha 1 inversioni dopo di sè
• il 9 ha 3 inversioni dopo di sè
• il 15 ha 4 inversioni dopo di sè
• il 8 ha 2 inversioni dopo di sè
• il 13 ha 2 inversioni dopo di sè
• il 6 ha 1 inversione dopo di sè

Se il numero 16, lo spazio vuoto, si trova su una riga pari, il numero di inversioni deve essere pari; se il 16 si trova su una riga dispari, il numero di inversioni deve essere dispari.
Nell'esempio appena mostrato, il 16 si trova sulla terza riga, dispari e il numero di inversioni è dispari, quindi è risolvibile.
Nel nostro programma, quando mescoliamo alla rinfusa i numeri, dobbiamo controllare se è risolvibile. In caso contrario la via più semplice è estrarre una nuova combinazione, poichè la metà delle combinazioni ottenibile è solvibile e il computer è più veloce a generare tantissime combinazioni fino ad ottenere una solvibile, piuttosto che altri metodi.
Il codice del programma va cambiato così:

on openCard
   mescola
end openCard

on controllaVittoria
   put the soluzione of me into ordine
   repeat with i=1 to 16
      put (the loc of button i ) & cr after temp
   end repeat
   if ordine = temp then
      answer "Hai vinto!"
   end if
end controllaVittoria

on impostaVittoria
   repeat with i=1 to 16
      put (the loc of button i ) & cr after temp
   end repeat
   set the soluzione of me to temp
end impostaVittoria

on mescola
   put "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16" into temp
   put the soluzione of me into posizioni
   repeat with i=1 to 16
      put the number of items of temp into nn      
      put random(nn) into elemento
      put item elemento of temp & CR after ordineBottoni
      delete item elemento of temp #così leva anche la virgola
   end repeat   
   put itemoffset("16",ordineBottoni) into n16
   put controllasolv(ordineBottoni) into nInv
   switch n16
      case ((1 <= n16 ) and (n16 <= 4))
      case ((9 <= n16 ) and (n16 <= 12))
         #la casello vuota e' su una riga dispari
         if (nInv mod 2) is 0 then mescola
         break
      case ((5 <= n16 ) and (n16 <= 8))
      case ((13 <= n16 ) and (n16 <= 16))
         #la casello vuota e' su una riga pari
         if (nInv mod 2) is not 0 then mescola
         break
   end switch
   repeat for each line tLine in ordineBottoni
      set the loc of button tLine to the first line of posizioni
      delete the first line of posizioni
   end repeat
   exit to top
end mescola

function controllasolv seq
   put 0 into nInv
   repeat with i=1 to 16
      put item i of seq into temp
      put item (i+1) to 16 of seq into tSeq
      add inversioni(temp,tSeq) to nInv
   end repeat
   return nInv
end controllasolv

function inversioni t,seq
   put 0 into nInv
   repeat for each item tItem in seq      
      if (t > tItem) and (t is not 16) then
         add 1 to nInv
      end if      
   end repeat
   return nInv
end inversioni



Detto ciò, il numero massimo per risolvere il gioco del 15 è di 80 mosse, ma calcolare la soluzione migliore per ogni configurazione richiede una potenza di calcolo spaventosa. Nel 2005 ci volevano settimane utilizzando super computers.
Potete utilizzare varie tecniche per trovare la soluzione, ma la migliore rimane quella di utilizzare un database.
Dalla soluzione, dovete cercare di arrivare alla sequenza di partenza, ogni mossa deve essere registrata nel database almeno nel seguente modo:

n.mossa

sequenza

sequenza precedente

In questo modo, se trovate una sequenza già eseguita, non dovete più proseguire e solo raffrontare il numero di mosse per arrivarci, per stabilire quale è la migliore. Se la nuova sequenza è già presente nel database e ci arrivate con un numero di mosse maggiore, allora non proseguite; in caso contrario cancellate dal database quella vecchia e lasciate quella nuova.
Inoltre segnare la sequenza precedente vi permette di andare a ritroso nella soluzione. Il database vi permette di trovare subito se una sequenza che è già stata elaborate precedentemente e non perde tempo nel calcolare la soluzione.
Finchè la tabella del database non raggiunge le 10'461'394'944'000 righe, voi  non avrete la certezza di trovare la soluzione col minor numero di mosse; ma di sicuro troverete una nel minor tempo di elaborazione possibile.
Ogni volta che cercherete la soluzione ad una sequenza, il database diventerà sempre più grande e la ricerca sarà sempre più veloce.
Qui trovate alcuni link interessanti:

• https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
• http://kevingong.com/Math/SixteenPuzzle.html
• http://kociemba.org/fifteen/fifteensolver.html