area pubblica
home page
chi siamo
come lavoriamo
collabora con noi
progetti
community projects
contatti
feedback
link
wallpapers
area riservata
progetti riservati
message board
gestione sito
webmail
 

Scuola di fumetto e illustrazione
 



Periodo: 2000
Stato di realizzazione: Concluso

Versione java del solitario della Dama Cinese.



Team
Coordinatore: Letizia Beriozza
Programmatori: Simone Re


Documentazione

29/03/2005
La Dama Cinese è un solitario che si gioca su una scacchiera di 33 caselle a forma di croce; ogni braccio della croce è un rettangolo di 3 x 2 . All'inizio della partita in tutte le caselle, tranne in quella centrale, vi è una pedina.
Lo scopo del gioco è eliminare tutte le pedine meno una dalla scacchiera.

E' possibile eliminare una sola palla per mossa scavalcandola con una adiacente; la pedina scavalcata viene eliminata e quella scavalcante si posiziona nella casella opposta a quella di partenza rispetto alla pedina eliminata. Naturalmente la casella di arrivo della pedina mossa deve essere libera.

La partita è persa se sulla scacchiera rimane più di una pedina e non è più possibile effettuare mosse.

Oltre all'implementazione classica di questo solitario, la versione finale comprende le seguenti funzionalità:
New Game

Questa funzione permette di iniziare una nuova partita in qualsiasi momento; naturalmente questo comporta l'azzeramento del punteggio e la cancellazione di ogni altro evento precedentemente memorizzato.

Hall Of Fame

Questa funzione memorizza i migliori risultati ottenuti in caso di vittoria. Una volta terminato il gioco con successo, una finestra permette di inserire il proprio nome accanto al relativo punteggio per creare una vera e propria classifica. Naturalmente per poter accedere all'Hall Of Fame il punteggio non deve essere negativo.

Rules

Alla pressione del tasto "rules" si apre una finestra dove è possibile consultare le regole del gioco e la funzione dei vari pulsanti presenti nel programma. Questa finestra è dotata di una scrollbar per permettere una visualizzazione più comoda.

Go Back

Questa funzione, quando invocata, permette di annullare a ritroso l'ultima mossa fatta. Infatti tutte le mosse fatte vengono di volta in volta memorizzate nell'oggetto History; in questo modo il programma è in grado di ricordarsi le mosse fatte e di risalire fino alla prima. Ad ogni pressione del tasto "back" il punteggio fino ad allora ottenuto viene decrementato di due punti per premiare i giocatori più "autodidatti".

Suggest Move

Questa funzione, quando invocata, esamina la disposizione delle pedine sulla scacchiera e cerca una soluzione; se la trova suggerisce al giocatore la mossa che porta alla soluzione trovata altrimenti il programma si dichiara incapace di risolvere la situazione. Il tempo massimo della ricerca è di un minuto.

Algoritmo di ricerca L'algoritmo di ricerca è implementato utilizzando diverse tecniche di Intelligenza Artificiale e in particolare di "Problem Solving".

Rappresentazione del problema: Per poter applicare l'algoritmo di ricerca il programma deve innanzi tutto rappresentare in qualche modo i dati su cui lavorare. Nel nostro caso i dati sono costituiti dalle diverse posizioni delle pedine sulla scacchiera (stati) e vengono memorizzate in diversi oggetti "Nodo".

Tecnica di ricerca La tecnica di ricerca consiste nella generazione ricorsiva di tutte le possibili mosse a partire dallo stato d'arrivo del giocatore. Viene in questo modo generato un albero di stati contenente tutte le mosse possibili. Purtroppo, nella maggior parte dei casi non è possibile generare l'intero albero delle mosse in un tempo relativamente breve (es. 1 minuto) a causa dell'elevato numero di stati da analizzare.

Per questo motivo si sono implementati una serie di algoritmi che permetono di velocizzare l'operazione:
  • Deep-first search
  • Greedy search
La deep-first search consiste nell'analizzare l'albero degli stati espandendo sempre un nodo al livello piu' basso dell'albero.

Si discende di fatto un ramo dell'albero fino a che non si trova la soluzione o non si hanno più mosse da fare (cioè stati da espandere). In quest'ultimo caso si risale l'albero fino all'ultimo "bivio" superato e si espande l'altro ramo.

La deep-first search abbatte notevolmente il numero di stati analizzati prima di trovare la soluzione nel caso il problema abbia diverse soluzioni "sparse" all'interno dell'albero.

La Dama Cinese ha questo requisito e si presta perfettamente all'utilizzo di questa tecnica anche per la profondità limitata del suo albero degli stati: infatti, poichè per ogni livello dell'albero il numero di pedine diminuisce di uno, le eventuali soluzioni si trovano tutte allo stesso livello; quindi una volta raggiunto quel livello, o si trova una soluzione o si ritorna sui propri passi. Questa proprietà impedisce le ricerche cicliche in rami privi di soluzioni.

Un altro aspetto importante della deep-first search è la poca memoria richiesta. Infatti invece di dover tenere in memoria l'intero albero degli stati ne tiene soltanto un ramo per volta.

La greedy search invece ha il compito di applicare una o più funzioni per valutare quanto sia "meglio" uno stato rispetto ad un altro. Naturalmente l'aggettivo "meglio" si riferisce a quanto lo stato si avvicina alla soluzione. Gli stati vengono successivamente ordinati ed analizzati dal migliore al peggiore.

Nel nostro caso si è voluto apportare una modifica alla tecnica di ricerca classica implementando una serie di algoritmi per scartare o tenere gli stati (senza quindi valutazioni intermedie).

Con questa tecnica si riduce la dimensione dell'albero degli stati velocizzando notevolmente il processo di analisi. Gli algoritmi utilizzati sono: L'Alone Plus si basa sul semplice presupposto che se uno stato ha una pedina irraggiungibile non può portare ad una soluzione. Il problema è quello di definire esattamente cosa significa irraggiungibile.

Come concetto di base si può dire che una pedina è irraggiungibile se non ha pedine nelle 4 caselle adiacenti (quindi non può né mangiare un'altra pedina né essere mangiata).
Naturalmente questa definizione è una buona base di partenza, ma è vistosamente incompleta; infatti basta avere due pedine poste in modo tale che in una mossa si riesca a raggiungere una casella adiacente alla pedina interessata perchè quest'ultima sia perfettamente raggiungibile!

Quindi si può modificare la definizione precedente:

una pedina è isolata se non ha una pedina adiacente e non ci sono pedine che in una mossa generano una pedina adiacente.

Di questo passo si possono aumentare le mosse controllate praticamente all'infinito. (una pedina è isolata se non ha una pedina adiacente e non ci sono pedine che in n mosse generano una pedina adiacente...)

L'algoritmo interno che fa questo è appunto il Fist che in questo caso controlla una profondità di sei mosse. Infatti un ulteriore aumento diminuisce il numero di stati analizzati prima di trovare una soluzione, ma aumenta il tempo complessivo di calcolo.

Nei controlli dell'esistenza delle pedine il Fist non considera naturalmente la pedina di riferimento né quelle già utilizzate.

Difetti: teoricamente nella Dama Cinese si può generare uno stato simile a questo
che porta chiaramente alla vittoria, ma che è scartato dall' Alone+ perchè non vede oltre le sei mosse. Si è deciso di accettare questo compromesso perchè tale stato è difficilmente raggiungibile in una fase di gioco vera e propria.


L'Alone Group applica lo stesso presupposto dell'algoritmo precedente però ragionando sui gruppi di pedine.

Infatti uno stato con una coppia di pedine non raggiungibili dalle altre non viene scartato dall'Alone Plus perchè le singole pedine non sono isolate (è infatti isolato il gruppo).

L'Alone Group analizza la disposizione delle pedine e le suddivide in gruppi (cioè pedine adiacenti tra loro); dopodiché applica il Fist VI a tutti i gruppi di dimensioni inferiori a 6.

La limitazione della dimensione del gruppo è stata dettata dallo stesso motivo che ha limitato la profondità delle mosse a 6 nell'algoritmo precedente.

Il procedimento applicato dall' Alone Group è il seguente : per ogni pedina della scacchiera ne calcola il gruppo ( se non fa già parte di un precedente). Genera le mosse possibili del gruppo e per ognuna di queste, ricorsivamente, viene creata una scacchiera temporanea e qui applico l' Alone+.


Infine il Fail Memory permette al programma di "ricordare" gli stati precedentamente scartati e da cui è dovuto tornare sui propri passi.

Se il nuovo stato da analizzare è uguale ad uno stato presente nel Fail Memory allora è inutile analizzarlo perchè porterà sicuramente ad un fallimento.

In realtà il Fail Memory funziona come una memoria cache infatti non memorizza tutti gli stati che portano ad un fallimento, ma solamente gli ultimi 800 per livello dell'albero. Infatti, nonostante il numero delle mosse diminuisce all'aumentare della dimensione della cache fino a un valore minimo in corrispondenza di una cache illimitata, il tempo raggiunge un valore minimo in un intorno di 800 e poi risale proporzionalmente alla cache.

Andamento del tempo e delle mosse con 21 palle
L'ordine di applicazione degli algoritmi precedenti è il seguente :
  • Alone+
  • Fail Memory
  • Alone Group
La scelta è stata dettata in base al numero medio degli stati non validi scartati dai vari algoritmi.


Apprendimento

Il programma è anche in grado di imparare ogni soluzione suggerita o trovata dal giocatore.

L'algoritmo di apprendimento è estremamente semplice:

quando il giocatore vince o quando il programma trova una soluzione nell'albero degli stati, tale soluzione viene memorizzata in una struttura persistente (oggetto "Memory") secondo un'organizzazione predefinita e il più sintetica possibile.

Tale organizzazione rispecchia una struttura ad labero nella quale ogni soluzione indipendente è rappresentata da un albero lineare. Le soluzioni che hanno in comune uno o più stati vengono rappresentati come rami alternativi della soluzione esistente.
Il programma, all'inizio, ha in memoria otto soluzioni diverse.

Quando invece il programma ricerca una soluzione nell'albero degli stati verifica che lo stato da analizzare sia uguale agli stati precedentemente "imparati", se così è interrompe la ricerca e propone la soluzione contenuta nell'oggetto Memory con un notevole ripsarmio di tempo.


Conclusioni

29/03/2005
Con l'implementazione di questi algoritmi si e' raggiunto un risultato piu' che soddisfacente, infatti il programma e' in grado di portare a termine la ricerca della soluzione (sia che questa esista o non esista) in un minuto per stati di partenza con 24 pedine o meno. La ricerca nell'albero degli stati non analizza mai stati con meno di 7 pedine se questi non portano ad una soluzione, infatti analizzando qualsiasi posizione di 7 pedine il programma riesce a determinare se la posizione porta o meno ad una soluzione.


area informativa
news
note legali

cerca in ninibeLabs con

Google



Powered by:
Laboratori Ninibe
BorderZone s.r.l.

Web master:Letizia Beriozza