source: trunk/minix/commands/simple/ttt.c@ 20

Last change on this file since 20 was 9, checked in by Mattia Monga, 14 years ago

Minix 3.1.2a
File size: 6.8 KB
Line 
1/* tic tac toe (noughts and crosses) Author: Warren Toomey */
2
3/* Copyright 1988 by Warren Toomey wkt@cs.adfa.oz.au[@uunet.uu.net]
4 *
5 * You may freely copy or distribute this code as long as this notice
6 * remains intact.
7 *
8 * You may modify this code, as long as this notice remains intact, and
9 * you add another notice indicating that the code has been modified.
10 *
11 * You may NOT sell this code or in any way profit from this code without
12 * prior agreement from the author.
13 */
14
15/* Compile with cc -o tic tic.c -lcurses -ltermcap */
16
17#include <stdlib.h>
18#include <time.h>
19
20#ifdef CURSES
21#include <curses.h>
22#endif
23
24#include <stdio.h>
25
26#ifndef CURSES
27#define printw printf
28#endif
29
30
31typedef struct {
32 int value; /* The move returned by the */
33 int path; /* alphabeta consists of a value */
34} MOVE; /* and an actual move (path) */
35
36_PROTOTYPE(int main, (void));
37_PROTOTYPE(int stateval, (int board [], int whosemove));
38_PROTOTYPE(MOVE alphabeta, (int board [], int whosemove, int alpha, int beta));
39_PROTOTYPE(void draw, (int board []));
40_PROTOTYPE(void getmove, (int board []));
41_PROTOTYPE(int endofgame, (int board []));
42_PROTOTYPE(int randommove, (void));
43
44 /* Static evaluator. Returns 100 if we have 3 in a row -100 if they have 3
45 * in a row
46 *
47 * Board is array of 9 ints, where 0=empty square 1=our move 4= their move
48 *
49 * and board is indices 0 1 2 3 4 5 6 7 8 */
50
51
52int stateval(board, whosemove)
53int board[];
54int whosemove;
55{
56 static int row[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, /* Indices of 3in-a-rows */
57 {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
58 {0, 4, 8}, {2, 4, 6}};
59
60 int temp; /* Temp row results */
61 int i, j; /* Loop counters */
62 int side; /* Depth multiplier */
63 int win, lose;
64
65 if (whosemove == 1) {
66 win = 100;
67 lose = -100;
68 side = 1;
69 } else {
70 /* Multiply by -1 if */
71 win = -100;
72 lose = 100;
73 side = -1;
74 } /* not out move */
75 for (i = 0; i < 8; i++) { /* For every 3-in-a-row */
76 temp = 0;
77 for (j = 0; j < 3; j++) /* Add up the board values */
78 temp += board[row[i][j]];
79
80 if (temp == 3) return(win); /* We've got 3 in a row */
81 if (temp == 12) return (lose); /* They've got 3 in a row */
82 }
83 return(0); /* Finally return sum */
84}
85
86
87MOVE alphabeta(board, whosemove, alpha, beta) /* Alphabeta: takes a board, */
88int board[]; /* whose move, alpha & beta cutoffs, */
89int whosemove; /* and returns a move to make and */
90int alpha; /* the value that the move has */
91int beta;
92{
93 MOVE result, successor;
94 int best_score, i, best_path, mademove;
95
96 result.value = stateval(board, whosemove); /* Work out the board's */
97 /* Static value */
98 if ((result.value == 100) || /* If a win or loss already */
99 (result.value == -100))
100 return(result); /* return the result */
101
102 best_score = beta; /* Ok, set worst score */
103 mademove = 0; /* to the beta cutoff */
104 for (i = 0; i < 9; i++) {
105 if (board[i] == 0) { /* For all valid moves */
106 mademove = 1;
107 board[i] = whosemove; /* make the move on board */
108 successor = alphabeta(board, 5 - whosemove, -best_score - 1, -alpha - 1);
109 /* Get value of the move */
110 board[i] = 0; /* Take move back */
111 if (-successor.value > best_score) { /* If a better score */
112 best_score = -successor.value; /* update our score */
113 best_path = i; /* and move */
114 if (best_score > alpha)
115 break; /* If we've beaten alpha */
116 } /* return immediately */
117 }
118 }
119 if (mademove) {
120 result.value = best_score; /* Finally return best score */
121 result.path = best_path;/* and best move */
122 }
123 return(result); /* If no move, return static result */
124}
125
126
127void draw(board) /* Draw the board */
128int board[];
129{
130 int i, j, row;
131 static char out[] = " X O"; /* Lookup table for character */
132
133 row = 6;
134#ifdef CURSES
135 move(row, 0);
136#endif
137 for (j = 0; j < 9; j += 3) {
138 printw(" %d | %d | %d ", j, j + 1, j + 2);
139 for (i = 0; i < 3; i++) {
140 printw("%c ", out[board[j + i]]);
141 if (i < 2) printw("| ");
142 }
143 if (j < 4) {
144#ifdef CURSES
145 move(++row, 0);
146#else
147 printw("\n");
148#endif
149 printw("---+---+--- ---+---+---");
150 }
151#ifdef CURSES
152 move(++row, 0);
153#else
154 printw("\n");
155#endif
156 }
157#ifdef CURSES
158 refresh();
159#else
160 printw("\n");
161#endif
162}
163
164
165void getmove(board) /* Get a player's move */
166int board[];
167{
168 int Move;
169 int ItemsRead;
170 char dumc;
171
172 do {
173 do {
174#ifdef CURSES
175 move(9, 40);
176 printw("Your move: "); /* Prompt for move */
177 refresh();
178#else
179 printw("Your move: "); /* Prompt for move */
180#endif
181 ItemsRead = scanf("%d", &Move); /* Input the move */
182 if (ItemsRead == 0) scanf("%c", &dumc); /* Remove the offending character */
183 }
184 while (ItemsRead != 1);
185 }
186 while (board[Move]);
187 board[Move] = 4; /* If legal, add to board */
188 draw(board); /* Draw the board */
189}
190
191
192int endofgame(board) /* Determine end of the game */
193int board[];
194{
195 int eval;
196 int count;
197
198 eval = stateval(board, 1);
199#ifdef CURSES
200 move(20, 25);
201#endif
202 if (eval == 100) {
203 printw("I have beaten you.\n");
204 return(1);
205 }
206 if (eval == -100) {
207 printw("Bus error (core dumped)\n");
208 return(1);
209 }
210 count = 0;
211 for (eval = 0; eval < 9; eval++)
212 if (board[eval] != 0) count++;
213 if (count == 9) {
214 printw("A draw!\n");
215 return(1);
216 }
217#ifdef CURSES
218 refresh();
219#endif
220 return(0);
221}
222
223
224int randommove()
225{ /* Make an initial random move */
226 int i;
227
228 i = abs((int) time((long *) 0));
229 return(i % 9);
230}
231
232
233int main()
234{ /* The actual game */
235 int i, board[9];
236 char ch;
237 MOVE ourmove;
238
239 for (i = 0; i < 9; i++) board[i] = 0; /* Initialise the board */
240#ifdef CURSES
241 initscr();
242 clear();
243 refresh();
244#endif
245 printw(" TIC TAC TOE \n\n");
246 printw(" Your moves are 'O'\n");
247 printw(" My moves are 'X'\n\n");
248#ifdef CURSES
249 move(5, 0);
250 printw("Do you wish to move first: ");
251 refresh();
252 while (scanf("%c", &ch) != 1);
253 move(5, 0);
254 printw(" ......."); /* Kludge to get rid */
255 refresh();
256 move(5, 0);
257 printw(" "); /* of input letter */
258 refresh();
259#else
260 do
261 printw("Do you wish to move first: ");
262 while (scanf("%c", &ch) != 1);
263#endif
264 if ((ch != 'y') && (ch != 'Y')) {
265 i = randommove(); /* If we move first */
266 board[i] = 1; /* make it random */
267#ifdef CURSES
268 move(7, 42);
269 printw("My move: %d\n", i);
270 refresh();
271#else
272 printw("My move: %d\n", i);
273#endif
274 }
275 draw(board);
276 getmove(board);
277
278 while (1) {
279 ourmove = alphabeta(board, 1, 99, -99); /* Get a move for us;
280 * return wins */
281 /* Immediately & ignore losses */
282 board[ourmove.path] = 1;/* and make it */
283#ifdef CURSES
284 move(7, 42);
285 printw("My move: %d\n", ourmove.path);
286 refresh();
287#else
288 printw("My move: %d\n", ourmove.path);
289#endif
290 draw(board);
291 if (endofgame(board)) break; /* If end of game, exit */
292 getmove(board); /* Get opponent's move */
293 if (endofgame(board)) break; /* If end of game, exit */
294 }
295#ifdef CURSES
296 endwin();
297#endif
298 return(0);
299}
Note: See TracBrowser for help on using the repository browser.