Fabio Ruini’s blog

Come tema d’esame, si richiede allo studente di scrivere un programma, in linguaggio C, in grado di far giocare all’utente una partita di dama “uomo vs macchina”.

Le regole del gioco della dama sono riportate qui di seguito, leggermente modificate rispetto alla descrizione presente su Wikipedia:

La Dama si svolge tra due giocatori disposti ai lati opposti di una damiera che muovono alternativamente i propri pezzi. Un giocatore controlla i pezzi bianchi, l’altro quelli neri. I pezzi si muovono diagonalmente, solo sulle caselle scure non occupate da altri pezzi e hanno la possibilità di prendere (o “mangiare”) quelli avversari, scavalcandoli. I pezzi catturati vengono rimossi dalla damiera ed esclusi dal gioco. La presa, quando possibile, è obbligatoria. Il giocatore a cui vengono catturati tutti i pezzi o che, al suo turno di mossa, è impossibilitato a muovere, ha perso.
I pezzi semplici (“pedine”) possono muoversi di una sola casella alla volta, diagonalmente e in avanti. Essi possono inoltre mangiare un pezzo avversario facendo un movimento di due caselle nella stessa direzione saltando sopra il pezzo avversario nella casella intermedia. Se nella casella di arrivo si presentano per la pedina le condizioni di una nuova presa, si è in presenza di una presa multipla che va effettuata nello stesso turno di gioco.
Quando una pedina raggiunge la base avversaria, ossia la riga più distante nella sua direzione di marcia, diventa “dama”. La dama viene contrassegnata apponendo un ulteriore pezzo sopra il primo e gode di particolari poteri: a differenza delle pedine può muoversi e catturare sia avanti che indietro. La dama non può inoltre essere mangiata da una pedina.
Durante una partita potrebbe verificarsi l’episodio di patta. La patta si effettua in 2 casi esclusivi: quando restano due dame (una per avversario) oppure quando restano tre dame (una di un giocatore e due dell’avversario);

Il software dovra’ costantemente visualizzare sullo schermo la damiera con le varie pedine/dame disposte su di essa. Attraverso un menu a scelta rapida, visualizzato preferibilmente in forma semi-grafica (intesa semplicemente come utilizzo dei caratteri ‘-‘, ‘|’ e simili), l’utente dovra’ effettuare la scelta tra una delle seguenti opzioni:

1. Inizia una nuova partita
2. Effettua una mossa
3. Individua la mossa migliore
4. Concludi una partita in corso
5. Esci dal programma

L’utente dovra’ scegliere l’operazione da eseguire digitando il numero corrispondente e premendo il tasto INVIO. Si tenga presente che l’utente non dovra’ avere sempre accesso a tutte le funzionalità del programma. Ad esempio, le operazioni 2, 3 e 4 non saranno disponibili fintanto che non verra’ iniziata una nuova partita.

Ulteriori note

• Il progetto dovra’ essere realizzato individualmente.
• Il programma dovrà essere scritto in codice ANSI C standard, al fine di garantirne il più ampio livello di portabilità possibile. Non e’ ammesso, a meno che tale possibilità non sia esplicitata nel testo d’esame o nelle FAQ pubblicate su Dolly, l’utilizzo di comandi propri del sistema operativo in uso. Il programma dovra’ essere in grado di “girare” allo stesso modo su qualsiasi piattaforma.
• Il programma dovra’ essere adeguatamente commentato. Non abbiate paura di essere eccessivamente prolissi nei vostri commenti.
• Il programma dovra’ rispettare in maniera assolutamente rigorosa le specifiche illustrare in questo documento. Qualsiasi modifica rispetto allo schema ivi delineato ed apportata in maniera arbitraria verra’ considerata un errore. Per qualsiasi dubbio o chiarimento si prega di utilizzare il forum.
• Il giocatore “umano” dovra’ controllare le pedine/dame bianche, mentre il computer controllera’ le pedine/dame nere.

La damiera dovra’ essere implementata attraverso una matrice di valori interi, dove: 0 corrisponde ad una casella vuota, 1 corrisponde ad una casella occupata da una pedina bianca, 2 corrisponde ad una casella occupata da una dama bianca, 3 corrisponde ad una casella occupata da una pedina nera, 4 corrisponde ad una casella occupata da una dama bianca.

• La funzione 1 dovra’ provvedere ad inizializzare la damiera, disponendo su di essa le pedine nella loro corretta posizione di partenza.
• La funzione 2 dovra’ presentarsi all’utente visualizzando innanzitutto una lista delle pedine/dame che e’ possibile muovere. L’utente dovra’ quindi scegliere la pedina/dama da muovere e successivamente il software dovra’ proporre le possibili mosse per la pedina/dama scelta. L’utente dovra’ scegliere tra queste quale mossa effettuare. In caso di ripensamenti o errori, l’utente dovra’ avere la possibilita’ di modificare la pedina/dama scelta.
• Alla mossa dell’utente dovra’ immediatamente far seguito la mossa eseguita dal computer. Tale mossa dovra’ essere puramente casuale (una pedina/dama scelta in maniera casuale, la quale effettua una mossa casuale), rispettando tuttavia le regole del gioco.
• La funzione 3, facendo ricorso ad un albero binario, dovra’ analizzare, tra le possibili mosse dell’utente, qual e’ quella con il “valore atteso” piu’ alto. La scrittura della funzione per il calcolo del valore atteso di una mossa viene lasciata alla fantasia dell’utente. A grandi linee, si consideri che i fattori in grado di incrementare il valore atteso di una mossa sono: il mangiare una pedina/dama avversaria, il rendere possibile la successiva cattura di una pedina/dama avversaria, fuggire da una cattura, il trasformarsi in dama di una pedina. L’utilizzo di un albero e’ previsto in maniera tale da poter valutare una mossa non soltanto nell’immediato, ma anche “in prospettiva” (ovvero, in funzione delle future mosse rese possibili dall’aver effettuato una certa mossa).