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