author | Markus Bröker <mbroeker@largo.dyndns.tv> |
Thu, 16 Apr 2009 12:47:18 +0200 | |
changeset 27 | 81a574d60c15 |
parent 9 | c3fecc82ade6 |
child 29 | 7abf6146898e |
permissions | -rw-r--r-- |
9
c3fecc82ade6
standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
8
diff
changeset
|
1 |
/** |
c3fecc82ade6
standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
8
diff
changeset
|
2 |
* test/demos/alpha_beta.c |
c3fecc82ade6
standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
8
diff
changeset
|
3 |
* Copyright (C) 2008 Markus Broeker |
0 | 4 |
*/ |
5 |
||
6 |
#include <stdio.h> |
|
7 |
#include <stdlib.h> |
|
8 |
#include <limits.h> |
|
9 |
||
10 |
#define BOARD_SIZE 9 |
|
11 |
#define EMPTY 32 |
|
12 |
||
13 |
struct Move { |
|
14 |
int target; |
|
15 |
int value; |
|
16 |
}; |
|
17 |
||
18 |
typedef struct Move Move; |
|
19 |
||
20 |
struct Node { |
|
21 |
Move *data; |
|
22 |
struct Node *prev; |
|
23 |
}; |
|
24 |
||
25 |
typedef struct Node Node; |
|
26 |
||
27 |
Move *bestMove; |
|
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
28 |
|
0 | 29 |
Node *stack_end; |
30 |
||
31 |
char board[BOARD_SIZE] = { |
|
32 |
EMPTY, EMPTY, EMPTY, |
|
33 |
EMPTY, EMPTY, EMPTY, |
|
34 |
EMPTY, EMPTY, EMPTY, |
|
35 |
}; |
|
36 |
||
37 |
int desired_depth = -1; |
|
38 |
||
39 |
int estimateFunction (); |
|
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
40 |
|
0 | 41 |
int max_alpha_beta (int, int, int); |
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
42 |
|
0 | 43 |
int min_alpha_beta (int, int, int); |
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
44 |
|
0 | 45 |
void print (void); |
46 |
||
47 |
/** |
|
48 |
* push: push a move onto the stack |
|
49 |
*/ |
|
50 |
void push (Move * move) |
|
51 |
{ |
|
52 |
Node *actual; |
|
53 |
||
54 |
if ((actual = malloc (sizeof (Node) + 1)) == NULL) { |
|
55 |
perror ("MALLOC"); |
|
56 |
exit (EXIT_FAILURE); |
|
57 |
} |
|
58 |
||
59 |
actual->data = move; |
|
60 |
actual->prev = stack_end; |
|
61 |
||
62 |
stack_end = actual; |
|
63 |
} |
|
64 |
||
65 |
/** |
|
66 |
* undo: revert the last move on the stack |
|
67 |
*/ |
|
68 |
void undo () |
|
69 |
{ |
|
70 |
Node *actual; |
|
71 |
||
72 |
if (stack_end == NULL) { |
|
73 |
printf ("Stack underrun\n"); |
|
74 |
return; |
|
75 |
} |
|
76 |
||
77 |
board[stack_end->data->target] = EMPTY; |
|
78 |
||
79 |
actual = stack_end->prev; |
|
80 |
free (stack_end); |
|
81 |
||
82 |
stack_end = actual; |
|
83 |
} |
|
84 |
||
85 |
/** |
|
86 |
* validMove returns true(1) when the inspected field is EMPTY |
|
87 |
*/ |
|
88 |
int validMove (int t) |
|
89 |
{ |
|
90 |
if (board[t] == EMPTY) |
|
91 |
return 1; |
|
92 |
return 0; |
|
93 |
} |
|
94 |
||
95 |
/** |
|
96 |
* Returns a Score of +-50 for 3 in a Row |
|
97 |
*/ |
|
98 |
int estimateFunction () |
|
99 |
{ |
|
100 |
if (board[0] == 'X' && board[1] == 'X' && board[2] == 'X') |
|
101 |
return -50; |
|
102 |
if (board[0] == 'O' && board[1] == 'O' && board[2] == 'O') |
|
103 |
return 50; |
|
104 |
||
105 |
if (board[3] == 'X' && board[4] == 'X' && board[5] == 'X') |
|
106 |
return -50; |
|
107 |
if (board[3] == 'O' && board[4] == 'O' && board[5] == 'O') |
|
108 |
return 50; |
|
109 |
||
110 |
if (board[6] == 'X' && board[7] == 'X' && board[8] == 'X') |
|
111 |
return -50; |
|
112 |
if (board[6] == 'O' && board[7] == 'O' && board[8] == 'O') |
|
113 |
return 50; |
|
114 |
||
115 |
if (board[0] == 'X' && board[3] == 'X' && board[6] == 'X') |
|
116 |
return -50; |
|
117 |
if (board[0] == 'O' && board[3] == 'O' && board[6] == 'O') |
|
118 |
return 50; |
|
119 |
||
120 |
if (board[1] == 'X' && board[4] == 'X' && board[7] == 'X') |
|
121 |
return -50; |
|
122 |
if (board[1] == 'O' && board[4] == 'O' && board[7] == 'O') |
|
123 |
return 50; |
|
124 |
||
125 |
if (board[2] == 'X' && board[5] == 'X' && board[8] == 'X') |
|
126 |
return -50; |
|
127 |
if (board[2] == 'O' && board[5] == 'O' && board[8] == 'O') |
|
128 |
return 50; |
|
129 |
||
130 |
if (board[0] == 'X' && board[4] == 'X' && board[8] == 'X') |
|
131 |
return -50; |
|
132 |
if (board[0] == 'O' && board[4] == 'O' && board[8] == 'O') |
|
133 |
return 50; |
|
134 |
||
135 |
if (board[2] == 'X' && board[4] == 'X' && board[6] == 'X') |
|
136 |
return -50; |
|
137 |
if (board[2] == 'O' && board[4] == 'O' && board[6] == 'O') |
|
138 |
return 50; |
|
139 |
||
140 |
return 0; |
|
141 |
} |
|
142 |
||
143 |
/** |
|
144 |
* this function visualizes the board |
|
145 |
*/ |
|
146 |
void print () |
|
147 |
{ |
|
148 |
int i; |
|
149 |
||
150 |
printf (" 1 2 3 \n +---+---+---+\n"); |
|
151 |
for (i = 0; i < 3; i++) { |
|
152 |
printf (" %d | ", i + 1); |
|
153 |
printf ("%c", board[3 * i]); |
|
154 |
printf (" | "); |
|
155 |
printf ("%c", board[3 * i + 1]); |
|
156 |
printf (" | "); |
|
157 |
printf ("%c", board[3 * i + 2]); |
|
158 |
printf (" | \n"); |
|
159 |
if (i != 2) { |
|
160 |
printf (" +---+---+---+\n"); |
|
161 |
} else { |
|
162 |
printf (" +---+---+---+\n"); |
|
163 |
} |
|
164 |
} |
|
165 |
if (stack_end->data != NULL) |
|
166 |
printf ("Score: %3d\n", stack_end->data->value); |
|
167 |
} |
|
168 |
||
169 |
/** |
|
170 |
* simulates and returns the next possible move for a Player or null, when no more moves are possible. |
|
171 |
*/ |
|
172 |
Move *simulate (int t, int player) |
|
173 |
{ |
|
174 |
Move *move; |
|
175 |
||
176 |
while (t < BOARD_SIZE) { |
|
177 |
if (!validMove (t)) { |
|
178 |
t++; |
|
179 |
continue; |
|
180 |
} |
|
181 |
||
182 |
if ((move = malloc (sizeof (Move) + 1)) == NULL) { |
|
183 |
perror ("MALLOC"); |
|
184 |
exit (EXIT_FAILURE); |
|
185 |
} |
|
186 |
||
187 |
if (player == 0) |
|
188 |
board[t] = 'O'; |
|
189 |
else |
|
190 |
board[t] = 'X'; |
|
191 |
||
192 |
move->target = t; |
|
193 |
move->value = estimateFunction (); |
|
194 |
||
195 |
push (move); |
|
196 |
||
197 |
return move; |
|
198 |
} |
|
199 |
return NULL; |
|
200 |
} |
|
201 |
||
202 |
/** |
|
203 |
* AlphaBeta-Algorithm: the Maximizer |
|
204 |
*/ |
|
205 |
int max_alpha_beta (int depth, int alpha, int beta) |
|
206 |
{ |
|
207 |
int moveValue; |
|
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
208 |
|
0 | 209 |
int t; |
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
210 |
|
0 | 211 |
Move *move; |
212 |
||
213 |
if (desired_depth == -1) |
|
214 |
desired_depth = depth; |
|
215 |
||
216 |
t = 0; |
|
217 |
while ((move = simulate (t, 0)) != NULL) { |
|
218 |
/* |
|
219 |
* particular move from black |
|
220 |
*/ |
|
221 |
t = move->target; |
|
222 |
||
223 |
if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500) |
|
224 |
moveValue = move->value; |
|
225 |
else /* best next move */ |
|
226 |
moveValue = min_alpha_beta (depth - 1, alpha, beta); |
|
227 |
||
228 |
print (); |
|
229 |
undo (); |
|
230 |
t++; |
|
231 |
||
232 |
if (moveValue >= beta) |
|
233 |
return beta; |
|
234 |
||
235 |
if (moveValue > alpha) { |
|
236 |
alpha = moveValue; |
|
237 |
if (depth == desired_depth) |
|
238 |
bestMove = move; |
|
239 |
} |
|
240 |
} |
|
241 |
||
242 |
return alpha; |
|
243 |
} |
|
244 |
||
245 |
/** |
|
246 |
* AlphaBeta-Algorithm: the Minimizer |
|
247 |
*/ |
|
248 |
int min_alpha_beta (int depth, int alpha, int beta) |
|
249 |
{ |
|
250 |
int moveValue; |
|
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
251 |
|
0 | 252 |
int t; |
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
253 |
|
0 | 254 |
Move *move; |
255 |
||
256 |
t = 0; |
|
257 |
while ((move = simulate (t, 1)) != NULL) { |
|
258 |
/* |
|
259 |
* particular move from white |
|
260 |
*/ |
|
261 |
t = move->target; |
|
262 |
||
263 |
if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500) |
|
264 |
moveValue = move->value; |
|
265 |
else /* best next move */ |
|
266 |
moveValue = max_alpha_beta (depth - 1, alpha, beta); |
|
267 |
||
268 |
undo (); |
|
269 |
t++; |
|
270 |
||
271 |
if (moveValue <= alpha) |
|
272 |
return alpha; |
|
273 |
||
274 |
if (moveValue < beta) |
|
275 |
beta = moveValue; |
|
276 |
} |
|
277 |
||
278 |
return beta; |
|
279 |
} |
|
280 |
||
281 |
/** |
|
282 |
* returns true when no more fields are empty |
|
283 |
*/ |
|
284 |
int game_over () |
|
285 |
{ |
|
286 |
int i; |
|
287 |
||
288 |
for (i = 0; i < BOARD_SIZE; i++) { |
|
289 |
if (board[i] == EMPTY) |
|
290 |
return 0; |
|
291 |
} |
|
292 |
||
293 |
return 1; |
|
294 |
} |
|
295 |
||
296 |
int main (int argc, char **argv) |
|
297 |
{ |
|
298 |
Node *actual; |
|
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
299 |
|
0 | 300 |
int i, t, value; |
27
81a574d60c15
typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
9
diff
changeset
|
301 |
|
0 | 302 |
int depth; |
303 |
||
304 |
if (argc == 2) |
|
305 |
depth = atoi (argv[1]); |
|
306 |
else |
|
307 |
depth = 1; |
|
308 |
||
309 |
if ((actual = malloc (sizeof (Node) + 1)) == NULL) { |
|
310 |
perror ("MALLOC"); |
|
311 |
return EXIT_FAILURE; |
|
312 |
} |
|
313 |
||
314 |
actual->data = NULL; |
|
315 |
actual->prev = NULL; |
|
316 |
||
317 |
stack_end = actual; |
|
318 |
||
319 |
printf ("\tTic Tac Toe\n"); |
|
320 |
||
321 |
for (i = 0; i < 5; i++) { |
|
322 |
printf ("Enter a number: "); |
|
323 |
while (scanf ("%d", &t) < 1) { |
|
324 |
printf ("Enter a number: "); |
|
325 |
t = getchar (); |
|
326 |
} |
|
327 |
||
328 |
if (!validMove (--t)) { |
|
329 |
i--; |
|
330 |
continue; |
|
331 |
} |
|
332 |
||
333 |
board[t] = 'X'; |
|
334 |
||
335 |
bestMove = NULL; |
|
336 |
value = max_alpha_beta (depth, SHRT_MIN, SHRT_MAX); |
|
337 |
||
338 |
if (bestMove == NULL) { |
|
339 |
break; |
|
340 |
} |
|
341 |
||
342 |
board[bestMove->target] = 'O'; |
|
343 |
print (); |
|
344 |
||
345 |
if ((estimateFunction () * estimateFunction ()) == 2500) { |
|
346 |
return EXIT_SUCCESS; |
|
347 |
} |
|
348 |
||
349 |
if (game_over ()) |
|
350 |
break; |
|
351 |
} |
|
352 |
||
353 |
print (); |
|
8
96d16dfe787a
We use return EXIT_SUCCESS instead of return 0
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
0
diff
changeset
|
354 |
|
0 | 355 |
return EXIT_SUCCESS; |
356 |
} |