1 /*
2 Copyright (C) 2014 Alessandro Bugatti (alessandro.bugatti@istruzione.it)
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 */
18
19 /*! \file
20 * \brief Semplice implementazione della metodologia MiniMax applicata la gioco del tris
21 * \author Alessandro Bugatti
22 *
23 * \version 0.1
24 * \date Creazione 21/05/2014
25 * \date Ultima modifica 21/05/2014
26 */
27
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31
32
33
34 struct mossa{
35 int riga;
36 int colonna;
37 };
38
39 int tris[3][3];
40 mossa da_fare; //La mossa da fare dopo ogni scelta minimax
41
42 //Converte i numeri nella matrice nei segni grafici desiderati
43 //Se si vogliono cambiare i simboli basta modificare qui
44 char conversione(int n)
45 {
46 if (n == 0) return ' ';
47 if (n == 1) return 'x';
48 if (n == -1) return 'o';
49 }
50
51 /*Stampa della griglia*/
52 void stampa_griglia()
53 {
54 int i;
55 char c1,c2,c3;
56 printf("\t\t\t\t***** TRIS *****\n\n");
57 for (i=0 ; i < 3 ; i++)
58 {
59 c1 = conversione( tris[i][0]);
60 c2 = conversione( tris[i][1]);
61 c3 = conversione( tris[i][2]);
62 printf("\t %c | %c | %c \n", c1,c2,c3);
63 if (i!= 2) printf("\t -----------\n");
64 }
65 }
66
67 //Cambia il turno da 1 a -1 e viceversa
68 int cambio_turno(int turno)
69 {
70 return -turno;
71 }
72
73 //Controlla se la mossa è corretta
74 //Restituisce 1 se lo è, 0 altrimenti
75 int mossa_corretta(int x, int y)
76 {
77 if ( (x < 1 || x > 3) || (y < 1 || y > 3) || tris[x-1][y-1] != 0)
78 return 0;
79 return 1;
80 }
81
82 //Controlla se il gioco è finito
83 int finito()
84 {
85 for (int i = 0; i < 3; i++)
86 for (int j = 0; j < 3; j++)
87 if (tris[i][j] == 0)
88 return 0;
89 return 1;
90 }
91
92 //controlla se qualcuno ha vinto
93 //Ritorna 1 se ha vinto il giocatore 1, -1 se ha vinto il giocatore -1,
94 //0 se nessuno ha vinto e la partita è finita, 2 se la partita è ancora in corso
95
96 int controlla_vittoria()
97 {
98 int i;
99 //Controllo le righe
100 for (i=0 ; i < 3 ; i++)
101 if (tris[i][0]!=0 && tris[i][0]==tris[i][1] && tris[i][1]==tris[i][2])
102 return tris[i][0];
103 //Controllo le colonne
104 for (i=0 ; i < 3 ; i++)
105 if (tris[0][i]!=0 && tris[0][i]==tris[1][i] && tris[1][i]==tris[2][i])
106 return tris[0][i];
107 //Controllo le diagonali
108 if (tris[0][0]!=0 && tris[0][0]==tris[1][1] && tris[1][1]==tris[2][2])
109 return tris[0][0];
110 if (tris[0][2]!=0 && tris[0][2]==tris[1][1] && tris[1][1]==tris[2][0])
111 return tris[0][2];
112 if (finito())
113 return 0;
114 return 2;
115 }
116
117
118 //Funzione minimax, i giocatori sono indicati con 1 e -1
119 int minimax(int giocatore)
120 {
121 int valore;
122 //Se la situazione è valutabile ritorna il valore
123 //1 vince il giocatore 1
124 //-1 vince il giocatore -1
125 //0 pareggio
126 if ((valore = controlla_vittoria()) != 2)
127 return valore;
128 int mossa_migliore;
129 int i,j;
130 mossa c;
131 //Inizializzo la mossa migliore con un valore che è sicuramente
132 //perdente per entrambi, in modo che venga sostituito da valori
133 //migliori
134 mossa_migliore = (giocatore == 1) ? -2 : 2;
135 //Provo tutte le mosse
136 for ( i = 0; i < 3; i++)
137 for ( j = 0; j < 3; j++)
138 {
139 //Se qualche casella è già occupata non viene provata
140 if (mossa_corretta(i+1,j+1))
141 {
142 //Segno la mossa che sto provando
143 tris[i][j] = giocatore;
144 //Calcolo ricorsivamente il valore della posizione
145 //chiamandola sull'altro giocatore
146 valore = minimax(cambio_turno(giocatore));
147 //Se sono il giocatore 1 cerco di massimizzare
148 if (giocatore == 1 && valore > mossa_migliore)
149 {
150 c.riga = i;
151 c.colonna = j;
152 mossa_migliore = valore;
153 }
154 //Se sono il giocatore -1 cerco di minimizzare
155 if (giocatore == -1 && valore < mossa_migliore)
156 {
157 c.riga = i;
158 c.colonna = j;
159 mossa_migliore = valore;
160 }
161 //Faccio backtracking
162 tris[i][j] = 0;
163 }
164 }
165 //Segno nella variabile globale la mossa da fare
166 da_fare = c;
167 //Ritorno il valore della posizione
168 return mossa_migliore;
169 }
170
171 int main()
172 {
173 char nomi[2][20], prima_mossa[20];
174 int riga, colonna, turno=1, mosse = 0, errore, vittoria = 0;
175 int computer;
176 vittoria = controlla_vittoria();
177 strcpy(nomi[0],"Computer");
178 printf("Nome giocatore: ");
179 scanf("%s", nomi[1]);
180 printf("Vuoi fare la prima mossa (s/n): ");
181 scanf("%s",prima_mossa);
182 if (strcmp(prima_mossa,"s")==0)
183 computer = -1;
184 else
185 computer = 1;
186 /*Riempimento griglia*/
187 for (riga=0 ; riga < 3 ; riga++)
188 for (colonna=0 ; colonna<3 ; colonna++)
189 tris[riga][colonna] = 0;
190 while (vittoria == 2) {
191 stampa_griglia();
192 if (turno == computer)
193 {
194 minimax(turno);
195 tris[da_fare.riga][da_fare.colonna] = turno;
196 }
197 else
198 /*Acquisizione coordinate*/
199 do {
200 errore = 0;
201 printf("Gioca %s\n", nomi[1]);
202 printf("Numero di riga : ");
203 scanf("%d", &riga);
204 printf("Numero di colonna : ");
205 scanf("%d", &colonna);
206 if (mossa_corretta(riga,colonna)==0) {
207 printf("POSIZIONE ERRATA!!\n");
208 putchar('\a');
209 errore = 1;
210 }
211 else tris[riga-1][colonna-1] = turno;
212 } while (errore == 1);
213 /*Controlli*/
214 vittoria = controlla_vittoria();
215 turno = cambio_turno(turno);
216 mosse++;
217 }
218 /*Visualizza risultati*/
219 stampa_griglia();
220 if (vittoria == 0)
221 printf("Partita patta.\n");
222 else
223 printf("Ha vinto %s\n",nomi[abs(vittoria-1)/2]);
224 return 0;
225 }