1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <strings.h>
4 #include <X11/Xlib.h>
5 #include "struct.h"
6
7 #define MAXMOVES (700)
8
9 typedef struct {
10 int ox,oy;
11 int nx,ny;
12 char jump;
13 } zthing;
14
15 int *tboard[10];
16
17 #define square(bd, x, y) (bd[(x)*y_board_size+(y)])
18
19 extern int b_look2(); /* return EMPTY, BLACK, WHITE, or OBSTACLE */
20 extern int x_board_size, y_board_size;
21 extern int *board, *bl2;
22 extern int botlevel;
23
init_nubot()24 void init_nubot()
25 {
26 register int i, x, y;
27 int *bd;
28
29 for (i=0; i<10; i++) {
30 bd = (int *) malloc(sizeof(int)*x_board_size*y_board_size);
31
32 for (x=0;x!=x_board_size;x++)
33 for (y=0;y!=y_board_size;y++)
34 bd[x*y_board_size+y] = EMPTY;
35 tboard[i] = bd;
36 }
37 }
38
fcopy_board(bd1,bd2)39 void fcopy_board(bd1, bd2)
40 int *bd1, *bd2;
41 {
42 bcopy(bd1, bd2, sizeof(int)*x_board_size*y_board_size);
43 }
44
b_lookr(x,y,bd)45 int b_lookr(x, y, bd)
46 int x, y;
47 int *bd;
48 {
49 if ((x>=0)&&(x<x_board_size)&&(y>=0)&&(y<y_board_size))
50 return(bd[x*y_board_size+y]);
51 else
52 return(OBSTACLE);
53 }
54
apply_move(player,bd,mv)55 void apply_move(player, bd, mv)
56 int player;
57 int *bd;
58 zthing *mv;
59 {
60 register int ix, iy;
61 int sq;
62
63 square(bd, mv->nx, mv->ny) = player;
64 if ((mv->nx-mv->ox < 2) && (mv->nx-mv->ox > -2) && (mv->ny-mv->oy < 2) && (mv->ny-mv->oy > -2)) {
65 /* leave orig alone */
66 }
67 else {
68 square(bd, mv->ox, mv->oy) = EMPTY;
69 };
70
71 for (ix=(-1); ix<=1; ix++)
72 for (iy=(-1); iy<=1; iy++) {
73 sq = square(bd, mv->nx+ix, mv->ny+iy);
74 if (sq!=EMPTY && sq!=OBSTACLE)
75 square(bd, mv->nx+ix, mv->ny+iy) = player;
76 }
77 }
78
valueb(player,oplayer,bd)79 int valueb(player, oplayer, bd) /* estimate the value of the board for player. oplayer should be the opposite color */
80 int player, oplayer;
81 int *bd;
82 {
83 register int ix, iy;
84 int good=0, bad=0, empty=0;
85 int sq;
86
87 for (ix=0; ix<x_board_size; ix++)
88 for (iy=0; iy<y_board_size; iy++) {
89 sq = square(bd, ix, iy);
90 if (sq == player) good++;
91 else if (sq == oplayer) bad++;
92 else if (sq == EMPTY) empty++;
93 }
94
95 if (empty==0) {
96 if (good>bad) return (10000);
97 else return (-10000);
98 };
99 if (good==0) return (-10000);
100 if (bad==0) return (10000);
101 return (good-bad);
102 }
103
list_moves(player,bd,movel)104 list_moves(player, bd, movel)
105 int player;
106 int *bd;
107 zthing *movel;
108 {
109 register int posx, posy;
110 int moves=0;
111
112 #define do_check(jflag, x, y, player) \
113 if (b_lookr((x), (y), bd)==EMPTY) { \
114 movel[moves].nx = (x); \
115 movel[moves].ny = (y); \
116 movel[moves].ox = (posx); \
117 movel[moves].oy = (posy); \
118 movel[moves].jump = (jflag); \
119 moves++; \
120 }
121
122 for (posx=0; posx<x_board_size; posx++)
123 for (posy=0; posy<y_board_size; posy++)
124 if (b_lookr((posx), (posy), bd)==player) {
125 do_check(0,posx-1,posy-1,player);
126 do_check(0,posx,posy-1,player);
127 do_check(0,posx+1,posy-1,player);
128 do_check(0,posx+1,posy,player);
129 do_check(0,posx+1,posy+1,player);
130 do_check(0,posx,posy+1,player);
131 do_check(0,posx-1,posy+1,player);
132 do_check(0,posx-1,posy,player);
133
134 do_check(1,posx-2,posy-2,player);
135 do_check(1,posx-1,posy-2,player);
136 do_check(1,posx,posy-2,player);
137 do_check(1,posx+1,posy-2,player);
138 do_check(1,posx+2,posy-2,player);
139 do_check(1,posx+2,posy-1,player);
140 do_check(1,posx+2,posy,player);
141 do_check(1,posx+2,posy+1,player);
142 do_check(1,posx+2,posy+2,player);
143 do_check(1,posx+1,posy+2,player);
144 do_check(1,posx,posy+2,player);
145 do_check(1,posx-1,posy+2,player);
146 do_check(1,posx-2,posy+2,player);
147 do_check(1,posx-2,posy+1,player);
148 do_check(1,posx-2,posy,player);
149 do_check(1,posx-2,posy-1,player);
150 }
151
152 movel[moves].ox = (-1);
153 }
154
155 /* Make a move for player. If no move possible, just return. */
robot_move(player)156 robot_move(player)
157 int player;
158 {
159 static int initted = 0;
160 zthing movel[MAXMOVES];
161 int vall[MAXMOVES];
162 register int ix;
163 int temp, bestval = (-10000);
164 int oplayer;
165 zthing *best;
166 int numbest, numglides, gomove;
167
168 if (!initted) {
169 init_nubot();
170 initted = 1;
171 }
172
173 oplayer = (player==WHITE) ? BLACK : WHITE;
174
175 list_moves(player, board, movel);
176
177 if (movel[0].ox==(-1)) return(0); /* there are no legal moves */
178
179 if (botlevel==0) {
180 for (ix=0; movel[ix].ox!=(-1); ix++);
181 ix = random() % ix;
182 best = &(movel[ix]);
183
184 move_piece(best->ox,best->oy,best->nx,best->ny,player);
185 return(0);
186 };
187
188 for (ix=0; movel[ix].ox!=(-1); ix++) {
189 fcopy_board(board, tboard[0]);
190 apply_move(player, tboard[0], &(movel[ix]));
191 vall[ix] = -veb(oplayer, tboard[0], 1, 10000);
192 if (vall[ix] > bestval) bestval = vall[ix];
193 }
194
195 do {
196 for (ix=0; movel[ix].ox!=(-1) && (vall[ix]!=bestval || random()%2); ix++);
197 } while (movel[ix].ox==(-1));
198
199 numbest = 0;
200 numglides = 0;
201 for (ix=0; movel[ix].ox!=(-1); ix++) {
202 /*
203 printf("%d: %d,%d -- %d,%d %c (val %d)\n", ix, movel[ix].ox, movel[ix].oy, movel[ix].nx, movel[ix].ny, movel[ix].jump ? 'J' : 'G', vall[ix]);
204 */
205 if (vall[ix]==bestval) {
206 numbest++;
207 if (!movel[ix].jump) numglides++;
208 }
209 }
210
211 if (numglides) {
212 gomove = (random() % numglides) + 1;
213 /*
214 printf("%d moves (%d glides); took %d'th glide ", numbest, numglides, gomove);
215 */
216 for (ix=0; gomove && movel[ix].ox!=(-1); ix++)
217 if (vall[ix]==bestval && (!movel[ix].jump)) gomove--;
218
219 }
220 else {
221 gomove = (random() % numbest) + 1;
222 /*
223 printf("%d moves (%d glides); took %d'th move ", numbest, numglides, gomove);
224 */
225 for (ix=0; gomove && movel[ix].ox!=(-1); ix++)
226 if (vall[ix]==bestval) gomove--;
227
228 }
229
230 ix--;
231 /*
232 printf("(ix=%d) \n", ix);
233 */
234 best = &(movel[ix]);
235 /*
236 printf("Move is %d,%d -- %d,%d (val %d vs %d)\n", best->ox,best->oy,best->nx,best->ny, vall[ix], bestval);
237 */
238 move_piece(best->ox,best->oy,best->nx,best->ny,player);
239 }
240
veb(player,given,depth,dee)241 int veb(player, given, depth, dee) /* return the value of given board for one player */
242 int player;
243 int *given;
244 int depth;
245 int dee;
246 {
247 int x,y;
248 int oplayer;
249 zthing movel[MAXMOVES];
250 int vall;
251 int temp, bestval = (-10000);
252 register int ix;
253
254 oplayer = (player==WHITE) ? BLACK : WHITE;
255
256 if (depth == botlevel) {
257 int val = valueb(player, oplayer, given);
258 return val;
259 }
260
261 list_moves(player, given, movel);
262
263 if (movel[0].ox==(-1)) return -10000; /* there are no legal moves */
264
265 for (ix=0; movel[ix].ox!=(-1); ix++) {
266 fcopy_board(given, tboard[depth]);
267 apply_move(player, tboard[depth], &(movel[ix]));
268 vall = -veb(oplayer, tboard[depth], depth+1, -bestval);
269 if (vall > bestval) bestval = vall;
270 if (bestval >= dee) return bestval;
271 }
272
273 return bestval;
274 }
275
dump_board(bd)276 dump_board(bd)
277 int *bd;
278 {
279 register int ix, iy;
280 int sq;
281 for (iy=0; iy<y_board_size; iy++) {
282 for (ix=0; ix<x_board_size; ix++) {
283 sq = square(bd, ix, iy);
284 switch (sq) {
285 case EMPTY:
286 printf("- ");
287 break;
288 case WHITE:
289 printf("W ");
290 break;
291 case BLACK:
292 printf("B ");
293 break;
294 case OBSTACLE:
295 printf("# ");
296 break;
297 }
298 };
299 printf("\n");
300 }
301 printf("\n");
302 }
303